From 45183abd7924f2d01aac0df10c012d564a94cf91 Mon Sep 17 00:00:00 2001 From: nekineki Date: Mon, 12 Dec 2022 15:31:28 +0100 Subject: day12 --- 2022/day12.py | 217 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 217 insertions(+) create mode 100755 2022/day12.py (limited to '2022/day12.py') diff --git a/2022/day12.py b/2022/day12.py new file mode 100755 index 0000000..b066a01 --- /dev/null +++ b/2022/day12.py @@ -0,0 +1,217 @@ +#!/usr/bin/env python3 + +# import numpy as np +from functools import reduce +from re import findall +from copy import deepcopy +import sys +import time + +# filename = "in/day12.ref" +filename = "in/day12.pzl" +data = open(filename).read() +lines = [line for line in data.rstrip('\n').split('\n')] +# print(lines) + +res1 = 0 +res2 = 0 + +grid = list() + +start_x = 0 +start_y = 0 +end_x = 0 +end_y = 0 +for y,line in enumerate(lines): + l = list() + for x,char in enumerate(line.strip()): + if char == 'S': + start_x = x + start_y = y + l.append(0) + elif char == 'E': + end_x = x + end_y = y + l.append(25) + else: + l.append(ord(char) - ord('a')) + grid.append(l) + +# print('grid', grid) +# print('end', end_y, end_x) + +def print_visited(visited, steps): + print('\x1b[2J') + for y,l in enumerate(visited): + for x,_ in enumerate(l): + if visited[y][x] > steps: + print('.', end='') + else: + print('#', end='') + print() + time.sleep(0.1) + + +# def traverse(grid, visited, steps, y, x): +# # if visited[y][x] < steps: +# # if visited[y][x] < 12345: +# # print('syx', steps, y,x) +# # print(steps, visited[y][x]) +# # return 420000, visited +# # visited[y][x] = steps + +# # if steps % 100 == 0: +# # print(steps) +# print_visited(visited, steps) + +# if x==end_x and y==end_y: +# print('steps', steps) +# return steps, visited + +# lowest = list() +# lowest.append(42000) +# if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1: +# low, visited = traverse(grid, visited, steps+1, y, x+1) +# lowest.append(low) + +# if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1: +# low, visited = traverse(grid, visited, steps+1, y+1, x) +# lowest.append(low) + +# if y > 0 and grid[y-1][x] <= grid[y][x]+1: +# low, visited = traverse(grid, visited, steps+1, y-1, x) +# lowest.append(low) + +# if x > 0 and grid[y][x-1] <= grid[y][x]+1: +# low, visited = traverse(grid, visited, steps+1, y, x-1) +# lowest.append(low) + +# return min(lowest), visited + + +# def traverse_same(s, y, x): +# for t in tiles: +# if (y,x) in t: +# # print('already in tiles', y,x) +# return s +# if (y,x) in s: +# # print('already in set', y,x) +# return s + +# s.add((y,x)) +# # if steps % 100 == 0: +# # print(steps) +# # print_visited(visited, steps) + +# if x+1 < len(grid[0]) and grid[y][x+1] == grid[y][x]: +# s.union(traverse_same(s, y, x+1)) + +# if x > 0 and grid[y][x-1] == grid[y][x]: +# s.union(traverse_same(s, y, x-1)) + +# if y+1 < len(grid) and grid[y+1][x] == grid[y][x]: +# s.union(traverse_same(s, y+1, x)) + +# if y > 0 and grid[y-1][x] == grid[y][x]: +# s.union(traverse_same(s, y-1, x)) + +# # print(y, x, s) +# return s + +# sys.setrecursionlimit(10000) +# visited = [[9999999 for i in l] for l in grid] +# print(visited) +# res1, visited = traverse(grid, visited, 0, start_y, start_x) + +# tiles = list() +# tiles_vals = list() +# yx_to_tile = [[None for i in l] for l in grid] + +# for j,l in enumerate(grid): +# for i,_ in enumerate(l): +# s = traverse_same(set(), j, i) +# if len(s) > 0: +# for (y,x) in s: +# yx_to_tile[y][x] = len(tiles) +# tiles.append(s) +# tiles_vals.append(grid[y][x]) +# # print(y, x, s) +# for line in grid: +# print(line) +# print(tiles) +# print(tiles_vals) +# for line in yx_to_tile: +# print(line) + + +def bfs(grid, start_y, start_x, end_y, end_x): + visited = set() + visited.add((start_y,start_x)) + + steps = 0 + while True: + new_visited = set() + # print(visited) + for (y,x) in visited: + if x == end_x and y == end_y: + # print('steps', steps, y, x) + return steps + + if x+1 < len(grid[0]) and grid[y][x+1] <= grid[y][x]+1: + new_visited.add((y, x+1)) + + if x > 0 and grid[y][x-1] <= grid[y][x]+1: + new_visited.add((y, x-1)) + + if y+1 < len(grid) and grid[y+1][x] <= grid[y][x]+1: + new_visited.add((y+1, x)) + + if y > 0 and grid[y-1][x] <= grid[y][x]+1: + new_visited.add((y-1, x)) + + visited = visited.union(new_visited) + steps += 1 + +res1 = bfs(grid, start_y, start_x, end_y, end_x) + +def bfs2(grid, start_y, start_x, end): + visited = set() + visited.add((start_y,start_x)) + + steps = 0 + while True: + new_visited = set() + # print(visited) + for (y,x) in visited: + if (y,x) in end: + # print('steps', steps, y, x) + return steps + + if x+1 < len(grid[0]) and grid[y][x+1]+1 >= grid[y][x]: + new_visited.add((y, x+1)) + + if x > 0 and grid[y][x-1]+1 >= grid[y][x]: + new_visited.add((y, x-1)) + + if y+1 < len(grid) and grid[y+1][x]+1 >= grid[y][x]: + new_visited.add((y+1, x)) + + if y > 0 and grid[y-1][x]+1 >= grid[y][x]: + new_visited.add((y-1, x)) + + visited = visited.union(new_visited) + steps += 1 + +elea = set() +for y,l in enumerate(grid): + for x,_ in enumerate(l): + if grid[y][x] == 0: + elea.add((y,x)) +# print(elea) + +res2 = bfs2(grid, end_y, end_x, elea) + + +print('res1:', res1) +print('res2:', res2) + -- cgit v1.2.3