Your task is to generate a valid juggling pattern by completing a given template. But first, you probably need to know how such a pattern is denoted.
Introduction to Siteswap
Siteswap is the established notation for juggling patterns. It works by dividing the pattern into beats. At each beat your left and right hand alternate at throwing a ball. Each throw (i.e. each beat) is denoted by a number which indicates when that ball is thrown next - this corresponds directly to the height of the throw.
Let's look at some examples. See animations of all of these here.
The simplest 3-ball pattern. Each ball is thrown at every third beat (alternating hands). Writing out the beats this looks like follows (the ASCII lines connect two beats at which the same ball is thrown):
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap 3 3 3 3 3 3 3 3 3 └─┼─┼─┘ │ │ └─┼───┘ │ └─────┘
Note how every ball thrown at an
L beat, is thrown next at an
R beat.Siteswap patterns repeat implicitly, so this pattern is usually denoted as
333, although simply
3 would also be sufficient.
Here is a slightly more complicated example with the siteswap 441:
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap 4 4 1 4 4 1 4 4 1 │ │ └─┘ │ │ └─┼─────┘ │ └───────┘
Note how even-numbered throws go to the same hand they were thrown from, while odd-numbered throws go to the other hand.
Sometimes you just want to hold a ball through a beat instead of throwing it. All that means, that this ball is thrown the next time its this hand's turn - i.e. 2 beats later. So holding a ball is equivalent to a
2 in the pattern:
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap 4 2 3 4 2 3 4 2 3 │ └─┼─┘ │ │ │ └───┼─┘ └───────┘
0 means that the current hand is empty at that beat, as this pattern shows:
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap 5 0 5 0 5 5 0 5 0 └───┼───┼─┘ │ └───┼─────┘ └───────>
This problem would be a bit too simple with vanilla siteswap though. Enter multiplex patterns! Multiplex juggling means that you throw multiple balls from one hand at the same time. For instance, in the above 3-ball cascade, if you were two throw an additional ball at every third beat, the pattern would become
33 and look like this:
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap  3 3  3 3  3 3 └┴──┼─┼──┴┘ │ │ └─┼──────┘ │ └────────┘
Here is another example, where the multiplex throw has two different heights/lengths. It could be denoted as either
Beat 1 2 3 4 5 6 7 8 9 Hand L R L R L R L R L Siteswap  1 1  1 1  1 1 ││ └─┴──┘│ │ │└────────┘ │ └────────────┘
(Note that the
1 thrown at beat
2 lands at beat
3 and is immediately thrown again (as another
1) to land at beat
4 and be part of the second multiplex throw.)
The siteswap for the animation at the beginning of this post was
For a pattern to be semantically valid the number of balls in a hand must always correspond to the number of throws indicated at that beat. This means, there must be no balls landing at a beat with a
0, there must be only one ball landing at a beat with any other single digit, and there must be n balls landing at a multiplex beat, where n is the number of digits in that multiplex throw. The pattern must also be able to repeat seamlessly.
Examples of invalid patterns are
543 (all balls would land at the same beat),
2 would land at the
0 beat) or
33 (no ball lands at the multiplex beat, but two balls land at both of the other two beats).
You will take a siteswap pattern which contains wildcards and output a valid pattern, with those wildcards filled in.
Take as input (via stdin, command-line argument, file or function parameter) a string of the format
n is an integer indicating the number of balls to be used, and
s is a siteswap pattern (without whitespace). You may assume that it is syntactically correct - all square brackets are matched and not nested, and there are no unexpected characters. All throws will be single-digit throws (
9). However, some beats may just be denoted as a
_, which is to be filled in with a single or a multiplex throw in the output.
Note: something like
[_3] will not be part of the input. Either the entire beat is missing or the entire beat is given.
Output a valid pattern, which can be juggled with the given number of balls and agrees with the input pattern in all the specified beats. If no valid pattern is possible with the given inputs, output
!. Output will also be via stdout, to a file or as a function return value.
Note: The output must not contain unnecessary square brackets or zeroes in multiplex throws. So outputs containing
 are not accepted, you have to output
3 instead. The order of digits in a multiplex throw is not relevant.
Note: You may omit patterns that are duplicates under cyclic permutations. E.g. for input
3 __ (note the two wildcards), both
24 are valid answers (among others), but they actually describe the same pattern. You can either output both or just one of them, but you'll have to do it consistently.
This is code golf, the shortest code wins (subject to bonuses listed at the bottom of the question).
You can use JugglingLab to play around with patterns to see if they are valid and what they look like.
Input Possible Outputs Comments 3 _ 3   3 4_3 423 4 4_2 42 42 42 3 _23_ 6231 4233 323 2235 223 0237 023 231 23
4 5_3 ! 5 and 3 will both land at the third beat, but there is only a single throw at that beat. This cannot be fixed with any throw in the blank. 2 5_4 ! Any possible throw in the wildcard (including a 0) will make a pattern for at least 3 balls. 3 54_ ! The only solution that would correspond to a 3-ball pattern is 540, which is not semantically valid because the 5 and 4 both land at beat 3. There are valid solutions, but they require at least 4 balls.
- If your answer can handle "digits" up to 35, denoted by letters (10 = A, 11 = B, ...), subtract 20 characters. You may decide if those letters should be upper-case, lower-case or case-insensitive. (JugglingLab can handle them in lower-case if you want to look at some insane patterns.)
- If your answer outputs all valid solutions, subtract 20 characters.