10
\$\begingroup\$

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 challenge. The time complexity must be at most polynomial in the length of the grid N.

Standard 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
\$\endgroup\$
7
  • \$\begingroup\$ Are the accepted alternative I/O formats from part 1 allowed? \$\endgroup\$
    – jezza_99
    Dec 13, 2022 at 2:21
  • \$\begingroup\$ @tsh and loopy wait, I... guess I made a mistake somewhere. 64512 is correct. \$\endgroup\$
    – Bubbler
    Dec 13, 2022 at 3:33
  • 1
    \$\begingroup\$ @jezza_99 Yes. Edited in now. \$\endgroup\$
    – Bubbler
    Dec 13, 2022 at 3:39
  • 1
    \$\begingroup\$ @Jonah Roughly yes, more precisely O(N^c) where c is a constant independent of N. \$\endgroup\$
    – Bubbler
    Dec 13, 2022 at 4:41
  • 1
    \$\begingroup\$ @Arnauld Yes, the answer can be 0 here. Added some test cases. \$\endgroup\$
    – Bubbler
    Dec 13, 2022 at 23:53

6 Answers 6

7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Can you add an explanation of the approach? \$\endgroup\$
    – Jonah
    Dec 13, 2022 at 4:34
  • 2
    \$\begingroup\$ @Arnauld The slice duplicate the string which cost O(N) for each iteration, so it is O(N^2). \$\endgroup\$
    – tsh
    Dec 13, 2022 at 10:29
  • \$\begingroup\$ Ah yes, I overlooked the slice() (and the time complexity of match() as well). \$\endgroup\$
    – Arnauld
    Dec 13, 2022 at 10:44
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 105 bytes by doing a naive back-port of my JS port. Shorter methods may be possible in Python. \$\endgroup\$
    – Arnauld
    Dec 13, 2022 at 13:32
  • \$\begingroup\$ 97 bytes \$\endgroup\$
    – Arnauld
    Dec 13, 2022 at 13:59
  • 1
    \$\begingroup\$ @Arnauld Your naive Python sure beats my naive JS! \$\endgroup\$
    – loopy walt
    Dec 13, 2022 at 14:44
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 52 bytes

F²⊞υ¬ιFEθ⁺ι§ηκUMυ⁺××κ№α§ιλX³⁼§ι¬λGקυ¬λ⬤ι№⁺§/\λGμI⊟υ

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

F²⊞υ¬ι

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

FEθ⁺ι§ηκ

Loop through the columns.

UMυ⁺××κ№α§ιλX³⁼§ι¬λ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.

I⊟υ

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.)

\$\endgroup\$
1
\$\begingroup\$

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\$

\$\endgroup\$
2
  • 1
    \$\begingroup\$ If I understand the explanation correctly, the amount of operations is 38N (which is still linear in N), not N^38. If it's the latter, the test cases for N=2 should time out badly. \$\endgroup\$
    – Bubbler
    Dec 13, 2022 at 23:56
  • \$\begingroup\$ @Bubbler Ah, you're completely right, it's 38N. Hmm, I assume 38N+2 still linear? I must admit I've never been too understanding when it comes to the \$O\$-complexity of things tbh. \$\endgroup\$ Dec 14, 2022 at 12:25
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.