Skip to content

Instantly share code, notes, and snippets.

@jac18281828
Last active May 11, 2025 21:20
Show Gist options
  • Save jac18281828/734bb130db94f6b2efa6b9b67b7ab0dd to your computer and use it in GitHub Desktop.
Save jac18281828/734bb130db94f6b2efa6b9b67b7ab0dd to your computer and use it in GitHub Desktop.
Grid Hopper - Imaginary Hacker Rank from ChatGPT
from collections import deque
from typing import List, Tuple
class Board:
"""
grid hopper
starting at (1,1) must hope either down or right by the amount at grid 1,1
can you reach (size, size)?
answer yes or now
"""
def __init__(self, size: int, grid: List[Tuple[int, int]]) -> None:
"""new board hopper"""
self.size = size
self.grid = grid
self.visited = [
[False for _ in range(self.size + 1)] for _ in range(self.size + 1)
]
def find_path_bfs(self) -> bool:
"""find a path from (1, 1) to (size, size)"""
position = deque()
position.append((1, 1))
while len(position) > 0:
p = position.popleft() # bfs
if p == (self.size, self.size):
return True
# down and right
x, y = p
dg = self.grid[x - 1][y - 1]
p1, p2 = (x, y + dg), (x + dg, y)
if self.is_valid_position(p1) and not self.visited[p1[0]][p1[1]]:
self.visited[p1[0]][p1[1]] = True
position.append(p1)
if self.is_valid_position(p2) and not self.visited[p2[0]][p2[1]]:
self.visited[p2[0]][p2[1]] = True
position.append(p2)
return False
def is_valid_position(self, position: Tuple[int, int]) -> bool:
"""True if position is one the board"""
return all(0 < d and d <= self.size for d in position)
if __name__ == "__main__":
N = 3
board = [
[2, 2, 1],
[1, 1, 1],
[1, 2, 1],
]
game = Board(N, board)
if game.find_path_bfs():
print("YES")
else:
print("NO")
@jac18281828
Copy link
Author

You’re given an N\times N board. Each cell (r,c) contains an integer J_{r,c}. You place a single token at the top-left cell (1,1). On each move, you must jump either right or down by exactly the number printed in your current cell. Formally, from (r,c) you may move to
• (r,;c + J_{r,c})
• (r + J_{r,c},;c)

The game is won if you can land exactly on (N,N); you lose if you have no legal jumps left before reaching (N,N).

Write a program that reads the board and determines whether the token can reach (N,N).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment