Turing Tumble Community

Make it harder - a basic repeating pattern

New Puzzles to Solve
#1

This new puzzle is similar to many in the book: output a repeating (alternating) pattern of blue (“B”) and red (“r”) marbles. For this challenge, the output must be 4 blue marbles followed by 4 red marbles, repeating until the marbles are exhausted. What makes it harder (possibly) is the required initial board layout, which is a vertical register of 4 bits. (See picture.)

Screenshot_20180711_155030

The 4 bits can be initially oriented in any positions. They are not required to all be pointing left as shown in the image. The initial board layout can be found here on jstumble.

The available parts inventory for solving this challenge includes only these parts:

  • the 4 provided bits (no additional bits)
  • 1 crossover
  • 22 or fewer ramps

Start with the blue lever.

Required output:

rrrrBBBBrrrrBBBBrrrrBBBB
(until out of marbles)

In the spirit of my other challenges, once you have solved this puzzle starting with the required initial board layout, see what alternative solutions you can find without any parts restrictions or layout preconditions (particularly if such solutions use fewer parts or replace “expensive” parts such as gear bits with “inexpensive” parts such as ramps or crossovers). For an alternative solution, all that is required is the specified output.

There is at least one major alternative solution which does not use the vertical register of 4 bits. That alternative is more intuitive and probably not as challenging. I may be wrong, but I think what makes this puzzle interesting is the required 4 bit vertical register. However, once solved, you will probably recognize the pattern. I hope this challenge encourages some out of the box thinking and leads to insights that help make you a stronger puzzle solver.

If requested, I can provide some explanation of how the puzzle works in terms of basic logic concepts.

I do not know how difficult people will consider this puzzle. I estimate the difficulty level as “medium”, on a par with puzzles in the middle of the book. The intended challenge is to cause you to think about the vertical 4 bit register in a different way. Please let me know if I have provided too much information or not enough information to make the puzzle interesting and challenging.

3 Likes
#2

If you start with the blue lever, surely the first ball will be blue, So, the result will be BrrrrBBBB…

#3

The first output is the rightmost position. That’s why it is shown as:

rrrrBBBBrrrrBBBBrrrrBBBB

This is based on the concept of significant digits in numbers, and it is the opposite of written languages that are left-to-right. In this case, the first 4 marbles are blue, the next 4 are red, then 4 more blue, 4 more red, etc.

I hope that clears up any confusion. Thanks for looking at my puzzle.

#4

Ah! Right. Like a picture of what would be seen in the output tray at the bottom

#5

Yes, that’s exactly right.

#6

Here’s a solution. (No screenshot because spoilers.) It uses only 20 of the available 22 ramps. There doesn’t seem to be any markup for spoilers in this forum, so all I can do is warn you that the next paragraph contains an explanation. :wink:

I assume that this is close to the intended solution. I’m splitting the four bits into two separate registers. The top one is used by the blue balls and counts down from 3 to 0 (before underflowing when releasing the fourth blue ball to the right) and the bottom one is used by the red balls and counts up from 0 to 3 (before overflowing when releasing the fourth red ball to the left).

Now for alternative solutions. We can save two ramps with the same material if we place the bits elsewhere.

I know you prefer solutions with simpler parts, but if we go the opposite way and add some gear bits to the mix, we can actually save another six parts (for 17 overall, with only a single 2-bit register). The idea here is to set up the three gear bits so that they don’t change their state when hit from the top, but that you can toggle them by going directly into one of the lower gear bits, which we do whenever the register overflows.

Btw, you might want to link to jstumble in the OP (possibly with the base layout already setup), in case people are not familiar with it yet.

3 Likes
#7

Nice job! You always seem to use fewer parts than I do. Here’s my original solution. It uses 1 more ramp than you used, and now that I see your solution it is obvious that I did not need that ramp.

You also described the essence of the idea behind this puzzle: splitting a register of 4 bits into 2 registers of 2 bits. I think this concept has real-world significance – do you agree? (I’m not a professional developer or EE, so I’m only guessing how useful this concept might be, but it does seem to be something that would commonly be done in real situations.)

You used the two registers of two bits exactly the way I did as well, and your explanation of the subtractor on top and adder on bottom is very clear.

Your alternatives are very interesting too! :grinning: Your solution with gear bits and only 17 total parts is great!

#8

Certainly. One use case that comes to mind is from computer graphics: often you can only pass 32-bit data to the GPU. But sometimes you only need a bunch of 8-bit values, so it’s wasteful to store each of them in a 32-bit variable. The solution is to pack four 8-bit values into a single 32-bit value. (Whether that trade-off is worth it or not depends on your application, but this kind of packing and unpacking definitely exists as a technique.)

1 Like
#9

@menderbug, for someone like you who already has so much real world programming experience, how useful is your time spent on Turing Tumble? How much do you learn and how much insight do you personally gain from solving these puzzles? Do you learn things you cannot learn easily via other methods?

1 Like
#10

I’m not sure I spend time on TT because it’s useful, but because it’s fun. :wink: That said, I definitely learn things, but not necessarily specific insights that can be applied directly to programming problems (most of the specific insights I gain here are more about the mechanics of TT itself and how certain configurations can be used to solve certain subproblems in a compact way). But solving and optimising TT puzzles (or any other form of recreational programming) is a great exercise for my problem solving skills, which definitely carries over to real-world programming, only in a much more indirect way.

3 Likes
#11

Yeah, there’s some opportunities to optimise bandwidth or storage by packing data more densely rather than breaking it semantically. But when you do that, you add some overhead packing and unpacking it, and, unless you’re careful and/or lucky, you also have to either unpack it in order to do any processing, or have to write custom processing routines rather than using the hardware to do it for you.

For example, adding 1 is something that can often be handled by the hardware as a special case, while adding 4 (adding 1 with a 2-bit offset) requires generic addition to be invoked. And overflow will be handled automatically if you’re using an entire register; if you’re treating it as two sub-registers, overflow from the less significant sub-register will mess up the data in the most significant sub-register…

So, yes, it is something that can be done, but there are trade-offs involved, and, unless you’re working on an embedded system with limited memory, dealing with very limited bandwidth, or working with large amounts of data, the costs from the added complexity are going to outweigh the benefits - and unless you’re working very low-level, you can just zip the data (or use some other third-party compression library) anyway.

1 Like
#12

Here is my solution:

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

It uses 21 ramps and 1 crossover. There are 26 pieces total (including the bits but not the balls). Also, the bits start all pointed left.

1 Like
#13

Ok, That’s including a free fall.
Here is my solution without a free fall.

#14

I lied, it uses 6 crossovers.

#15

I think this is a good puzzle and you rated its difficulty correctly. I found the same solution as menderbug, so no need to post it again. As for alternate solutions, I’m surprised no one posted:

Screen Shot 2020-08-06 at 11.02.53 PM

https://lodev.org/jstumble/?board=10r10lerxlfrlfexferlfexferlfexferleex