CGAC2022 Day 12: Santa's gift and the laser lock

Question

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

---

There's a good news and a bad news.

Good news: you got a Christmas present from Santa. (Already?! Christmas is two weeks away!)

Bad news: the present is locked with a laser lock. And a note next to it says:

Only the ones who can properly open the lock deserve the present inside. If you force it or fail to open in 24 hours, the present will turn into a piece of coal.

You carefully examine the laser lock. It has a laser, a sensor, and a grid of square cells. Some cells already have a piece of mirror, and some of the empty ones are colored red; the others are green.

          +-+-+-+-+-+-+-+
laser --> |G|G|R|\|G|G|G|
          +-+-+-+-+-+-+-+
          |\|R|/|G|R|G|\| --> sensor
          +-+-+-+-+-+-+-+

You immediately think, "Aha, so I'm supposed to place some mirrors on some of the green cells so the laser goes to the sensor."

So one possible solution to the above would be:

          +-+-+-+-+-+-+-+
laser --> |.|.|R|\|.|/|\|
          +-+-+-+-+-+-+-+
          |\|R|/|\|R|/|\| --> sensor
          +-+-+-+-+-+-+-+

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 a possible solution.

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

The output must be in the same format as the input, with each G replaced with . (nothing) or one of \/ (a mirror). Replacing all Rs with . in addition to the above is allowed.

..R\./\  or  ...\./\
\R/\R/\      \./\./\

You may assume that the solution always exists. If there are multiple solutions, you may output any one of them.

No other alternative I/O formats are allowed.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

G
G
->
\
\

GG
RG
->
.\
R\

G\/R/\/GG
GRGGGRGR\
->
\\/R/\/.\
\R...R/R\

G\
G\
->
.\ or .\ or .\
.\    /\    \\

Answer 1

JavaScript (Node.js), 128 bytes

f=a=>[...'./\\'].some(c=>(b=a.replace(/g/,c))<a?f(b):b.split`
`.map(v=>p=v==['\\\\','//'][p]?1-p:p/ /r|\./.test(v[p]),p=0)|p)&&b

Try it online!

\$O\left(3^n\right)\$ solution. Input a multiple line string as transposed matrix with lowercase letters.

Is this somehow "if you force it"?

f=(
  a // the input grid
)=>
[...'./\\'].some(c=> // for each possible replacement of letter "g"
  (b=a.replace(/g/,c)) // replace the first occurrence of "g"
    <a? // if any "g" exists (replaced successfully)
        // or the string is out of "g" otherwise
      f(b): // recursively try next "g"s
      b.split`\n`.map(v=> // for each column of a possible replacement
        p=v==['\\\\','//'][p]?1-p: // If the pattern is '//' or '\\' it reflect laser to another row
        p/ /r|\./.test(v[p]) // if the cell is 'r' or '.', it keeps laser on the same row (p/1==p); otherwise, set to invalid values (NaN or Infity)
      ,p=0) // the laser starts from first row
      |p)&&b // if the laser finally output from second row, "b" is a solution we found

---

JavaScript (Node.js), 142 bytes

f=([x,y,...a],p=[],q,h=s=>q&&!/(.).(?!\1)[^RG]|[^.].R/.test(s+x+y)&&q+s,o=h(x+'.')||h`..`,O=h`//`)=>x?f(a,h('.'+y,q=p)||h`..`||O,o||h`\\\\`):q

Try it online!

\$O(n)\$ solution. Input transposed flatten string with uppercase letters.

f=(
  [x,y, // for each column of the grid, "x" and "y" are two cells on this column
  ...a], // the remaining grid
  p=[], // A solution where laser on the first row, or falsy if impossible
  q, // A solution where laser on the second row, or falsy if impossible
  h=s=> // "s" is a possible replacement of current column
    // if the laser can running on row "p" ("p" is reassigned later)
    // and the replacement of current column is valid
    // then we got a solution
    p&&!/(.).(?!\1)[^RG]|[^.].R/.test(s+x+y)&&p+s,
    o=h('\\\\')
)=>x? // if any more columns here
  f(a,
    h(D='..')||h('.'+y)||h('//',p=q), // all possible patterns where laser on first row
    o||h(D,p=q)||h(x+'.') // all possible patterns where laser on second row
  ):q

---

Only valid patterns are:

Laser -> \
         \ -> Laser

Laser -> . -> Laser
         ?

         / -> Laser
Laser -> /

         ?
Laser -> . -> Laser

So we only need to verify all these patterns and treat all other patterns as invalid.

Answer 2

Charcoal, 93 74 bytes

⊞υ\ＦＥθ⁺ι§ηκ≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ⪪Φ⊟Φυ⌕\ικ²‖↙

Attempt This Online! Link is to verbose version of code. Explanation: Inspired by the alternate input format, this sticks to the original input format and pays the 8 byte penalty for transposing the input and output.

⊞υ\

Start with a single state of the beam in the top row. The first character of the state is \ if the beam is in the top and / if the beam is in the bottom row, while the remaining characters are the columns processed so far in a flattened representation.

ＦＥθ⁺ι§ηκ

Transpose the input and loop over each column. (Note: row/column here refer to the original input, not the transposed version.)

≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ

• ⭆κ⎇νμ⁻\/μ - Flips the row of the state.
• ⪫⪪ιG¦. - Replaces Gs in the current column with .s
• №α§ι⁼§κ⁰/ - Checks whether the current cell is empty.
• ⬤ι№⁺G§κ⁰ξ - Checks whether both the rows can contain the correct mirror.

Loop over the current states, collecting states where the beam switches or doesn't switch appropriately depending on whether the column can have the correct mirrors or there is an empty space in the current cell.

⪪Φ⊟Φυ⌕\ικ²

Output any state which has the beam in the bottom row.

‖↙

Transpose the output.

66 bytes using the new transposed input format:

⊞υ\ＷＳ≔ΣＥυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ιG¦.⟧⎇ν№α§ι⁼§κ⁰/⬤ι№⁺G§κ⁰ξυ⪪Φ⊟Φυ⌕\ικ²

Attempt This Online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation: As above but simply uses ＷＳ to iterate over the input and doesn't need to transpose at the end either of course.

Answer 3

JavaScript (ES6), 147 bytes

I/O format: matrix of ASCII codes.

I would probably have golfed this differently if I had noticed the rule about removing all G's earlier.

m=>(g=(x,y=0,d=1,_,r=m[y],c=r[x])=>c?c%9&2?c%2^y^d&&g(x+!d,y^d,!d):d&&g(x+1,y)||c==71&&g(x,y,d,r[x]=y^d?92:47):y&&m.map(r=>r.map(c=>c-71?c:46)))(0)

Try it online!

Answer 4

Python, 309 281 243 bytes

lambda a:max(map(lambda t,b=0:all(i%2^1and(s:=j)or s==j=="\\/"[b]and~(b:=b^1)or(s,j)[b]in".R"for i,j in E(t))and t*b or"",["".join(sum(zip(a.split("G"),[*g,""]),()))for g in product(*["\\/."]*a.count("G"))]))
from itertools import*
E=enumerate

Attempt This Online!

-a massive 38 bytes thanks to @tsh.

Saved 20 bytes by switching to a flattened transposed string for input and output. Brute force solution. Explanation:

["".join(sum(zip(a.split("G"),[*g,""]),()))for g in product(*["\\/."]*a.count("G"))]

Generates all possible substitutions for "G" using

product(*["\\/."]*a.count("G"))

The cartesian product of \/. repeated for every occurence of "G", where each combination is

"".join(sum(zip(a.split("G"),[*g,""]),()))

Manually mapped to the input string to replace the respective "G"'s.

lambda t,b=0:all([i%2^1and(s:=j)or s==j=="\\/"[b]and~(b:=b^1)or(s,j)[b]in".R"for i,j in E(t)])and t*b or""

The testing function is then mapped over the generated combinations, which checks for every column that either:

• s==j=="\\/"[b] the correct mirror for the given laser row b is in that column. ~(b:=b^1) is used to switch the laser row
• (s,j)[b]in".R" the laser row in the column is R or .
• or "" outputs an empty list if above two tests fail
• t*b outputs the combination tested if the laser is on the bottom row for the last column, otherwise an empty list

i%2^1and(s:=j)or is used to generate the column pairs from the transposed flattened list by storing a value on every even iteration and testing on every odd iteration

Then max() is used to return a correct solution from the test results of all combinations

Answer 5

Pip, 92 75 71 bytes

@FI{WG N({UQaQ"\/"@i&Ui|a@iN".R"}M<>a)&aX%i}M J(a^'GWV_)MCP:"\/."Ma@*'G

Try It Online!

-17 21 bytes thanks to @DLosc

Port of my Python answer. I'm sure there are some further golfs that can be done. I could save a byte by outputting the list of all possible solutions as in @KevinCruijssen's answer. Explanation:

J(a^'GWV_)MCP:"\/."Ma@*'G

Generates all possible combinations using the cartesian product of "\/." by the number of "G" in the input

WG N({UQaQ"\/"@i&Ui|a@iN".R"}M<>a)&aX%i

Is the testing function that is mapped over all combinations. WG is required to reset the global variable i, which is used to store the laser row.

@FI

Finally filters out all falsy values from the output list, giving only the list of solutions. @ outputs the first in the list.

Answer 6

Python3, 350 bytes:

def f(b):
 q=[(0,0,[*map(list,b.replace('R','.').replace('G','.').split('\n'))])]
 while q:
  x,y,B=q.pop(0)
  if(x,y)==(1,len(B[0])):return B
  try:
   B=eval(str(B))
   if(V:=B[x][y])in'\\/':B[(X:=x+[-1,1][V=='\\'])][y]=V;q+=[(X,y+1,B)]
   else:j=eval(str(B));j[x][y]=(K:='\\/'[x]);j[(X:=x+[-1,1][K=='\\'])][y]=K;q+=[(x,y+1,B),(X,y+1,j)]
  except:1

Try it online!

Answer 7

05AB1E, 61 50 bytes

…\/.I'G¢ãε'GsS.;}ʒ0U¶¡ε„\\º2äXèQiX_Uë„R.yXèå}Ā}PX*

Takes the input as a transposed multiline string. Outputs a list of all possible results (R remains R).

Try it online or verify all test cases.

Explanation:

Partially inspired by @tsh's JavaScript's answer, so also checks pairs as:

0 → \
    \ → 1

    / → 0
1 → /

0 → . → 0
    *

0 → R → 0
    *

    *
1 → . → 1

    *
1 → R → 1

anything else: invalid

…\/.              # Push string "\/."
    I'G¢         '# Count how many "G" are in the input-string
        ã         # Get the cartesian product of "\/." with this count
         ε        # Map over each string:
              .;  #  Replace in the (implicit) input-string every first occurrence of
          'G     '#  character "G", one by one with
            sS    #  the characters in the current string
         }        # Close the map
ʒ                 # Filter this list of potential results with:
 0U               #  (Re)set `X` to 0
 ¶¡               #  Split the multiline string on newlines
   ε              #  Map over each pair:
    „\\           #   Push string "\\"
       º          #   Mirror it to "\\//"
        2ä        #   Split it into two parts: ["\\","//"]
          Xè      #   Get the 0-based `X`'th string in this pair
    Qi            #   If it's equal to the current pair we're mapping over:
      X_U         #    Invert `X` (0 becomes 1 and vice versa)
                  #    (and implicitly map to the implicit input-string)
     ë            #   Else:
         yXè      #    Get the 0-based `X`'th character from the current pair
      „R.   å     #    Check if this character is in string "R."
     }Ā           #   After the if-else: Python-style trutify the value
                  #   (0 remains 0; everything else becomes 1)
   }P             #  After the map: check if all are truthy by taking the product
     X*           #  Multiply it by `X` to check whether we've ended at the bottom row
                  # (after which the filtered results are output implicitly)