20
\$\begingroup\$

Background

In a 2d game that I play, each screen is a 2d grid of tiles with walls and walkable tiles, with the player only able to travel on walkable tiles, and being stopped by walls. When the player walks past the edge of the screen, he will travel to the adjacent screen on the map, with the player's relative screen location on the opposite side of the edge he entered in the previous screen (Think about it this way: when he walks left to another screen, it makes sense that he will be on the right of next screen).

There is a glitch that you can perform that will allow the player to glitch into a wall and, in certain cases, clip out of the map. After that, the player can travel through walls. Since the player is out of the map, if he travels past any edge of the screen, he will be warped to the other side relative to the screen, but the actual 2d grid will be the same (the game tries to determine where the player is to generate the new screen, but because he is out of bounds, it won't find a valid screen to generate, so the screen won't change). If the player travels out of a wall and into a walkable tile, he can't walk through walls until he is in a wall again. This rule also applies when the player warps to the other side of the screen after he travels through an edge; if he warps from a wall to a walkable tile, he will not be able to go through walls. On the flip side, if the player warps from a walkable tile to a wall, he will clip into the wall and be able to go through walls again.

A side effect of this glitch is that the player's actual coordinates in the game map will change based on which edge he travels through. When the player travels through the top or bottom edge, his y-coordinate will increase or decrease by 1 respectively. Similarly, when the player travels through the left or right edge, his x-coordinate will decrease or increase by 1 respectively.

Challenge

Given a configuration of walls and walkable tiles of the screen, is it possible for the player to reach a certain map coordinate? Assume that the player is always out of bounds (so the screen configuration always stays the same), and that the player starts at map coordinates (0,0). You can place the initial position of the player relative to the screen anywhere you want (you can place the player in a wall or a walkable tile). You can also optionally take in the dimensions, n by m, of the screen.

Example

Let's say the screen is 3 by 4 has the following configuration (1 represent walls, 0 represent walkable tiles):

1 0 0 1
1 0 0 1
1 0 0 1

Can the player get to the coordinates (-2,0)? Let's start by placing the player on one of the walkable tiles. I will denote the player with a letter P:

1 0 0 1
1 0 P 1
1 0 0 1

Because there are two columns of walls lining the left and right edge of the screen, the player cannot access those two edges. Therefore, he can only go through the top and bottom edge. In other words, the y-coordinate can change, but the x-coordinate stays the same. The same goes for any other walkable tile on the screen. So (-2,0) can't be reached by placing the player on a walkable tile. But what if you place the player on one of the walls; for example, one of the left ones?

1 0 0 1
P 0 0 1
1 0 0 1

First, if the player travels to the right, he will pop out of the wall, resulting in the situation described above. In this case, the player can travel through the left edge to get to (-1,0), but he will be warped to the right side of the screen:

1 0 0 1
1 0 0 P
1 0 0 1

The player is now at (-1,0), but the goal is to get to (-2,0) ! The player has to go through the left edge again, but it can't be reached. If the player walks to the left onto the walkable tile, he will pop out of the wall and won't be able to warp back into the wall again. Going through the top or bottom edge won't help, because the player will still be in the walls on the right side, which is not connected to the left side. Travelling through the right edge will warp the player back to the left walls, but at the same time, it will increase his x-coordinate by 1, bringing the player back to (0,0).

Lastly, if you place the player on one of the right walls, like so:

1 0 0 P
1 0 0 1
1 0 0 1

You will find that reaching (-2,0) is still impossible. Using a similar reasoning as above, you can determine that in order for the player to access the left edge to get closer to (-2,0), the player will first have to travel to the right. That will give him access to the left edge, but that will increase his x-coordinate by 1, so his coordinates are now (1,0). Now, travelling through the left edge as we intended initially will bring the player back to (0,0), instead of (-1,0) like we wanted. Popping out of the wall at the start by going to the left is also not an option, because it will result in the first situation described above.

So, it is impossible to reach (-2,0) with the above screen configuration.

Input

Your code should take in a rectangular 2d list (or any representation of a 2d grid) of two distinct characters or numbers, one representing walls and the other representing walkable tiles, for the screen configuration. It should also take in a coordinate pair with integer coordinates. Your code can optionally take in the dimensions n and m.

Scoring

This is , so the shortest code in byte count wins!

Test Cases

Uses 0 for walkable tiles and 1 for walls. The 2d ascii grid above each test case is just for reference.

n, m, coordinates, configuration
--> Output

False Cases
------------
1 0 0 1 
1 0 0 1 
1 0 0 1 

3, 4, (-2, 0), [[1, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 1]]
--> False

1 0 1 
0 1 0 
1 0 1 

3, 3, (0, 2), [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
--> False

1 0 1 1 1 1 1 1 1 
1 1 0 0 0 1 0 1 1 
1 1 1 0 1 0 1 0 1 
0 1 0 1 1 1 1 1 0 
1 0 1 1 1 1 1 1 1 

5, 9, (2, 2), [[1, 0, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 1, 1, 1, 1, 0], [1, 0, 1, 1, 1, 1, 1, 1, 1]]
--> False

1 0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1 0
0 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1
0 0 1 0 0 0 1 0 0 0 1 0 0

6, 13, (-200, 100), [[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1], [0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0], [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]]
--> False

True Cases
------------
0 0 0 1 
1 0 0 1 
1 0 0 1 

3, 4, (-2, -2), [[0, 0, 0, 1], [1, 0, 0, 1], [1, 0, 0, 1]]
--> True

1 1 1 1 
1 0 0 0 
1 0 0 0 
1 0 0 0

4, 4, (100, 100), [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]
--> True

0 0 1 0 0 
0 0 1 0 0 
1 1 1 1 1 
0 0 1 0 0 
0 0 1 0 0 

5, 5, (1, -1), [[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]]
--> True

0 0 1 0 0 
1 1 1 0 0 
0 0 1 1 1 
0 0 1 0 0 

4, 5, (-123, 456) [[0, 0, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 0, 1, 0, 0]]
--> True

1 0 0 0 1 0 0 0 1 0 1 1 0
0 1 1 1 0 1 1 1 0 1 0 0 1
1 1 1 1 1 0 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1 1 1 0
1 1 0 1 1 1 0 1 1 1 1 1 0
0 0 1 0 0 0 1 0 0 0 1 0 0

6, 13, (-200, 100), [[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0], [0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1], [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0], [1, 1, 0, 1, 1, 1, 0, 1, 1, ,1 ,1 ,1 ,0], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]]
--> True
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Sandbox \$\endgroup\$
    – Aiden Chow
    Feb 9, 2022 at 3:22
  • \$\begingroup\$ Could you show me why the very last case is true? Maybe provide a short worked example. \$\endgroup\$
    – ophact
    Apr 22, 2022 at 13:51
  • \$\begingroup\$ @ophact Hopefully this is understandable: example \$\endgroup\$
    – Aiden Chow
    Apr 23, 2022 at 20:13
  • \$\begingroup\$ Thanks, got it. Looks like I'll have to change my method, then. ;) \$\endgroup\$
    – ophact
    Apr 24, 2022 at 7:57
  • \$\begingroup\$ @ophact No problem and good luck! I'm glad that someone is finally attempting to solve this challenge after 2 months :P \$\endgroup\$
    – Aiden Chow
    Apr 25, 2022 at 9:21

1 Answer 1

5
\$\begingroup\$

Python3, 975 bytes:

E=enumerate
def S(b,x,y):
 q=[(x,y,0,0,b[x][y],[(x,y)])]
 while q:
  n,m,j,k,t,p=q.pop(0)
  for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
   N=n+X;M=m+Y;F=0;J=j;K=k
   if N<0 or M<0:J,K=j+(N<0),k-(M<0);yield J,K,0;N=len(b)-1 if N<0 else N;M=len(b[0])-1 if Y<0 else M;F=1
   elif N>=len(b)or M>=len(b[0]):J,K=j-(N>=len(b)),k+(M>=len(b[0]));yield J,K,0;N=0 if N>=len(b)else N;M=0 if M>=len(b[0])else M;F=1
   if(N,M)==(x,y)and(b[N][M]==0 or t):yield J,K,1,p
   elif(N,M)not in p:
    if F or b[N][M]==0 or t:q+=[(N,M,*([0,0]if b[N][M]==0 and t and F==0 else [J,K]),b[N][M],p+[(N,M)])]
def V(g,h,G,H):
 r=[]
 if g==0:r+=[G==0]
 else:r+=([(g<0)==(G<0),g%G==0]if G else[0])
 if h==0:r+=[H==0]
 else:r+=([(h<0)==(H<0),h%H==0]if H else[0])
 return all(r)
def f(t,b):
 for x,a in E(b):
  for y,_ in E(a):
   K={0:set(),1:set()}
   for z,v,F,*_ in S(b,x,y):
    if(v,z)==t and not F:return 1
    if F:K[0].add(v);K[1].add(z)
   if any(V(*t,G,H)for G in K[0] for H in K[1]):return 1
 return 0

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Wow! You actually did it. I had given up after failing to find a method \$\endgroup\$
    – ophact
    May 6, 2022 at 19:32
  • \$\begingroup\$ By the way, you can claim the good unanswered questions bounty for this \$\endgroup\$
    – ophact
    May 6, 2022 at 19:34
  • \$\begingroup\$ u can remove 10 bytes of whitespace: Try it online! \$\endgroup\$
    – naffetS
    May 6, 2022 at 20:16
  • \$\begingroup\$ Wow, really impressive! If you don't mind, could you provide a brief explanation on what your code does? I'm curious :) \$\endgroup\$
    – Aiden Chow
    May 7, 2022 at 3:25
  • \$\begingroup\$ @AidenChow Thank you. My answer is very verbose, and I think I read too deeply into your (well crafted) post. Nevertheless, the basic idea is to 1. find cycles starting from both the points in valid space and on/in a wall, and then check that the coordinates that lead to the cycle, produced from following the glitching rules, evenly divide the test case coordinates (the signs and 0 receive special attention, see function V) and 2. check that any of the produced coordinates is exactly the same as the target (no factors, not necessarily a cycle). \$\endgroup\$
    – Ajax1234
    May 7, 2022 at 4:17

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.