I’m often struck by how differently children think.
My 9.5 year old son is fond of playing the following “magic trick” on his friends. The magician asks the subject to think of a number between, say, 1 and 63. Then the magician shows the subject a set of 6 cards, each of which has numbers written on it, and asks the subject to state “yes” or “no” depending on whether the chosen number is printed on the card. At the end the magician guesses the number.
The principle is simple: n “yes” or “no” answers yield n bits of information and can be used to uniquely encode a number up to 2^n-1. But it appears surprising if one hasn’t thought about it.
The kid wanted to go up to higher powers of 2. So he needed to generate his own “magic cards”, which he decided to do via a small Scratch program. (His initial plan was to print cards up to 2^21 but strict rationing of the use of the printer has limited him to 2^10. )
In any case, the precise question is as follows: “given a number, 2^n, generate n lists so that the k^th list has the property that it contains all numbers up to 2^n whose binary representation has 1 in the k^th place.”
Here is what the kid came up with (see image). Or test the full code here: https://scratch.mit.edu/projects/740194941/
To me, this is a perfect example of obfuscated code! I can never imagine writing this code to solve the problem above. I challenge any of the adults reading this to figure out how the code works without reading it at least thrice. But this was perfectly natural for the child. He wrote it pretty quickly — in under 15 min. And, remarkably, it is not particularly inefficient either in terms of code-size or running-time. (For those who still find the code crytpic, see the discussion with Rukmini below.)
I am sure, in a few years, when he has had more formal training, he will write a “more standard” algorithm for this problem. Just as formal training makes us see hats instead of boa constrictors with elephants.
