Turing Tumble Community

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.
  • Create-your-own: your puzzle here.
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.
TuringTumble-DivisibleByThree

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. :slight_smile:

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:

Screenshot%20from%202018-08-17%2023-08-01

simulator link

Here’s my take on “divisible by three” – two years later (but I’m new to this). I wanted to see if I could come up with a solution where a single bit encodes the answer. Here the topmost gear bit points right if the answer is divisible by three; left otherwise. (It should start right, of course). Red balls are 1s, blue balls are 0s.TT divisible by three

This is a great idea and I’m surprised this hasn’t had a lot of discussion lately.
Here is my solution for Alternation. You can start with either color. The lower interceptor will catch a ball when you stop the pattern. It can be made with the standard parts list. Both gears start pointing left. Tell me what you think
https://jessecrossen.github.io/ttsim/#s=13,17&z=32&cc=6&cr=8&t=3&sp=1&sc=0&b=data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAA0AAAASCAYAAACAa1QyAAAAAXNSR0IArs4c6QAAARdJREFUOE+Fk0FuhDAMRb83Xc+yy+QMPQCo6kFA9B5kDoIE92irLLuqeoNkOauqJxiXJJhBJHQsIYj5zx87hKy116ZpEK5xHFHXNay1kNjnjTEggYLIOQ+t1QrIwzB4dF3KFyBHBAKDobVm5xydCegZcZ1BQRBLzdh5xnrc7vQO8HMqtDpVVZWAmZHK4kgfFAGJaZo49rSFopkIpcKmyyK0Oiy9yfquUzSQnnjjDKDsRARmvvW2rO86HQ0hgIeDSJNPjvv4F8rUSyJCxpjrXtD3/bpvbdtmdqSUyiDnHbTSGPyATnWZaQZt/+rSJ4b3RScBS1A4PkUoiANYinDe5r1nflVP+Dr94OH3BZfTGx6/PT6Pxjfn/wDIOcew6myktgAAAABJRU5ErkJggg==