day_20.py

import re
from datetime import datetime
from time import sleep

time_start = datetime.now()


with open('day_20.input', 'r') as file:
    lines = file.readlines()

walls = {}
start = None
end = None
height = len(lines)
width = len(lines[0])
for y in range(height):
    for x in range(width):
        if lines[y][x] == "#":
            # (Nanoseconds, cheated)
            walls[x,y] = (0, False)
        if lines[y][x] == "S":
            start = x, y
        if lines[y][x] == "E":
            end = x, y


class RaceHorse:
    def __init__(self, start, end):
        self.pos = start
        self.end = end
        self.steps = 0
        self.cheated = False

    def get_moves(self):
        x, y = self.pos
        return [
            (x-1, y),
            (x+1, y),
            (x, y+1),
            (x, y-1)
        ]

    def escape(self):
        path = {self.pos: 0}
        while self.pos != self.end:
            moves = self.get_moves()
            for move in moves:
                if move in walls:
                    continue
                if move in path:
                    continue
                self.steps += 1
                self.pos = move
                path[move] = self.steps

            # fancy_print(self)
            # sleep(0.1)
        return path

    def cheat(self, path, cutoff):
        total = 0
        for x, y in path.keys():
            steps = path[x,y]
            if (x - 2, y) in path:
                if path[x-2,y] - steps > cutoff:
                    total += 1
            if (x + 2, y) in path:
                if path[x+2,y] - steps > cutoff:
                    total += 1
            if (x, y - 2) in path:
                if path[x,y-2] - steps > cutoff:
                    total += 1
            if (x, y + 2) in path:
                if path[x,y+2] - steps > cutoff:
                    total += 1
        return total

    def cheat_time(self, time, path, cutoff):
        total = 0

        for x, y in path.keys():
            steps = path[x,y]
            if self.steps - steps < cutoff:
                break

            positions = {(x, y)}
            for i in range(time):
                new_positions = set()
                for x_i, y_i in positions:
                    new_positions.add((x_i + 1, y_i))
                    new_positions.add((x_i - 1, y_i))
                    new_positions.add((x_i, y_i - 1))
                    new_positions.add((x_i, y_i + 1))
                positions.update(new_positions)

            for pos in positions:
                if pos in path:
                    if path[pos] - steps - abs(x - pos[0]) - abs(y - pos[1]) >= cutoff:
                        total += 1
        return total

# def fancy_print_debug_2(start, pos):
#     for y in range(height):
#         line = ""
#         for x in range(width):
#             if start == (x, y):
#                 line += "F"
#             elif (x, y) in pos:
#                 line += "C"
#
#             else:
#                 line += lines[y][x]
#         print(line)
#
#
# def fancy_print_debug(start, end, path):
#     for y in range(height):
#         line = ""
#         for x in range(width):
#             if start == (x, y):
#                 line +=  '\033[92m'+ "F" + '\033[0m'
#             elif end == (x, y):
#                 line += '\033[94m'+ "H" + '\033[0m'
#             elif (x,y) in path:
#                 line += str(path[x,y])
#             else:
#                 line += lines[y][x]
#         print(line)
#
# def fancy_print(race: RaceHorse):
#     for y in range(height):
#         line = ""
#         for x in range(width):
#             if race.pos == (x, y):
#                 line += "S"
#             else:
#                 line += lines[y][x]
#         print(line)

race = RaceHorse(start, end)
# fancy_print(race)
path = race.escape()
print("part1", race.cheat(path, 100))
print("part2", race.cheat_time(20, path, 100))

print("Total time: ", datetime.now() - time_start)
#Total time:  0:00:13.792486