Turing Tumble Community

What patterns are(n't) possible?

Just some general musings…I was marveling at the variety of problems and patterns that have been proposed and achieved, both in the original book, as well as in the discussions here. We know that with large enough board and sufficient supply of pieces the TT can do anything a computer can, and so any finite sequence can be generated. But what about the TT as it comes out of the box?

There are 2^n possible sequences of length n. What is the largest value of n so that all 2^n sequences can be generated with the original TT set? Or, said differently, what is the shortest sequence that cannot be generated?

It seems that sequences with regularity of some sort will be easiest to generate with a smaller number of pieces, and sequences with no apparent regularity or repeating pattern will require more pieces. Perhaps that would be a place to start to find short sequences that cannot be generated.

2 Likes

This is my guess and my thought process, though it may not be correct
First off, I’m going to assume an upper bound would be as many balls come in the box (~20 each color). We can make another approximation by assuming the pattern is RBR n[RB] BRB for now. Now, we need to find n. In order to do this we need to find the largest counter that can be changed by 2 balls (This is ignoring a lot of small factors), and still flip positions. With this, we get n=9, so an upper bound would be around RBRRBRBRBRBRBRBRBRBRBBRB, giving 2^24. Now, possibly we need to find one shorter than this, such as shortening the beginning sequence.

If we started with BR n[RB] BR, that would shorten n down to 5, giving BRRBRBRBRBRBBR as an answer, granted, we still haven’t even brought up the amount of pieces in the box, which may or may not come into play.

I don’t think I understand your notation.
Also, in my musings, I was imagining we had as many balls as we needed. But, I suspect that there are already many patterns with the about 40 balls that can’t be generated. In fact I’ll bet there are 10-ball patterns that can’t be generated.

Here is my knee-jerk attempt at a candidate. BB RRR B R B RR .
Why? Because it seems to have no repetition or structure that one can easily exploit. I haven’t had a hand at trying to build it, since I’m feeling lazy. But being cooped in will probably give me plenty of time…

Ah, that makes more sense. I shall attempt to change it this way. Thank you very muchc for specifying.

The very largest I could get that is a good enough example for now is 128R, 1B, 128R, 1B, 64R, etc. This is based on the largest counter I could make on a single board with a single ball before switching to another color one time, which can count to, which is 64. We can make this even smaller with an actual pattern of R BB RR B R BB RR B R BB RR B R B R
[Repeat] or (Infinite)(3(1R 2B 2R 1B) 1R). This limits not by the amount of resources but by the board’s space. This uses 21 balls before it repeats, though I can almost guarantee there is a shorter pattern. I am jumping a bit to conclusions with this guess, though it isn’t very far out that this pattern is indeed impossible to make on a board.

Here was my test board to get this pattern by making a short sequence that used “all” of the board, starting with a red lever
https://www.lodev.org/jstumble/?board=bbrgbgbglexeleerllfxrfrrrf1rreerrrlee1rxeer0lre0_71_70

Perhaps a way to progress this (very interesting) topic would be to adopt a convention of numbering: let red represent 0 and blue represent 1. We can then imagine a “silent” extra blue ball at the end. Example: first ball down so R, then two blues, then three reds. Physical balls are 000110. To ensure it’s always a distinct binary number, add a leading “silent” blue ball - 1000110. So - the sequence RRRBBR becomes (1)000110 or decimal 70. We can now describe the problem as “create the pattern represented by each decimal number in turn”. What’s the first pattern you can’t create on a standard physical board (kit without additional parts)? —-@Florentin - you might like this one too

A couple of variations: strict version: all 40 balls must be loaded in and sequence ends with balls exhausted or an intercept. Lax version: you are allowed to generate a sequence by adjusting the number of balls in the hoppers.
I am also assuming colours cannot be mixed in the hoppers!! (That would be too simple a cheat)

That’s an efficient way to repertoriate any possible configuration. Just to be clear the silent blue ball doesn’t have to really appear on the board, it is only an element of notation ?
A first optimisation, would be that we only need to check the half of the numbers, because if a pattern is possible, then its 1’s complement is as well possible by only mirroring the board.
So to check all 6 bits sequences, it would require 32 patterns to be generated (Not that long), but even with @lennypitt 's conjecture that a 10-ball pattern can’t be generated, the amount of patterns required to be checked could amount up to 512. It would already take quite some time, but let say it is possible.
What do we do when we find a pattern that we can’t generate?
How to decide whether we are simply bad or if it is really impossible to achieve, what are the tools we have at hand?
That doesn’t seem to be an easy puzzle.

That very pattern is actually feasible:
jstumble (lodev.org)
image

I agree - a hard and time consuming puzzle- but ideal for a community😀. We could probably quite quickly dismiss all the 5 ball patterns, then work our way up. When finding a hard one, get the community to assist. What to do when we get one no one can solve? Well, we may have determined the limit. But could be by them we have discovered a way to demonstrate a limit has been reached (rather than just nobody has yet solved). I suspect several patters will emerge ( bit like sifting for prime numbers) - eg B nxR or nxB nxR ; are solvable for reasonable n.

The tl;dr version of this comment is that since there are only 18 bit pieces supplied in the game, only patterns of length at most 2^18 may be generated.

The comment by @Florentin seems to be the crux of the problem of thinking about this - what tools do we have? The only tool I can think of offhand would be in essence a counting argument, similar to the pumping lemma for finite state machines. But first let’s firm up the statement of the problem:

Say that a finite pattern p can be generated by TT out of the box if when pressing either the left or right lever to start, with all balls initially at the top, the machine halts by routing a ball to an interceptor, and the pattern p is what has been output. So, the longest pattern that can be generated would have length 39, since 40 balls come with the machine. But let us consider a more interesting extended version of the problem which allows longer patterns to be generated if the machine started with more than the supplied 20 blue and 20 red balls, but halted with a ball in an interceptor.

Now, following along a simple counting argument, there are only 18 bit pieces (10 regular, and 8 gear) supplied in the box. So, regardless of how the pieces are laid down, if a pattern p of length more than 2^18 is being output, then the pattern of bit settings must repeat some configuration, so the machine is in a loop, and will never halt. We conclude that regardless of the number of starting balls, only patterns of length at most 2^18 can be output (with the machine stopping via interceptor) according to our definition.

While that number is way high, it is a very weak starting point towards arguing about patterns that may not be generated.

Finally, this suggests another challenge - sorry if it has appeared already. What is the largest number n such that the machine when run, outputs n balls and then stops via interceptor. We can consider two versions of this, both on the standard board size: Version 1, you are supplied only the parts in the box. Version 2, you may use any pieces you’d like, as long as you use the standard board. I can see how to make a 10-bit counter that halts on overflow. Is a number higher than 1024 possible?

Perhaps we need a genre of “unlimited balls, standard board, ending with an interceptor”. Within that genre we could have a) longest achievable output pattern and b) shortest impossible pattern. The first question (a) has parallels with some of the “cheats” of the highest number that can be represented on the board.

This alternative challenge is similar to the one having been explored in this post How Many Balls Can You Count? - New Puzzles to Solve - Turing Tumble Community, since you can anticipate the amount of red balls falling on the right, you should be able to do what you want.

For this post I’m going to use the “unlimited balls, standard board, ending with an interceptor” formulation, an address the both the longest pattern and shortest impossible pattern variants.

Longest Pattern:

I believe this 18-bit counter (based on @wyrm_slayr’s designs) creates the longest pattern that can be generated using only the parts in the kit. HOWEVER! The length of the pattern is not 262,144 (2^18), as one might expect: this is the number of blue balls counted. Every time the left register overflows, a red ball is released. Thus, the pattern is 1024 Blue, 1 Red, 1024 Blue, and so on until the 256th red ball is intercepted. Thus, the length of the pattern is actually: 1024*256+255 = 262,399.

Screen Shot 2021-01-10 at 7.42.08 PM
jstumble

Now, if we aren’t limited to the parts in the kit, then the longest pattern I know of is 324,927, which is generated by the largest counter I know of.

Shortest Impossible Pattern:

I agree with much of what has been said above, so I have gone ahead and found a solution for every pattern of up to five balls. I like the analogy of “sifting for primes”, since some solutions will be able to generate multiple patterns. Here are the main ones I used:

A - nR
B - nB,nR
C - RBRB… or BRBR…
D - RRBB…
E - same as D, but E counts every red ball, instead of every other

I am continuing with the convention of representing each pattern as a binary number where blue = 1 and red = 0. As pointed about above, for n balls, only the first 2^(n-1) patterns have to be tested, since the remaining half of the patterns can be generated by mirroring the solutions for the first half.

0 (A)

00 (A)
01 (B)

000 (A)
001 (B)
010 (C)
011 (B)

0000 (A)
0001 (B)
0010 (D Variant)
0011 (D Variant)
0100 (D Variant)
0101 (C)
0110 (D Variant)
0111 (B)

00000 (A)
00001 (B)
00010
00011 (B)
00100
00101
00110 (E Variant)
00111 (B)
01000
01001 (same as previous)
01010 (C)
01011
01100 (E Variant)
01101
01110
01111 (B)

So there you have it, all patterns of five balls or fewer are possible. If anyone wants to continue to six balls and beyond, please feel free to use anything in this post.

Hi - Thanks for the solution for longest pattern (with standard set) - I calculated 262399 as well.
Regarding shortest impossible pattern, you may be interested in “Universal” configurable pattern generator - which can be configured to create any of the up to 5 ball patterns you worked through - all from a single board. I couldn’t manage 6 from a single board, but any 6 ball pattern (allowing some variations to a board) is pretty certain. I would be surprised if the first impossible pattern were less than 10 balls long - but very laborious to prove.

Note slightly different challenges. @wyrm_slayr original post was to count BLUE balls (allowing reds to be in the mix). Same configuration also leads (probably) to longest pattern. But “longest pattern” is 319 longer than “most blue balls counted”.

Six Balls

@pt153 your five-ball pattern generator is impressive! It pretty much fills the board, so I agree that an arbitrary six-ball pattern generator is unlikely. Also, it turns out you were right about six balls: I was able to do a lot with variations on a surprisingly small number of base solutions. I didn’t bother to note the variants this time, but I do want to point out that I found a better version of E above. (Note: many of these solutions were inspired by @Florentin’s example above)

Solutions

000000

000001

000010

000011

000100

000101 - will work up to n = 17

000110

000111

001000

001001

001010

001011 - I figured this one out last, probably because I couldn’t adapt what I had already worked out (note the unique structure)

001100

001101

001110

001111

010000

010001

010010

010011

010100

010101

010110

010111

011000

011001

011010

011011

011100

011101

011110

011111

Seven Balls!

Ok, I’m taking a (permanent?) break here. It looks like things will get pretty tricky at eight, and I don’t know how much solution reuse is going to be viable there. It turned out to be hugely beneficial here, so detailed the solutions I found as some will be useful for eight balls and beyond.

A - 32 Patterns
This one can generate any pattern that is 1) all red, 2) some blue, then some red, 3) red, blue, red, or 4) one blue, then red, blue, red. This solution is valid for all such patterns up to 14 balls, and then some patterns at 15 and higher.

B1, B2, B3, B4 - 14 Patterns
These generate repeating patterns of one and two balls, where the start of the pattern is different (e.g. first one blue, then two blue thereafter)

C, D, E, and F - 18 Patterns
These generate patterns of seven balls containing 2, 3, 4, and 5 blue balls, respectively. The pattern is determined by the routing of the output of two counters. This means that each variant is used for exactly one pattern.

Solutions

0 - 0000000: A

1 - 0000001: A

2 - 0000010: A

3 - 0000011: A

4 - 0000100: A

5 - 0000101: A

6 - 0000110: A

7 - 0000111: A

8 - 0001000: A

9 - 0001001: A

10 - 0001010: C1

11 - 0001011: D1

12 - 0001100: A

13 - 0001101: A

14 - 0001110: A

15 - 0001111: A

16 - 0010000: A

17 - 0010001: A

18 - 0010010: B2

19 - 0010011: B2

20 - 0010100: C2

21 - 0010101: D2

22 - 0010110: D3

23 - 0010111: E1

24 - 0011000: A

25 - 0011001: A

26 - 0011010: D4

27 - 0011011: B4

28 - 0011100: A

29 - 0011101: A

30 - 0011110: A

31 - 0011111: A

32 - 0100000: A

33 - 0100001: A

34 - 0100010: C3

35 - 0100011: D5

36 - 0100100: B2

37 - 0100101: B2

38 - 0100110: B2

39 - 0100111: E2

40 - 0101000: C4

41 - 0101001: B1

42 - 0101010: B1

43 - 0101011: B1

44 - 0101100: B1

45 - 0101101: E3

46 - 0101110: E4

47 - 0101111: F1

48 - 0110000: A

49 - 0110001: A

50 - 0110010: B4

51 - 0110011: B3

52 - 0110100: B3

53 - 0110101: E5

54 - 0110110: B3

55 - 0110111: F2

56 - 0111000: A

57 - 0111001: A

58 - 0111010: E6

59 - 0111011: F3

60 - 0111100: A

61 - 0111101: A

62 - 0111110: A

63 - 0111111: A

Wow! Well done @RingTheBell . Have you gained any insights regarding which the hardest ones are likely to be? I think we need to request a feature from the moderator to easily post solutions so we can spread the load.

Actually, I did gain an insight into what is possible. On C through F, I now realize I was getting hung up on the color of the last ball. The last dropped ball has to be red, but the intercepted ball can be either color. This means that the smaller of the two counters can be used to catch the last ball, which may save enough space to make eight balls possible (I’ve got 2 blue and 6 red worked out already). It also means that C and F and D and E could’ve been like mirror images of each other.

As to what the hardest patterns are, it’s basically what was speculated in the original post. More specifically though, it’s patterns that require counting past six, because I don’t think a counter with seven or more outputs will fit on the board with enough room for a second counter.