diff options
Diffstat (limited to '20')
| -rw-r--r-- | 20/README | 2 | ||||
| -rw-r--r-- | 20/py/aoc20.py | 2 | ||||
| -rw-r--r-- | 20/py/d11.py | 155 |
3 files changed, 97 insertions, 62 deletions
@@ -12,6 +12,7 @@ Day Time Ans Time Ans 8 0.261 2025 5.063 2001 9 2.741 26796446 2.875 3353494 10 0.027 2046 0.161 1157018619904 + 11 432.343 2338 580.579 2134 ------- ------- tot TBD TBD @@ -20,6 +21,7 @@ Stats: -------Part 1-------- -------Part 2-------- Day Time Rank Score Time Rank Score + 11 00:55:39 4799 0 01:20:27 4040 0 10 00:08:17 1496 0 00:51:01 2766 0 9 00:25:55 6220 0 00:31:44 4392 0 8 00:08:21 1632 0 00:17:34 1265 0 diff --git a/20/py/aoc20.py b/20/py/aoc20.py index cf36581..c904e21 100644 --- a/20/py/aoc20.py +++ b/20/py/aoc20.py @@ -106,7 +106,7 @@ if __name__ == "__main__": times.append(ans_time-start) avg_time = sum(times) / len(times) tot_time[part] += avg_time - print(f" {avg_time*1000:6.3f} {ans:14}", end="") + print(f" {avg_time*1000:8.3f} {ans:14}", end="") print() if decorate: diff --git a/20/py/d11.py b/20/py/d11.py index 048367c..f78eb8c 100644 --- a/20/py/d11.py +++ b/20/py/d11.py @@ -1,94 +1,127 @@ #!/usr/bin/env python3 import aoc20 import sys +import functools + + +def vis(board): + s = "" + for r in board: + for c in r: + s += "T" if c[0] else "F" + s += str(c[1]) if c[1] >= 0 else "-" + s += str(c[2]) + s += " " + s += "\n" + return s def read(lines): - board = {} + board = [] h = len(lines) - w = len(lines[0]) + w = len(lines[0]) - 1 for y in range(h): + row = [] for x in range(w): if lines[y][x] == "L": - board[(x, y)] = 0 + row.append([False, 0, 0, []]) elif lines[y][x] == ".": - board[(x, y)] = -1 + row.append([False, -1, 0, []]) + board.append(row) + + def update_in_sight(x, y): + for dy in range(-1, 1+1): + for dx in range(-1, 1+1): + if dy == dx == 0: + continue + step = 0 + while True: + step += 1 + px, py = x + (dx * step), y + (dy * step) + if px < 0 or px >= w or py < 0 or py >= h: + break + if board[py][px][1] != -1: + board[py][px][3].append((x, y)) + break + + for y in range(h): + for x in range(w): + update_in_sight(x, y) return board, w, h -def amount_neighbours_occ(p, board): - amount = 0 +@functools.cache +def neighbours_occ(p, w, h): + n = [] for dy in range(-1, 1+1): - for dx in range(-1, 1+1): - if dy == dx == 0: - continue - new_p = (p[0] + dx, p[1] + dy) - if new_p in board and board[new_p] == 1: - amount += 1 - return amount + py = p[1] + dy + if 0 <= py < h: + for dx in range(-1, 1+1): + if dy == dx == 0: + continue + px = p[0] + dx + if 0 <= px < w: + n.append((px, py)) + return n def pt1(_in): board, w, h = read(_in) while True: - prev_board = board.copy() - for p, state in prev_board.items(): - if state == 0: - # empty - if amount_neighbours_occ(p, prev_board) == 0: - board[p] = 1 - if state == 1: - # occ - if amount_neighbours_occ(p, prev_board) >= 4: - board[p] = 0 - if prev_board == board: + changed = False + for y in range(h): + for x in range(w): + if not board[y][x][0] and board[y][x][1] == 0: + changed = True + board[y][x][0] = True + for nx, ny in neighbours_occ((x, y), w, h): + board[ny][nx][2] += 1 + if board[y][x][0] and board[y][x][1] >= 4: + changed = True + board[y][x][0] = False + for nx, ny in neighbours_occ((x, y), w, h): + board[ny][nx][2] -= 1 + for y in range(h): + for x in range(w): + if board[y][x][1] != -1: + board[y][x][1] = board[y][x][2] + if not changed: break - prev_board = board res = 0 - for _, state in board.items(): - if state == 1: - res += 1 + for y in range(h): + for x in range(w): + if board[y][x][0]: + res += 1 return res -def amount_in_sight_occ(p, board, w, h): - amount = 0 - dirs = ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)) - for dir in dirs: - step = 0 - while True: - step += 1 - new_p = p[0] + dir[0] * step, p[1] + dir[1] * step - if new_p not in board: - break - if board[new_p] == -1: - continue - if board[new_p] == 1: - amount += 1 - break - return amount - - def pt2(_in): board, w, h = read(_in) while True: - prev_board = board.copy() - for p, state in prev_board.items(): - if state == 0: - # empty - if amount_in_sight_occ(p, prev_board, w, h) == 0: - board[p] = 1 - if state == 1: - # occ - if amount_in_sight_occ(p, prev_board, w, h) >= 5: - board[p] = 0 - if prev_board == board: + changed = False + for y in range(h): + for x in range(w): + if not board[y][x][0] and board[y][x][1] == 0: + changed = True + board[y][x][0] = True + for nx, ny in board[y][x][3]: + board[ny][nx][2] += 1 + if board[y][x][0] and board[y][x][1] >= 5: + changed = True + board[y][x][0] = False + for nx, ny in board[y][x][3]: + board[ny][nx][2] -= 1 + for y in range(h): + for x in range(w): + if board[y][x][1] != -1: + board[y][x][1] = board[y][x][2] + if not changed: break - prev_board = board res = 0 - for _, state in board.items(): - if state == 1: - res += 1 + for y in range(h): + for x in range(w): + if board[y][x][0]: + res += 1 return res |