Hi everyone,
I’m not going to lie, I found this puzzle quite hard, even though I’m a programmer by trade.
Most of the solutions to the puzzle use a register that decrements from 4 (100b) to 0. The ball is trapped on 000b.
For the purposes of this post I’ll call the register that decrements A and the register we want to serialize S. I’ll reference the bit positions as A0, A1, A2 and S0, S1, S2 respectively. A0/S0 are the least significant bit (with decimal value 1) and A2/S2 are the most significant bit (with decimal value 4).
What I find unsatisfactory about this solution is that it doesn’t seem generalisable to serializing higher number of bits, never mind the fact that the board probably isn’t big enough.
It seems clear to me that the only reason we are able to get 3 distinct paths through each of the bits to be serialized is because the decrementing sequence is this
100b = 4
011b = 3
010b = 2
001b = 1
000b = 0
If we restrict ourselves to just 4, 3, 2 we can see something very interesting.
For 4 = 100b, it is bit A2 that gets flipped
For 3 = 011b, it is bit A0 that gets flipped (and the rest skipped)
For 2 = 010b, it is bit A1 that gets flipped (and the rest skipped)
This covers all of the three bit positions (but not in order). The order is: A2, A0, A1
Each of these bit positions (A0, A1, A2) is the start of a path that you must hook up to the three bits.
In the solution from the book (and many others) the paths are hooked up this way:
A2 → C0
A0 → C1
A1 → C2
So, why isn’t this generalisable to higher numbers of bits. Well, presumably, the way to generalise to 4 bits of serialization would be to add a 4th bit called C3, and then just set A = 5 (currently A = 4). You would set this as A0 = 1, A1 = 0, A2 = 1.
However, this wouldn’t create 4 paths! (even though it would terminate after 5 balls had been dropped).
Why? As we counted down these are the bits that would be flipped.
101b = 5 - A0 flipped
100b = 4 - A2 flipped
011b = 3 - A0 flipped
… Bzzzt. We have reused a path.
Okay, maybe we should be adding another bit to A then? What should we set it’s initial value to though? 5 still doesn’t work as it would be the same as above.
1010b - A0 flipped
… etc
The only other reasonable suggestion would be 8
1000b = 8 - A3 flipped
0111b = 7 - A0 flipped
0110b = 6. - A1 flipped
0101b = 6 - A0 flipped
… Bzzt.
It also doesn’t work. Not only have we reused a path, eight balls will be released! (and we only want 5 released).
The solution for 3 bits just doesn’t seem to generalise to higher bits.
For this reason, the whole idea of using a decrementing register A just feels really inelegant to me.
Does anyone else feel this way?
Even if you don’t, how exactly would we generalise the solution to this problem so that we could seralize any number of bits in C?