From 9f8603a3e116d590d68c9f1cb6764e2f60438e5c Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Wed, 14 Dec 2022 13:27:07 +0000 Subject: 14 much faster --- 14.py | 48 ++++++++++++++++++++++++++---------------------- 1 file changed, 26 insertions(+), 22 deletions(-) diff --git a/14.py b/14.py index 6f49e37..f74e30b 100644 --- a/14.py +++ b/14.py @@ -1,12 +1,13 @@ -from utils import open_day, Point2D, sliding_window, inbounds +from utils import open_day, sliding_window from enum import Enum, auto from itertools import count +import cProfile def display(sandbox, minx, miny, maxx, maxy): for y in range(miny, maxy + 1): line = [] for x in range(minx, maxx + 1): - p = Point2D(x, y) + p = x, y if p in sandbox: if sandbox[p] == Tile.WALL: line.append('#') @@ -19,23 +20,23 @@ def display(sandbox, minx, miny, maxx, maxy): print(''.join(line)) def point_from_str(s): - return Point2D(*(int(d) for d in s.split(','))) + return tuple(int(d) for d in s.split(',')) class Tile(Enum): WALL = auto() SAND = auto() class Sandbox: - def __init__(self, source=Point2D(500, 0)): + def __init__(self, source=(500, 0)): self.tiles = dict() self.source = source - self.minx, self.maxx = source.x, source.x - self.miny, self.maxy = source.y, source.y + self.minx, self.maxx = source[0], source[0] + self.miny, self.maxy = source[1], source[1] def __setitem__(self, key, value): - if key.x < self.minx: self.minx = key.x - elif key.x > self.maxx: self.maxx = key.x - if key.y < self.miny: self.miny = key.y - elif key.y > self.maxy: self.maxy = key.y + if key[0] < self.minx: self.minx = key[0] + elif key[0] > self.maxx: self.maxx = key[0] + if key[1] < self.miny: self.miny = key[1] + elif key[1] > self.maxy: self.maxy = key[1] self.tiles[key] = value def __getitem__(self, key): return self.tiles[key] @@ -44,23 +45,25 @@ class Sandbox: for y in range(self.miny, self.maxy + 1): line = [] for x in range(self.minx, self.maxx + 1): - p = Point2D(x, y) + p = x, y match self.tiles.get(p): case Tile.WALL: line.append('#') case Tile.SAND: line.append('o') case None: line.append('.') - if x == self.source.x and y == self.source.y: + if x == self.source[0] and y == self.source[1]: line[-1] = '+' lines.append(''.join(line)) return '\n'.join(lines) def simulate(self): - bounds = (Point2D(self.minx, self.miny), Point2D(self.maxx, self.maxy)) for units in count(): sandpos = self.source - while self.source not in self.tiles and inbounds(sandpos, *bounds): - for d in (Point2D( 0, 1), Point2D(-1, 1), Point2D( 1, 1)): - if sandpos + d not in self.tiles: - sandpos += d + while self.minx <= sandpos[0] <= self.maxx and \ + self.miny <= sandpos[1] <= self.maxy and \ + self.source not in self.tiles: + for dx in (0, -1, 1): + npos = sandpos[0] + dx, sandpos[1] + 1 + if npos not in self.tiles: + sandpos = (sandpos[0] + dx, sandpos[1] + 1) break else: self.tiles[sandpos] = Tile.SAND @@ -74,18 +77,19 @@ sandbox = Sandbox() with open_day(14) as f: for line in f: for b, e in sliding_window(map(point_from_str, line.rstrip().split(' -> ')), 2): - minlx, maxlx = min(b.x, e.x), max(b.x, e.x) - minly, maxly = min(b.y, e.y), max(b.y, e.y) + minlx, maxlx = min(b[0], e[0]), max(b[0], e[0]) + minly, maxly = min(b[1], e[1]), max(b[1], e[1]) for x in range(minlx, maxlx + 1): for y in range(minly, maxly + 1): - sandbox[Point2D(x, y)] = Tile.WALL + sandbox[x, y] = Tile.WALL p1 = sandbox.simulate() print(p1) floory = sandbox.maxy + 2 -height = floory - sandbox.source.y +height = floory - sandbox.source[1] for x in range(500 - height, 500 + height + 1): - sandbox[Point2D(x, floory)] = Tile.WALL + sandbox[x, floory] = Tile.WALL +# cProfile.run('sandbox.simulate()') print(p1 + sandbox.simulate()) -- cgit v1.2.3-54-g00ecf