Juggling by Numbers

Question

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.

3-Ball Cascade

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.

441

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.

423

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
         │ └─┼─┘ │ │
         │   └───┼─┘
         └───────┘

50505

A 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
         └───┼───┼─┘   │
             └───┼─────┘
                 └───────>

Multiplex Juggling

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]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 [33] 3 3 [33] 3 3 [33] 3 3
          └┴──┼─┼──┴┘  │ │
              └─┼──────┘ │
                └────────┘

Here is another example, where the multiplex throw has two different heights/lengths. It could be denoted as either [34]11 or [43]11:

Beat     1    2 3 4    5 6 7    8 9
Hand     L    R L R    L R L    R L
Siteswap [43] 1 1 [43] 1 1 [43] 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 [53]15121.

Pattern Validity

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), 240 (the 2 would land at the 0 beat) or 33[24] (no ball lands at the multiplex beat, but two balls land at both of the other two beats).

The Challenge

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 s

Where 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 (0 - 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 [3] or [03] 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 42 and 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.

Examples

Input           Possible Outputs     Comments

3 _             3
                [21]
                [111]

3 4_3           423

4 4_2           4[51]2
                4[42]2
                4[321]2

3 _23_          6231
                4233
                323[31]
                2235
                223[41]
                0237
                023[43]
                [42]231
                [32]23[11]

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.

Bonuses

• 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.

Answer 1

Python, 587 - 20 = 567 chars

from itertools import *
E,J,L,R,X=enumerate,''.join,len,range,list
def f(x):
 [u,p]=str.split(x);n=int(u);a=[[[x],x][type(x)==X]for x in eval("["+J(c if c=="["else"-1,"if c=="_"else c+","for c in p)+"]")];l,w=L(a),[i for i,x in E(a)if x==[-1]]
 for j in product([[0]]+X(chain(*[combinations_with_replacement(R(1,10),i+1)for i in R(n+1)])),repeat=L(w)):
  for k,m in zip(w,j):a[k]=m
  b=[0]*l
  for k,x in E(a):
   for y in x:b[(k+y)%l]+=1
  if all(x==L(y)for x,y in zip(b,a))&((sum(map(sum,a))/l)==n):
   u=0;yield J([['['+J(map(str,x))+']',str(x[0])][L(x)==1]for x in a])
 if u:yield"!"