122 lines
2.5 KiB
Python
122 lines
2.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
|
|
input_file = sys.argv[1]
|
|
|
|
with open(input_file) as fd:
|
|
lines = [line.rstrip() for line in fd.readlines()]
|
|
|
|
falls = list()
|
|
for line in lines:
|
|
xs, ys = line.split(",")
|
|
falls.append((int(xs), int(ys)))
|
|
|
|
if input_file.startswith("input"):
|
|
cote = 71
|
|
simu = 1024
|
|
else:
|
|
cote = 7
|
|
simu = 12
|
|
|
|
vec = tuple[int, int]
|
|
directions = [
|
|
# COMMENT NOT CORRECT BUT WHO CARES
|
|
(-1, 0), # ^ North
|
|
(0, 1), # > East
|
|
(1, 0), # v South
|
|
(0, -1), # < West
|
|
]
|
|
|
|
exit = cote - 1, cote - 1
|
|
|
|
visited: set[vec] = set()
|
|
fallen: set[vec] = set()
|
|
|
|
|
|
def print_grid() -> None:
|
|
for y in range(cote):
|
|
line = ""
|
|
for x in range(cote):
|
|
char = "."
|
|
pos = x, y
|
|
if pos in fallen:
|
|
char = "#"
|
|
elif pos in visited:
|
|
char = "O"
|
|
line += char
|
|
print(line)
|
|
print()
|
|
|
|
|
|
for simu in range(len(falls)):
|
|
print("Simu", simu)
|
|
|
|
fallen = set(falls[:simu])
|
|
visited = set()
|
|
curs: set[vec] = {(0, 0)}
|
|
steps = 0
|
|
|
|
found = False
|
|
while exit not in curs:
|
|
# print("Step", steps)
|
|
if not curs:
|
|
break
|
|
visited |= curs
|
|
ncurs: set[vec] = set()
|
|
for x, y in curs:
|
|
for direction in directions:
|
|
xx, yy = x + direction[0], y + direction[1]
|
|
npos = xx, yy
|
|
if npos in visited or npos in fallen:
|
|
continue
|
|
if x not in range(cote) or y not in range(cote):
|
|
continue
|
|
ncurs.add(npos)
|
|
curs = ncurs
|
|
steps += 1
|
|
else:
|
|
found = True
|
|
|
|
if not found:
|
|
break
|
|
|
|
print_grid()
|
|
print(simu)
|
|
print(falls[simu-1])
|
|
|
|
# visited: dict[vec, int] = dict()
|
|
#
|
|
# def dig(pos: vec, steps: int) -> int | None:
|
|
# if steps > 300:
|
|
# return None
|
|
# # print(" " * steps, 55, pos)
|
|
# if pos == exit:
|
|
# return steps
|
|
# if pos in fallen:
|
|
# return None
|
|
# x, y = pos
|
|
# if x not in range(cote) or y not in range(cote):
|
|
# return None
|
|
# if pos in visited and visited[pos] < steps:
|
|
# return None
|
|
# visited[pos] = steps
|
|
#
|
|
# mini = None
|
|
# steps += 1
|
|
# for direction in directions:
|
|
# xx, yy = x + direction[0], y + direction[1]
|
|
# res = dig((xx, yy), steps)
|
|
# if res is None:
|
|
# continue
|
|
# if mini is None or res < mini:
|
|
# mini = res
|
|
# return mini
|
|
|
|
# sys.setrecursionlimit(9000)
|
|
# res = dig((0, 0), 0)
|
|
#
|
|
# print_grid()
|
|
#
|
|
# print(res)
|