From the article: So far, no one has found a road-and wheel combination in which the road has the same shape as the wheel. That's an intriguing challenge for mathematicians.
I don't get this part. A wheel is a small closed shape, you go once around it and you're back where you started from. On the other hand, a road has to GO somewhere along the ground - if it was a closed shape suspended in the air then you would fall off when you come around to the bottom side of it - so of COURSE they can't be the same shape - one has to have open topology and one has to have closed topology.
The only way to get around this, really, is to use the whole earth. Pave a road all the way around the earth in a circle - it will require some bridges for the water, and it will require some risers to make the road circular when the earth is eliptical - but hey, we're talking theory not practice - so let's pretend we have the money to pull this off.
Now, you have a circular road. Drive on it with a normal circular wheel.
Uh, why would most of them *need* to be looking anywhere except their consoles ? It's not like they're transcribing letters or the phasers are aimed by moving a set of crosshairs across the main viewscreen. Even when multiple things are shown on the same display, humans' eyes still can't process multiple inputs at the same time with any degree of usefulness - you can concentrate on looking at one thing and listening to something else and feel something else with ease, but it's hard to look at multiple things at once, or hear multiple things at once, or feel multiple things at once. One sense per thing you are paying attention to works better. The checkout chicks at my local supermarket absolutely blast through their touch screen interfaces when they package up my groceries. They sure as hell aren't being slowed down by the interface.
Not in comparasin to how fast they used to do it with keys. Besides, it's a bad example because use of a POS keyboard when checking out isn't a speed-crucial task because the big bottleneck when checking out isn't the checkout person typing - it's running the items over the scanner, bagging them, and the customer's payment method, and all of THOSE things have gotten faster in recent years. If the use of the computer keys is slower, you will barely even notice. Once you've done that with a touchscreen, the process is identical.
No. Close your eyes and find the "F" key on your keyboard. Now, Close your eyes and find the 'F' key on a picture of a keyboard on the screen. The second is flat and you can't tell where one key ends and the next begins. On a keyboard, every time you press a key you get a new confirmation of where the keyboard is reletive to your hands. If your hand drifts off a bit, you can tell it's happening because you can feel the edges of the keys and you can tell subconsiously that your fingers are about to start missing the keys if you keep drifting off in that direction, and so you subconsiously correct this.
On a screen, the line between two keys feels just as flat as the rest of the screen. On a keyboard the line between two keys feels like a crack. I guarantee you can talk a lot faster than you can type.
I can type { faster than I can say "new nesting level". I can type ';' faster than I can say "end statement". I can type 'cp' faster than I can say "copy". I can type ab(tab) faster than I can say, "file beginning with 'ab'".
Right but my point is that the suggestion in the post, of using an assert(), wouldn't have helped (even if it was allowed) because BOTH intentional and unintentional program crashes look identical in the judge's report that you can see.
They still limit the team to only one computer for all of them (the theory is that this allows poorer installations, that can't afford a spot for everyone, to participate fairly - also it forces the team members to 'talk offline' about solutions while one is frantically typing code. (Each team is given a private room near the computer lab, to run off to and make plans and come back.) Actually, they defineded 'terminal' as a single installation of keyboard and screen, regardless of whether it's a standalone PC or a terminal.
They don't do fortran anymore, but they do specify the language. Back when I did it (10 years ago), they said you had to do either C or Pascal. Today it's probably going to include Java, but I don't know that for sure. languages that tend to do a lot of data structure work for you, like lisp, were not allowed.
They allowed us to bring books and notes, but in paper form only - no stuff that could be transferred electronically.
The problems aren't overly tough, but you are given seven or eight of them to solve in just five hours. It's the time crunch that makes it hard. Anyone can get a right solution eventually, but how many can you belt out as fast as possible - that's the challenge. The contest is designed so that even the winning team doesn't have the time to get all of the problems right.
In general, it's a lot of fun. As I stated elsewhere here, the one time I tried it there was a mistake in the givens that made things unfair, but in general it's a fun idea. They just need to be a lot more careful with their problem handouts. Perhaps they should do some trial runs with test students first before using the problems for real.
How did any of the descriptions of the problems actually lie?
Did you read my post that started this? It's right in there. The problem stated, as a given, that the max number of digits we would have to calculate for was FOO, when the input they used actually contained some data requiring something like FOO+200 digits. My first submitted program to solve it was perfect - except that it needed a bigger array than the givens claimed I would need.
Please don't pretend to speak for me, and don't put words in my mouth that make me look like I support your point when I don't. I don't tolerate that kind of bull. My post you refer to EXPLICITLY states what it was that I'm bitter over, and it's the fact that the misprint in the handouts was at a really, really critical spot and they were unwilling to admit that this made the contest unfair. It was fairness that I'm annoyed about, not that the contest existed, nor that it was tough, nor that it was a tight deadline - (those were actually the fun parts).
And, yes, learning how to handle the high-stress situation is extremely useful. The goal of the contest wasn't to produce robust reusable code. It was to challenge your ability to think on your toes.
The bridge of the next generation's enterprise is designed to look cool to TV viewers, not to actually be a useful interface. In fact, it's a terrible interface because of the touchscreens - the crew would have to look down to use the buttons and could never learn the tactile feedback that people currently use with their computer keyboards. Visual touchscreens are great when you don't know what you're doing and need to be led through the interface. They're very slow to use, however, and require attention from multple senses. A keyboard with keys you can feel only requires one sense to use. That's why you can type while reading something off the screen.
And talking to the computer to get it to do what you want is no worse than typing it - you still have to remember the right words, and still have all the same problems because essentailly, speaking to a machine is just like typing to it, in terms of it being a one-dimensional stream of data the computer has to parse.
I think he meant a terminal window. That is sad. And, no, those CS majors won't be able to adapt. One of the necessary lessons to learn is to get the difference between the OS and the presentation of that OS - if you only ever interface with the OS in one and only one way, then you don't really grok that idea. The notion that a shell and a file manager are kind of the same thing, but will completely different visual presentations, is going to be an alien concept to these graduates.
Once upon a time I hated vi for the same reason you did - without a manual you can't figure it out, and at my college there were no manuals for it - there's too much memorizing of seemingly random keybindings. And at that time I preferred emacs. Then I was stuck working somewhere where I had no choice but to use vi because emacs had a huge footprint and there were lots of users logged in to one server - they can't all use emacs without clogging the system. So I grumbled and forced my way through it, using nothing more than a fold-out reference card from O'Rielly. After about a month of this I found I was already faster with vi than I ever was with Emacs. This surprised me. It didn't seem like it should be faster, but it was.
One of my problems with emacs is that the reliance on lisp made it a royal pain in the ass to configure it the way I like. The help always assumed you knew lisp, and it always assumed you know where you were supposed to type these lisp commands in order to put them into the editor's configuration. In days and days and days of searching emacs' info system, I never did find out WHERE I'm supposed to be typing all these lisp commands in order to make them take effect whenever I launch emacs. RMS might be a smart guy, but he has no clue how to write coherent help text to help people learn.
IDE's are wonderful. But so long as they insist that I type less efficiently (by, for example, requiring that I keep losing my home-row position of my fingers by always moving my hand to the arrow keys and the mouse), then their help isn't worth their hindrance. I do use IDE's for debugging, but not for composing. The day a good IDE supports a better editing keyboard mapping, I'll consider using it.
As you say, typing isn't the point of programming. But this is all the more reason to make it go by faster - so you can spend time thinking instead of doing manual labor.
If you did that, then this is the only response you'd get back from the judges from that run:
- program produced incorrect output.
Now try to decipher, from that alone, that this was caused by your numbers too big print statement instead of by something else in the code.
The problem with the ACM contest is that it robs you of ANY sort of feedback, and thus when there is a discrepency between the handout's description of things and the actual test the judges run, you can't tell that that's what's happeneing. And it's not just misprints like this was. It could be the input data format (seeing spaces in the handout where there aren't any in the real input, or a strange exception case like using 8-bit extended ascii in the test data when the examples shown in the handout were all standard 7-bit ascii, and nothing was said one way or the other about it.)
In their attempt to rob cheaters of their tool to peek at the test data and hardcode to it, they also robbed programmers of one of the primary means of detecting that the specs don't match reality - looking at actual examples of how the users are trying to use the program.
To: Dunbartheinept Are you from Dunbar High School in Fort Worth?
No. (geek alert) Dunbar is a halfling thief character I used to play back in those college days. The title "The Inept" was given to me by other players due to the fact that for three game sessions straight I never once rolled a number smaller than 75% on my percentiles, and thus failed absolutley every attempt to be sneaky. Entire campaign arcs were caused by that string of bad luck.
Spoken like someone who never tried solving 7 time consuming problems in a contest that lasts only 5 hours, and all three team members only get one computer to share to type on. Under those circumastances if you distrust the givens in the problem, you never even get one problem done.
Yeah, but this was supposed to be the one really easy problem in the mix. They do throw one in there that is quickly do-able - and part of the contest is identifying which one that is and doing it first. But that misprint turned it into a very hard problem, since you had to have the realization that the contest creators are the ones in error instead of you.
I totally agree. I was in this contest one year, and it was when it was too late that I realized that the key to being successful in this contest is having the ability to pick out the easy problems and do them first.
Actually, that IS supposed to be part of the contest. They explain carefully how the scoring works, and even point out that this means it's best to identify those problems you think are fastest and work on them first.
The ability to detect that the description of the problem is defining a thorny problem that's harder than it looks *is* part of what you're supposed to be good at. The ability to detect that the description of the problem is actually LYING to you, on the other hand, isn't suppossed to be part of the contest.
intentionally crash your program (using assert()) if an assumption you make about the program fails.
In this case that wouldn't have helped. Regardless of if an assert() fails or if the program crashes because it blew past an array, the result that we could see would look the same - the standard ACM judge response would just be "program terminated before processing all input", and you wouldn't get to see the output of the run, so you can't tell if it's your assert() that's causing the crash or not.
One of the really annoying things about how they run the contest is how they firewall off the test environment such that you can never figure out why your program didn't work. The judges are only allowed to give you one of the following five responses (This is from memory, I could be wrong):
1 - didn't run at all (syntax problems, or linking problems, or something like that)
2 - terminated before processing all input (usually a crash, but could be just an exit(0);)
3 - took longer than X minutes and was thus assumed to be infinitely hanging (where X was told to you ahead of time so you knew how long your program had - it was really large. The point wasn't to force you to write fast code, but rather that they had to have some way to define a cutoff where they would assume you're in an infinite loop - since there's no way to really tell with certainty - NP completeness and all that.
4 - finished, but gave wrong answers.
5 - finished, and was correct.
That's it. That's *all* you could ever learn about your program run when you submitted it to the judges. They were not allowed to tell anything else, and you were not allowed to see the output of your program. (The theory was that you could cheat and have your first program do nothing more than echo what the test data was, and then your second attempt could hardcode a solution to just that test data and no other.)
Because of this setup, when the givens in the handout are lying to you, there is NO way to detect this. We had a solution that worked according to the givens in the problem, but the test data violated those givens and due to the setup as explained above, there's no way to tell that this is what is happening.
At the time, the contest specified that you MUST use either Pascal or C. Partly this is because they wanted the problems to be equally difficult for everyone, and partly so they could control exactly what libraries were available. (Some of the things the problems asked you to solve are in commonly available libraries.)
Slashdot Mirror
From the article:
So far, no one has found a road-and wheel combination in which the road has the same shape as the wheel. That's an intriguing challenge for mathematicians.
I don't get this part. A wheel is a small closed shape, you go once around it and you're back where you started from. On the other hand, a road has to GO somewhere along the ground - if it was a closed shape suspended in the air then you would fall off when you come around to the bottom side of it - so of COURSE they can't be the same shape - one has to have open topology and one has to have closed topology.
The only way to get around this, really, is to use the whole earth. Pave a road all the way around the earth in a circle - it will require some bridges for the water, and it will require some risers to make the road circular when the earth is eliptical - but hey, we're talking theory not practice - so let's pretend we have the money to pull this off.
Now, you have a circular road. Drive on it with a normal circular wheel.
That's pretty much the only way to do it.
Uh, why would most of them *need* to be looking anywhere except their consoles ? It's not like they're transcribing letters or the phasers are aimed by moving a set of crosshairs across the main viewscreen.
Even when multiple things are shown on the same display, humans' eyes still can't process multiple inputs at the same time with any degree of usefulness - you can concentrate on looking at one thing and listening to something else and feel something else with ease, but it's hard to look at multiple things at once, or hear multiple things at once, or feel multiple things at once. One sense per thing you are paying attention to works better.
The checkout chicks at my local supermarket absolutely blast through their touch screen interfaces when they package up my groceries. They sure as hell aren't being slowed down by the interface.
Not in comparasin to how fast they used to do it with keys. Besides, it's a bad example because use of a POS keyboard when checking out isn't a speed-crucial task because the big bottleneck when checking out isn't the checkout person typing - it's running the items over the scanner, bagging them, and the customer's payment method, and all of THOSE things have gotten faster in recent years. If the use of the computer keys is slower, you will barely even notice.
Once you've done that with a touchscreen, the process is identical.
No. Close your eyes and find the "F" key on your keyboard. Now, Close your eyes and find the 'F' key on a picture of a keyboard on the screen. The second is flat and you can't tell where one key ends and the next begins. On a keyboard, every time you press a key you get a new confirmation of where the keyboard is reletive to your hands. If your hand drifts off a bit, you can tell it's happening because you can feel the edges of the keys and you can tell subconsiously that your fingers are about to start missing the keys if you keep drifting off in that direction, and so you subconsiously correct this.
On a screen, the line between two keys feels just as flat as the rest of the screen. On a keyboard the line between two keys feels like a crack.
I guarantee you can talk a lot faster than you can type.
I can type { faster than I can say "new nesting level". I can type ';' faster than I can say "end statement". I can type 'cp' faster than I can say "copy". I can type ab(tab) faster than I can say, "file beginning with 'ab'".
Right but my point is that the suggestion in the post, of using an assert(), wouldn't have helped (even if it was allowed) because BOTH intentional and unintentional program crashes look identical in the judge's report that you can see.
They still limit the team to only one computer for all of them (the theory is that this allows poorer installations, that can't afford a spot for everyone, to participate fairly - also it forces the team members to 'talk offline' about solutions while one is frantically typing code. (Each team is given a private room near the computer lab, to run off to and make plans and come back.) Actually, they defineded 'terminal' as a single installation of keyboard and screen, regardless of whether it's a standalone PC or a terminal.
They don't do fortran anymore, but they do specify the language. Back when I did it (10 years ago), they said you had to do either C or Pascal. Today it's probably going to include Java, but I don't know that for sure. languages that tend to do a lot of data structure work for you, like lisp, were not allowed.
They allowed us to bring books and notes, but in paper form only - no stuff that could be transferred electronically.
The problems aren't overly tough, but you are given seven or eight of them to solve in just five hours. It's the time crunch that makes it hard. Anyone can get a right solution eventually, but how many can you belt out as fast as possible - that's the challenge. The contest is designed so that even the winning team doesn't have the time to get all of the problems right.
In general, it's a lot of fun. As I stated elsewhere here, the one time I tried it there was a mistake in the givens that made things unfair, but in general it's a fun idea. They just need to be a lot more careful with their problem handouts. Perhaps they should do some trial runs with test students first before using the problems for real.
Dude, learn what "a little bit" means, as in my original post where I said "a little bit of a bitter memory".
How did any of the descriptions of the problems actually lie?
Did you read my post that started this? It's right in there. The problem stated, as a given, that the max number of digits we would have to calculate for was FOO, when the input they used actually contained some data requiring something like FOO+200 digits. My first submitted program to solve it was perfect - except that it needed a bigger array than the givens claimed I would need.
If he is sore about losing then it's his problem.
"unformed" lied when he said I didn't have fun.
Please don't pretend to speak for me, and don't put words in my mouth that make me look like I support your point when I don't. I don't tolerate that kind of bull. My post you refer to EXPLICITLY states what it was that I'm bitter over, and it's the fact that the misprint in the handouts was at a really, really critical spot and they were unwilling to admit that this made the contest unfair. It was fairness that I'm annoyed about, not that the contest existed, nor that it was tough, nor that it was a tight deadline - (those were actually the fun parts).
And, yes, learning how to handle the high-stress situation is extremely useful. The goal of the contest wasn't to produce robust reusable code. It was to challenge your ability to think on your toes.
I never said I was scarred for life, liar.
I just said I was bitter about it.
There's a clear difference.
The bridge of the next generation's enterprise is designed to look cool to TV viewers, not to actually be a useful interface. In fact, it's a terrible interface because of the touchscreens - the crew would have to look down to use the buttons and could never learn the tactile feedback that people currently use with their computer keyboards. Visual touchscreens are great when you don't know what you're doing and need to be led through the interface. They're very slow to use, however, and require attention from multple senses. A keyboard with keys you can feel only requires one sense to use. That's why you can type while reading something off the screen.
And talking to the computer to get it to do what you want is no worse than typing it - you still have to remember the right words, and still have all the same problems because essentailly, speaking to a machine is just like typing to it, in terms of it being a one-dimensional stream of data the computer has to parse.
I think he meant a terminal window. That is sad. And, no, those CS majors won't be able to adapt. One of the necessary lessons to learn is to get the difference between the OS and the presentation of that OS - if you only ever interface with the OS in one and only one way, then you don't really grok that idea. The notion that a shell and a file manager are kind of the same thing, but will completely different visual presentations, is going to be an alien concept to these graduates.
Intuative is just another word for "The same as what I already know".
If intuative interfaces was the be-all-end-all of UI design, then we'd be driving our cars with an interface designed to imitate reins and a whip.
Once upon a time I hated vi for the same reason you did - without a manual you can't figure it out, and at my college there were no manuals for it - there's too much memorizing of seemingly random keybindings. And at that time I preferred emacs. Then I was stuck working somewhere where I had no choice but to use vi because emacs had a huge footprint and there were lots of users logged in to one server - they can't all use emacs without clogging the system. So I grumbled and forced my way through it, using nothing more than a fold-out reference card from O'Rielly. After about a month of this I found I was already faster with vi than I ever was with Emacs. This surprised me. It didn't seem like it should be faster, but it was.
One of my problems with emacs is that the reliance on lisp made it a royal pain in the ass to configure it the way I like. The help always assumed you knew lisp, and it always assumed you know where you were supposed to type these lisp commands in order to put them into the editor's configuration. In days and days and days of searching emacs' info system, I never did find out WHERE I'm supposed to be typing all these lisp commands in order to make them take effect whenever I launch emacs. RMS might be a smart guy, but he has no clue how to write coherent help text to help people learn.
IDE's are wonderful. But so long as they insist that I type less efficiently (by, for example, requiring that I keep losing my home-row position of my fingers by always moving my hand to the arrow keys and the mouse), then their help isn't worth their hindrance. I do use IDE's for debugging, but not for composing. The day a good IDE supports a better editing keyboard mapping, I'll consider using it.
As you say, typing isn't the point of programming. But this is all the more reason to make it go by faster - so you can spend time thinking instead of doing manual labor.
If you did that, then this is the only response you'd get back from the judges from that run:
- program produced incorrect output.
Now try to decipher, from that alone, that this was caused by your numbers too big print statement instead of by something else in the code.
The problem with the ACM contest is that it robs you of ANY sort of feedback, and thus when there is a discrepency between the handout's description of things and the actual test the judges run, you can't tell that that's what's happeneing. And it's not just misprints like this was. It could be the input data format (seeing spaces in the handout where there aren't any in the real input, or a strange exception case like using 8-bit extended ascii in the test data when the examples shown in the handout were all standard 7-bit ascii, and nothing was said one way or the other about it.)
In their attempt to rob cheaters of their tool to peek at the test data and hardcode to it, they also robbed programmers of one of the primary means of detecting that the specs don't match reality - looking at actual examples of how the users are trying to use the program.
To: Dunbartheinept
Are you from Dunbar High School in Fort Worth?
No. (geek alert) Dunbar is a halfling thief character I used to play back in those college days. The title "The Inept" was given to me by other players due to the fact that for three game sessions straight I never once rolled a number smaller than 75% on my percentiles, and thus failed absolutley every attempt to be sneaky. Entire campaign arcs were caused by that string of bad luck.
Spoken like someone who never tried solving 7 time consuming problems in a contest that lasts only 5 hours, and all three team members only get one computer to share to type on. Under those circumastances if you distrust the givens in the problem, you never even get one problem done.
Yeah, but this was supposed to be the one really easy problem in the mix. They do throw one in there that is quickly do-able - and part of the contest is identifying which one that is and doing it first. But that misprint turned it into a very hard problem, since you had to have the realization that the contest creators are the ones in error instead of you.
I totally agree. I was in this contest one year, and it was when it was too late that I realized that the key to being successful in this contest is having the ability to pick out the easy problems and do them first.
Actually, that IS supposed to be part of the contest. They explain carefully how the scoring works, and even point out that this means it's best to identify those problems you think are fastest and work on them first.
The ability to detect that the description of the problem is defining a thorny problem that's harder than it looks *is* part of what you're supposed to be good at. The ability to detect that the description of the problem is actually LYING to you, on the other hand, isn't suppossed to be part of the contest.
Lisp was not an allowed language in that contest. It would have made a lot of the problems too easy.
intentionally crash your program (using assert()) if an assumption you make about the program fails.
In this case that wouldn't have helped. Regardless of if an assert() fails or if the program crashes because it blew past an array, the result that we could see would look the same - the standard ACM judge response would just be "program terminated before processing all input", and you wouldn't get to see the output of the run, so you can't tell if it's your assert() that's causing the crash or not.
One of the really annoying things about how they run the contest is how they firewall off the test environment such that you can never figure out why your program didn't work. The judges are only allowed to give you one of the following five responses (This is from memory, I could be wrong):
1 - didn't run at all (syntax problems, or linking problems, or something like that)
2 - terminated before processing all input (usually a crash, but could be just an exit(0);)
3 - took longer than X minutes and was thus assumed to be infinitely hanging (where X was told to you ahead of time so you knew how long your program had - it was really large. The point wasn't to force you to write fast code, but rather that they had to have some way to define a cutoff where they would assume you're in an infinite loop - since there's no way to really tell with certainty - NP completeness and all that.
4 - finished, but gave wrong answers.
5 - finished, and was correct.
That's it. That's *all* you could ever learn about your program run when you submitted it to the judges. They were not allowed to tell anything else, and you were not allowed to see the output of your program. (The theory was that you could cheat and have your first program do nothing more than echo what the test data was, and then your second attempt could hardcode a solution to just that test data and no other.)
Because of this setup, when the givens in the handout are lying to you, there is NO way to detect this. We had a solution that worked according to the givens in the problem, but the test data violated those givens and due to the setup as explained above, there's no way to tell that this is what is happening.
At the time, the contest specified that you MUST use either Pascal or C. Partly this is because they wanted the problems to be equally difficult for everyone, and partly so they could control exactly what libraries were available. (Some of the things the problems asked you to solve are in commonly available libraries.)
That is your spec. I think the folks running the contest are smarter than you give credit.
No, because the misprint was not deliberate.