Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
You successfully route the laser into the sensor, but nothing happens.
"What?" Frustrated, you flip the note from Santa. There's some more text:
Calculate the number of ways to complete the laser puzzle, and enter it into the number pad on the back side of the package.
Wow, now it's a hard problem. The time is ticking and it's got so many G's, so a simple brute force (
O(3^G)) won't cut it.
For the example problem below,
+-+-+-+-+-+-+-+ laser --> |G|G|R|\|G|G|G| +-+-+-+-+-+-+-+ |\|R|/|G|R|G|\| --> sensor +-+-+-+-+-+-+-+
the answer is 3. The G at the 5th cell on the top row can be anything (
./\); the others are fixed.
In this task, the positions of the laser and the sensor are fixed, and the height of the grid is always 2. Given the state of the lock as a 2-by-N grid, output the number of its solutions.
The input grid is given as a 2D string like
but the following variations (and combinations thereof) are allowed:
- an array of rows / a matrix / a flattened string or array
- charcodes instead of characters
- transposed grid (in other words, columns instead of rows)
- lowercase instead of uppercase
No other alternative I/O formats are allowed.
This is a restricted-complexity challenge. The time complexity must be at most polynomial in the length of the grid N.
Standard code-golf rules apply. The shortest code in bytes wins.
G G -> 1 GG GG -> 6 G\GGGGGRGGGGG GGG/G\GG/GGGR -> 64512 RR RR -> 0 R\ \R -> 0 /GGG GGGG -> 0