Colored Bead Plate

Time limit2sMemory limit1024 MB

Summary

Run up to 16 random bead drops and tilts on a 4x4 plate and report the probability that the final layout matches the target.

Level: Medium6 of 10
Topics: Probability, Simulation, Brute force
Solved: No attempts yet

Problem

A square plate has 16 bead slots laid out in a 4x4 grid. Beads come in two kinds, white and green. Six actions are available.

(W) Drop a white bead onto the middle of the plate.
(G) Drop a green bead onto the middle of the plate.
(L) Tilt the plate to the left.
(R) Tilt the plate to the right.
(T) Tilt the plate up.
(B) Tilt the plate down.

A bead dropped onto the middle settles into one of the four centre slots, the middle 2x2 block, and the current contents of those four slots decide where.

If all four are empty, the bead settles into each of them with probability $1/4$ .
If three are empty, the bead settles with probability $1$ into the slot diagonally opposite the occupied one.
If two are empty, the bead settles into each of the two with probability $1/2$ .
If one is empty, the bead settles there with probability $1$ .
If all four are occupied, the bead settles into one of the empty slots left on the plate, every one of them equally likely.

Tilting the plate makes gravity move the beads. Tilt to the left and every bead slides left until there is no empty slot to its left. The other three directions work the same way.

E is an empty slot, W is a white bead, G is a green bead. Take this plate.

EWEE
WEGW
GWGE
EEEE

Tilting it to the left gives this.

WEEE
WGWE
GWGE
EEEE

Tilting it to the right gives this.

EEEW
EWGW
EGWG
EEEE

Tilting it up gives this.

WWGW
GWGE
EEEE
EEEE

Tilting it down gives this.

EEEE
EEEE
WWGE
GWGW

You are given $N$ actions and one plate state. Start from an empty plate, run the actions in the given order, and compute the probability that the plate ends up in that state.

Input

The first line has the number of test cases $T$ . $T = 1$ .

The first line of each test case has the number of actions $N$ ( $0 \le N \le 16$ ) followed by the $N$ actions, separated by spaces. Each action is one of W, G, L, R, T, B.

The next four lines give the target plate state, four characters per line. Each character is one of E, W, G.

Output

For each test case print the probability on one line. Round it to six digits after the decimal point and print all six digits. A probability of $1$ prints as 1.000000 and a probability of $0$ prints as 0.000000.

Examples4

Example 1
Input
```
1
2 W T
EWEE
EEEE
EEEE
EEEE
```
Expected output
```
0.500000
```
Example 2
Input
```
1
3 G R B
EEEE
EEEE
EEEE
EEEG
```
Expected output
```
1.000000
```
Example 3
Input
```
1
0
EEEE
EEEE
EEEE
EEEE
```
Expected output
```
1.000000
```
Example 4
Input
```
1
1 W
EEEE
EWEE
EEEE
EEEE
```
Expected output
```
0.250000
```