StyleInCode

""" day_20_01.py """

# usage: python3 day_20_01.py 100 < input

import sys
from collections import namedtuple


Point = namedtuple('Point', 'x, y')


def moddiv(value, num):
    """ reverse divmod """
    return value % num, value // num


def scout(loc, track, obstacles):
    """ single possible move from loc not in track """
    deltas = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)]
    dest = None
    for d in deltas:
        dest = Point(loc.x + d.x, loc.y + d.y)
        if dest not in obstacles:
            if dest not in track:
                break
    return dest


def solve(begin, finish, obstacles):
    """ single path to go from begin to finish """
    visited = []
    pos = begin
    while pos != finish:
        visited.append(pos)
        pos = scout(pos, visited, obstacles)

    return visited


def cheats(loc, path, obstacles):
    """ select cheat locations from loc """
    deltas = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)]
    outcome = []
    for d in deltas:
        if Point(loc.x + d.x, loc.y + d.y) in obstacles:
            dest = Point(loc.x + 2 * d.x, loc.y + 2 * d.y)
            if dest in path:
                if path.index(loc) < path.index(dest):
                    outcome.append(dest)
    return outcome


with sys.stdin as infile:
    raw = infile.read()

saving = int(sys.argv[1])
width = raw.find('\n')
raw = raw.replace('\n', '')
height = len(raw) // width

start = Point(*moddiv(raw.find('S'), width))
end = Point(*moddiv(raw.find('E'), width))

cpu = {Point(*moddiv(i, width)) for i, obj in enumerate(raw) if obj == '#'}
single_path = solve(start, end, cpu)

log = [0 for _ in range(len(single_path))]
for i, step in enumerate(single_path):
    for cheat in cheats(step, single_path, cpu):
        time_saving = single_path.index(cheat) - i - 2
        log[time_saving] += 1

print(sum(log[saving:]))

""" day_20_02.py """

# usage: python3 day_20_02.py 100 < input

import sys
from collections import namedtuple


Point = namedtuple('Point', 'x, y')


def moddiv(value, num):
    """ reverse divmod """
    return value % num, value // num


def scout(loc, track, obstacles):
    """ single possible move from loc not in track """
    deltas = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)]
    dest = None
    for d in deltas:
        dest = Point(loc.x + d.x, loc.y + d.y)
        if dest not in obstacles:
            if dest not in track:
                break
    return dest


def solve(begin, finish, obstacles):
    """ single path to go from begin to finish """
    visited = []
    pos = begin
    while pos != finish:
        visited.append(pos)
        pos = scout(pos, visited, obstacles)

    return visited + [finish]


def cheats(loc, path):
    """ select cheat locations from loc """
    def dist(a, b):
        """ Manhattan distance """
        return abs(a.x - b.x) + abs(a.y - b.y)

    outcome = set()
    for pos in path[path.index(loc):]:
        if (d := dist(loc, pos)) <= 20:
            outcome.add((pos, d))
    return outcome


with sys.stdin as infile:
    raw = infile.read()

saving = int(sys.argv[1])
width = raw.find('\n')
raw = raw.replace('\n', '')
height = len(raw) // width

start = Point(*moddiv(raw.find('S'), width))
end = Point(*moddiv(raw.find('E'), width))

cpu = {Point(*moddiv(i, width)) for i, obj in enumerate(raw) if obj == '#'}
single_path = solve(start, end, cpu)

log = [0 for _ in range(len(single_path))]
for i, step in enumerate(single_path):
    for cheat, time in cheats(step, single_path):
        time_saving = single_path.index(cheat) - i - time
        log[time_saving] += 1

print(sum(log[saving:]))