Last active
May 11, 2025 21:20
-
-
Save jac18281828/734bb130db94f6b2efa6b9b67b7ab0dd to your computer and use it in GitHub Desktop.
Grid Hopper - Imaginary Hacker Rank from ChatGPT
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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).