6
\$\begingroup\$

Challenge

You just entered a room. Here's how it looks (you are the X):

|\  /|
| \/ |
| X  |
|    |
|----|

You challenge yourself to see if you can reach where you started by following the walls. You go right until you find a wall. Then, you turn clockwise until you are facing parallel to the wall.

For example, if you hit a \ while going down, you will go up-left.

After that, you continue and repeat. In this visualisation, you will leave a trail. Here is how the example above would progress:

|\  /|
| \/ |
| Sxx|
|   X|
|----|

You continue following this pattern.

|\  /|
|X\/ |
|xSxx|
|xxxx|
|----|

And yes, you reached the starting point.

|\  /|
|x\/ |
|xXxx|
|xxxx|
|----|

However, if there was a hole, you could get lost:

|\  /|
| \/ |
| SxxX
|    |
|----|

Input

As input, in any reasonable format, your program must recieve the room you are in, which consists of walls (|/-), spaces and your starting point (the X) (the starting direction is always right).

Output

As output, your program needs to output a truthy or falsy value representing if you got to your starting point.

Test cases

The format here is input -> output (reason for being false).

/-\
|X| -> true
\-/
X -> false (hits boundary)
X    |

       -> true


    \
X    |
 -
   |   -> false (trapped in endless loop)
|
  - -

Scoring

This is code-golf, so the program with the least bytes wins!

\$\endgroup\$
12
  • 1
    \$\begingroup\$ Do I understand right that the slope of the wall doesn't matter? \$\endgroup\$
    – xnor
    Aug 20, 2023 at 21:54
  • 1
    \$\begingroup\$ Can you clarify test case 3? I don't understand why he doesn't walk forever after hitting the \ and turning right. \$\endgroup\$
    – Jonah
    Aug 20, 2023 at 22:21
  • 1
    \$\begingroup\$ @Joao-3, can you clarify how the path will change when hitting a / from each direction. Ie, N becomes ?, E becomes ?, etc? And same question for \ . \$\endgroup\$
    – Jonah
    Aug 20, 2023 at 22:29
  • 1
    \$\begingroup\$ @Jonah the X bounces off the vertical line and heads down to the backslash. Then, it turns clockwise (Quote: Then you follow the next appropriate direction in a clockwise cycle) until it faces parallel to the slash (meaning it points diagonally up). Then, it treads diagonally to its original position. If you had read that quote, it would be totally clear. No need for the OP to clarify. \$\endgroup\$ Aug 21, 2023 at 13:39
  • 1
    \$\begingroup\$ @Neil You are correct -- this is a correct truthy case for recross your path without a loop \$\endgroup\$
    – Jonah
    Aug 21, 2023 at 21:57

4 Answers 4

2
\$\begingroup\$

Charcoal, 94 bytes

WS⊞υι≔⪫υ¶θPθ…θ⌕θX≔⟦⟧η≔⁰ζW∧KK∧¬№η⟦ⅈⅉζ⟧∨φ⁻XKK«⊞η⟦ⅈⅉζ⟧¿№ X⊟KD²✳ζ«M✳ζ≔⁰φ»≔&⁷⁻ζ&³⁻ζ⌕-/|⊟KD²✳ζζ»T¹¦¹

Try it online! Link is to verbose version of code. Takes input as a rectangular array of newline-terminated strings and outputs X if you reach the starting point. Explanation:

WS⊞υι

Input the map.

≔⪫υ¶θPθ…θ⌕θX

Write the map to the canvas and start at the X.

≔⟦⟧η

Prepare to detect an infinite loop.

≔⁰ζ

Start moving horizontally.

W∧KK∧¬№η⟦ⅈⅉζ⟧∨φ⁻XKK«

Repeat until the cursor moves out of bounds, repeats itself, or moves back on to the X.

⊞η⟦ⅈⅉζ⟧

Remember the current position for loop detection.

¿№ X⊟KD²✳ζ«

If the next step is out of bounds, empty or the start, then...

M✳ζ

... move to that square, and...

≔⁰φ

... remember that a step was taken.

»≔&⁷⁻ζ&³⁻ζ⌕-/|⊟KD²✳ζζ

Otherwise, rotate clockwise appropriately to the new direction.

»T¹¦¹

Output the final square.

\$\endgroup\$
3
  • \$\begingroup\$ It seems that Test Case 1 causes your solution to get stuck in an infinite loop? Try It Online! \$\endgroup\$
    – Fhuvi
    Aug 24, 2023 at 8:10
  • 1
    \$\begingroup\$ @Fhuvi Whoops, despite writing my loop detection specifically with that test case in mind, I hadn't actually tested it, and it turned out two have not one but two bugs! Should be fixed now. \$\endgroup\$
    – Neil
    Aug 24, 2023 at 8:41
  • \$\begingroup\$ Well done! Your code also passes the recross a specific space 8 times without considering it a stuck loop test case :D \$\endgroup\$
    – Fhuvi
    Aug 24, 2023 at 12:16
1
\$\begingroup\$

JavaScript (Node.js), 197 199 205 208 bytes

Gained some bytes by improving solution, but lost some by fixing a bug regarding "bonus case 2"
Gained 8 bytes after analyzing suggestions from ceilingcat !

Interesting challenge!
The input is a single string, with line breaks at the end of each row. Each row must have the same length. Returns true if we can reach the starting point X, and false otherwise.

s=>{i=(d=(p,q)=>p.indexOf(q))(s,"X");l=~d(s,`
`);try{(g=(x,y)=>{d(`X `,c=s[z=i+x-y*l]||" ")+1?i=z:0;g([0,x,-y,0,-x|-y,t=x|-y][a=d(`X -|/\\`,c)],[0,y,0,x,x|y,t][a])})(1,0)}catch(e){}return"X"==s[i]}

Try it online!


This solution uses recursive calls of the g() function and catching exceptions to end an infinite loop (particularly useful for test cases 1 and 4)

Our position is the single int i corresponding to the index in our one-dimensional string. To go up or down, we substract or add the length l of the first row. This works only if all lines have the same length, which is a prerequisite for this code.

In each call we check the cell where we are supposed to go with our current direction (expressed with the x and y parameters of the g() function. These 2 parameters can only have the values [-1, 0, 1]) :

  • if it's a space, we change our position to this cell and keep the same direction, then proceed to the next call
  • if it's an X or a line break or if our target cell is outside of the string (undefined), we change our position to the index of this cell, and change our direction to [0,0], then proceed to the next call. This allow to "stuck" our cursor on the target cell, and never move while we provoke an infinite loop to end the algorithm
  • if we encounter a wall, we don't move but we determine the resulting direction for the next call, and we proceed with this call. For this part i created this tool to help golfing it separately of the whole "mess".
  • At the end we check the final position we've reached. If it's X, it's truthy.
  • d() function is a shortened indexOf (because we use it more than 2 times)
  • in the core mechanism, i used a lot of arrays combined with the already shortened indexOf because i throught it's the shortest way of doing a switch case?
\$\endgroup\$
0
0
\$\begingroup\$

Python3, 484 bytes:

E=enumerate
def f(b):
 r,X,Y,F=[(x,y)for x,r in E(b)for y,c in E(r)if'X'==c],0,1,0
 x,y=r.pop(0)
 while 1:
  if F==4 or(r and(x,y)==r[0][:2]):return 1
  if(len(r)>1 and(x,y,X,Y)in r)or any([(j:=x+X)<0,j>=len(b),(k:=y+Y)<0,k>=len(b[0])]):return
  B,U,I=b[j][k],X,Y
  if'|'==B:X,Y=[-1,1][Y>0],0
  if'-'==B:X,Y=0,[1,-1][X>0]
  if'\\'==B:X,Y=[1,-1][max(X,Y)>0],[1,-1][max(X,Y)>0]
  if'/'==B:X,Y=[-1,1][min(X,Y)<0],[-1,1][min(X,Y)<0]
  if(X,Y)==(U,I):r+=[(x,y,U,I)];x,y=j,k;F=0
  else:F+=1

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ You can get it down to 446 bytes by removing the repat definitions in ` and /`. \$\endgroup\$
    – Joao-3
    Aug 24, 2023 at 0:29
  • \$\begingroup\$ In this case, your code should return none because X would go north-east \$\endgroup\$
    – Fhuvi
    Aug 24, 2023 at 12:50
  • 1
    \$\begingroup\$ 324 bytes \$\endgroup\$
    – STerliakov
    Aug 24, 2023 at 16:43
0
\$\begingroup\$

Java (JDK), 282 283 287 292 bytes

-2 and -1 bytes thanks to ceilingcat !
-7 bytes with some optimizations

Not bad for Java!

The input is a single string, with line breaks at the end of each row. Each row must have the same length. Returns true if we can reach the starting point X, and false otherwise.

In this solution, we take advantage of the thinness of the boundary between char and int in Java.

s->{int i=s.indexOf(88),l=~s.indexOf(10),x=1,y=0,z,a,c=0,d[],r=2;for(var t=s.toCharArray();r>1;y=d[z+5])x=(d=new int[]{x,-y,0,-x|-y,a=x|-y,y,0,x,x|y,a,r=(z=i+x-y*l)<0|z>=s.length()||(c=t[z])==10|c==40?0:t[i=c>31&c<41?z:i]++>0&c==88|t[i]>95?1:2})[z="-|/\\".indexOf(c)+1];return r>0;}

Try it online!


This solution transforms the input string into an array of characters, and our cursor "increases" the ASCII values of the characters it passes through.

An infinite path is detected if we pass strictly more than 8 times through the same cell, which would return a false. But if this cell also happens to be our starting point X, then it returns a true.

If we aren't in an infinite loop at all, reaching the X or a \n or having an index outside of the string will return a true or false accordingly.

r is the result and is kind of a ternary boolean: as long as it has the value 2, the algorithm must continue. 0 and 1 are the falsy and truthy values before normalization.

Note:

  1. I reused my "wall direction conversion system", and 1-dimensional string indexing from my JavaScript solution.
  2. For debugging purpose, we can visualize the path drawn by the cursor (via increase of the ASCII values of the characters) : to do so, move var t=s.toCharArray() with a ; before the for, and add System.out.println(t); just before the return.
\$\endgroup\$
0

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.