Advent of Code 2022 day 17
Part 1 is now redundant because Part 2 also covers its case. Part 1 also takes an incredibly long time. Part 2 uses two tricks to speed up the calculation:
it only looks at the top part of the grid which is still relevant;
once a loop has been found, it works out how often the loop would occur and ‘skips’ doing them.
Part 1
def create_shape(data: str) -> dict:
return {
"height": data.count("\n")+1,
"width": len(data.split("\n")[0]),
"shape": data.replace("#", "@")
}
def grid_top(grid: str) -> int:
return ((len(grid.rstrip("."))-1) // grid_width) + 1
def display_grid(grid: str) -> None:
print(
"\n".join(
"|"+grid[i*grid_width:(i+1)*grid_width]+"|"
for i in reversed(range(grid_top(grid)+1))
) +
"\n" +
"+" + "-"*grid_width + "+"
)
def initialise_shape(shape: dict, grid: str) -> str:
end_height = init_x + grid_top(grid)
start_height = shape["height"] + end_height
return (
grid[:end_height*grid_width] +
"".join(
"."*init_y +
shape["shape"].split("\n")[i] +
"."*(grid_width - init_y - shape["width"])
for i in reversed(range(shape["height"]))
) +
grid[start_height*grid_width:]
)
def can_move_left(grid: str) -> bool:
return all(
i % grid_width != 0 and grid[i-1] != "#"
for i, x in enumerate(grid) if x == "@"
)
def can_move_right(grid: str) -> bool:
return all(
i % grid_width != grid_width-1 and grid[i+1] != "#"
for i, x in enumerate(grid) if x == "@"
)
def can_move_down(grid: str) -> bool:
return all(
i - grid_width > 0 and grid[i-grid_width] != "#"
for i, x in enumerate(grid) if x == "@"
)
def move_left(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i-1] + "@" + new_grid[i:]
)
return new_grid
def move_right(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i+1] + "@" + new_grid[i+2:]
)
return new_grid
def move_down(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i-grid_width] + "@" + new_grid[i-grid_width+1:]
)
return new_grid
def move_left_right(grid: str) -> str:
next_move = move()
if next_move == "<" and can_move_left(grid):
grid = move_left(grid)
elif next_move == ">" and can_move_right(grid):
grid = move_right(grid)
return grid
def turn_stationary(grid: str) -> str:
return grid.replace("@", "#")
shapes_raw = """####
.#.
###
.#.
..#
..#
###
#
#
#
#
##
##"""
shapes = [create_shape(x) for x in shapes_raw.split("\n\n")]
number_of_rocks = 2022
# number_of_rocks = 20
grid_height = number_of_rocks*4
grid_width = 7
init_x = 3
init_y = 2
grid = "."*grid_width*grid_height
with open("17.txt") as f:
jet_stream = f.read().strip()
print(jet_stream)
move_i = -1
def move() -> str:
global move_i
move_i += 1
return jet_stream[move_i % len(jet_stream)]
for i in range(number_of_rocks):
print(i)
shape = shapes[i % len(shapes)]
grid = initialise_shape(shape, grid)
# display_grid(grid)
grid = move_left_right(grid)
while can_move_down(grid):
grid = move_down(grid)
grid = move_left_right(grid)
grid = turn_stationary(grid)
print(grid_top(grid))
Part 2
def create_shape(data: str) -> dict:
return {
"height": data.count("\n")+1,
"width": len(data.split("\n")[0]),
"shape": data.replace("#", "@")
}
def grid_top(grid: str) -> int:
return ((len(grid.rstrip("."))-1) // grid_width) + 1
def display_grid(grid: str) -> None:
print(
"\n".join(
"|"+grid[i*grid_width:(i+1)*grid_width]+"|"
for i in reversed(range(grid_top(grid)+1))
) +
"\n" +
"+" + "-"*grid_width + "+"
)
def cut_grid(grid: str, grid_height: int) -> (str, int):
at = len(grid)
for i in range(grid_width):
row = 0
for j in range(grid_top(grid)):
if grid[j*grid_width+i] == "#":
row = j
if row < at:
at = row
if at == len(grid):
return grid+grid_addon, grid_height
return (grid[at*grid_width:]+grid_addon, grid_height+at)
def trim_grid(grid: str) -> str:
return grid[:(grid_top(grid)+1)*grid_width]
def initialise_shape(shape: dict, grid: str) -> str:
end_height = init_x + grid_top(grid)
start_height = shape["height"] + end_height
return (
grid[:end_height*grid_width] +
"".join(
"."*init_y +
shape["shape"].split("\n")[i] +
"."*(grid_width - init_y - shape["width"])
for i in reversed(range(shape["height"]))
) +
grid[start_height*grid_width:]
)
def can_move_left(grid: str) -> bool:
return all(
i % grid_width != 0 and grid[i-1] != "#"
for i, x in enumerate(grid) if x == "@"
)
def can_move_right(grid: str) -> bool:
return all(
i % grid_width != grid_width-1 and grid[i+1] != "#"
for i, x in enumerate(grid) if x == "@"
)
def can_move_down(grid: str) -> bool:
return all(
i - grid_width > 0 and grid[i-grid_width] != "#"
for i, x in enumerate(grid) if x == "@"
)
def move_left(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i-1] + "@" + new_grid[i:]
)
return new_grid
def move_right(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i+1] + "@" + new_grid[i+2:]
)
return new_grid
def move_down(grid: str) -> str:
new_grid = grid.replace("@", ".")
for i, x in enumerate(grid):
if x == "@":
new_grid = (
new_grid[:i-grid_width] + "@" + new_grid[i-grid_width+1:]
)
return new_grid
def move_left_right(grid: str) -> str:
def move() -> str:
global move_i
move_i += 1
return jet_stream[move_i % len(jet_stream)]
next_move = move()
if next_move == "<" and can_move_left(grid):
grid = move_left(grid)
elif next_move == ">" and can_move_right(grid):
grid = move_right(grid)
return grid
def turn_stationary(grid: str) -> str:
return grid.replace("@", "#")
shapes_raw = """####
.#.
###
.#.
..#
..#
###
#
#
#
#
##
##"""
shapes = [create_shape(x) for x in shapes_raw.split("\n\n")]
number_of_rocks = 1000000000000
# number_of_rocks = 2022
# number_of_rocks = 100
grid_height = 0
grid_width = 7
init_x = 3
init_y = 2
with open("17.txt") as f:
# with open("17_test.txt") as f:
jet_stream = f.read().strip()
print(jet_stream)
move_i = -1
grid_addon = "."*grid_width*(init_x+1+max(shape["height"] for shape in shapes))
grid = grid_addon
grids_so_far = set()
def find_previous_turn(grids_so_far: set, grid: str, move_i: int):
for g, m, old_turn, old_grid_height in grids_so_far:
if g == grid and m == move_i:
return g, m, old_turn, old_grid_height
return None, None, None, None
# # Manually
# for i in range(number_of_rocks):
# shape = shapes[i % len(shapes)]
# grid, grid_height = cut_grid(grid, grid_height)
# grid = initialise_shape(shape, grid)
# grid = trim_grid(grid)
# # display_grid(grid)
# grid = move_left_right(grid)
# while can_move_down(grid):
# grid = move_down(grid)
# grid = move_left_right(grid)
# grid = turn_stationary(grid)
# print("Real answer", grid_height+grid_top(grid))
# display_grid(grid)
# ###################################
# # Copied over
# with open("17.txt") as f:
# # with open("17_test.txt") as f:
# jet_stream = f.read().strip()
# print(jet_stream)
# move_i = -1
# grid_addon = "."*grid_width*(init_x+1+max(shape["height"] for shape in shapes))
# grid = grid_addon
# grid_height = 0
# grids_so_far = set()
# ###################################
old_turn = 0
old_grid_height = 0
for i in range(number_of_rocks):
shape = shapes[i % len(shapes)]
grid, grid_height = cut_grid(grid, grid_height)
grid = initialise_shape(shape, grid)
grid = trim_grid(grid)
grid = move_left_right(grid)
while can_move_down(grid):
grid = move_down(grid)
grid = move_left_right(grid)
grid = turn_stationary(grid)
turns = i
if any(
grid == g and move_i % len(jet_stream) == m
for g, m, old_i, old_grid_height in grids_so_far
):
old_grid, _, old_turn, old_grid_height = find_previous_turn(
grids_so_far,
grid,
move_i % len(jet_stream)
)
break
else:
grids_so_far.add((grid, move_i % len(jet_stream), i, grid_height))
repeat = (number_of_rocks // (turns - old_turn)) - 1
grid_height = old_grid_height + ((grid_height - old_grid_height) * repeat)
for i in range(old_turn + (turns-old_turn)*repeat + 1, number_of_rocks):
shape = shapes[i % len(shapes)]
grid, grid_height = cut_grid(grid, grid_height)
grid = initialise_shape(shape, grid)
grid = trim_grid(grid)
grid = move_left_right(grid)
while can_move_down(grid):
grid = move_down(grid)
grid = move_left_right(grid)
grid = turn_stationary(grid)
print("answer", grid_height+grid_top(grid))
