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.
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.
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.
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)
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
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.
Eight Balls!
A and B are as before, and C, D, E, F, and G generate patterns of eight balls containing 2, 3, 4, 5, and 6 blue balls, respectively. Also, I used hexadecimal as shorthand for the binary this time since it’s much more convenient than decimal (I really should have been using it all along 
).
@pt153 An insight I’ve gained from eight balls is that crossovers may be the limiting resource: there were a few cases where I ran out, but luckily I was able to substitute a bit. This may be a constraint going forward, but on the other hand I think this is the end of arbitrary pattern generators so the demand may be less. (Or maybe I just use more crossovers than are strictly necessary 
)
Solutions
0x00 - 00000000: A
0x01 - 00000001: A
0x02 - 00000010: A
0x03 - 00000011: A
0x04 - 00000100: A
0x05 - 00000101: A
0x06 - 00000110: A
0x07 - 00000111: A
0x08 - 00001000: A
0x09 - 00001001: A
0x0A - 00001010: C1
0x0B - 00001011: D1
0x0C - 00001100: A
0x0D - 00001101: A
0x0E - 00001110: A
0x0F - 00001111: A
0x10 - 00010000: A
0x11 - 00010001: A
0x12 - 00010010: C2
0x13 - 00010011: D2
0x14 - 00010100: C3
0x15 - 00010101: D3
0x16 - 00010110: D4
0x17 - 00010111: E1
0x18 - 00011000: A
0x19 - 00011001: A
0x1A - 00011010: D5
0x1B - 00011011: E2
0x1C - 00011100: A
0x1D - 00011101: A
0x1E - 00011110: A
0x1F - 00011111: A
0x20 - 00100000: A
0x21 - 00100001: A
0x22 - 00100010: C4
0x23 - 00100011: D6
0x24 - 00100100: B2
0x25 - 00100101: B2
0x26 - 00100110: B2
0x27 - 00100111: E3
0x28 - 00101000: C5
0x29 - 00101001: D7
0x2A - 00101010: D8
0x2B - 00101011: E4
0x2C - 00101100: D9
0x2D - 00101101: E5
0x2E - 00101110: E6
0x2F - 00101111: F1
0x30 - 00110000: A
0x31 - 00110001: A
0x32 - 00110010: B4
0x33 - 00110011: B4
0x34 - 00110100: D10
0x35 - 00110101: E7
0x36 - 00110110: E8
0x37 - 00110111: F2
0x38 - 00111000: A
0x39 - 00111001: A
0x3A - 00111010: E9
0x3B - 00111011: F3
0x3C - 00111100: A
0x3D - 00111101: A
0x3E - 00111110: A
0x3F - 00111111: A
0x40 - 01000000: A
0x41 - 01000001: A
0x42 - 01000010: C6
0x43 - 01000011: D11
0x44 - 01000100: C7
0x45 - 01000101: D12
0x46 - 01000110: D13
0x47 - 01000111: E10
0x48 - 01001000: C8
0x49 - 01001001: B2
0x4A - 01001010: D14
0x4B - 01001011: B2
0x4C - 01001100: B2
0x4D - 01001101: E11
0x4E - 01001110: E12
0x4F - 01001111: F4
0x50 - 01010000: C9
0x51 - 01010001: D15
0x52 - 01010010: D16
0x53 - 01010011: B1
0x54 - 01010100: B1
0x55 - 01010101: B1
0x56 - 01010110: B1
0x57 - 01010111: F5
0x58 - 01011000: D17
0x59 - 01011001: E13
0x5A - 01011010: E14
0x5B - 01011011: F6
0x5C - 01011100: E15
0x5D - 01011101: F7
0x5E - 01011110: F8
0x5F - 01011111: G1
0x60 - 01100000: A
0x61 - 01100001: A
0x62 - 01100010: D18
0x63 - 01100011: E16
0x64 - 01100100: B4
0x65 - 01100101: E17
0x66 - 01100110: B4
0x67 - 01100111: F9
0x68 - 01101000: D19
0x69 - 01101001: E18
0x6A - 01101010: E19
0x6B - 01101011: F10
0x6C - 01101100: B3
0x6D - 01101101: B3
0x6E - 01101110: F11
0x6F - 01101111: G2
0x70 - 01110000: A
0x71 - 01110001: A
0x72 - 01110010: E20
0x73 - 01110011: F12
0x74 - 01110100: E21
0x75 - 01110101: F13
0x76 - 01110110: F14
0x77 - 01110111: G3
0x78 - 01111000: A
0x79 - 01111001: A
0x7A - 01111010: F15
0x7B - 01111011: G4
0x7C - 01111100: A
0x7D - 01111101: A
0x7E - 01111110: A
0x7F - 01111111: A
1 Like
Amazing and disciplined effort. Well done @RingTheBell !
Any 8 ball combination from what is basically 7 “standard” approaches makes me think we are not that close to the limit yet. I would still be surprised if there were any 10 ball combinations that cannot be done. In the “Universal pattern Generator” crossovers were my limiting factor too . I had a solution for any pattern up to 6 balls on the standard board size, but it used more crossovers than the standard set. I think loads of crossovers comes partly from wanting to have fewer standard boards to generate multiple patterns each.
Hex notation works absolutely brilliantly for 8 balls. Notation that works for both 9 and 10 balls might be more of a challenge (but I have an idea for that :- 
).
1 Like
Woo! Nine Balls!
I’ve created a new pattern generator, C, that can do everything A does, but also patterns that are blue, then red, then blue, then red. However, A is not obsolete because it can generate longer patterns than C.
When I did the eight-ball patterns, I noticed that having two counters was somewhat redundant, so for D (2 blue, 7 red, and 3 blue, 6 red), E (4 blue, 5 red), F (5 blue, 4 red), and G (6 blue, 3 red), there is only one counter and then some supporting logic. Also since there are so many versions of these in use here, I didn’t bother numbering the ones that are only used once, and instead marked them with ‘v’.
Solutions 0x00-0x3F
0x00 - 000000000: A
0x01 - 000000001: A
0x02 - 000000010: A
0x03 - 000000011: A
0x04 - 000000100: A
0x05 - 000000101: A
0x06 - 000000110: A
0x07 - 000000111: A
0x08 - 000001000: A
0x09 - 000001001: A
0x0A - 000001010: Dv
0x0B - 000001011: C
0x0C - 000001100: A
0x0D - 000001101: A
0x0E - 000001110: A
0x0F - 000001111: A
0x10 - 000010000: A
0x11 - 000010001: A
0x12 - 000010010: Dv
0x13 - 000010011: C
0x14 - 000010100: Dv
0x15 - 000010101: Dv
0x16 - 000010110: Dv
0x17 - 000010111: C
0x18 - 000011000: A
0x19 - 000011001: A
0x1A - 000011010: Dv
0x1B - 000011011: C
0x1C - 000011100: A
0x1D - 000011101: A
0x1E - 000011110: A
0x1F - 000011111: A
0x20 - 000100000: A
0x21 - 000100001: A
0x22 - 000100010: Dv
0x23 - 000100011: C
0x24 - 000100100: Dv
0x25 - 000100101: Dv
0x26 - 000100110: Dv
0x27 - 000100111: C
0x28 - 000101000: Dv
0x29 - 000101001: Dv
0x2A - 000101010: Dv
0x2B - 000101011: Ev
0x2C - 000101100: Dv
0x2D - 000101101: Ev
0x2E - 000101110: E1
0x2F - 000101111: C
0x30 - 000110000: A
0x31 - 000110001: A
0x32 - 000110010: Dv
0x33 - 000110011: C
0x34 - 000110100: Dv
0x35 - 000110101: Ev
0x36 - 000110110: Ev
0x37 - 000110111: C
0x38 - 000111000: A
0x39 - 000111001: A
0x3A - 000111010: E1
0x3B - 000111011: C
0x3C - 000111100: A
0x3D - 000111101: A
0x3E - 000111110: A
0x3F - 000111111: A
Solutions 0x40-0x7F
0x40 - 001000000: A
0x41 - 001000001: A
0x42 - 001000010: Dv
0x43 - 001000011: C
0x44 - 001000100: Dv
0x45 - 001000101: Dv
0x46 - 001000110: Dv
0x47 - 001000111: C
0x48 - 001001000: Dv
0x49 - 001001001: B2
0x4A - 001001010: Dv
0x4B - 001001011: B2
0x4C - 001001100: B2
0x4D - 001001101: Ev
0x4E - 001001110: E2
0x4F - 001001111: C
0x50 - 001010000: Dv
0x51 - 001010001: Dv
0x52 - 001010010: Dv
0x53 - 001010011: Ev
0x54 - 001010100: Dv
0x55 - 001010101: Ev
0x56 - 001010110: Ev
0x57 - 001010111: Fv
0x58 - 001011000: Dv
0x59 - 001011001: Ev
0x5A - 001011010: Ev
0x5B - 001011011: Fv
0x5C - 001011100: E4
0x5D - 001011101: Fv
0x5E - 001011110: Fv
0x5F - 001011111: C
0x60 - 001100000: A
0x61 - 001100001: A
0x62 - 001100010: Dv
0x63 - 001100011: C
0x64 - 001100100: B4
0x65 - 001100101: Ev
0x66 - 001100110: B4
0x67 - 001100111: C
0x68 - 001101000: Dv
0x69 - 001101001: Ev
0x6A - 001101010: Ev
0x6B - 001101011: Fv
0x6C - 001101100: Ev
0x6D - 001101101: Fv
0x6E - 001101110: Fv
0x6F - 001101111: C
0x70 - 001110000: A
0x71 - 001110001: A
0x72 - 001110010: E2
0x73 - 001110011: C
0x74 - 001110100: E4
0x75 - 001110101: Fv
0x76 - 001110110: Fv
0x77 - 001110111: C
0x78 - 001111000: A
0x79 - 001111001: A
0x7A - 001111010: Fv
0x7B - 001111011: C
0x7C - 001111100: A
0x7D - 001111101: A
0x7E - 001111110: A
0x7F - 001111111: A
Solutions 0x80-0xBF
0x80 - 010000000: A
0x81 - 010000001: A
0x82 - 010000010: Dv
0x83 - 010000011: C
0x84 - 010000100: Dv
0x85 - 010000101: Dv
0x86 - 010000110: Dv
0x87 - 010000111: C
0x88 - 010001000: Dv
0x89 - 010001001: Dv
0x8A - 010001010: Dv
0x8B - 010001011: Ev
0x8C - 010001100: Dv
0x8D - 010001101: Ev
0x8E - 010001110: E3
0x8F - 010001111: C
0x90 - 010010000: Dv
0x91 - 010010001: Dv
0x92 - 010010010: B2
0x93 - 010010011: B2
0x94 - 010010100: Dv
0x95 - 010010101: Ev
0x96 - 010010110: Ev
0x97 - 010010111: Fv
0x98 - 010011000: Dv
0x99 - 010011001: Ev
0x9A - 010011010: Ev
0x9B - 010011011: Fv
0x9C - 010011100: E5
0x9D - 010011101: Fv
0x9E - 010011110: Fv
0x9F - 010011111: C
0xA0 - 010100000: Dv
0xA1 - 010100001: Dv
0xA2 - 010100010: Dv
0xA3 - 010100011: Ev
0xA4 - 010100100: Dv
0xA5 - 010100101: Ev
0xA6 - 010100110: Ev
0xA7 - 010100111: Fv
0xA8 - 010101000: Dv
0xA9 - 010101001: B1
0xAA - 010101010: B1
0xAB - 010101011: B1
0xAC - 010101100: B1
0xAD - 010101101: Fv
0xAE - 010101110: Fv
0xAF - 010101111: Gv
0xB0 - 010110000: Dv
0xB1 - 010110001: Ev
0xB2 - 010110010: Ev
0xB3 - 010110011: Fv
0xB4 - 010110100: Ev
0xB5 - 010110101: Fv
0xB6 - 010110110: Fv
0xB7 - 010110111: Gv
0xB8 - 010111000: E6
0xB9 - 010111001: Fv
0xBA - 010111010: Fv
0xBB - 010111011: Gv
0xBC - 010111100: Fv
0xBD - 010111101: Gv
0xBE - 010111110: Gv
0xBF - 010111111: C
Solutions 0xC0-0xFF
0xC0 - 011000000: A
0xC1 - 011000001: A
0xC2 - 011000010: Dv
0xC3 - 011000011: C
0xC4 - 011000100: Dv
0xC5 - 011000101: Ev
0xC6 - 011000110: Ev
0xC7 - 011000111: C
0xC8 - 011001000: D
0xC9 - 011001001: Ev
0xCA - 011001010: Ev
0xCB - 011001011: Fv
0xCC - 011001100: B4
0xCD - 011001101: B4
0xCE - 011001110: Fv
0xCF - 011001111: C
0xD0 - 011010000: Dv
0xD1 - 011010001: Ev
0xD2 - 011010010: Ev
0xD3 - 011010011: Fv
0xD4 - 011010100: Ev
0xD5 - 011010101: Fv
0xD6 - 011010110: Fv
0xD7 - 011010111: Gv
0xD8 - 011011000: Ev
0xD9 - 011011001: Fv
0xDA - 011011010: B3
0xDB - 011011011: B3
0xDC - 011011100: Fv
0xDD - 011011101: Gv
0xDE - 011011110: Gv
0xDF - 011011111: C
0xE0 - 011100000: A
0xE1 - 011100001: A
0xE2 - 011100010: E3
0xE3 - 011100011: C
0xE4 - 011100100: E5
0xE5 - 011100101: Fv
0xE6 - 011100110: Fv
0xE7 - 011100111: C
0xE8 - 011101000: E6
0xE9 - 011101001: Fv
0xEA - 011101010: Fv
0xEB - 011101011: Gv
0xEC - 011101100: Fv
0xED - 011101101: Gv
0xEE - 011101110: Gv
0xEF - 011101111: C
0xF0 - 011110000: A
0xF1 - 011110001: A
0xF2 - 011110010: Fv
0xF3 - 011110011: C
0xF4 - 011110100: Fv
0xF5 - 011110101: Gv
0xF6 - 011110110: Gv
0xF7 - 011110111: C
0xF8 - 011111000: A
0xF9 - 011111001: A
0xFA - 011111010: Gv
0xFB - 011111011: C
0xFC - 011111100: A
0xFD - 011111101: A
0xFE - 011111110: A
0xFF - 011111111: A
Ok that was a lot I’m going back on hiatus
2 Likes