day12.py

#!/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))