CGAC2022 Day 13: Santa's gift and the laser lock, Part 2

Question

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.

Task

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

GGR\GGG
\R/GRG\

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.

Test cases

G
G
-> 1

GG
GG
-> 6

G\GGGGGRGGGGG
GGG/G\GG/GGGR
-> 64512

RR
RR
-> 0

R\
\R
-> 0

/GGG
GGGG
-> 0

Answer 1

JavaScript (Node.js), 117 bytes

f=(a,p=1,q=0,h=r=>!!a.match('^'+r))=>a?f(a.slice(2),h`\\w`*3**h`.g`*p+h`[g/]{2}`*q,h`.\\w`*3**h`g`*q+h`[S-g]{2}`*p):q

Try it online!

Input transposed, flatten, lowercase grid.

f=(
  a,  // the input grid, transposed flatten lowercase
  p=1,q=0, // number of solutions where laser reach the first / second row
  h=r=>!!a.match('^'+r) // test if input "a" matches given regex
                        // or in the other word, test if the first column match given pattern
)=>a? // whenever there are remaining columns
  f(a.slice(2), // recursively call function with first column removed
    h`\\w`*3**h`.g`*p+ // pattern "g?", "r?" (where "?" is whatever) allow laser from row 1 to row 1
    h`[g/]{2}`*q, // pattern "//" allow laser from row 2 to row 1
    h`.\\w`*3**h`g`*q+ // pattern "?g", "?r" allow laser from row 2 to row 2
    h`[S-g]{2}`*p // pattern "\\" allow laser from row 1 to row 2
                  // as /[g\\]/ need to be written as "[g\\\\\\\\]"
                  // we use "[S-g]" to avoid leaning toothpick syndrome 
):q

For any grid with \$2\times N\$ cells, the algorithm took \$O(N^2)\$ time to compute the result.

Answer 2

Python, 97 bytes (@Arnauld)

def f(a,t=1,b=0):
 for T,B in a:t,b=B*3%5*t*(T&8<1)+T*B%2*b,T*3%5*b*(B&8<1)+t*(T*B%7<2)
 return b

Attempt This Online!

Python, 127 bytes

def f(a,t=1,b=0):
 for T,B in a:t,b=t*(T>"a")*3**(B=='g')+b*({T,B}<={*"/g"}),b*(B>"a")*3**(T=="g")+t*({T,B}<={*"\g"})
 return b

Attempt This Online!

Using small letters saves a few bytes.

Python, 134 bytes

def f(a,t=1,b=0):
 for T,B in a:t,b=t*(T in"RG")*3**(B=='G')+b*({T,B}<={*"/G"}),b*(B in"RG")*3**(T=="G")+t*({T,B}<={*"\\G"})
 return b

Attempt This Online!

Takes the transpose, i.e. a list of 2-strings.

Note: this is linear in the grid length.

How?

The key insight here would be that there are no nasty interdependencies. Any partial path that leaves column n in the top row, say, can be combined with any partial path that enters column n+1 in the top row. This allows for many counting methods.

A particularly simple one - used here - is to advance column by column keeping track of the numbers of paths that leave the current column at the top or the bottom.

Answer 3

JavaScript (ES6), 86 bytes

This is a port of loopy walt's answer with an extra layer of ASCII code trickery.

Expects a transposed matrix of ASCII codes, using upper case.

m=>m.map(([T,B])=>[t,b]=[B*3%5*t*!(T&8)+T*B%2*b,T*3%5*b*!(B&8)+t*(T*B%7<2)],t=1,b=0)|b

Try it online!

Expressions

• X * 3 % 5 evaluates to \$3\$ if \$X=71\$ (G) or \$1\$ otherwise
• !(X & 8) evaluates to \$1\$ (true) if \$X\in\{71,82\}\$ (G or R) or \$0\$ (false) otherwise
• T * B % 2 evaluates to \$1\$ if \$T,B\in\{47,71\}\$ (/ or G) or \$0\$ otherwise
• T * B % 7 < 2 evaluates to \$1\$ (true) if \$T,B\in\{71,92\}\$ (G or \) or \$0\$ (false) otherwise

Answer 4

Charcoal, 52 bytes

Ｆ²⊞υ¬ιＦＥθ⁺ι§ηκＵＭυ⁺××κ№α§ιλＸ³⁼§ι¬λGקυ¬λ⬤ι№⁺§/\λGμＩ⊟υ

Try it online! Link is to verbose version of code. Explanation: Port of @loopywalt's Python answer.

Ｆ²⊞υ¬ι

Start with one possible beam on the top row and none on the bottom row.

ＦＥθ⁺ι§ηκ

Loop through the columns.

ＵＭυ⁺××κ№α§ιλＸ³⁼§ι¬λGקυ¬λ⬤ι№⁺§/\λGμ

Update each row, keeping the count for R and G with no G in the other row or trebling it with G in the other row, plus the count of the other row if the column is or can be changed to // or \\ as appropriate.

Ｉ⊟υ

Output the final count for the bottom row.

(As with my answer to the linked question, six bytes could be saved by taking the input in transposed format.)

Answer 5

05AB1E, 54 bytes

1¾‚Iv©y`'GQ3smsa*y„/G2ãQà‚*y„\G2ãQày`as'GQ3sm*‚®*R‚O}θ

Port of @tsh's JavaScript answer, so make sure to upvote him/her as well!
Unlike his/her answer, I think my answer is \$O(38N)\$ for a grid of dimensions \$2\times N\$.

Input is transposed and as a list of 2-char strings.

Try it online or verify all test cases.

Explanation:

1¾‚                   # † Push 1 and 0, and pair them together
   Iv                 # Loop `y` over the input-list:
     ©                #  Store the current pair in variable `®` (without popping)
     y                #  Push the current string-pair `y`
      `               #  Pop and push them separated to the stack
       'GQ           '#  Check if the second/top is equal to "G"
          3sm         #  Take 3 to the power this y[1]=="G" check
       s              #  Swap so the first character is at the top
        a             #  Check whether it's a letter ("R" or "G"): isLetter(y[0])
             *        #  Multiply the checks together: (3**(y[1]=="G"))*isLetter(y[0])
     y                #  Push the current pair `y` again
      „/G             #  Push string "/G"
         2ã           #  Cartesian power of 2: ["//","/G","G/","GG"]
           Q          #  Check for each whether it's equal to `y`
            à         #  Check if any is truthy by taking the maximum
              ‚       #  Pair the two together
               *      #  Multiply the values in the two pairs together
     y„\G2ãQà         #  Same as above for ["\\","\G","G\","GG"]
     y`as'GQ3sm*     '#  Same as above for isLetter(y[1])*(3**(y[0]=="G"))
                ‚     #  Pair the two together
                 ®*   #  Multiply the values with pair `®` as well
                   R  #  Then revert it
     ‚                #  Pair these two pairs together
      O               #  Sum each inner pair
    }θ                # After the loop: leave last element of the resulting pair
                      # (which is output implicitly as result)

† This could have been 0L instead for -1 byte, but it would change the complexity to \$O(38N+2)\$.

Why I think it's \$O(38N)\$:

Looping with Iv is the \$N\$ complexity.

Within its body, the following add to the complexity:

• ` (2x): pop and dumping both characters to the stack: \$2\times2=4\$
• „/G2ã and „\G2ã: cartesian power of 2 on a 2-char string: \$2\times2^2=8\$
• Q (2x): equals check on all four values in a quadruplet list: \$2\times4=8\$
• à (2x): maximum on a quadruplet list: \$2\times4=8\$
• ‚* and ‚®*: multiply the values in two pairs together: \$2\times2=4\$
• R: reversing a pair: \$2\$
• ‚O: summing the inner pairs of a pair of pairs: \$2^2=4\$

All summed together: \$4+8+8+8+4+2+4=38\$

Answer 6

PARI/GP, 84 bytes

a->l=[1,0];[l*=[if(u%15%2,v*3%5),u*v%7<2;u*v%2,if(v%15%2,u*3%5)]|t<-a,[u,v]=t~];l[2]

Attempt This Online!

Takes a matrix of ASCII codes.

A port of @Arnauld's JavaScript answer. Uses X % 15 % 2 instead of !(X & 8) because PARI/GP doesn't have a bitand operator.