# New type of puzzle: binary input puzzles

Most of the puzzles use data represented by bits on the board, which of course makes a lot of sense, and the balls are mostly used to drive the computation. But there is a whole class of other puzzles we can consider if we view the blue/red ball sequence as data. Assume that all balls are intercepted, and that the user presses a lever for each ball to be released. Let blue = 1, and red = 0. Then the user can input a number like 6, for example, by pressing blue, blue, red, since 110 = 6 in binary.

The puzzle types Iâ€™m imagining are those where the objective is to determine whether the sequences entered by the user meets some specified condition, and the answer is reflected somehow on the final board configuration.

An easy example is just â€śis the (binary) number the user input an even number?â€ť. This just tests whether the last marble was red or not, and the result can be shown with a single bit.

Here is a harder one: â€śIs the (binary) number the user input divisible by 3?â€ť Iâ€™ve solved that with lots of parts and a large board using the emulator, and a link is in another thread. Iâ€™m curious if there is a simple solution that can actually be done on the physical gameboard, so ask it here.

I can imagine lots of puzzles. Here are five more beyond the divisible-by-three:

• Equality: Did the user enter an equal number of reds and blues? (This can be solved, assuming a bound on reds and blues, using a solution of another puzzle appearing elsewhere on the forum.)
• Two-for-one: Did the user enter twice as many reds as blues? (An extension of the same solution. Again, assume a bound on the number.)
• Alternation: Did the user enter an alternating sequence brbrbrbrâ€¦? Or did they deviate from that pattern?
• Prime: Was the binary number entered a prime number less than 15 (we need the bound, otherwise it is impossible).
• Encoding: This one isnâ€™t a yes/no condition, but rather to have register A, when done, reflect the binary value input by the user.
6 Likes

Whoa - thatâ€™s brilliant. I didnâ€™t think of that. Geez - you really could make a lot of cool puzzles this way. What a great idea!

1 Like

I managed to solve the â€śDivisible by Three in Binaryâ€ť challenge on a normal board. Here is my solution: jstumble

Note, I am not intercepting the balls in order to â€śstoreâ€ť the binary number in the balls collected at the bottom. The bit near the exit can be used interactively to select the value of the next bit.

The number is divisible by three when both â€ścolumn bitsâ€ť are set to zero. Hereâ€™s an example showing that nine is divisible by three.

3 Likes

@donutcomputer, this doesnâ€™t seem to be working. I tried entering just a single â€ś1â€ť, and the bit stayed pointing to the left, indicating that 1 is divisible by 3. Actually, no matter how many times one pushes the blue bar, the bit will stay pointing to the left, so something is wrong here.

Aha. I thought something was wrong, but I see youâ€™re using red = 1, blue =0.
I assume this is somehow keeping track of the remainder when divided by 3. (Each blue ball doubles the current remainder, and each red ball multiplies it by 2 and adds 1.) If this is the method youâ€™re using, is there an intuition on how that is being done using the two columns? If this isnâ€™t the method, then how are you doing this?

OK, I forgot the even number constraint. (Actually the blue =0, red =1 comment was for @eriban. So it seems perhaps I am the odd one out on blue=1, red=0.)

Here is a simple solution to the alternating-blue-and-red-checker. If the bits at the bottom point to the right, then the sequence was not of the form brbrbrbâ€¦ If they point to the left, then the sequence started with a blue, and has alternated since.

You have two unused interceptors and a gear bit.

My apologies for not using your convention wrt to the coloring of bits. It was my intention to follow your suggestion, but apparently I got things mixed up somewhere.

Indeed, my solution keeps track of the remainder when divided by three. This can in principle be done using a 3-state counter as was used in the solution for Challenge 39.

My next observation was that there is a periodicity to the amount that each bit contributes to this. The first bit adds one, the second two, the third adds one again (4 mod 3 = 1), the fourth two (8 mod 3 = 2), and so on. This has a period of two, which the row-bit at the top keeps track of.

So the next question was how to add the value two to this counter? For a normal counter this can be done by letting the ball enter at the second bit, but that does not work for this 3-state counter. I then observed that adding two effectively means visiting the three states in the reverse order:

• Adding one: 00 -> 11 -> 01 -> 00 â€¦
• Adding two: 00 -> 01 -> 11 -> 00 â€¦

This symmetry hinted at a symmetrical solution, which I could then quickly determine and the result is the two-column structure. Itâ€™s based on the 3-state counter from Challenge 39, but with the inverse feedback path added also (where toggling of the second bit by the ball entering there can be undone based on the state of the first bit).

Surely if you want to input 6 (110 or BBR) it should be least sig bit first? As in RBB?

You indeed enter the least significant bit first, i.e. the one, then the two, then the four, etc. If you do not intercept the balls, the sequence collected at the bottom of the Turing Tumble also has the least significant bit at the right, matching the normal binary notation. The confusion may be that in my example, the red balls are the 1s. So â€śbrbbrâ€ť is â€ś01001â€ť in binary, equalling nine.

Oh - so I do. Must have been not been paying attention too well, or perhaps my need for symmetry forced me to do it.

If one wants a solution where you enter the most significant bit first, a key observation is that adding a 0 to the stream multiplies the current value by 2, and adding a 1 to the stream multiplies by 2 and adds 1.

1 Like

Hereâ€™s my (final) solution to the "Divisible by Three in Binaryâ€ť challenge on a normal board with only pieces in the set.

https://www.lodev.org/jstumble/?board=rleagaeerxrfxlleelxreeraaleelg0greeragaleeralfrleei1

If the â€śpitchforkâ€ť gear formation and the regular bit are pointing left, then the number is divisible by three. Otherwise, the number isnâ€™t divisible by three.

Hope you enjoy it.

Here, I think, is a solution to the â€śEncoding problemâ€ť (or perhaps better labeled â€śLoad Register problemâ€ť) mentioned above â€“ that of inputting a binary number (most significant bit first), and having the board reflect the number input. Here, blue is 1, and red is 0, and you can load up to a 4-bit number, but extension is obvious from the repeating pattern.

The idea is just a shift register - a ball going through a bit that was 0 is directed to the right side of the bit below it, where a 0 is written. A ball going through a bit that was 1 is directed to the left side of the bit below it, where a 1 is written. In this way the value of the bit above is shifted down to the bit below as a ball moves through. The top unit just writes a 1 or a 0, depending on whether the ball is blue or red.

Of course, this can also be used just to multiply a register by 2 for a non-binary-input problem. Just send a red ball down, because shifting is multiplication by 2.

Edit: Here is a simpler (narrower) version - doing the same thing. Iâ€™m not sure if we can get it narrower.

Itâ€™s not actually narrower (still 5 units wide), but it kinda looks narrower because it has the ramps on the outside and fewer gearbits per bit: