Problem F
Juggling Patterns
Juggling patterns are notated by a system called siteswap. Siteswap patterns look like strings of digits, like this: ‘$3$’, ‘$441$’, ‘$345$’, etc. Each number represents the time duration of a throw (how long it is in the air). For example, a $5$ throw is higher than a $3$ throw. We consider time to advance in discrete steps (called ‘beats’), so that each ball is caught and thrown at a particular beat. For example, if we throw a $3$ at beat $2$, it lands back in a hand at beat $5$ ($=2+3$).
In the simplest form of siteswap (which we’ll use here), at most one ball is caught and at most one ball is thrown on a beat. If a ball is caught on a beat, it should be thrown on the same beat. However, it is possible to catch nothing on a beat and therefore throw nothing on that beat.
It is understood that the pattern (theoretically) repeats forever. So the pattern ‘$51$’ means “throw a $5$ on beat $1$, throw a $1$ on beat $2$, throw a $5$ on beat $3$, throw a $1$ on beat $4$, …”. It is also understood that the throws alternate hands. So the pattern ‘$441$’ means “throw a $4$ with the left hand, then throw a $4$ with the right, then a $1$ with the left, then a $4$ with the right, …”.
If a throw is an odd number (e.g. $3$), then it is a throw to the other hand (right to left or left to right). If it is even (e.g. $4$), it is a throw to the same hand (right to right or left to left).
You can discern the number of balls required for a pattern by summing the numbers in the pattern notation and dividing by the length of the pattern. So the pattern ‘$3$’ uses $3$ balls ($= 3 / 1$), and the pattern ‘$441$’ also uses $3$ balls ($=(4+4+1)/3 = 3$). The pattern ‘$7531$’ uses $4$ balls, as does ‘$345$’.
Write a program to distinguish between valid and invalid siteswap patterns. A valid siteswap pattern must use an integer number of balls. It must also allow at most one ball to be caught and thrown on any beat. Any other pattern is invalid.
An example of an invalid pattern is ‘$543$’, because if we throw a $5$ with the left hand on beat $1$, then throw a $4$ on beat $2$ with the right hand, they will both land in the right hand on beat $6$, which is not allowed (in simple siteswap). Another invalid pattern is ‘$247$’ because it does not use an integer number of balls ($=(2+4+7)/3\approx 4.3\ldots $).
Input
Input will be a list of up to $100$ siteswap patterns, one per line, ending at end of file. All patterns be a string of at most $1\, 000$ digits (throws), and all throws will be between $0$ and $9$ (inclusive). A throw of $0$ is valid, and it means that no ball is thrown on that beat.
Output
For each siteswap pattern, print the pattern, followed by a colon, followed by one of the following messages as appropriate:
-
‘valid with X balls’, where X is the number of balls in the pattern,
-
‘invalid # of balls’, if the number of balls used is not an integer,
-
‘invalid pattern’, if the pattern has an integer number of balls but requires more than one ball to be caught or thrown at some time.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 33333 345 542 543 55550 |
3: valid with 3 balls 33333: valid with 3 balls 345: valid with 4 balls 542: invalid # of balls 543: invalid pattern 55550: valid with 4 balls |
