15
\$\begingroup\$

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 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 .\
.\    /\    \\
\$\endgroup\$
4
  • \$\begingroup\$ For the given example, is a single string "g\grr/\ggrggg\" (column first) allowed? \$\endgroup\$
    – tsh
    Dec 12, 2022 at 2:19
  • \$\begingroup\$ @tsh I guess I'll allow transposed grid (as it doesn't break the mirror layout) and a flattened representation. \$\endgroup\$
    – Bubbler
    Dec 12, 2022 at 3:05
  • 1
    \$\begingroup\$ Suggested testcase: \$\begin{matrix}\text{G} & \text{\\}\\\text{G} & \text{\\}\end{matrix}\$ . I got a wrong answer on this one \$\endgroup\$
    – tsh
    Dec 12, 2022 at 10:04
  • \$\begingroup\$ "the present will turn into a piece of coal." Let's assume the present IS a piece of coal \$\endgroup\$
    – l4m2
    Dec 15, 2022 at 14:41

7 Answers 7

6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Not a very common pattern while you need an extra space in p/ /r|\./ to avoid interpreter ignore a comment starts with //. \$\endgroup\$
    – tsh
    Dec 12, 2022 at 6:39
  • \$\begingroup\$ ` /r|\./.test(v[p])` => (v[p]>f|1+v[p]) \$\endgroup\$
    – l4m2
    Dec 15, 2022 at 14:53
  • \$\begingroup\$ 120 \$\endgroup\$
    – l4m2
    Dec 15, 2022 at 15:01
4
\$\begingroup\$

Charcoal, 93 74 bytes

⊞υ\FEθ⁺ι§ηκ≔ΣEυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ι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.

FEθ⁺ι§ηκ

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

≔ΣEυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ι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:

⊞υ\WS≔ΣEυΦ⟦⁺⭆κ⎇νμ⁻\/μײ§κ⁰⁺κ⪫⪪ι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 WS to iterate over the input and doesn't need to transpose at the end either of course.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ ["".join(sum(zip(a.split("G"),[*g,""]),()))for g in product(*["\\/."]*a.count("G"))] \$\endgroup\$
    – tsh
    Dec 13, 2022 at 2:15
  • \$\begingroup\$ @tsh I knew there was a better way to generate the modified strings, thanks! \$\endgroup\$
    – jezza_99
    Dec 13, 2022 at 2:17
2
+250
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Wow, never thought I'd see WG actually used in a code-golf answer! Here's 75 bytes. Ping me in chat if you want any explanations. \$\endgroup\$
    – DLosc
    Dec 17, 2022 at 0:57
  • \$\begingroup\$ @DLosc haha well it did the trick. Some good golfs in there, I think I get them all. The <>a operator is super useful, I can see myself using that a lot \$\endgroup\$
    – jezza_99
    Dec 17, 2022 at 4:23
  • 1
    \$\begingroup\$ I just realized that since you're mostly using i for indexing into length-2 strings, you can just increment it instead of swapping it with o: 71 bytes \$\endgroup\$
    – DLosc
    Dec 18, 2022 at 5:57
  • \$\begingroup\$ @DLosc good insight, I'm too used to python lists \$\endgroup\$
    – jezza_99
    Dec 19, 2022 at 3:50
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 350 bytes \$\endgroup\$
    – The Thonnu
    Dec 12, 2022 at 17:02
  • \$\begingroup\$ @TheThonnu Thanks, updated \$\endgroup\$
    – Ajax1234
    Dec 12, 2022 at 17:11
1
\$\begingroup\$

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

Your Answer

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

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