Spaces:
Running
Running
File size: 4,417 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
from dataclasses import dataclass
file = "input.txt"
with open(file) as f:
data = f.readlines()
grid = []
for line in data:
line = line.strip("\n")
grid.append(list(line))
M = len(grid)
N = len(grid[0])
@dataclass
class Position:
i: int
j: int
direction: str
def rotate_90(self):
directions = ["^", ">", "v", "<"]
new_idx = (directions.index(self.direction) + 1) % len(directions)
self.direction = directions[new_idx]
def is_in_bounds(self, grid):
M = len(grid)
N = len(grid[0])
return self.i in range(M) and self.j in range(N)
def get_next_pos(position: Position):
i, j, direction = position.i, position.j, position.direction
if direction == "^":
# Up
i -= 1
elif direction == "v":
# Down
i += 1
elif direction == "<":
# Left
j -= 1
elif direction == ">":
# Right
j += 1
return Position(i, j, direction)
def get_start_pos(grid):
M = len(grid)
N = len(grid[0])
for i in range(M):
for j in range(N):
if grid[i][j] == "^":
return Position(i, j, "^")
def count_Xs(grid):
total = 0
for i in range(M):
for j in range(N):
if grid[i][j] == "X":
total += 1
return total
def pprint(grid, pos = None):
grid_copy = grid.copy()
if pos:
# Print the current position
grid_copy[pos.i][pos.j] = pos.direction
grid_str = ""
for line in grid_copy:
grid_str += "".join(line)
grid_str += "\n"
print("*"*20)
print()
print(grid_str)
print()
print("*"*20)
pos = get_start_pos(grid)
grid[pos.i][pos.j] = "X" # Mark starting point as visited
in_bounds = True
while in_bounds:
# pprint(grid, pos)
next_pos = get_next_pos(pos)
if next_pos.is_in_bounds(grid):
if grid[next_pos.i][next_pos.j] in [".", "X"]:
# Valid next mode, mark as visited and move
grid[pos.i][pos.j] = "X"
pos = next_pos
else:
# Otherwise, rotate
pos.rotate_90()
else:
# Out of bounds, game over
in_bounds = False
grid[pos.i][pos.j] = "X"
pos = None
# pprint(grid, pos)
print(count_Xs(grid))
### Part 2
prev_grid = grid.copy()
def load_grid(file):
with open(file) as f:
data = f.readlines()
grid = []
for line in data:
line = line.strip("\n")
grid.append(list(line))
return grid
def check_is_infinite(grid):
pos = get_start_pos(grid)
grid[pos.i][pos.j] = "X" # Mark starting point as visited
visited = set() # Keep track of positions and orientations
in_bounds = True
infinite_loop = False
while in_bounds and not infinite_loop:
# pprint(grid, pos)
next_pos = get_next_pos(pos)
if next_pos.is_in_bounds(grid):
if grid[next_pos.i][next_pos.j] in [".", "X"]:
# Valid next mode, mark as visited and move
grid[pos.i][pos.j] = "X"
pos = next_pos
else:
# Otherwise, rotate
pos.rotate_90()
set_pos = (pos.i, pos.j, pos.direction)
if set_pos in visited:
infinite_loop = True
else:
visited.add(set_pos)
else:
# Out of bounds, game over
in_bounds = False
grid[pos.i][pos.j] = "X"
pos = None
return infinite_loop
file = "input.txt"
# Load first to get stats
# grid = load_grid(file)
M = len(grid)
N = len(grid[0])
# This is a very brute-force solution, takes long to run...
# For every point, place an obstacle, run the game, check if it gets stuck in infinite loop or not
# Surely, there must be a quicker way, but it works
total = 0
for i in range(M):
for j in range(N):
# Reset grid
grid = load_grid(file)
start_pos = get_start_pos(grid)
if start_pos.i == i and start_pos.j == j:
# Can't set obstacle on starting point, ignore
continue
if prev_grid[i][j] != "X":
# It never passed by there, so we can ignore
continue
# print(i, j)
grid[i][j] = "O" # Set Obstacle
if check_is_infinite(grid):
total += 1
print(total)
|