Skip to content

Instantly share code, notes, and snippets.

@Dotrar
Created December 12, 2022 10:22
Show Gist options
  • Save Dotrar/98c6fd20ec99f83c6cb7bf1435715bac to your computer and use it in GitHub Desktop.
Save Dotrar/98c6fd20ec99f83c6cb7bf1435715bac to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
from __future__ import annotations
import dataclasses
import math
import os
import time
from typing import Callable
import aocd
import parse
AOC_DAY = 12
test_data = """\
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
"""
def data_parse(dstr):
return [[c for c in line] for line in dstr.splitlines()]
test_data = data_parse(test_data)
assert len(test_data) == 5
assert len(test_data[0]) == 8
test_answer_one = 31
test_answer_two = 29
USE_ASTAR = False
def print_map(data, sr, sc, visited, search):
buffer = "Breadth First Search\n" if not USE_ASTAR else "A* Search\n"
search = [s for s, l in search]
for r, row in enumerate(data):
for c, col in enumerate(row):
draw = col
if (r, c) in search:
draw = "."
elif (r, c) in visited:
draw = "#"
if sr == r and sc == c:
draw = "$"
buffer += draw
buffer += "\n"
buffer += "-" * len(data[0])
buffer = "\b" * len(buffer) + buffer
print(buffer, end="")
return 0
def find_char_position(data, char):
for r, row in enumerate(data):
for c, col in enumerate(row):
if col == char:
return (r, c)
def position_valid(pos, map):
y = len(map)
x = len(map[0])
r, c = pos
return r in range(y) and c in range(x)
def surrounding_points(pos):
a, b = pos
return [
(a + 1, b),
(a - 1, b),
(a, b + 1),
(a, b - 1),
]
def get_height_at(pos, map):
r, c = pos
char = map[r][c]
if char == "S":
char = "a"
elif char == "E":
char = "z"
return ord(char) - ord("a")
def can_move(pos, newpos, map):
old = get_height_at(pos, map)
new = get_height_at(newpos, map)
return new <= (old + 1)
def can_move_2(pos, newpos, map):
new = get_height_at(pos, map)
old = get_height_at(newpos, map)
return new <= (old + 1)
def get_positions_to_goal(data) -> int:
start_pos = find_char_position(data, "S")
end_pos = find_char_position(data, "E")
visited = {start_pos}
def suitable_point(origin, newpos):
return (
newpos not in visited
and position_valid(newpos, data)
and can_move(origin, newpos, data)
)
def next_points(s, l):
return [(p, l) for p in surrounding_points(s) if suitable_point(s, p)]
search = next_points(start_pos, 1)
while search:
s, pathlength = search.pop()
sr, sc = s
print_map(data, sr, sc, visited, search)
visited.add(s)
if s == end_pos:
return pathlength
search = next_points(s, pathlength + 1) + search
search = [(s, l) for s, l in search if s not in visited]
# arrange search by sorting by their delta to E:
def distance(p, l):
ra, ca = p
rb, cb = end_pos
return int(math.sqrt(((rb - ra) ** 2) + ((cb - ca) ** 2))), l
if USE_ASTAR:
search = sorted(search, key=lambda x: distance(*x), reverse=True)
print()
time.sleep(0.01)
return -1
def get_positions_to_goal_2(data) -> int:
start_pos = find_char_position(data, "E")
# end_pos = find_char_position(data, "E")
visited = {start_pos}
def suitable_point(origin, newpos):
return (
newpos not in visited
and position_valid(newpos, data)
and can_move_2(origin, newpos, data)
)
def next_points(s, l):
return [(p, l) for p in surrounding_points(s) if suitable_point(s, p)]
search = next_points(start_pos, 1)
while search:
s, pathlength = search.pop()
sr, sc = s
print_map(data, sr, sc, visited, search)
visited.add(s)
if get_height_at(s, data) == 0:
return pathlength
search = next_points(s, pathlength + 1) + search
search = [(s, l) for s, l in search if s not in visited]
# # arrange search by sorting by their delta to E:
# def distance(p, l):
# ra, ca = p
# rb, cb = end_pos
# return int(math.sqrt(((rb - ra) ** 2) + ((cb - ca) ** 2))), l
# if USE_ASTAR:
# search = sorted(search, key=lambda x: distance(*x), reverse=True)
print()
time.sleep(0.01)
return -1
def part_one(data: list[list[str]]) -> int:
# breadth first search
path = get_positions_to_goal(data)
return path
def part_two(data: list[str]) -> int:
path = get_positions_to_goal_2(data)
return path
if __name__ == "__main__":
# part_one_ans = part_one(test_data)
# assert part_one_ans == test_answer_one, f"{part_one_ans=}, not {test_answer_one=}"
real_data = data_parse(aocd.get_data(day=AOC_DAY, year=2022))
# print("part 1:", part_one(real_data))
part_two_ans = part_two(test_data)
assert part_two_ans == test_answer_two, f"{part_two_ans=}, not {test_answer_two=}"
print("part 2:", part_two(real_data))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment