Problem D: Dice from pennies

Colin likes to play role playing games. These games usually involve dice with varying numbers of sides; a 20 sided die is known as a D20 (marked 1-20 inclusive), a regular six sided die a D6, and so on. Unfortunately, Colin has forgotten his bag of dice, and has only a jar full of pennies. Help him make his savings throw! For each required roll, Colin will tip out the pennies and read off whether they are heads or tails. This will serve as the random input to a function that returns a number fitting the range of the die. For example, to simulate a regular die, the pairing is as follows:

 
HHH = 1
HHT = 2
HTH = 3
HTT = 4
THH = 5
THT = 6
and analogously for other dice using the minimum number of pennies to encode all the needed die numbers. See sample input for examples. Note that some outputs from the coins will not match to a die number when read from the first position. In this case, use the next coins in the list to return a result. For example, in case of 6 sided dice, TTTHHH maps to the value 1, not 5 as someone may expect.

The input will consist of multiple sets of input, each set consisting of a number of dice to be rolled and a type (e.g., 2D6 means roll 2 regular 6 sided dice), followed by the status of the pennies in the next line with no spaces. The last set will start with 0D0 and this set should not be processed.

Output will be a single number for each set, consisting of the sum of the simulated dice. If there are insufficient coins to determine an outcome, return -1. There will be at most 1000 coins.

Sample input

1D6
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
1D6
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
1D6
HTTHHHHTHTHTTTTHTHTHHHTHTHTHTHTHTTHTHTTTTTTHTHHTT
2D2
THTHTHHHHTHHHHTTTTTHTHTHHTHTHTTHTHTHHTHTHTHTHHHHH
1D20
THHHTHHHHTTHTTTTTTHHHHTHTHHHHHHHHHTTTTHTHHHHHHTTT
0D0

Output for sample input

1
-1
4
3
18

Chris Procter

Note: The above is the best description that Chris has come up with. Trying to sort out what he meant is part of the challenge.