Pin alley duel
HardOnline Assessment
Count the winning first moves in a two-player bowling-alley pin game.
lanes is a list of strings, one per lane. In a lane string, "I" is a pin still standing and "." is a pin that has been knocked down. Two players alternate turns, and on a turn the player picks one lane and knocks down 2 or 3 pins that are adjacent in that lane and all still standing. Pins separated by a knocked-down pin are not adjacent. A player who cannot move on their turn loses.
Both players play perfectly. The first player is to move now.
Two moves are different if they differ in lane, in the position of the leftmost pin knocked down, or in how many pins (2 or 3) they knock down. Lanes with identical contents count as different lanes.
Input: lanes, the current state of each lane.
Output: the number of different moves for the first player after which the second player (now to move) is in a position that loses against perfect play. It is 0 when the first player has no winning move, which includes the case where there is no move at all.
A lane can hold up to 120 pins and there can be several lanes, so exploring the game tree by brute force will never finish. Positions in different lanes do not interact except through who gets stuck first.
Example 1
- Input:
- [["IIII",".II."]]
- Output:
- 2
- Explanation
- In the first lane (4 pins) the only moves that win are knocking down the two end pins (positions 0 and 2). Each leaves two pins in that lane and two in the other lane, a mirror position for the opponent, who must break it. Knocking pins 1 and 2 splits the lane into two single pins, which is not winning, and neither is taking three pins or emptying the second lane. Mirroring and equal splits mean 2 winning moves.
Example 2
- Input:
- [["IIIII","II"]]
- Output:
- 6
- Explanation
- Six moves leave the opponent in a lost position: in the 5-pin lane, knocking two pins at positions 0, 1, 2 or 3, and knocking three pins at positions 0 or 2. Moves in the 2-pin lane do not win. Moves are different if their lane, starting pin or number of pins differs, so the answer is 6.
Example 3
- Input:
- [["IIIII","I.IIII"]]
- Output:
- 0
- Explanation
- The lone pin at position 0 of the second lane can never be knocked down on its own, so it is dead weight; the rest of the second lane is a 4-pin row. The two rows (5 and 4 pins) are worth the same, so whatever the first player does, the second player has an answer. No first move wins: 0.
Constraints
0 <= lanes.length <= 160 <= lanes[i].length <= 120- every character is
"I"or"."