Compare commits
46 Commits
2022/day16
...
master
Author | SHA1 | Date | |
---|---|---|---|
|
3edaa249fc | ||
|
57fcb47fe9 | ||
|
cfa7718475 | ||
|
2d23e355b2 | ||
|
fab4899715 | ||
|
b6e20eefa3 | ||
|
872fd72dcd | ||
|
98f28e96f8 | ||
|
ed7aba80ad | ||
|
e507dad5e0 | ||
|
04172beb5a | ||
|
15ef67e757 | ||
|
cd0ada785c | ||
|
42bd8d6983 | ||
|
0567ab7440 | ||
|
7d2eb6b5ec | ||
|
3a9c7e728b | ||
|
d002e419c3 | ||
|
19d93e0c1d | ||
|
5c05ee5c85 | ||
|
103af21915 | ||
|
af2fbf2da1 | ||
|
c496ea25c9 | ||
|
5f8c74fd1c | ||
|
dda2be2505 | ||
|
12891194bb | ||
|
f15908876d | ||
|
5f5ebda674 | ||
|
5b30cc00d5 | ||
|
3a7f8e83dc | ||
|
ba5b01c594 | ||
|
d0970c090b | ||
|
8e90bf7002 | ||
9698dfcdac | |||
|
1a6ab1cc0e | ||
|
f5aabbee8f | ||
|
6c00341ab0 | ||
|
755e0bd4b3 | ||
|
a52d077a40 | ||
|
3fc0f94b1c | ||
|
8a0412f926 | ||
|
855efeb0aa | ||
|
f2a65e03e5 | ||
|
759f47bfab | ||
|
999207b007 | ||
|
d92e4744a4 |
1
.gitignore
vendored
1
.gitignore
vendored
@ -1 +1,2 @@
|
|||||||
venv
|
venv
|
||||||
|
__pycache__
|
||||||
|
13
2023/day6.py
13
2023/day6.py
@ -1,13 +0,0 @@
|
|||||||
import sys
|
|
||||||
from collections import defaultdict
|
|
||||||
from dataclasses import dataclass
|
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
|
||||||
|
|
||||||
# part 1
|
|
||||||
answer_1 = ...
|
|
||||||
print(f"answer 1 is {answer_1}")
|
|
||||||
|
|
||||||
# part 2
|
|
||||||
answer_2 = ...
|
|
||||||
print(f"answer 2 is {answer_2}")
|
|
13
2023/day7.py
13
2023/day7.py
@ -1,13 +0,0 @@
|
|||||||
import sys
|
|
||||||
from collections import defaultdict
|
|
||||||
from dataclasses import dataclass
|
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
|
||||||
|
|
||||||
# part 1
|
|
||||||
answer_1 = ...
|
|
||||||
print(f"answer 1 is {answer_1}")
|
|
||||||
|
|
||||||
# part 2
|
|
||||||
answer_2 = ...
|
|
||||||
print(f"answer 2 is {answer_2}")
|
|
13
2023/day8.py
13
2023/day8.py
@ -1,13 +0,0 @@
|
|||||||
import sys
|
|
||||||
from collections import defaultdict
|
|
||||||
from dataclasses import dataclass
|
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
|
||||||
|
|
||||||
# part 1
|
|
||||||
answer_1 = ...
|
|
||||||
print(f"answer 1 is {answer_1}")
|
|
||||||
|
|
||||||
# part 2
|
|
||||||
answer_2 = ...
|
|
||||||
print(f"answer 2 is {answer_2}")
|
|
13
2023/day9.py
13
2023/day9.py
@ -1,13 +0,0 @@
|
|||||||
import sys
|
|
||||||
from collections import defaultdict
|
|
||||||
from dataclasses import dataclass
|
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
|
||||||
|
|
||||||
# part 1
|
|
||||||
answer_1 = ...
|
|
||||||
print(f"answer 1 is {answer_1}")
|
|
||||||
|
|
||||||
# part 2
|
|
||||||
answer_2 = ...
|
|
||||||
print(f"answer 2 is {answer_2}")
|
|
35
README.md
35
README.md
@ -1,7 +1,36 @@
|
|||||||
# Advent Of Code
|
# Holt59 - Advent Of Code
|
||||||
|
|
||||||
To run any script, you need to pipe the input:
|
Installation (with [`poetry`](https://python-poetry.org/)):
|
||||||
|
|
||||||
```bash
|
```bash
|
||||||
cat 2022/inputs/day2.txt | python 2022/day2.py
|
poetry install
|
||||||
|
```
|
||||||
|
|
||||||
|
To run any day:
|
||||||
|
|
||||||
|
```bash
|
||||||
|
holt59-aoc $day
|
||||||
|
```
|
||||||
|
|
||||||
|
You can use `-v` / `--verbose` for extra outputs in some case, `-t` / `--test` to run
|
||||||
|
the code on the test data (one of the test data if multiple are present) or even
|
||||||
|
`-u XXX` / `--user XXX` to run the code on a specific input after putting the input
|
||||||
|
file under `src/holt59/aoc/inputs/XXX/$year/$day`.
|
||||||
|
|
||||||
|
Full usage:
|
||||||
|
|
||||||
|
```bash
|
||||||
|
usage: Holt59 Advent-Of-Code Runner [-h] [-v] [-t] [-u USER] [-i INPUT] [-y YEAR] day
|
||||||
|
|
||||||
|
positional arguments:
|
||||||
|
day day to run
|
||||||
|
|
||||||
|
options:
|
||||||
|
-h, --help show this help message and exit
|
||||||
|
-v, --verbose verbose mode
|
||||||
|
-t, --test test mode
|
||||||
|
-u USER, --user USER user input to use
|
||||||
|
-i INPUT, --input INPUT
|
||||||
|
input to use (override user and test)
|
||||||
|
-y YEAR, --year YEAR year to run
|
||||||
```
|
```
|
||||||
|
1395
poetry.lock
generated
Normal file
1395
poetry.lock
generated
Normal file
File diff suppressed because it is too large
Load Diff
52
pyproject.toml
Normal file
52
pyproject.toml
Normal file
@ -0,0 +1,52 @@
|
|||||||
|
[tool.poetry]
|
||||||
|
name = "holt59-advent-of-code"
|
||||||
|
version = "0.1.0"
|
||||||
|
description = ""
|
||||||
|
authors = ["Mikael CAPELLE <capelle.mikael@gmail.com>"]
|
||||||
|
license = "MIT"
|
||||||
|
readme = "README.md"
|
||||||
|
packages = [{ include = "holt59", from = "src" }]
|
||||||
|
|
||||||
|
[tool.poetry.dependencies]
|
||||||
|
python = "^3.10"
|
||||||
|
numpy = "^1.26.2"
|
||||||
|
tqdm = "^4.66.1"
|
||||||
|
parse = "^1.20.0"
|
||||||
|
scipy = "^1.11.4"
|
||||||
|
ortools = "^9.8.3296"
|
||||||
|
sympy = "^1.12"
|
||||||
|
networkx = "^3.2.1"
|
||||||
|
|
||||||
|
[tool.poetry.scripts]
|
||||||
|
holt59-aoc = "holt59.aoc.__main__:main"
|
||||||
|
|
||||||
|
[tool.poe.tasks]
|
||||||
|
lint-black = "black --check --diff src tests typings"
|
||||||
|
lint-isort = "isort -c src tests typings"
|
||||||
|
lint-ruff = "ruff src tests typings"
|
||||||
|
lint-flake8 = "flake8 src tests typings"
|
||||||
|
lint-pyright = "pyright src tests"
|
||||||
|
lint-all.sequence = [
|
||||||
|
"lint-black",
|
||||||
|
"lint-isort",
|
||||||
|
"lint-flake8",
|
||||||
|
"lint-ruff",
|
||||||
|
"lint-pyright",
|
||||||
|
]
|
||||||
|
lint-all.ignore_fail = "return_non_zero"
|
||||||
|
|
||||||
|
[tool.poetry.group.dev.dependencies]
|
||||||
|
flake8 = "^6.1.0"
|
||||||
|
flake8-black = "^0.3.6"
|
||||||
|
black = "^23.12.0"
|
||||||
|
pyright = "^1.1.341"
|
||||||
|
mypy = "^1.7.1"
|
||||||
|
isort = "^5.13.2"
|
||||||
|
ruff = "^0.1.8"
|
||||||
|
poethepoet = "^0.24.4"
|
||||||
|
ipykernel = "^6.27.1"
|
||||||
|
networkx-stubs = "^0.0.1"
|
||||||
|
|
||||||
|
[build-system]
|
||||||
|
requires = ["poetry-core"]
|
||||||
|
build-backend = "poetry.core.masonry.api"
|
1
run.ps1
1
run.ps1
@ -8,4 +8,5 @@ param(
|
|||||||
|
|
||||||
$folder = $Test ? "tests" : "inputs"
|
$folder = $Test ? "tests" : "inputs"
|
||||||
|
|
||||||
|
$env:AOC_VERBOSE = $VerbosePreference -eq "Continue"
|
||||||
Get-Content ".\$Year\$folder\day$Day.txt" | python ".\$Year\day$Day.py"
|
Get-Content ".\$Year\$folder\day$Day.txt" | python ".\$Year\day$Day.py"
|
||||||
|
10
src/holt59/aoc/2015/day1.py
Normal file
10
src/holt59/aoc/2015/day1.py
Normal file
@ -0,0 +1,10 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
line = sys.stdin.read().strip()
|
||||||
|
|
||||||
|
floor = 0
|
||||||
|
floors = [(floor := floor + (1 if c == "(" else -1)) for c in line]
|
||||||
|
|
||||||
|
|
||||||
|
print(f"answer 1 is {floors[-1]}")
|
||||||
|
print(f"answer 2 is {floors.index(-1)}")
|
148
src/holt59/aoc/2015/day10.py
Normal file
148
src/holt59/aoc/2015/day10.py
Normal file
@ -0,0 +1,148 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
|
||||||
|
line = sys.stdin.read().strip()
|
||||||
|
|
||||||
|
# see http://www.se16.info/js/lands2.htm for the explanation of 'atoms' (or elements)
|
||||||
|
#
|
||||||
|
# see also https://www.youtube.com/watch?v=ea7lJkEhytA (video link from AOC) and this
|
||||||
|
# CodeGolf answer https://codegolf.stackexchange.com/a/8479/42148
|
||||||
|
|
||||||
|
# fmt: off
|
||||||
|
atoms = [
|
||||||
|
("22", (0, )), # 0
|
||||||
|
("13112221133211322112211213322112", (71, 90, 0, 19, 2, )), # 1
|
||||||
|
("312211322212221121123222112", (1, )), # 2
|
||||||
|
("111312211312113221133211322112211213322112", (31, 19, 2, )), # 3
|
||||||
|
("1321132122211322212221121123222112", (3, )), # 4
|
||||||
|
("3113112211322112211213322112", (4, )), # 5
|
||||||
|
("111312212221121123222112", (5, )), # 6
|
||||||
|
("132112211213322112", (6, )), # 7
|
||||||
|
("31121123222112", (7, )), # 8
|
||||||
|
("111213322112", (8, )), # 9
|
||||||
|
("123222112", (9, )), # 10
|
||||||
|
("3113322112", (60, 10, )), # 11
|
||||||
|
("1113222112", (11, )), # 12
|
||||||
|
("1322112", (12, )), # 13
|
||||||
|
("311311222112", (66, 13, )), # 14
|
||||||
|
("1113122112", (14, )), # 15
|
||||||
|
("132112", (15, )), # 16
|
||||||
|
("3112", (16, )), # 17
|
||||||
|
("1112", (17, )), # 18
|
||||||
|
("12", (18, )), # 19
|
||||||
|
("3113112221133112", (66, 90, 0, 19, 26, )), # 20
|
||||||
|
("11131221131112", (20, )), # 21
|
||||||
|
("13211312", (21, )), # 22
|
||||||
|
("31132", (22, )), # 23
|
||||||
|
("111311222112", (23, 13, )), # 24
|
||||||
|
("13122112", (24, )), # 25
|
||||||
|
("32112", (25, )), # 26
|
||||||
|
("11133112", (29, 26, )), # 27
|
||||||
|
("131112", (27, )), # 28
|
||||||
|
("312", (28, )), # 29
|
||||||
|
("13221133122211332", (62, 19, 88, 0, 19, 29, )), # 30
|
||||||
|
("31131122211311122113222", (66, 30, )), # 31
|
||||||
|
("11131221131211322113322112", (31, 10, )), # 32
|
||||||
|
("13211321222113222112", (32, )), # 33
|
||||||
|
("3113112211322112", (33, )), # 34
|
||||||
|
("11131221222112", (34, )), # 35
|
||||||
|
("1321122112", (35, )), # 36
|
||||||
|
("3112112", (36, )), # 37
|
||||||
|
("1112133", (37, 91, )), # 38
|
||||||
|
("12322211331222113112211", (38, 0, 19, 42, )), # 39
|
||||||
|
("1113122113322113111221131221", (67, 39, )), # 40
|
||||||
|
("13211322211312113211", (40, )), # 41
|
||||||
|
("311322113212221", (41, )), # 42
|
||||||
|
("132211331222113112211", (62, 19, 42, )), # 43
|
||||||
|
("311311222113111221131221", (66, 43, )), # 44
|
||||||
|
("111312211312113211", (44, )), # 45
|
||||||
|
("132113212221", (45, )), # 46
|
||||||
|
("3113112211", (46, )), # 47
|
||||||
|
("11131221", (47, )), # 48
|
||||||
|
("13211", (48, )), # 49
|
||||||
|
("3112221", (60, 49, )), # 50
|
||||||
|
("1322113312211", (62, 19, 50, )), # 51
|
||||||
|
("311311222113111221", (66, 51, )), # 52
|
||||||
|
("11131221131211", (52, )), # 53
|
||||||
|
("13211321", (53, )), # 54
|
||||||
|
("311311", (54, )), # 55
|
||||||
|
("11131", (55, )), # 56
|
||||||
|
("1321133112", (56, 0, 19, 26, )), # 57
|
||||||
|
("31131112", (57, )), # 58
|
||||||
|
("111312", (58, )), # 59
|
||||||
|
("132", (59, )), # 60
|
||||||
|
("311332", (60, 19, 29, )), # 61
|
||||||
|
("1113222", (61, )), # 62
|
||||||
|
("13221133112", (62, 19, 26, )), # 63
|
||||||
|
("3113112221131112", (66, 63, )), # 64
|
||||||
|
("111312211312", (64, )), # 65
|
||||||
|
("1321132", (65, )), # 66
|
||||||
|
("311311222", (66, 60, )), # 67
|
||||||
|
("11131221133112", (67, 19, 26, )), # 68
|
||||||
|
("1321131112", (68, )), # 69
|
||||||
|
("311312", (69, )), # 70
|
||||||
|
("11132", (70, )), # 71
|
||||||
|
("13112221133211322112211213322113", (71, 90, 0, 19, 73, )), # 72
|
||||||
|
("312211322212221121123222113", (72, )), # 73
|
||||||
|
("111312211312113221133211322112211213322113", (31, 19, 73, )), # 74
|
||||||
|
("1321132122211322212221121123222113", (74, )), # 75
|
||||||
|
("3113112211322112211213322113", (75, )), # 76
|
||||||
|
("111312212221121123222113", (76, )), # 77
|
||||||
|
("132112211213322113", (77, )), # 78
|
||||||
|
("31121123222113", (78, )), # 79
|
||||||
|
("111213322113", (79, )), # 80
|
||||||
|
("123222113", (80, )), # 81
|
||||||
|
("3113322113", (60, 81, )), # 82
|
||||||
|
("1113222113", (82, )), # 83
|
||||||
|
("1322113", (83, )), # 84
|
||||||
|
("311311222113", (66, 84, )), # 85
|
||||||
|
("1113122113", (85, )), # 86
|
||||||
|
("132113", (86, )), # 87
|
||||||
|
("3113", (87, )), # 88
|
||||||
|
("1113", (88, )), # 89
|
||||||
|
("13", (89, )), # 90
|
||||||
|
("3", (90, )), # 91
|
||||||
|
]
|
||||||
|
# fmt: on
|
||||||
|
|
||||||
|
starters = [
|
||||||
|
"1",
|
||||||
|
"11",
|
||||||
|
"21",
|
||||||
|
"1211",
|
||||||
|
"111221",
|
||||||
|
"312211",
|
||||||
|
"13112221",
|
||||||
|
"1113213211",
|
||||||
|
"31131211131221",
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
def look_and_say_length(s: str, n: int) -> int:
|
||||||
|
if n == 0:
|
||||||
|
return len(s)
|
||||||
|
|
||||||
|
if s in starters:
|
||||||
|
return look_and_say_length(
|
||||||
|
"".join(f"{len(list(g))}{k}" for k, g in itertools.groupby(s)), n - 1
|
||||||
|
)
|
||||||
|
|
||||||
|
counts = {i: 0 for i in range(len(atoms))}
|
||||||
|
idx = next(i for i, (a, _) in enumerate(atoms) if s == a)
|
||||||
|
counts[idx] = 1
|
||||||
|
|
||||||
|
for _ in range(n):
|
||||||
|
c2 = {i: 0 for i in range(len(atoms))}
|
||||||
|
for i in counts:
|
||||||
|
for j in atoms[i][1]:
|
||||||
|
c2[j] += counts[i]
|
||||||
|
counts = c2
|
||||||
|
|
||||||
|
return sum(counts[i] * len(a[0]) for i, a in enumerate(atoms))
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = look_and_say_length(line, 40)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = look_and_say_length(line, 50)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
49
src/holt59/aoc/2015/day11.py
Normal file
49
src/holt59/aoc/2015/day11.py
Normal file
@ -0,0 +1,49 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
|
||||||
|
|
||||||
|
def is_valid(p: str) -> bool:
|
||||||
|
if any(c in "iol" for c in p):
|
||||||
|
return False
|
||||||
|
|
||||||
|
if not any(
|
||||||
|
ord(a) + 1 == ord(b) and ord(b) + 1 == ord(c)
|
||||||
|
for a, b, c in zip(p, p[1:], p[2:])
|
||||||
|
):
|
||||||
|
return False
|
||||||
|
|
||||||
|
if sum(len(list(g)) >= 2 for _, g in itertools.groupby(p)) < 2:
|
||||||
|
return False
|
||||||
|
|
||||||
|
return True
|
||||||
|
|
||||||
|
|
||||||
|
assert not is_valid("hijklmmn")
|
||||||
|
assert not is_valid("abbceffg")
|
||||||
|
assert not is_valid("abbcegjk")
|
||||||
|
assert is_valid("abcdffaa")
|
||||||
|
assert is_valid("ghjaabcc")
|
||||||
|
|
||||||
|
|
||||||
|
def increment(p: str) -> str:
|
||||||
|
if p[-1] == "z":
|
||||||
|
return increment(p[:-1]) + "a"
|
||||||
|
elif p[-1] in "iol":
|
||||||
|
return p[:-1] + chr(ord(p[-1]) + 2)
|
||||||
|
else:
|
||||||
|
return p[:-1] + chr(ord(p[-1]) + 1)
|
||||||
|
|
||||||
|
|
||||||
|
def find_next_password(p: str) -> str:
|
||||||
|
while not is_valid(p):
|
||||||
|
p = increment(p)
|
||||||
|
return p
|
||||||
|
|
||||||
|
|
||||||
|
line = sys.stdin.read().strip()
|
||||||
|
|
||||||
|
answer_1 = find_next_password(line)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = find_next_password(increment(answer_1))
|
||||||
|
print(f"answer 2 is {answer_2}")
|
27
src/holt59/aoc/2015/day12.py
Normal file
27
src/holt59/aoc/2015/day12.py
Normal file
@ -0,0 +1,27 @@
|
|||||||
|
import json
|
||||||
|
import sys
|
||||||
|
from typing import TypeAlias
|
||||||
|
|
||||||
|
JsonObject: TypeAlias = dict[str, "JsonObject"] | list["JsonObject"] | int | str
|
||||||
|
|
||||||
|
|
||||||
|
def json_sum(value: JsonObject, ignore: str | None = None) -> int:
|
||||||
|
if isinstance(value, str):
|
||||||
|
return 0
|
||||||
|
elif isinstance(value, int):
|
||||||
|
return value
|
||||||
|
elif isinstance(value, list):
|
||||||
|
return sum(json_sum(v, ignore=ignore) for v in value)
|
||||||
|
elif ignore not in value.values():
|
||||||
|
return sum(json_sum(v, ignore=ignore) for v in value.values())
|
||||||
|
else:
|
||||||
|
return 0
|
||||||
|
|
||||||
|
|
||||||
|
data: JsonObject = json.load(sys.stdin)
|
||||||
|
|
||||||
|
answer_1 = json_sum(data)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = json_sum(data, "red")
|
||||||
|
print(f"answer 2 is {answer_2}")
|
41
src/holt59/aoc/2015/day13.py
Normal file
41
src/holt59/aoc/2015/day13.py
Normal file
@ -0,0 +1,41 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
from typing import Literal, cast
|
||||||
|
|
||||||
|
import parse # type: ignore
|
||||||
|
|
||||||
|
|
||||||
|
def max_change_in_happiness(happiness: dict[str, dict[str, int]]) -> int:
|
||||||
|
guests = list(happiness)
|
||||||
|
return max(
|
||||||
|
sum(
|
||||||
|
happiness[o][d] + happiness[d][o]
|
||||||
|
for o, d in zip((guests[0],) + order, order + (guests[0],))
|
||||||
|
)
|
||||||
|
for order in map(tuple, itertools.permutations(guests[1:]))
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
happiness: dict[str, dict[str, int]] = defaultdict(dict)
|
||||||
|
for line in lines:
|
||||||
|
u1, gain_or_loose, hap, u2 = cast(
|
||||||
|
tuple[str, Literal["gain", "lose"], int, str],
|
||||||
|
parse.parse( # type: ignore
|
||||||
|
"{} would {} {:d} happiness units by sitting next to {}.", line
|
||||||
|
),
|
||||||
|
)
|
||||||
|
happiness[u1][u2] = hap if gain_or_loose == "gain" else -hap
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = max_change_in_happiness(happiness)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
for guest in list(happiness):
|
||||||
|
happiness["me"][guest] = 0
|
||||||
|
happiness[guest]["me"] = 0
|
||||||
|
|
||||||
|
answer_2 = max_change_in_happiness(happiness)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
62
src/holt59/aoc/2015/day14.py
Normal file
62
src/holt59/aoc/2015/day14.py
Normal file
@ -0,0 +1,62 @@
|
|||||||
|
import sys
|
||||||
|
from dataclasses import dataclass
|
||||||
|
from typing import Literal, cast
|
||||||
|
|
||||||
|
import parse # type: ignore
|
||||||
|
|
||||||
|
|
||||||
|
@dataclass(frozen=True)
|
||||||
|
class Reindeer:
|
||||||
|
name: str
|
||||||
|
speed: int
|
||||||
|
fly_time: int
|
||||||
|
rest_time: int
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
reindeers: list[Reindeer] = []
|
||||||
|
for line in lines:
|
||||||
|
reindeer, speed, speed_time, rest_time = cast(
|
||||||
|
tuple[str, int, int, int],
|
||||||
|
parse.parse( # type: ignore
|
||||||
|
"{} can fly {:d} km/s for {:d} seconds, "
|
||||||
|
"but then must rest for {:d} seconds.",
|
||||||
|
line,
|
||||||
|
),
|
||||||
|
)
|
||||||
|
reindeers.append(
|
||||||
|
Reindeer(name=reindeer, speed=speed, fly_time=speed_time, rest_time=rest_time)
|
||||||
|
)
|
||||||
|
|
||||||
|
target = 1000 if len(reindeers) <= 2 else 2503
|
||||||
|
|
||||||
|
states: dict[Reindeer, tuple[Literal["resting", "flying"], int]] = {
|
||||||
|
reindeer: ("resting", 0) for reindeer in reindeers
|
||||||
|
}
|
||||||
|
distances: dict[Reindeer, int] = {reindeer: 0 for reindeer in reindeers}
|
||||||
|
points: dict[Reindeer, int] = {reindeer: 0 for reindeer in reindeers}
|
||||||
|
|
||||||
|
for time in range(target):
|
||||||
|
for reindeer in reindeers:
|
||||||
|
if states[reindeer][0] == "flying":
|
||||||
|
distances[reindeer] += reindeer.speed
|
||||||
|
|
||||||
|
top_distance = max(distances.values())
|
||||||
|
for reindeer in reindeers:
|
||||||
|
if distances[reindeer] == top_distance:
|
||||||
|
points[reindeer] += 1
|
||||||
|
|
||||||
|
for reindeer in reindeers:
|
||||||
|
if states[reindeer][1] == time:
|
||||||
|
if states[reindeer][0] == "resting":
|
||||||
|
states[reindeer] = ("flying", time + reindeer.fly_time)
|
||||||
|
else:
|
||||||
|
states[reindeer] = ("resting", time + reindeer.rest_time)
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = max(distances.values())
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = max(points.values()) - 1
|
||||||
|
print(f"answer 2 is {answer_2}")
|
57
src/holt59/aoc/2015/day15.py
Normal file
57
src/holt59/aoc/2015/day15.py
Normal file
@ -0,0 +1,57 @@
|
|||||||
|
import math
|
||||||
|
import sys
|
||||||
|
from typing import Sequence, cast
|
||||||
|
|
||||||
|
import parse # type: ignore
|
||||||
|
|
||||||
|
|
||||||
|
def score(ingredients: list[list[int]], teaspoons: Sequence[int]) -> int:
|
||||||
|
return math.prod(
|
||||||
|
max(
|
||||||
|
0,
|
||||||
|
sum(
|
||||||
|
ingredient[prop] * teaspoon
|
||||||
|
for ingredient, teaspoon in zip(ingredients, teaspoons)
|
||||||
|
),
|
||||||
|
)
|
||||||
|
for prop in range(len(ingredients[0]) - 1)
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
ingredients: list[list[int]] = []
|
||||||
|
for line in lines:
|
||||||
|
_, *scores = cast(
|
||||||
|
tuple[str, int, int, int, int, int],
|
||||||
|
parse.parse( # type: ignore
|
||||||
|
"{}: capacity {:d}, durability {:d}, flavor {:d}, "
|
||||||
|
"texture {:d}, calories {:d}",
|
||||||
|
line,
|
||||||
|
),
|
||||||
|
)
|
||||||
|
ingredients.append(scores)
|
||||||
|
|
||||||
|
total_teaspoons = 100
|
||||||
|
calories: list[int] = []
|
||||||
|
scores: list[int] = []
|
||||||
|
|
||||||
|
for a in range(total_teaspoons + 1):
|
||||||
|
for b in range(total_teaspoons + 1 - a):
|
||||||
|
for c in range(total_teaspoons + 1 - a - b):
|
||||||
|
teaspoons = (a, b, c, total_teaspoons - a - b - c)
|
||||||
|
|
||||||
|
scores.append(score(ingredients, teaspoons))
|
||||||
|
calories.append(
|
||||||
|
sum(
|
||||||
|
ingredient[-1] * teaspoon
|
||||||
|
for ingredient, teaspoon in zip(ingredients, teaspoons)
|
||||||
|
)
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = max(scores)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = max(score for score, calory in zip(scores, calories) if calory == 500)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
51
src/holt59/aoc/2015/day16.py
Normal file
51
src/holt59/aoc/2015/day16.py
Normal file
@ -0,0 +1,51 @@
|
|||||||
|
import operator as op
|
||||||
|
import re
|
||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
from typing import Callable
|
||||||
|
|
||||||
|
MFCSAM: dict[str, int] = {
|
||||||
|
"children": 3,
|
||||||
|
"cats": 7,
|
||||||
|
"samoyeds": 2,
|
||||||
|
"pomeranians": 3,
|
||||||
|
"akitas": 0,
|
||||||
|
"vizslas": 0,
|
||||||
|
"goldfish": 5,
|
||||||
|
"trees": 3,
|
||||||
|
"cars": 2,
|
||||||
|
"perfumes": 1,
|
||||||
|
}
|
||||||
|
|
||||||
|
lines = sys.stdin.readlines()
|
||||||
|
|
||||||
|
aunts: list[dict[str, int]] = [
|
||||||
|
{
|
||||||
|
match[1]: int(match[2])
|
||||||
|
for match in re.findall(R"((?P<compound>[^:, ]+): (?P<quantity>\d+))", line)
|
||||||
|
}
|
||||||
|
for line in lines
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
def match(operators: dict[str, Callable[[int, int], bool]]) -> int:
|
||||||
|
return next(
|
||||||
|
i
|
||||||
|
for i, aunt in enumerate(aunts, start=1)
|
||||||
|
if all(operators[k](aunt[k], MFCSAM[k]) for k in aunt)
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = match(defaultdict(lambda: op.eq))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = match(
|
||||||
|
defaultdict(
|
||||||
|
lambda: op.eq,
|
||||||
|
trees=op.gt,
|
||||||
|
cats=op.gt,
|
||||||
|
pomeranians=op.lt,
|
||||||
|
goldfish=op.lt,
|
||||||
|
)
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
30
src/holt59/aoc/2015/day17.py
Normal file
30
src/holt59/aoc/2015/day17.py
Normal file
@ -0,0 +1,30 @@
|
|||||||
|
import sys
|
||||||
|
from typing import Iterator
|
||||||
|
|
||||||
|
|
||||||
|
def iter_combinations(value: int, containers: list[int]) -> Iterator[tuple[int, ...]]:
|
||||||
|
if value < 0:
|
||||||
|
return
|
||||||
|
|
||||||
|
if value == 0:
|
||||||
|
yield ()
|
||||||
|
|
||||||
|
for i in range(len(containers)):
|
||||||
|
for combination in iter_combinations(
|
||||||
|
value - containers[i], containers[i + 1 :]
|
||||||
|
):
|
||||||
|
yield (containers[i],) + combination
|
||||||
|
|
||||||
|
|
||||||
|
containers = [int(c) for c in sys.stdin.read().split()]
|
||||||
|
total = 25 if len(containers) <= 5 else 150
|
||||||
|
|
||||||
|
combinations = [combination for combination in iter_combinations(total, containers)]
|
||||||
|
|
||||||
|
answer_1 = len(combinations)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
min_containers = min(len(combination) for combination in combinations)
|
||||||
|
|
||||||
|
answer_2 = sum(1 for combination in combinations if len(combination) == min_containers)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
66
src/holt59/aoc/2015/day18.py
Normal file
66
src/holt59/aoc/2015/day18.py
Normal file
@ -0,0 +1,66 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
from numpy.typing import NDArray
|
||||||
|
|
||||||
|
grid0 = np.array([[c == "#" for c in line] for line in sys.stdin.read().splitlines()])
|
||||||
|
|
||||||
|
# add an always off circle around
|
||||||
|
grid0 = np.concatenate(
|
||||||
|
[
|
||||||
|
np.zeros((grid0.shape[0] + 2, 1), dtype=bool),
|
||||||
|
np.concatenate(
|
||||||
|
[
|
||||||
|
np.zeros((1, grid0.shape[1]), dtype=bool),
|
||||||
|
grid0,
|
||||||
|
np.zeros((1, grid0.shape[1]), dtype=bool),
|
||||||
|
]
|
||||||
|
),
|
||||||
|
np.zeros((grid0.shape[0] + 2, 1), dtype=bool),
|
||||||
|
],
|
||||||
|
axis=1,
|
||||||
|
)
|
||||||
|
|
||||||
|
moves = list(itertools.product([-1, 0, 1], repeat=2))
|
||||||
|
moves.remove((0, 0))
|
||||||
|
|
||||||
|
jjs, iis = np.meshgrid(
|
||||||
|
np.arange(1, grid0.shape[0] - 1, dtype=int),
|
||||||
|
np.arange(1, grid0.shape[1] - 1, dtype=int),
|
||||||
|
)
|
||||||
|
iis, jjs = iis.flatten(), jjs.flatten()
|
||||||
|
|
||||||
|
ins = iis[:, None] + np.array(moves)[:, 0]
|
||||||
|
jns = jjs[:, None] + np.array(moves)[:, 1]
|
||||||
|
|
||||||
|
|
||||||
|
def game_of_life(grid: NDArray[np.bool_]) -> NDArray[np.bool_]:
|
||||||
|
neighbors_on = grid[ins, jns].sum(axis=1)
|
||||||
|
cells_on = grid[iis, jjs]
|
||||||
|
|
||||||
|
grid = np.zeros_like(grid)
|
||||||
|
grid[iis, jjs] = (neighbors_on == 3) | (cells_on & (neighbors_on == 2))
|
||||||
|
|
||||||
|
return grid
|
||||||
|
|
||||||
|
|
||||||
|
grid = grid0
|
||||||
|
n_steps = 4 if len(grid) < 10 else 100
|
||||||
|
for _ in range(n_steps):
|
||||||
|
grid = game_of_life(grid)
|
||||||
|
|
||||||
|
answer_1 = grid.sum()
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
|
||||||
|
n_steps = 5 if len(grid) < 10 else 100
|
||||||
|
grid = grid0
|
||||||
|
for _ in range(n_steps):
|
||||||
|
grid[[1, 1, -2, -2], [1, -2, 1, -2]] = True
|
||||||
|
grid = game_of_life(grid)
|
||||||
|
|
||||||
|
grid[[1, 1, -2, -2], [1, -2, 1, -2]] = True
|
||||||
|
|
||||||
|
answer_2 = sum(cell for line in grid for cell in line)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
56
src/holt59/aoc/2015/day19.py
Normal file
56
src/holt59/aoc/2015/day19.py
Normal file
@ -0,0 +1,56 @@
|
|||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
|
||||||
|
replacements_s, molecule = sys.stdin.read().split("\n\n")
|
||||||
|
|
||||||
|
REPLACEMENTS: dict[str, list[str]] = defaultdict(list)
|
||||||
|
for replacement_s in replacements_s.splitlines():
|
||||||
|
p = replacement_s.split(" => ")
|
||||||
|
REPLACEMENTS[p[0]].append(p[1])
|
||||||
|
molecule = molecule.strip()
|
||||||
|
|
||||||
|
generated = [
|
||||||
|
molecule[:i] + replacement + molecule[i + len(symbol) :]
|
||||||
|
for symbol, replacements in REPLACEMENTS.items()
|
||||||
|
for replacement in replacements
|
||||||
|
for i in range(len(molecule))
|
||||||
|
if molecule[i:].startswith(symbol)
|
||||||
|
]
|
||||||
|
|
||||||
|
answer_1 = len(set(generated))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
inversion: dict[str, str] = {
|
||||||
|
replacement: symbol
|
||||||
|
for symbol, replacements in REPLACEMENTS.items()
|
||||||
|
for replacement in replacements
|
||||||
|
}
|
||||||
|
|
||||||
|
# there is actually only one way to create the molecule, and we can greedily replace
|
||||||
|
# tokens with their replacements, e.g., if H => OH then we can replace OH by H directly
|
||||||
|
# without thinking
|
||||||
|
|
||||||
|
count = 0
|
||||||
|
while molecule != "e":
|
||||||
|
i = 0
|
||||||
|
m2 = ""
|
||||||
|
while i < len(molecule):
|
||||||
|
found = False
|
||||||
|
for replacement in inversion:
|
||||||
|
if molecule[i:].startswith(replacement):
|
||||||
|
m2 += inversion[replacement]
|
||||||
|
i += len(replacement)
|
||||||
|
count += 1
|
||||||
|
found = True
|
||||||
|
break
|
||||||
|
|
||||||
|
if not found:
|
||||||
|
m2 += molecule[i]
|
||||||
|
i += 1
|
||||||
|
|
||||||
|
# print(m2)
|
||||||
|
molecule = m2
|
||||||
|
|
||||||
|
|
||||||
|
answer_2 = count
|
||||||
|
print(f"answer 2 is {count}")
|
20
src/holt59/aoc/2015/day2.py
Normal file
20
src/holt59/aoc/2015/day2.py
Normal file
@ -0,0 +1,20 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
length, width, height = np.array(
|
||||||
|
[[int(c) for c in line.split("x")] for line in lines]
|
||||||
|
).T
|
||||||
|
|
||||||
|
lw, wh, hl = (length * width, width * height, height * length)
|
||||||
|
|
||||||
|
answer_1 = np.sum(2 * (lw + wh + hl) + np.min(np.stack([lw, wh, hl]), axis=0))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = np.sum(
|
||||||
|
length * width * height
|
||||||
|
+ 2 * np.min(np.stack([length + width, length + height, height + width]), axis=0)
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
28
src/holt59/aoc/2015/day20.py
Normal file
28
src/holt59/aoc/2015/day20.py
Normal file
@ -0,0 +1,28 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
|
||||||
|
target = int(sys.stdin.read())
|
||||||
|
|
||||||
|
|
||||||
|
def presents(n: int, elf: int, max: int = target) -> int:
|
||||||
|
count = 0
|
||||||
|
k = 1
|
||||||
|
while k * k < n:
|
||||||
|
if n % k == 0:
|
||||||
|
if n // k <= max:
|
||||||
|
count += elf * k
|
||||||
|
if k <= max:
|
||||||
|
count += elf * (n // k)
|
||||||
|
k += 1
|
||||||
|
|
||||||
|
if k * k == n and k <= max:
|
||||||
|
count += elf * k
|
||||||
|
|
||||||
|
return count
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = next(n for n in itertools.count(1) if presents(n, 10) >= target)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = next(n for n in itertools.count(1) if presents(n, 11, 50) >= target)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
66
src/holt59/aoc/2015/day21.py
Normal file
66
src/holt59/aoc/2015/day21.py
Normal file
@ -0,0 +1,66 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
from math import ceil
|
||||||
|
from typing import TypeAlias
|
||||||
|
|
||||||
|
Modifier: TypeAlias = tuple[str, int, int, int]
|
||||||
|
|
||||||
|
WEAPONS: list[Modifier] = [
|
||||||
|
("Dagger", 8, 4, 0),
|
||||||
|
("Shortsword", 10, 5, 0),
|
||||||
|
("Warhammer", 25, 6, 0),
|
||||||
|
("Longsword", 40, 7, 0),
|
||||||
|
("Greataxe", 74, 8, 0),
|
||||||
|
]
|
||||||
|
|
||||||
|
ARMORS: list[Modifier] = [
|
||||||
|
("", 0, 0, 0),
|
||||||
|
("Leather", 13, 0, 1),
|
||||||
|
("Chainmail", 31, 0, 2),
|
||||||
|
("Splintmail", 53, 0, 3),
|
||||||
|
("Bandedmail", 75, 0, 4),
|
||||||
|
("Platemail", 102, 0, 5),
|
||||||
|
]
|
||||||
|
|
||||||
|
RINGS: list[Modifier] = [
|
||||||
|
("", 0, 0, 0),
|
||||||
|
("Damage +1", 25, 1, 0),
|
||||||
|
("Damage +2", 50, 2, 0),
|
||||||
|
("Damage +3", 100, 3, 0),
|
||||||
|
("Defense +1", 20, 0, 1),
|
||||||
|
("Defense +2", 40, 0, 2),
|
||||||
|
("Defense +3", 80, 0, 3),
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
player_hp = 100
|
||||||
|
|
||||||
|
boss_attack = int(lines[1].split(":")[1].strip())
|
||||||
|
boss_armor = int(lines[2].split(":")[1].strip())
|
||||||
|
boss_hp = int(lines[0].split(":")[1].strip())
|
||||||
|
|
||||||
|
|
||||||
|
min_cost, max_cost = 1_000_000, 0
|
||||||
|
for equipments in itertools.product(WEAPONS, ARMORS, RINGS, RINGS):
|
||||||
|
if equipments[-1][0] != "" and equipments[-2] == equipments[-1]:
|
||||||
|
continue
|
||||||
|
|
||||||
|
cost, player_attack, player_armor = (
|
||||||
|
sum(equipment[1:][k] for equipment in equipments) for k in range(3)
|
||||||
|
)
|
||||||
|
|
||||||
|
if ceil(boss_hp / max(1, player_attack - boss_armor)) <= ceil(
|
||||||
|
player_hp / max(1, boss_attack - player_armor)
|
||||||
|
):
|
||||||
|
min_cost = min(cost, min_cost)
|
||||||
|
else:
|
||||||
|
max_cost = max(cost, max_cost)
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = min_cost
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = max_cost
|
||||||
|
print(f"answer 2 is {answer_2}")
|
34
src/holt59/aoc/2015/day3.py
Normal file
34
src/holt59/aoc/2015/day3.py
Normal file
@ -0,0 +1,34 @@
|
|||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
|
||||||
|
line = sys.stdin.read().strip()
|
||||||
|
|
||||||
|
|
||||||
|
def process(directions: str) -> dict[tuple[int, int], int]:
|
||||||
|
counts: dict[tuple[int, int], int] = defaultdict(lambda: 0)
|
||||||
|
counts[0, 0] = 1
|
||||||
|
x, y = (0, 0)
|
||||||
|
|
||||||
|
for c in directions:
|
||||||
|
match c:
|
||||||
|
case ">":
|
||||||
|
x += 1
|
||||||
|
case "<":
|
||||||
|
x -= 1
|
||||||
|
case "^":
|
||||||
|
y -= 1
|
||||||
|
case "v":
|
||||||
|
y += 1
|
||||||
|
case _:
|
||||||
|
raise ValueError()
|
||||||
|
|
||||||
|
counts[x, y] += 1
|
||||||
|
|
||||||
|
return counts
|
||||||
|
|
||||||
|
|
||||||
|
answer_1 = len(process(line))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = len(process(line[::2]) | process(line[1::2]))
|
||||||
|
print(f"answer 2 is {answer_2}")
|
16
src/holt59/aoc/2015/day4.py
Normal file
16
src/holt59/aoc/2015/day4.py
Normal file
@ -0,0 +1,16 @@
|
|||||||
|
import hashlib
|
||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
|
||||||
|
line = sys.stdin.read().strip()
|
||||||
|
|
||||||
|
it = iter(itertools.count(1))
|
||||||
|
answer_1 = next(
|
||||||
|
i for i in it if hashlib.md5(f"{line}{i}".encode()).hexdigest().startswith("00000")
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = next(
|
||||||
|
i for i in it if hashlib.md5(f"{line}{i}".encode()).hexdigest().startswith("000000")
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
36
src/holt59/aoc/2015/day5.py
Normal file
36
src/holt59/aoc/2015/day5.py
Normal file
@ -0,0 +1,36 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
VOWELS = "aeiou"
|
||||||
|
FORBIDDEN = {"ab", "cd", "pq", "xy"}
|
||||||
|
|
||||||
|
|
||||||
|
def is_nice_1(s: str) -> bool:
|
||||||
|
if sum(c in VOWELS for c in s) < 3:
|
||||||
|
return False
|
||||||
|
|
||||||
|
if not any(a == b for a, b in zip(s[:-1:], s[1::])):
|
||||||
|
return False
|
||||||
|
|
||||||
|
if any(s.find(f) >= 0 for f in FORBIDDEN):
|
||||||
|
return False
|
||||||
|
|
||||||
|
return True
|
||||||
|
|
||||||
|
|
||||||
|
def is_nice_2(s: str) -> bool:
|
||||||
|
if not any(s.find(s[i : i + 2], i + 2) >= 0 for i in range(len(s))):
|
||||||
|
return False
|
||||||
|
|
||||||
|
if not any(a == b for a, b in zip(s[:-1:], s[2::])):
|
||||||
|
return False
|
||||||
|
|
||||||
|
return True
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
answer_1 = sum(map(is_nice_1, lines))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = sum(map(is_nice_2, lines))
|
||||||
|
print(f"answer 2 is {answer_2}")
|
33
src/holt59/aoc/2015/day6.py
Normal file
33
src/holt59/aoc/2015/day6.py
Normal file
@ -0,0 +1,33 @@
|
|||||||
|
import sys
|
||||||
|
from typing import Literal, cast
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
import parse # type: ignore
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
lights_1 = np.zeros((1000, 1000), dtype=bool)
|
||||||
|
lights_2 = np.zeros((1000, 1000), dtype=int)
|
||||||
|
for line in lines:
|
||||||
|
action, sx, sy, ex, ey = cast(
|
||||||
|
tuple[Literal["turn on", "turn off", "toggle"], int, int, int, int],
|
||||||
|
parse.parse("{} {:d},{:d} through {:d},{:d}", line), # type: ignore
|
||||||
|
)
|
||||||
|
ex, ey = ex + 1, ey + 1
|
||||||
|
|
||||||
|
match action:
|
||||||
|
case "turn on":
|
||||||
|
lights_1[sx:ex, sy:ey] = True
|
||||||
|
lights_2[sx:ex, sy:ey] += 1
|
||||||
|
case "turn off":
|
||||||
|
lights_1[sx:ex, sy:ey] = False
|
||||||
|
lights_2[sx:ex, sy:ey] = np.maximum(lights_2[sx:ex, sy:ey] - 1, 0)
|
||||||
|
case "toggle":
|
||||||
|
lights_1[sx:ex, sy:ey] = ~lights_1[sx:ex, sy:ey]
|
||||||
|
lights_2[sx:ex, sy:ey] += 2
|
||||||
|
|
||||||
|
answer_1 = lights_1.sum()
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = lights_2.sum()
|
||||||
|
print(f"answer 2 is {answer_2}")
|
101
src/holt59/aoc/2015/day7.py
Normal file
101
src/holt59/aoc/2015/day7.py
Normal file
@ -0,0 +1,101 @@
|
|||||||
|
import logging
|
||||||
|
import operator
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from typing import Callable
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
logging.basicConfig(level=logging.INFO if VERBOSE else logging.WARNING)
|
||||||
|
|
||||||
|
OPERATORS = {
|
||||||
|
"AND": operator.and_,
|
||||||
|
"OR": operator.or_,
|
||||||
|
"LSHIFT": operator.lshift,
|
||||||
|
"RSHIFT": operator.rshift,
|
||||||
|
}
|
||||||
|
|
||||||
|
ValueGetter = Callable[[dict[str, int]], int]
|
||||||
|
Signals = dict[
|
||||||
|
str,
|
||||||
|
tuple[
|
||||||
|
tuple[str, str],
|
||||||
|
tuple[ValueGetter, ValueGetter],
|
||||||
|
Callable[[int, int], int],
|
||||||
|
],
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
def zero_op(_a: int, _b: int) -> int:
|
||||||
|
return 0
|
||||||
|
|
||||||
|
|
||||||
|
def value_of(key: str) -> tuple[str, Callable[[dict[str, int]], int]]:
|
||||||
|
try:
|
||||||
|
return "", lambda _p, _v=int(key): _v
|
||||||
|
except ValueError:
|
||||||
|
return key, lambda values: values[key]
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
signals: Signals = {}
|
||||||
|
values: dict[str, int] = {"": 0}
|
||||||
|
|
||||||
|
for line in lines:
|
||||||
|
command, signal = line.split(" -> ")
|
||||||
|
|
||||||
|
if command.startswith("NOT"):
|
||||||
|
name = command.split(" ")[1]
|
||||||
|
signals[signal] = (
|
||||||
|
(name, ""),
|
||||||
|
(lambda values, _n=name: values[_n], lambda _v: 0),
|
||||||
|
lambda a, _b: ~a,
|
||||||
|
)
|
||||||
|
|
||||||
|
elif not any(command.find(name) >= 0 for name in OPERATORS):
|
||||||
|
try:
|
||||||
|
values[signal] = int(command)
|
||||||
|
except ValueError:
|
||||||
|
signals[signal] = (
|
||||||
|
(command, ""),
|
||||||
|
(lambda values, _c=command: values[_c], lambda _v: 0),
|
||||||
|
lambda a, _b: a,
|
||||||
|
)
|
||||||
|
|
||||||
|
else:
|
||||||
|
op: Callable[[int, int], int] = zero_op
|
||||||
|
lhs_s, rhs_s = "", ""
|
||||||
|
|
||||||
|
for name in OPERATORS:
|
||||||
|
if command.find(name) >= 0:
|
||||||
|
op = OPERATORS[name]
|
||||||
|
lhs_s, rhs_s = command.split(f" {name} ")
|
||||||
|
break
|
||||||
|
|
||||||
|
lhs_s, lhs_fn = value_of(lhs_s)
|
||||||
|
rhs_s, rhs_fn = value_of(rhs_s)
|
||||||
|
|
||||||
|
signals[signal] = ((lhs_s, rhs_s), (lhs_fn, rhs_fn), op)
|
||||||
|
|
||||||
|
|
||||||
|
def process(
|
||||||
|
signals: Signals,
|
||||||
|
values: dict[str, int],
|
||||||
|
) -> dict[str, int]:
|
||||||
|
while signals:
|
||||||
|
signal = next(s for s in signals if all(p in values for p in signals[s][0]))
|
||||||
|
_, deps, command = signals[signal]
|
||||||
|
values[signal] = command(deps[0](values), deps[1](values)) % 65536
|
||||||
|
del signals[signal]
|
||||||
|
|
||||||
|
return values
|
||||||
|
|
||||||
|
|
||||||
|
values_1 = process(signals.copy(), values.copy())
|
||||||
|
logging.info("\n" + "\n".join(f"{k}: {values_1[k]}" for k in sorted(values_1)))
|
||||||
|
answer_1 = values_1["a"]
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
values_2 = process(signals.copy(), values | {"b": values_1["a"]})
|
||||||
|
answer_2 = values_2["a"]
|
||||||
|
print(f"answer 2 is {answer_2}")
|
35
src/holt59/aoc/2015/day8.py
Normal file
35
src/holt59/aoc/2015/day8.py
Normal file
@ -0,0 +1,35 @@
|
|||||||
|
import logging
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
logging.basicConfig(level=logging.INFO if VERBOSE else logging.WARNING)
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
answer_1 = sum(
|
||||||
|
# left and right quotes (not in memory)
|
||||||
|
2
|
||||||
|
# each \\ adds one character in the literals (compared to memory)
|
||||||
|
+ line.count(R"\\")
|
||||||
|
# each \" adds one character in the literals (compared to memory)
|
||||||
|
+ line[1:-1].count(R"\"")
|
||||||
|
# each \xFF adds 3 characters in the literals (compared to memory), but we must not
|
||||||
|
# count A\\x (A != \), but we must count A\\\x (A != \) - in practice we should also
|
||||||
|
# avoid \\\\x, etc., but this does not occur in the examples and the actual input
|
||||||
|
+ 3 * (line.count(R"\x") - line.count(R"\\x") + line.count(R"\\\x"))
|
||||||
|
for line in lines
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = sum(
|
||||||
|
# needs to wrap in quotes (2 characters)
|
||||||
|
2
|
||||||
|
# needs to escape every \ with an extra \
|
||||||
|
+ line.count("\\")
|
||||||
|
# needs to escape every " with an extra \ (including the first and last ones)
|
||||||
|
+ line.count('"')
|
||||||
|
for line in lines
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
26
src/holt59/aoc/2015/day9.py
Normal file
26
src/holt59/aoc/2015/day9.py
Normal file
@ -0,0 +1,26 @@
|
|||||||
|
import itertools
|
||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
from typing import cast
|
||||||
|
|
||||||
|
import parse # type: ignore
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
distances: dict[str, dict[str, int]] = defaultdict(dict)
|
||||||
|
for line in lines:
|
||||||
|
origin, destination, length = cast(
|
||||||
|
tuple[str, str, int], parse.parse("{} to {} = {:d}", line) # type: ignore
|
||||||
|
)
|
||||||
|
distances[origin][destination] = distances[destination][origin] = length
|
||||||
|
|
||||||
|
distance_of_routes = {
|
||||||
|
route: sum(distances[o][d] for o, d in zip(route[:-1], route[1:]))
|
||||||
|
for route in map(tuple, itertools.permutations(distances))
|
||||||
|
}
|
||||||
|
|
||||||
|
answer_1 = min(distance_of_routes.values())
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
answer_2 = max(distance_of_routes.values())
|
||||||
|
print(f"answer 2 is {answer_2}")
|
14
src/holt59/aoc/2021/day1.py
Normal file
14
src/holt59/aoc/2021/day1.py
Normal file
@ -0,0 +1,14 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
values = [int(line) for line in lines]
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(v2 > v1 for v1, v2 in zip(values[:-1], values[1:]))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
runnings = [sum(values[i : i + 3]) for i in range(len(values) - 2)]
|
||||||
|
answer_2 = sum(v2 > v1 for v1, v2 in zip(runnings[:-1], runnings[1:]))
|
||||||
|
print(f"answer 2 is {answer_2}")
|
40
src/holt59/aoc/2021/day2.py
Normal file
40
src/holt59/aoc/2021/day2.py
Normal file
@ -0,0 +1,40 @@
|
|||||||
|
import sys
|
||||||
|
from math import prod
|
||||||
|
from typing import Literal, cast
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
commands = [
|
||||||
|
(cast(Literal["forward", "up", "down"], (p := line.split())[0]), int(p[1]))
|
||||||
|
for line in lines
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
def depth_and_position(use_aim: bool):
|
||||||
|
aim, pos, depth = 0, 0, 0
|
||||||
|
for command, value in commands:
|
||||||
|
d_depth = 0
|
||||||
|
match command:
|
||||||
|
case "forward":
|
||||||
|
pos += value
|
||||||
|
depth += value * aim
|
||||||
|
case "up":
|
||||||
|
d_depth = -value
|
||||||
|
case "down":
|
||||||
|
d_depth = value
|
||||||
|
|
||||||
|
if use_aim:
|
||||||
|
aim += d_depth
|
||||||
|
else:
|
||||||
|
depth += value
|
||||||
|
|
||||||
|
return depth, pos
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = prod(depth_and_position(False))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = prod(depth_and_position(True))
|
||||||
|
print(f"answer 2 is {answer_2}")
|
39
src/holt59/aoc/2021/day3.py
Normal file
39
src/holt59/aoc/2021/day3.py
Normal file
@ -0,0 +1,39 @@
|
|||||||
|
import sys
|
||||||
|
from collections import Counter
|
||||||
|
from typing import Literal
|
||||||
|
|
||||||
|
|
||||||
|
def generator_rating(
|
||||||
|
values: list[str], most_common: bool, default: Literal["0", "1"]
|
||||||
|
) -> str:
|
||||||
|
index = 0
|
||||||
|
most_common_idx = 0 if most_common else 1
|
||||||
|
|
||||||
|
while len(values) > 1:
|
||||||
|
cnt = Counter(value[index] for value in values)
|
||||||
|
bit = cnt.most_common(2)[most_common_idx][0]
|
||||||
|
if cnt["0"] == cnt["1"]:
|
||||||
|
bit = default
|
||||||
|
values = [value for value in values if value[index] == bit]
|
||||||
|
index += 1
|
||||||
|
|
||||||
|
return values[0]
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
most_and_least_common = [
|
||||||
|
tuple(Counter(line[col] for line in lines).most_common(2)[m][0] for m in range(2))
|
||||||
|
for col in range(len(lines[0]))
|
||||||
|
]
|
||||||
|
gamma_rate = int("".join(most for most, _ in most_and_least_common), base=2)
|
||||||
|
epsilon_rate = int("".join(least for _, least in most_and_least_common), base=2)
|
||||||
|
print(f"answer 1 is {gamma_rate * epsilon_rate}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
oxygen_generator_rating = int(generator_rating(lines, True, "1"), base=2)
|
||||||
|
co2_scrubber_rating = int(generator_rating(lines, False, "0"), base=2)
|
||||||
|
answer_2 = oxygen_generator_rating * co2_scrubber_rating
|
||||||
|
print(f"answer 2 is {answer_2}")
|
45
src/holt59/aoc/2021/day4.py
Normal file
45
src/holt59/aoc/2021/day4.py
Normal file
@ -0,0 +1,45 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
numbers = [int(c) for c in lines[0].split(",")]
|
||||||
|
|
||||||
|
boards = np.asarray(
|
||||||
|
[
|
||||||
|
[[int(c) for c in line.split()] for line in lines[start : start + 5]]
|
||||||
|
for start in range(2, len(lines), 6)
|
||||||
|
]
|
||||||
|
)
|
||||||
|
|
||||||
|
# (round, score) for each board (-1 when not found)
|
||||||
|
winning_rounds: list[tuple[int, int]] = [(-1, -1) for _ in range(len(boards))]
|
||||||
|
marked = np.zeros_like(boards, dtype=bool)
|
||||||
|
|
||||||
|
for round, number in enumerate(numbers):
|
||||||
|
# mark boards
|
||||||
|
marked[boards == number] = True
|
||||||
|
|
||||||
|
# check each board for winning
|
||||||
|
for index in range(len(boards)):
|
||||||
|
if winning_rounds[index][0] > 0:
|
||||||
|
continue
|
||||||
|
|
||||||
|
if np.any(np.all(marked[index], axis=0) | np.all(marked[index], axis=1)):
|
||||||
|
winning_rounds[index] = (
|
||||||
|
round,
|
||||||
|
number * int(np.sum(boards[index][~marked[index]])),
|
||||||
|
)
|
||||||
|
|
||||||
|
# all boards are winning - break
|
||||||
|
if np.all(marked.all(axis=1) | marked.all(axis=2)):
|
||||||
|
break
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
(_, score) = min(winning_rounds, key=lambda w: w[0])
|
||||||
|
print(f"answer 1 is {score}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
(_, score) = max(winning_rounds, key=lambda w: w[0])
|
||||||
|
print(f"answer 2 is {score}")
|
@ -1,7 +1,4 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from collections import defaultdict
|
|
||||||
|
|
||||||
import numpy as np
|
import numpy as np
|
||||||
|
|
||||||
@ -34,7 +31,6 @@ counts_1 = np.zeros((y_max + 1, x_max + 1), dtype=int)
|
|||||||
counts_2 = counts_1.copy()
|
counts_2 = counts_1.copy()
|
||||||
|
|
||||||
for (x1, y1), (x2, y2) in sections:
|
for (x1, y1), (x2, y2) in sections:
|
||||||
|
|
||||||
x_rng = range(x1, x2 + 1, 1) if x2 >= x1 else range(x1, x2 - 1, -1)
|
x_rng = range(x1, x2 + 1, 1) if x2 >= x1 else range(x1, x2 - 1, -1)
|
||||||
y_rng = range(y1, y2 + 1, 1) if y2 >= y1 else range(y1, y2 - 1, -1)
|
y_rng = range(y1, y2 + 1, 1) if y2 >= y1 else range(y1, y2 - 1, -1)
|
||||||
|
|
21
src/holt59/aoc/2021/day6.py
Normal file
21
src/holt59/aoc/2021/day6.py
Normal file
@ -0,0 +1,21 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
values = [int(c) for c in sys.stdin.read().strip().split(",")]
|
||||||
|
|
||||||
|
days = 256
|
||||||
|
lanterns = {day: 0 for day in range(days)}
|
||||||
|
for value in values:
|
||||||
|
for day in range(value, days, 7):
|
||||||
|
lanterns[day] += 1
|
||||||
|
|
||||||
|
for day in range(days):
|
||||||
|
for day2 in range(day + 9, days, 7):
|
||||||
|
lanterns[day2] += lanterns[day]
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(v for k, v in lanterns.items() if k < 80) + len(values)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = sum(lanterns.values()) + len(values)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
21
src/holt59/aoc/2021/day7.py
Normal file
21
src/holt59/aoc/2021/day7.py
Normal file
@ -0,0 +1,21 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
|
||||||
|
positions = np.asarray([int(c) for c in sys.stdin.read().strip().split(",")])
|
||||||
|
|
||||||
|
min_position, max_position = positions.min(), positions.max()
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = min(
|
||||||
|
np.sum(np.abs(positions - position))
|
||||||
|
for position in range(min_position, max_position + 1)
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = min(
|
||||||
|
np.sum(abs(positions - position) * (abs(positions - position) + 1) // 2)
|
||||||
|
for position in range(min_position, max_position + 1)
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
87
src/holt59/aoc/2021/day8.py
Normal file
87
src/holt59/aoc/2021/day8.py
Normal file
@ -0,0 +1,87 @@
|
|||||||
|
import itertools
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
digits = {
|
||||||
|
"abcefg": 0,
|
||||||
|
"cf": 1,
|
||||||
|
"acdeg": 2,
|
||||||
|
"acdfg": 3,
|
||||||
|
"bcdf": 4,
|
||||||
|
"abdfg": 5,
|
||||||
|
"abdefg": 6,
|
||||||
|
"acf": 7,
|
||||||
|
"abcdefg": 8,
|
||||||
|
"abcdfg": 9,
|
||||||
|
}
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
lengths = {len(k) for k, v in digits.items() if v in (1, 4, 7, 8)}
|
||||||
|
answer_1 = sum(
|
||||||
|
len(p) in lengths for line in lines for p in line.split("|")[1].strip().split()
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
values: list[int] = []
|
||||||
|
|
||||||
|
for line in lines:
|
||||||
|
parts = line.split("|")
|
||||||
|
broken_digits = sorted(parts[0].strip().split(), key=len)
|
||||||
|
|
||||||
|
per_length = {
|
||||||
|
k: list(v)
|
||||||
|
for k, v in itertools.groupby(sorted(broken_digits, key=len), key=len)
|
||||||
|
}
|
||||||
|
|
||||||
|
# a can be found immediately
|
||||||
|
a = next(u for u in per_length[3][0] if u not in per_length[2][0])
|
||||||
|
|
||||||
|
# c and f have only two possible values corresponding to the single entry of
|
||||||
|
# length 2
|
||||||
|
cf = list(per_length[2][0])
|
||||||
|
|
||||||
|
# the only digit of length 4 contains bcdf, so we can deduce bd by removing cf
|
||||||
|
bd = [u for u in per_length[4][0] if u not in cf]
|
||||||
|
|
||||||
|
# the 3 digits of length 5 have a, d and g in common
|
||||||
|
adg = [u for u in per_length[5][0] if all(u in pe for pe in per_length[5][1:])]
|
||||||
|
|
||||||
|
# we can remove a
|
||||||
|
dg = [u for u in adg if u != a]
|
||||||
|
|
||||||
|
# we can deduce d and g
|
||||||
|
d = next(u for u in dg if u in bd)
|
||||||
|
g = next(u for u in dg if u != d)
|
||||||
|
|
||||||
|
# then b
|
||||||
|
b = next(u for u in bd if u != d)
|
||||||
|
|
||||||
|
# f is in the three 6-length digits, while c is only in 2
|
||||||
|
f = next(u for u in cf if all(u in p for p in per_length[6]))
|
||||||
|
|
||||||
|
# c is not f
|
||||||
|
c = next(u for u in cf if u != f)
|
||||||
|
|
||||||
|
# e is the last one
|
||||||
|
e = next(u for u in "abcdefg" if u not in {a, b, c, d, f, g})
|
||||||
|
|
||||||
|
mapping = dict(zip((a, b, c, d, e, f, g), "abcdefg"))
|
||||||
|
|
||||||
|
value = 0
|
||||||
|
for number in parts[1].strip().split():
|
||||||
|
digit = "".join(sorted(mapping[c] for c in number))
|
||||||
|
value = 10 * value + digits[digit]
|
||||||
|
|
||||||
|
if VERBOSE:
|
||||||
|
print(value)
|
||||||
|
|
||||||
|
values.append(value)
|
||||||
|
|
||||||
|
|
||||||
|
answer_2 = sum(values)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
44
src/holt59/aoc/2021/day9.py
Normal file
44
src/holt59/aoc/2021/day9.py
Normal file
@ -0,0 +1,44 @@
|
|||||||
|
import sys
|
||||||
|
from math import prod
|
||||||
|
|
||||||
|
values = [[int(c) for c in row] for row in sys.stdin.read().splitlines()]
|
||||||
|
n_rows, n_cols = len(values), len(values[0])
|
||||||
|
|
||||||
|
|
||||||
|
def neighbors(point: tuple[int, int]):
|
||||||
|
i, j = point
|
||||||
|
for di, dj in ((-1, 0), (+1, 0), (0, -1), (0, +1)):
|
||||||
|
if 0 <= i + di < n_rows and 0 <= j + dj < n_cols:
|
||||||
|
yield (i + di, j + dj)
|
||||||
|
|
||||||
|
|
||||||
|
def basin(start: tuple[int, int]) -> set[tuple[int, int]]:
|
||||||
|
visited: set[tuple[int, int]] = set()
|
||||||
|
queue = [start]
|
||||||
|
|
||||||
|
while queue:
|
||||||
|
i, j = queue.pop()
|
||||||
|
|
||||||
|
if (i, j) in visited or values[i][j] == 9:
|
||||||
|
continue
|
||||||
|
|
||||||
|
visited.add((i, j))
|
||||||
|
queue.extend(neighbors((i, j)))
|
||||||
|
|
||||||
|
return visited
|
||||||
|
|
||||||
|
|
||||||
|
low_points = [
|
||||||
|
(i, j)
|
||||||
|
for i in range(n_rows)
|
||||||
|
for j in range(n_cols)
|
||||||
|
if all(values[ti][tj] > values[i][j] for ti, tj in neighbors((i, j)))
|
||||||
|
]
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(values[i][j] + 1 for i, j in low_points)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = prod(sorted(len(basin(point)) for point in low_points)[-3:])
|
||||||
|
print(f"answer 2 is {answer_2}")
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
blocks = sys.stdin.read().split("\n\n")
|
blocks = sys.stdin.read().split("\n\n")
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
lines = sys.stdin.read().splitlines()
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import copy
|
import copy
|
||||||
import sys
|
import sys
|
||||||
from functools import reduce
|
from functools import reduce
|
||||||
@ -7,7 +5,6 @@ from typing import Callable, Final, Mapping, Sequence
|
|||||||
|
|
||||||
|
|
||||||
class Monkey:
|
class Monkey:
|
||||||
|
|
||||||
id: Final[int]
|
id: Final[int]
|
||||||
items: Final[Sequence[int]]
|
items: Final[Sequence[int]]
|
||||||
worry_fn: Final[Callable[[int], int]]
|
worry_fn: Final[Callable[[int], int]]
|
||||||
@ -97,8 +94,7 @@ def run(
|
|||||||
# number of inspects
|
# number of inspects
|
||||||
inspects = {monkey: 0 for monkey in monkeys}
|
inspects = {monkey: 0 for monkey in monkeys}
|
||||||
|
|
||||||
for round in range(n_rounds):
|
for _ in range(n_rounds):
|
||||||
|
|
||||||
for monkey in monkeys:
|
for monkey in monkeys:
|
||||||
for item in items[monkey]:
|
for item in items[monkey]:
|
||||||
inspects[monkey] += 1
|
inspects[monkey] += 1
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import heapq
|
import heapq
|
||||||
import sys
|
import sys
|
||||||
from typing import Callable, Iterator, TypeVar
|
from typing import Callable, Iterator, TypeVar
|
||||||
@ -44,7 +42,6 @@ def dijkstra(
|
|||||||
visited.add(current)
|
visited.add(current)
|
||||||
|
|
||||||
for neighbor in neighbors(current):
|
for neighbor in neighbors(current):
|
||||||
|
|
||||||
if neighbor in visited:
|
if neighbor in visited:
|
||||||
continue
|
continue
|
||||||
|
|
||||||
@ -60,7 +57,6 @@ def dijkstra(
|
|||||||
|
|
||||||
|
|
||||||
def make_path(parents: dict[Node, Node], start: Node, end: Node) -> list[Node] | None:
|
def make_path(parents: dict[Node, Node], start: Node, end: Node) -> list[Node] | None:
|
||||||
|
|
||||||
if end not in parents:
|
if end not in parents:
|
||||||
return None
|
return None
|
||||||
|
|
||||||
@ -109,7 +105,6 @@ def neighbors(
|
|||||||
(c_row, c_col - 1),
|
(c_row, c_col - 1),
|
||||||
(c_row, c_col + 1),
|
(c_row, c_col + 1),
|
||||||
):
|
):
|
||||||
|
|
||||||
if not (n_row >= 0 and n_row < n_rows and n_col >= 0 and n_col < n_cols):
|
if not (n_row >= 0 and n_row < n_rows and n_col >= 0 and n_col < n_cols):
|
||||||
continue
|
continue
|
||||||
|
|
@ -1,27 +1,27 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import json
|
import json
|
||||||
import sys
|
import sys
|
||||||
from functools import cmp_to_key
|
from functools import cmp_to_key
|
||||||
|
from typing import TypeAlias, cast
|
||||||
|
|
||||||
blocks = sys.stdin.read().strip().split("\n\n")
|
blocks = sys.stdin.read().strip().split("\n\n")
|
||||||
|
|
||||||
pairs = [tuple(json.loads(p) for p in block.split("\n")) for block in blocks]
|
pairs = [tuple(json.loads(p) for p in block.split("\n")) for block in blocks]
|
||||||
|
|
||||||
|
Packet: TypeAlias = list[int | list["Packet"]]
|
||||||
|
|
||||||
def compare(lhs: list[int | list], rhs: list[int | list]) -> int:
|
|
||||||
|
|
||||||
|
def compare(lhs: Packet, rhs: Packet) -> int:
|
||||||
for lhs_a, rhs_a in zip(lhs, rhs):
|
for lhs_a, rhs_a in zip(lhs, rhs):
|
||||||
if isinstance(lhs_a, int) and isinstance(rhs_a, int):
|
if isinstance(lhs_a, int) and isinstance(rhs_a, int):
|
||||||
if lhs_a != rhs_a:
|
if lhs_a != rhs_a:
|
||||||
return rhs_a - lhs_a
|
return rhs_a - lhs_a
|
||||||
else:
|
else:
|
||||||
if not isinstance(lhs_a, list):
|
if not isinstance(lhs_a, list):
|
||||||
lhs_a = [lhs_a]
|
lhs_a = [lhs_a] # type: ignore
|
||||||
elif not isinstance(rhs_a, list):
|
elif not isinstance(rhs_a, list):
|
||||||
rhs_a = [rhs_a]
|
rhs_a = [rhs_a] # type: ignore
|
||||||
assert isinstance(rhs_a, list) and isinstance(lhs_a, list)
|
assert isinstance(rhs_a, list) and isinstance(lhs_a, list)
|
||||||
r = compare(lhs_a, rhs_a)
|
r = compare(cast(Packet, lhs_a), cast(Packet, rhs_a))
|
||||||
if r != 0:
|
if r != 0:
|
||||||
return r
|
return r
|
||||||
|
|
@ -1,7 +1,4 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from collections import defaultdict
|
|
||||||
from enum import Enum, auto
|
from enum import Enum, auto
|
||||||
from typing import Callable, cast
|
from typing import Callable, cast
|
||||||
|
|
||||||
@ -23,10 +20,10 @@ def print_blocks(blocks: dict[tuple[int, int], Cell]):
|
|||||||
blocks: Set of blocks to print.
|
blocks: Set of blocks to print.
|
||||||
"""
|
"""
|
||||||
x_min, y_min, x_max, y_max = (
|
x_min, y_min, x_max, y_max = (
|
||||||
min(x for x, y in blocks),
|
min(x for x, _ in blocks),
|
||||||
0,
|
0,
|
||||||
max(x for x, y in blocks),
|
max(x for x, _ in blocks),
|
||||||
max(y for x, y in blocks),
|
max(y for _, y in blocks),
|
||||||
)
|
)
|
||||||
|
|
||||||
for y in range(y_min, y_max + 1):
|
for y in range(y_min, y_max + 1):
|
||||||
@ -56,13 +53,12 @@ def flow(
|
|||||||
The input blocks.
|
The input blocks.
|
||||||
"""
|
"""
|
||||||
|
|
||||||
y_max = max(y for x, y in blocks)
|
y_max = max(y for _, y in blocks)
|
||||||
|
|
||||||
while True:
|
while True:
|
||||||
x, y = 500, 0
|
x, y = 500, 0
|
||||||
|
|
||||||
while y <= y_max:
|
while y <= y_max:
|
||||||
|
|
||||||
moved = False
|
moved = False
|
||||||
for cx, cy in ((x, y + 1), (x - 1, y + 1), (x + 1, y + 1)):
|
for cx, cy in ((x, y + 1), (x - 1, y + 1), (x + 1, y + 1)):
|
||||||
if (cx, cy) not in blocks and fill_fn(cx, cy) == Cell.AIR:
|
if (cx, cy) not in blocks and fill_fn(cx, cy) == Cell.AIR:
|
||||||
@ -117,10 +113,10 @@ print_blocks(blocks)
|
|||||||
print()
|
print()
|
||||||
|
|
||||||
x_min, y_min, x_max, y_max = (
|
x_min, y_min, x_max, y_max = (
|
||||||
min(x for x, y in blocks),
|
min(x for x, _ in blocks),
|
||||||
0,
|
0,
|
||||||
max(x for x, y in blocks),
|
max(x for x, _ in blocks),
|
||||||
max(y for x, y in blocks),
|
max(y for _, y in blocks),
|
||||||
)
|
)
|
||||||
|
|
||||||
# === part 1 ===
|
# === part 1 ===
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
import numpy as np
|
import numpy as np
|
||||||
@ -7,7 +5,6 @@ import parse
|
|||||||
|
|
||||||
|
|
||||||
def part1(sensor_to_beacon: dict[tuple[int, int], tuple[int, int]], row: int) -> int:
|
def part1(sensor_to_beacon: dict[tuple[int, int], tuple[int, int]], row: int) -> int:
|
||||||
|
|
||||||
no_beacons_row_l: list[np.ndarray] = []
|
no_beacons_row_l: list[np.ndarray] = []
|
||||||
|
|
||||||
for (sx, sy), (bx, by) in sensor_to_beacon.items():
|
for (sx, sy), (bx, by) in sensor_to_beacon.items():
|
||||||
@ -37,7 +34,7 @@ def part2_intervals(
|
|||||||
its.append((max(0, sx - dx), min(sx + dx, xy_max)))
|
its.append((max(0, sx - dx), min(sx + dx, xy_max)))
|
||||||
|
|
||||||
its = sorted(its)
|
its = sorted(its)
|
||||||
s, e = its[0]
|
_, e = its[0]
|
||||||
|
|
||||||
for si, ei in its[1:]:
|
for si, ei in its[1:]:
|
||||||
if si > e + 1:
|
if si > e + 1:
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
from __future__ import annotations
|
from __future__ import annotations
|
||||||
|
|
||||||
import heapq
|
import heapq
|
||||||
@ -69,7 +67,6 @@ def part_1(
|
|||||||
distances: dict[tuple[Pipe, Pipe], int],
|
distances: dict[tuple[Pipe, Pipe], int],
|
||||||
relevant_pipes: FrozenSet[Pipe],
|
relevant_pipes: FrozenSet[Pipe],
|
||||||
):
|
):
|
||||||
|
|
||||||
node_at_times: dict[int, dict[Pipe, dict[FrozenSet[Pipe], int]]] = defaultdict(
|
node_at_times: dict[int, dict[Pipe, dict[FrozenSet[Pipe], int]]] = defaultdict(
|
||||||
lambda: defaultdict(lambda: defaultdict(lambda: 0))
|
lambda: defaultdict(lambda: defaultdict(lambda: 0))
|
||||||
)
|
)
|
||||||
@ -79,7 +76,6 @@ def part_1(
|
|||||||
for c_pipe, nodes in node_at_times[time].items():
|
for c_pipe, nodes in node_at_times[time].items():
|
||||||
for flowing, flow in nodes.items():
|
for flowing, flow in nodes.items():
|
||||||
for target in relevant_pipes:
|
for target in relevant_pipes:
|
||||||
|
|
||||||
distance = distances[c_pipe, target] + 1
|
distance = distances[c_pipe, target] + 1
|
||||||
if time + distance >= max_time or target in flowing:
|
if time + distance >= max_time or target in flowing:
|
||||||
continue
|
continue
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from typing import Sequence, TypeVar
|
from typing import Sequence, TypeVar
|
||||||
|
|
||||||
@ -49,7 +47,6 @@ def build_tower(
|
|||||||
early_stop: bool = False,
|
early_stop: bool = False,
|
||||||
init: np.ndarray = np.ones(WIDTH, dtype=bool),
|
init: np.ndarray = np.ones(WIDTH, dtype=bool),
|
||||||
) -> tuple[np.ndarray, int, int, dict[int, int]]:
|
) -> tuple[np.ndarray, int, int, dict[int, int]]:
|
||||||
|
|
||||||
tower = EMPTY_BLOCKS.copy()
|
tower = EMPTY_BLOCKS.copy()
|
||||||
tower[0, :] = init
|
tower[0, :] = init
|
||||||
|
|
||||||
@ -59,7 +56,6 @@ def build_tower(
|
|||||||
rock_count = 0
|
rock_count = 0
|
||||||
|
|
||||||
for rock_count in range(n_rocks):
|
for rock_count in range(n_rocks):
|
||||||
|
|
||||||
if early_stop:
|
if early_stop:
|
||||||
if i_rock == 0 and (i_rock, i_jet) in done_at:
|
if i_rock == 0 and (i_rock, i_jet) in done_at:
|
||||||
break
|
break
|
||||||
@ -75,7 +71,6 @@ def build_tower(
|
|||||||
tower = np.concatenate([tower, EMPTY_BLOCKS], axis=0)
|
tower = np.concatenate([tower, EMPTY_BLOCKS], axis=0)
|
||||||
|
|
||||||
while True:
|
while True:
|
||||||
|
|
||||||
jet, i_jet = next_cycle(jets, i_jet)
|
jet, i_jet = next_cycle(jets, i_jet)
|
||||||
|
|
||||||
dx = 0
|
dx = 0
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from typing import FrozenSet
|
from typing import FrozenSet
|
||||||
|
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from typing import Literal
|
from typing import Literal
|
||||||
|
|
||||||
@ -88,7 +86,6 @@ for line in lines:
|
|||||||
|
|
||||||
|
|
||||||
def run(blueprint: dict[Reagent, dict[Reagent, int]], max_time: int) -> int:
|
def run(blueprint: dict[Reagent, dict[Reagent, int]], max_time: int) -> int:
|
||||||
|
|
||||||
# since we can only build one robot per time, we do not need more than X robots
|
# since we can only build one robot per time, we do not need more than X robots
|
||||||
# of type K where X is the maximum number of K required among all robots, e.g.,
|
# of type K where X is the maximum number of K required among all robots, e.g.,
|
||||||
# in the first toy blueprint, we need at most 4 ore robots, 14 clay ones and 7
|
# in the first toy blueprint, we need at most 4 ore robots, 14 clay ones and 7
|
||||||
@ -100,7 +97,6 @@ def run(blueprint: dict[Reagent, dict[Reagent, int]], max_time: int) -> int:
|
|||||||
state_after_t: dict[int, set[State]] = {0: [State()]}
|
state_after_t: dict[int, set[State]] = {0: [State()]}
|
||||||
|
|
||||||
for t in range(1, max_time + 1):
|
for t in range(1, max_time + 1):
|
||||||
|
|
||||||
# list of new states at the end of step t that we are going to prune later
|
# list of new states at the end of step t that we are going to prune later
|
||||||
states_for_t: set[State] = set()
|
states_for_t: set[State] = set()
|
||||||
|
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
|
|
||||||
@ -49,7 +47,7 @@ lines = sys.stdin.readlines()
|
|||||||
values = [(ord(row[0]) - ord("A"), ord(row[2]) - ord("X")) for row in lines]
|
values = [(ord(row[0]) - ord("A"), ord(row[2]) - ord("X")) for row in lines]
|
||||||
|
|
||||||
# part 1 - 13526
|
# part 1 - 13526
|
||||||
print(f"score 1 is {sum(score_1(*v) for v in values)}")
|
print(f"answer 1 is {sum(score_1(*v) for v in values)}")
|
||||||
|
|
||||||
# part 2 - 14204
|
# part 2 - 14204
|
||||||
print(f"score 2 is {sum(score_2(*v) for v in values)}")
|
print(f"answer 2 is {sum(score_2(*v) for v in values)}")
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
from __future__ import annotations
|
from __future__ import annotations
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
@ -21,7 +19,6 @@ class Number:
|
|||||||
|
|
||||||
|
|
||||||
def decrypt(numbers: list[Number], key: int, rounds: int) -> int:
|
def decrypt(numbers: list[Number], key: int, rounds: int) -> int:
|
||||||
|
|
||||||
numbers = numbers.copy()
|
numbers = numbers.copy()
|
||||||
original = numbers.copy()
|
original = numbers.copy()
|
||||||
|
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import operator
|
import operator
|
||||||
import sys
|
import sys
|
||||||
from typing import Callable
|
from typing import Callable
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import re
|
import re
|
||||||
import sys
|
import sys
|
||||||
from typing import Callable
|
from typing import Callable
|
||||||
@ -126,7 +124,6 @@ def wrap_part_2(y0: int, x0: int, r0: str) -> tuple[int, int, str]:
|
|||||||
|
|
||||||
|
|
||||||
def run(wrap: Callable[[int, int, str], tuple[int, int, str]]) -> tuple[int, int, str]:
|
def run(wrap: Callable[[int, int, str], tuple[int, int, str]]) -> tuple[int, int, str]:
|
||||||
|
|
||||||
y0 = 0
|
y0 = 0
|
||||||
x0 = np.where(board[0] == EMPTY)[0][0]
|
x0 = np.where(board[0] == EMPTY)[0][0]
|
||||||
r0 = "E"
|
r0 = "E"
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import itertools
|
import itertools
|
||||||
import sys
|
import sys
|
||||||
from collections import defaultdict
|
from collections import defaultdict
|
||||||
@ -41,7 +39,7 @@ def round(
|
|||||||
directions: Directions,
|
directions: Directions,
|
||||||
):
|
):
|
||||||
to_move: dict[tuple[int, int], list[tuple[int, int]]] = defaultdict(lambda: [])
|
to_move: dict[tuple[int, int], list[tuple[int, int]]] = defaultdict(lambda: [])
|
||||||
for (y, x) in positions:
|
for y, x in positions:
|
||||||
elves = {
|
elves = {
|
||||||
(dy, dx): (y + dy, x + dx) in positions
|
(dy, dx): (y + dy, x + dx) in positions
|
||||||
for dy, dx in itertools.product((-1, 0, 1), (-1, 0, 1))
|
for dy, dx in itertools.product((-1, 0, 1), (-1, 0, 1))
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import heapq
|
import heapq
|
||||||
import math
|
import math
|
||||||
import sys
|
import sys
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
lines = sys.stdin.read().splitlines()
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import string
|
import string
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
@ -13,7 +11,7 @@ priorities = {c: i + 1 for i, c in enumerate(string.ascii_letters)}
|
|||||||
|
|
||||||
# part 1
|
# part 1
|
||||||
part1 = sum(priorities[c] for p1, p2 in parts for c in p1.intersection(p2))
|
part1 = sum(priorities[c] for p1, p2 in parts for c in p1.intersection(p2))
|
||||||
print(f"score 1 is {part1}")
|
print(f"answer 1 is {part1}")
|
||||||
|
|
||||||
# part 2
|
# part 2
|
||||||
n_per_group = 3
|
n_per_group = 3
|
||||||
@ -22,4 +20,4 @@ part2 = sum(
|
|||||||
for i in range(0, len(lines), n_per_group)
|
for i in range(0, len(lines), n_per_group)
|
||||||
for c in set(lines[i]).intersection(*lines[i + 1 : i + n_per_group])
|
for c in set(lines[i]).intersection(*lines[i + 1 : i + n_per_group])
|
||||||
)
|
)
|
||||||
print(f"score 2 is {part2}")
|
print(f"answer 2 is {part2}")
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
lines = [line.strip() for line in sys.stdin.readlines()]
|
lines = [line.strip() for line in sys.stdin.readlines()]
|
||||||
@ -12,8 +10,8 @@ def make_range(value: str) -> set[int]:
|
|||||||
|
|
||||||
sections = [tuple(make_range(part) for part in line.split(",")) for line in lines]
|
sections = [tuple(make_range(part) for part in line.split(",")) for line in lines]
|
||||||
|
|
||||||
score_1 = sum(s1.issubset(s2) or s2.issubset(s1) for s1, s2 in sections)
|
answer_1 = sum(s1.issubset(s2) or s2.issubset(s1) for s1, s2 in sections)
|
||||||
print(f"score 1 is {score_1}")
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
score_2 = sum(bool(s1.intersection(s2)) for s1, s2 in sections)
|
answer_2 = sum(bool(s1.intersection(s2)) for s1, s2 in sections)
|
||||||
print(f"score 1 is {score_2}")
|
print(f"answer 1 is {answer_2}")
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import copy
|
import copy
|
||||||
import sys
|
import sys
|
||||||
|
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
|
|
@ -1,5 +1,3 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
from pathlib import Path
|
from pathlib import Path
|
||||||
|
|
@ -1,8 +1,7 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
import numpy as np
|
import numpy as np
|
||||||
|
from numpy.typing import NDArray
|
||||||
|
|
||||||
lines = sys.stdin.read().splitlines()
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
@ -27,7 +26,7 @@ answer_1 = (highest_trees.min(axis=2) < trees).sum()
|
|||||||
print(f"answer 1 is {answer_1}")
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
|
||||||
def viewing_distance(row_of_trees: np.ndarray, value: int) -> int:
|
def viewing_distance(row_of_trees: NDArray[np.int_], value: int) -> int:
|
||||||
w = np.where(row_of_trees >= value)[0]
|
w = np.where(row_of_trees >= value)[0]
|
||||||
|
|
||||||
if not w.size:
|
if not w.size:
|
@ -1,12 +1,9 @@
|
|||||||
# -*- encoding: utf-8 -*-
|
|
||||||
|
|
||||||
import sys
|
import sys
|
||||||
|
|
||||||
import numpy as np
|
import numpy as np
|
||||||
|
|
||||||
|
|
||||||
def move(head: tuple[int, int], command: str) -> tuple[int, int]:
|
def move(head: tuple[int, int], command: str) -> tuple[int, int]:
|
||||||
|
|
||||||
h_col, h_row = head
|
h_col, h_row = head
|
||||||
|
|
||||||
if command == "L":
|
if command == "L":
|
||||||
@ -22,7 +19,6 @@ def move(head: tuple[int, int], command: str) -> tuple[int, int]:
|
|||||||
|
|
||||||
|
|
||||||
def follow(head: tuple[int, int], tail: tuple[int, int]) -> tuple[int, int]:
|
def follow(head: tuple[int, int], tail: tuple[int, int]) -> tuple[int, int]:
|
||||||
|
|
||||||
h_col, h_row = head
|
h_col, h_row = head
|
||||||
t_col, t_row = tail
|
t_col, t_row = tail
|
||||||
|
|
||||||
@ -33,8 +29,7 @@ def follow(head: tuple[int, int], tail: tuple[int, int]) -> tuple[int, int]:
|
|||||||
|
|
||||||
|
|
||||||
def run(commands: list[str], n_blocks: int) -> list[tuple[int, int]]:
|
def run(commands: list[str], n_blocks: int) -> list[tuple[int, int]]:
|
||||||
|
blocks: list[tuple[int, int]] = [(0, 0) for _ in range(n_blocks)]
|
||||||
blocks = [(0, 0) for _ in range(n_blocks)]
|
|
||||||
visited = [blocks[-1]]
|
visited = [blocks[-1]]
|
||||||
|
|
||||||
for command in commands:
|
for command in commands:
|
100
src/holt59/aoc/2023/day10.py
Normal file
100
src/holt59/aoc/2023/day10.py
Normal file
@ -0,0 +1,100 @@
|
|||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from typing import Literal, cast
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
Symbol = Literal["|", "-", "L", "J", "7", "F", ".", "S"]
|
||||||
|
|
||||||
|
lines: list[list[Symbol]] = [
|
||||||
|
[cast(Symbol, symbol) for symbol in line] for line in sys.stdin.read().splitlines()
|
||||||
|
]
|
||||||
|
|
||||||
|
# find starting point
|
||||||
|
si, sj = next(
|
||||||
|
(i, j)
|
||||||
|
for i in range(len(lines))
|
||||||
|
for j in range(len(lines[0]))
|
||||||
|
if lines[i][j] == "S"
|
||||||
|
)
|
||||||
|
|
||||||
|
# find one of the two outputs
|
||||||
|
ni, nj = si, sj
|
||||||
|
for ni, nj, chars in (
|
||||||
|
(si - 1, sj, "|7F"),
|
||||||
|
(si + 1, sj, "|LJ"),
|
||||||
|
(si, sj - 1, "-LF"),
|
||||||
|
(si, sj + 1, "-J7"),
|
||||||
|
):
|
||||||
|
if lines[ni][nj] in chars:
|
||||||
|
break
|
||||||
|
|
||||||
|
# part 1 - find the loop (re-used in part 2)
|
||||||
|
loop = [(si, sj), (ni, nj)]
|
||||||
|
while True:
|
||||||
|
pi, pj = loop[-2]
|
||||||
|
i, j = loop[-1]
|
||||||
|
|
||||||
|
sym = lines[i][j]
|
||||||
|
|
||||||
|
if sym == "|" and pi > i or sym in "JL" and pi == i:
|
||||||
|
i -= 1
|
||||||
|
elif sym == "|" and pi < i or sym in "7F" and pi == i:
|
||||||
|
i += 1
|
||||||
|
elif sym == "-" and pj > j or sym in "J7" and pj == j:
|
||||||
|
j -= 1
|
||||||
|
elif sym == "-" and pj < j or sym in "LF" and pj == j:
|
||||||
|
j += 1
|
||||||
|
|
||||||
|
if (i, j) == (si, sj):
|
||||||
|
break
|
||||||
|
|
||||||
|
loop.append((i, j))
|
||||||
|
|
||||||
|
answer_1 = len(loop) // 2
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
|
||||||
|
# replace S by an appropriate character for the loop below
|
||||||
|
di1, dj1 = loop[1][0] - loop[0][0], loop[1][1] - loop[0][1]
|
||||||
|
di2, dj2 = loop[0][0] - loop[-1][0], loop[0][1] - loop[-1][1]
|
||||||
|
mapping: dict[tuple[int, int], dict[tuple[int, int], Symbol]] = {
|
||||||
|
(0, 1): {(0, 1): "-", (-1, 0): "F", (1, 0): "L"},
|
||||||
|
(0, -1): {(0, -1): "-", (-1, 0): "7", (1, 0): "J"},
|
||||||
|
(1, 0): {(1, 0): "|", (0, 1): "7", (0, -1): "F"},
|
||||||
|
(-1, 0): {(-1, 0): "|", (0, -1): "L", (0, 1): "J"},
|
||||||
|
}
|
||||||
|
lines[si][sj] = mapping[di1, dj1][di2, dj2]
|
||||||
|
|
||||||
|
# find the points inside the loop using an adaptation of ray casting for a discrete
|
||||||
|
# grid (https://stackoverflow.com/a/218081/2666289)
|
||||||
|
#
|
||||||
|
# use a set for faster '... in loop' check
|
||||||
|
#
|
||||||
|
loop_s = set(loop)
|
||||||
|
inside: set[tuple[int, int]] = set()
|
||||||
|
for i in range(len(lines)):
|
||||||
|
cnt = 0
|
||||||
|
for j in range(len(lines[0])):
|
||||||
|
if (i, j) not in loop_s and cnt % 2 == 1:
|
||||||
|
inside.add((i, j))
|
||||||
|
|
||||||
|
if (i, j) in loop_s and lines[i][j] in "|LJ":
|
||||||
|
cnt += 1
|
||||||
|
|
||||||
|
if VERBOSE:
|
||||||
|
for i in range(len(lines)):
|
||||||
|
for j in range(len(lines[0])):
|
||||||
|
if (i, j) == (si, sj):
|
||||||
|
print("\033[91mS\033[0m", end="")
|
||||||
|
elif (i, j) in loop:
|
||||||
|
print(lines[i][j], end="")
|
||||||
|
elif (i, j) in inside:
|
||||||
|
print("\033[92mI\033[0m", end="")
|
||||||
|
else:
|
||||||
|
print(".", end="")
|
||||||
|
print()
|
||||||
|
|
||||||
|
answer_2 = len(inside)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
41
src/holt59/aoc/2023/day11.py
Normal file
41
src/holt59/aoc/2023/day11.py
Normal file
@ -0,0 +1,41 @@
|
|||||||
|
import sys
|
||||||
|
|
||||||
|
import numpy as np
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
data = np.array([[c == "#" for c in line] for line in lines])
|
||||||
|
|
||||||
|
rows = {c for c in range(data.shape[0]) if not data[c, :].any()}
|
||||||
|
columns = {c for c in range(data.shape[1]) if not data[:, c].any()}
|
||||||
|
|
||||||
|
galaxies_y, galaxies_x = np.where(data) # type: ignore
|
||||||
|
|
||||||
|
|
||||||
|
def compute_total_distance(expansion: int) -> int:
|
||||||
|
distances: list[int] = []
|
||||||
|
for g1 in range(len(galaxies_y)):
|
||||||
|
x1, y1 = int(galaxies_x[g1]), int(galaxies_y[g1])
|
||||||
|
for g2 in range(g1 + 1, len(galaxies_y)):
|
||||||
|
x2, y2 = int(galaxies_x[g2]), int(galaxies_y[g2])
|
||||||
|
|
||||||
|
dx = sum(
|
||||||
|
1 + (expansion - 1) * (x in columns)
|
||||||
|
for x in range(min(x1, x2), max(x1, x2))
|
||||||
|
)
|
||||||
|
dy = sum(
|
||||||
|
1 + (expansion - 1) * (y in rows)
|
||||||
|
for y in range(min(y1, y2), max(y1, y2))
|
||||||
|
)
|
||||||
|
|
||||||
|
distances.append(dx + dy)
|
||||||
|
return sum(distances)
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = compute_total_distance(2)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = compute_total_distance(1000000)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
107
src/holt59/aoc/2023/day12.py
Normal file
107
src/holt59/aoc/2023/day12.py
Normal file
@ -0,0 +1,107 @@
|
|||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from functools import lru_cache
|
||||||
|
from typing import Iterable
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
|
||||||
|
@lru_cache
|
||||||
|
def compute_fitting_arrangements(pattern: str, counts: tuple[int, ...]) -> int:
|
||||||
|
"""
|
||||||
|
fn3p tries to fit ALL values in counts() inside the pattern.
|
||||||
|
"""
|
||||||
|
# no pattern -> ok if nothing to fit, otherwise ko
|
||||||
|
if not pattern:
|
||||||
|
count = 1 if not counts else 0
|
||||||
|
|
||||||
|
# no count -> ok if pattern has no mandatory entry, else ko
|
||||||
|
elif not counts:
|
||||||
|
count = 1 if pattern.find("#") == -1 else 0
|
||||||
|
|
||||||
|
# cannot fit all values -> ko
|
||||||
|
elif len(pattern) < sum(counts) + len(counts) - 1:
|
||||||
|
count = 0
|
||||||
|
|
||||||
|
elif len(pattern) < counts[0]:
|
||||||
|
count = 0
|
||||||
|
|
||||||
|
else:
|
||||||
|
count = 0
|
||||||
|
|
||||||
|
if pattern[0] == "?":
|
||||||
|
count += compute_fitting_arrangements(pattern[1:], counts)
|
||||||
|
|
||||||
|
if len(pattern) == counts[0]:
|
||||||
|
count += 1
|
||||||
|
|
||||||
|
elif pattern[counts[0]] != "#":
|
||||||
|
count += compute_fitting_arrangements(pattern[counts[0] + 1 :], counts[1:])
|
||||||
|
|
||||||
|
return count
|
||||||
|
|
||||||
|
|
||||||
|
@lru_cache
|
||||||
|
def compute_possible_arrangements(
|
||||||
|
patterns: tuple[str, ...], counts: tuple[int, ...]
|
||||||
|
) -> int:
|
||||||
|
if not patterns:
|
||||||
|
return 1 if not counts else 0
|
||||||
|
|
||||||
|
with_hash = sum(1 for p in patterns[1:] if p.find("#") >= 0)
|
||||||
|
|
||||||
|
if with_hash > len(counts):
|
||||||
|
return 0
|
||||||
|
|
||||||
|
to_fit = counts if with_hash == 0 else counts[:-with_hash]
|
||||||
|
remaining = () if with_hash == 0 else counts[-with_hash:]
|
||||||
|
|
||||||
|
if not to_fit:
|
||||||
|
if patterns[0].find("#") != -1:
|
||||||
|
return 0
|
||||||
|
return compute_possible_arrangements(patterns[1:], remaining)
|
||||||
|
|
||||||
|
elif patterns[0].find("#") != -1 and len(patterns[0]) < to_fit[0]:
|
||||||
|
return 0
|
||||||
|
|
||||||
|
elif patterns[0].find("?") == -1:
|
||||||
|
if len(patterns[0]) != to_fit[0]:
|
||||||
|
return 0
|
||||||
|
return compute_possible_arrangements(patterns[1:], counts[1:])
|
||||||
|
|
||||||
|
else:
|
||||||
|
return sum(
|
||||||
|
fp * compute_possible_arrangements(patterns[1:], to_fit[i:] + remaining)
|
||||||
|
for i in range(len(to_fit) + 1)
|
||||||
|
if (fp := compute_fitting_arrangements(patterns[0], to_fit[:i])) > 0
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
def compute_all_possible_arrangements(lines: Iterable[str], repeat: int) -> int:
|
||||||
|
count = 0
|
||||||
|
|
||||||
|
if VERBOSE:
|
||||||
|
from tqdm import tqdm
|
||||||
|
|
||||||
|
lines = tqdm(lines)
|
||||||
|
|
||||||
|
for line in lines:
|
||||||
|
parts = line.split(" ")
|
||||||
|
count += compute_possible_arrangements(
|
||||||
|
tuple(filter(len, "?".join(parts[0] for _ in range(repeat)).split("."))),
|
||||||
|
tuple(int(c) for c in parts[1].split(",")) * repeat,
|
||||||
|
)
|
||||||
|
|
||||||
|
return count
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = compute_all_possible_arrangements(lines, 1)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = compute_all_possible_arrangements(lines, 5)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
43
src/holt59/aoc/2023/day13.py
Normal file
43
src/holt59/aoc/2023/day13.py
Normal file
@ -0,0 +1,43 @@
|
|||||||
|
import sys
|
||||||
|
from typing import Callable, Literal
|
||||||
|
|
||||||
|
|
||||||
|
def split(block: list[str], axis: Literal[0, 1], count: int) -> int:
|
||||||
|
n_iter = len(block) if axis == 0 else len(block[0])
|
||||||
|
n_check = len(block) if axis == 1 else len(block[0])
|
||||||
|
|
||||||
|
at: Callable[[int, int], str] = (
|
||||||
|
(lambda i, j: block[i][j]) if axis == 0 else (lambda i, j: block[j][i])
|
||||||
|
)
|
||||||
|
|
||||||
|
for i in range(n_iter - 1):
|
||||||
|
size = min(i + 1, n_iter - i - 1)
|
||||||
|
if (
|
||||||
|
sum(
|
||||||
|
at(i - s, j) != at(i + 1 + s, j)
|
||||||
|
for s in range(0, size)
|
||||||
|
for j in range(n_check)
|
||||||
|
)
|
||||||
|
== count
|
||||||
|
):
|
||||||
|
return i + 1
|
||||||
|
|
||||||
|
return 0
|
||||||
|
|
||||||
|
|
||||||
|
blocks = [block.splitlines() for block in sys.stdin.read().split("\n\n")]
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(
|
||||||
|
split(block, axis=1, count=0) + 100 * split(block, axis=0, count=0)
|
||||||
|
for block in blocks
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = sum(
|
||||||
|
split(block, axis=1, count=1) + 100 * split(block, axis=0, count=1)
|
||||||
|
for block in blocks
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
68
src/holt59/aoc/2023/day14.py
Normal file
68
src/holt59/aoc/2023/day14.py
Normal file
@ -0,0 +1,68 @@
|
|||||||
|
import sys
|
||||||
|
from typing import TypeAlias
|
||||||
|
|
||||||
|
RockGrid: TypeAlias = list[list[str]]
|
||||||
|
|
||||||
|
rocks0 = [list(line) for line in sys.stdin.read().splitlines()]
|
||||||
|
|
||||||
|
|
||||||
|
def slide_rocks_top(rocks: RockGrid) -> RockGrid:
|
||||||
|
top = [0 if c == "." else 1 for c in rocks[0]]
|
||||||
|
for row in range(1, len(rocks)):
|
||||||
|
for col in range(len(rocks[0])):
|
||||||
|
match rocks[row][col]:
|
||||||
|
case "O":
|
||||||
|
if top[col] != row:
|
||||||
|
rocks[top[col]][col] = "O"
|
||||||
|
rocks[row][col] = "."
|
||||||
|
top[col] = top[col] + 1
|
||||||
|
case "#":
|
||||||
|
top[col] = row + 1
|
||||||
|
case _:
|
||||||
|
pass
|
||||||
|
return rocks
|
||||||
|
|
||||||
|
|
||||||
|
def cycle(rocks: RockGrid) -> RockGrid:
|
||||||
|
for _ in range(4):
|
||||||
|
rocks = slide_rocks_top(rocks)
|
||||||
|
rocks = [
|
||||||
|
[rocks[len(rocks) - j - 1][i] for j in range(len(rocks))]
|
||||||
|
for i in range(len(rocks[0]))
|
||||||
|
]
|
||||||
|
|
||||||
|
return rocks
|
||||||
|
|
||||||
|
|
||||||
|
rocks = slide_rocks_top([[c for c in r] for r in rocks0])
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(
|
||||||
|
(len(rocks) - i) * sum(1 for c in row if c == "O") for i, row in enumerate(rocks)
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
rocks = rocks0
|
||||||
|
|
||||||
|
N = 1000000000
|
||||||
|
cycles: list[RockGrid] = []
|
||||||
|
i_cycle: int = -1
|
||||||
|
for i_cycle in range(N):
|
||||||
|
rocks = cycle(rocks)
|
||||||
|
|
||||||
|
if any(rocks == c for c in cycles):
|
||||||
|
break
|
||||||
|
|
||||||
|
cycles.append([[c for c in r] for r in rocks])
|
||||||
|
|
||||||
|
cycle_start = next(i for i in range(len(cycles)) if (rocks == cycles[i]))
|
||||||
|
cycle_length = i_cycle - cycle_start
|
||||||
|
|
||||||
|
ci = cycle_start + (N - cycle_start) % cycle_length - 1
|
||||||
|
|
||||||
|
answer_2 = sum(
|
||||||
|
(len(rocks) - i) * sum(1 for c in row if c == "O")
|
||||||
|
for i, row in enumerate(cycles[ci])
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
31
src/holt59/aoc/2023/day15.py
Normal file
31
src/holt59/aoc/2023/day15.py
Normal file
@ -0,0 +1,31 @@
|
|||||||
|
import sys
|
||||||
|
from functools import reduce
|
||||||
|
|
||||||
|
steps = sys.stdin.read().strip().split(",")
|
||||||
|
|
||||||
|
|
||||||
|
def _hash(s: str) -> int:
|
||||||
|
return reduce(lambda v, u: ((v + ord(u)) * 17) % 256, s, 0)
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(map(_hash, steps))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
boxes: list[dict[str, int]] = [{} for _ in range(256)]
|
||||||
|
|
||||||
|
for step in steps:
|
||||||
|
if (i := step.find("=")) >= 0:
|
||||||
|
label, length = step[:i], int(step[i + 1 :])
|
||||||
|
boxes[_hash(label)][label] = length
|
||||||
|
else:
|
||||||
|
label = step[:-1]
|
||||||
|
boxes[_hash(label)].pop(label, None)
|
||||||
|
|
||||||
|
answer_2 = sum(
|
||||||
|
i_box * i_lens * length
|
||||||
|
for i_box, box in enumerate(boxes, start=1)
|
||||||
|
for i_lens, length in enumerate(box.values(), start=1)
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
110
src/holt59/aoc/2023/day16.py
Normal file
110
src/holt59/aoc/2023/day16.py
Normal file
@ -0,0 +1,110 @@
|
|||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from typing import Literal, TypeAlias, cast
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
CellType: TypeAlias = Literal[".", "|", "-", "\\", "/"]
|
||||||
|
Direction: TypeAlias = Literal["R", "L", "U", "D"]
|
||||||
|
|
||||||
|
Mappings: dict[
|
||||||
|
CellType,
|
||||||
|
dict[
|
||||||
|
Direction,
|
||||||
|
tuple[tuple[tuple[int, int, Direction], ...], tuple[Direction, ...]],
|
||||||
|
],
|
||||||
|
] = {
|
||||||
|
".": {
|
||||||
|
"R": (((0, +1, "R"),), ("R", "L")),
|
||||||
|
"L": (((0, -1, "L"),), ("R", "L")),
|
||||||
|
"U": (((-1, 0, "U"),), ("U", "D")),
|
||||||
|
"D": (((+1, 0, "D"),), ("U", "D")),
|
||||||
|
},
|
||||||
|
"-": {
|
||||||
|
"R": (((0, +1, "R"),), ("R", "L")),
|
||||||
|
"L": (((0, -1, "L"),), ("R", "L")),
|
||||||
|
"U": (((0, +1, "R"), (0, -1, "L")), ("U", "D")),
|
||||||
|
"D": (((0, +1, "R"), (0, -1, "L")), ("U", "D")),
|
||||||
|
},
|
||||||
|
"|": {
|
||||||
|
"U": (((-1, 0, "U"),), ("U", "D")),
|
||||||
|
"D": (((+1, 0, "D"),), ("U", "D")),
|
||||||
|
"R": (((-1, 0, "U"), (+1, 0, "D")), ("R", "L")),
|
||||||
|
"L": (((-1, 0, "U"), (+1, 0, "D")), ("R", "L")),
|
||||||
|
},
|
||||||
|
"/": {
|
||||||
|
"R": (((-1, 0, "U"),), ("R", "D")),
|
||||||
|
"L": (((+1, 0, "D"),), ("L", "U")),
|
||||||
|
"U": (((0, +1, "R"),), ("U", "L")),
|
||||||
|
"D": (((0, -1, "L"),), ("R", "D")),
|
||||||
|
},
|
||||||
|
"\\": {
|
||||||
|
"R": (((+1, 0, "D"),), ("R", "U")),
|
||||||
|
"L": (((-1, 0, "U"),), ("L", "D")),
|
||||||
|
"U": (((0, -1, "L"),), ("U", "R")),
|
||||||
|
"D": (((0, +1, "R"),), ("L", "D")),
|
||||||
|
},
|
||||||
|
}
|
||||||
|
|
||||||
|
|
||||||
|
def propagate(
|
||||||
|
layout: list[list[CellType]], start: tuple[int, int], direction: Direction
|
||||||
|
) -> list[list[tuple[Direction, ...]]]:
|
||||||
|
n_rows, n_cols = len(layout), len(layout[0])
|
||||||
|
|
||||||
|
beams: list[list[tuple[Direction, ...]]] = [
|
||||||
|
[() for _ in range(len(layout[0]))] for _ in range(len(layout))
|
||||||
|
]
|
||||||
|
|
||||||
|
queue = [(start, direction)]
|
||||||
|
|
||||||
|
while queue:
|
||||||
|
(row, col), direction = queue.pop()
|
||||||
|
|
||||||
|
if (
|
||||||
|
row not in range(0, n_rows)
|
||||||
|
or col not in range(0, n_cols)
|
||||||
|
or direction in beams[row][col]
|
||||||
|
):
|
||||||
|
continue
|
||||||
|
|
||||||
|
moves, update = Mappings[layout[row][col]][direction]
|
||||||
|
|
||||||
|
beams[row][col] += update
|
||||||
|
|
||||||
|
for move in moves:
|
||||||
|
queue.append(((row + move[0], col + move[1]), move[2]))
|
||||||
|
|
||||||
|
return beams
|
||||||
|
|
||||||
|
|
||||||
|
layout: list[list[CellType]] = [
|
||||||
|
[cast(CellType, col) for col in row] for row in sys.stdin.read().splitlines()
|
||||||
|
]
|
||||||
|
|
||||||
|
|
||||||
|
beams = propagate(layout, (0, 0), "R")
|
||||||
|
|
||||||
|
if VERBOSE:
|
||||||
|
print("\n".join(["".join("#" if col else "." for col in row) for row in beams]))
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = sum(sum(map(bool, row)) for row in beams)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
n_rows, n_cols = len(layout), len(layout[0])
|
||||||
|
cases: list[tuple[tuple[int, int], Direction]] = []
|
||||||
|
|
||||||
|
for row in range(n_rows):
|
||||||
|
cases.append(((row, 0), "R"))
|
||||||
|
cases.append(((row, n_cols - 1), "L"))
|
||||||
|
for col in range(n_cols):
|
||||||
|
cases.append(((0, col), "D"))
|
||||||
|
cases.append(((n_rows - 1, col), "U"))
|
||||||
|
|
||||||
|
answer_2 = max(
|
||||||
|
sum(sum(map(bool, row)) for row in propagate(layout, start, direction))
|
||||||
|
for start, direction in cases
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
233
src/holt59/aoc/2023/day17.py
Normal file
233
src/holt59/aoc/2023/day17.py
Normal file
@ -0,0 +1,233 @@
|
|||||||
|
from __future__ import annotations
|
||||||
|
|
||||||
|
import heapq
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
from dataclasses import dataclass
|
||||||
|
from typing import Literal, TypeAlias
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
Direction: TypeAlias = Literal[">", "<", "^", "v"]
|
||||||
|
|
||||||
|
|
||||||
|
@dataclass(frozen=True, order=True)
|
||||||
|
class Label:
|
||||||
|
row: int
|
||||||
|
col: int
|
||||||
|
|
||||||
|
direction: Direction
|
||||||
|
count: int
|
||||||
|
|
||||||
|
parent: Label | None = None
|
||||||
|
|
||||||
|
|
||||||
|
# mappings from direction to row shift / col shift / opposite direction
|
||||||
|
MAPPINGS: dict[Direction, tuple[int, int, Direction]] = {
|
||||||
|
">": (0, +1, "<"),
|
||||||
|
"<": (0, -1, ">"),
|
||||||
|
"v": (+1, 0, "^"),
|
||||||
|
"^": (-1, 0, "v"),
|
||||||
|
}
|
||||||
|
|
||||||
|
|
||||||
|
def print_shortest_path(
|
||||||
|
grid: list[list[int]],
|
||||||
|
target: tuple[int, int],
|
||||||
|
per_cell: dict[tuple[int, int], list[tuple[Label, int]]],
|
||||||
|
):
|
||||||
|
assert len(per_cell[target]) == 1
|
||||||
|
label = per_cell[target][0][0]
|
||||||
|
|
||||||
|
path: list[Label] = []
|
||||||
|
while True:
|
||||||
|
path.insert(0, label)
|
||||||
|
if label.parent is None:
|
||||||
|
break
|
||||||
|
label = label.parent
|
||||||
|
|
||||||
|
p_grid = [[str(c) for c in r] for r in grid]
|
||||||
|
|
||||||
|
for i in range(len(grid)):
|
||||||
|
for j in range(len(grid[0])):
|
||||||
|
if per_cell[i, j]:
|
||||||
|
p_grid[i][j] = f"\033[94m{grid[i][j]}\033[0m"
|
||||||
|
|
||||||
|
prev_label = path[0]
|
||||||
|
for label in path[1:]:
|
||||||
|
for r in range(
|
||||||
|
min(prev_label.row, label.row), max(prev_label.row, label.row) + 1
|
||||||
|
):
|
||||||
|
for c in range(
|
||||||
|
min(prev_label.col, label.col),
|
||||||
|
max(prev_label.col, label.col) + 1,
|
||||||
|
):
|
||||||
|
if (r, c) != (prev_label.row, prev_label.col):
|
||||||
|
p_grid[r][c] = f"\033[93m{grid[r][c]}\033[0m"
|
||||||
|
|
||||||
|
p_grid[label.row][label.col] = f"\033[91m{grid[label.row][label.col]}\033[0m"
|
||||||
|
|
||||||
|
prev_label = label
|
||||||
|
|
||||||
|
p_grid[0][0] = f"\033[92m{grid[0][0]}\033[0m"
|
||||||
|
|
||||||
|
print("\n".join("".join(row) for row in p_grid))
|
||||||
|
|
||||||
|
|
||||||
|
def shortest_many_paths(grid: list[list[int]]) -> dict[tuple[int, int], int]:
|
||||||
|
n_rows, n_cols = len(grid), len(grid[0])
|
||||||
|
|
||||||
|
visited: dict[tuple[int, int], tuple[Label, int]] = {}
|
||||||
|
|
||||||
|
queue: list[tuple[int, Label]] = [
|
||||||
|
(0, Label(row=n_rows - 1, col=n_cols - 1, direction="^", count=0))
|
||||||
|
]
|
||||||
|
|
||||||
|
while queue and len(visited) != n_rows * n_cols:
|
||||||
|
distance, label = heapq.heappop(queue)
|
||||||
|
|
||||||
|
if (label.row, label.col) in visited:
|
||||||
|
continue
|
||||||
|
|
||||||
|
visited[label.row, label.col] = (label, distance)
|
||||||
|
|
||||||
|
for direction, (c_row, c_col, i_direction) in MAPPINGS.items():
|
||||||
|
if label.direction == i_direction:
|
||||||
|
continue
|
||||||
|
else:
|
||||||
|
row, col = (label.row + c_row, label.col + c_col)
|
||||||
|
|
||||||
|
# exclude labels outside the grid or with too many moves in the same
|
||||||
|
# direction
|
||||||
|
if row not in range(0, n_rows) or col not in range(0, n_cols):
|
||||||
|
continue
|
||||||
|
|
||||||
|
heapq.heappush(
|
||||||
|
queue,
|
||||||
|
(
|
||||||
|
distance
|
||||||
|
+ sum(
|
||||||
|
grid[r][c]
|
||||||
|
for r in range(min(row, label.row), max(row, label.row) + 1)
|
||||||
|
for c in range(min(col, label.col), max(col, label.col) + 1)
|
||||||
|
)
|
||||||
|
- grid[row][col],
|
||||||
|
Label(
|
||||||
|
row=row,
|
||||||
|
col=col,
|
||||||
|
direction=direction,
|
||||||
|
count=0,
|
||||||
|
parent=label,
|
||||||
|
),
|
||||||
|
),
|
||||||
|
)
|
||||||
|
|
||||||
|
return {(r, c): visited[r, c][1] for r in range(n_rows) for c in range(n_cols)}
|
||||||
|
|
||||||
|
|
||||||
|
def shortest_path(
|
||||||
|
grid: list[list[int]],
|
||||||
|
min_straight: int,
|
||||||
|
max_straight: int,
|
||||||
|
lower_bounds: dict[tuple[int, int], int],
|
||||||
|
) -> int:
|
||||||
|
n_rows, n_cols = len(grid), len(grid[0])
|
||||||
|
|
||||||
|
target = (len(grid) - 1, len(grid[0]) - 1)
|
||||||
|
|
||||||
|
# for each tuple (row, col, direction, count), the associated label when visited
|
||||||
|
visited: dict[tuple[int, int, str, int], Label] = {}
|
||||||
|
|
||||||
|
# list of all visited labels for a cell (with associated distance)
|
||||||
|
per_cell: dict[tuple[int, int], list[tuple[Label, int]]] = defaultdict(list)
|
||||||
|
|
||||||
|
# need to add two start labels, otherwise one of the two possible direction will
|
||||||
|
# not be possible
|
||||||
|
queue: list[tuple[int, int, Label]] = [
|
||||||
|
(lower_bounds[0, 0], 0, Label(row=0, col=0, direction="^", count=0)),
|
||||||
|
(lower_bounds[0, 0], 0, Label(row=0, col=0, direction="<", count=0)),
|
||||||
|
]
|
||||||
|
|
||||||
|
while queue:
|
||||||
|
_, distance, label = heapq.heappop(queue)
|
||||||
|
|
||||||
|
if (label.row, label.col, label.direction, label.count) in visited:
|
||||||
|
continue
|
||||||
|
|
||||||
|
visited[label.row, label.col, label.direction, label.count] = label
|
||||||
|
per_cell[label.row, label.col].append((label, distance))
|
||||||
|
|
||||||
|
if (label.row, label.col) == target:
|
||||||
|
break
|
||||||
|
|
||||||
|
for direction, (c_row, c_col, i_direction) in MAPPINGS.items():
|
||||||
|
# cannot move in the opposite direction
|
||||||
|
if label.direction == i_direction:
|
||||||
|
continue
|
||||||
|
|
||||||
|
# other direction, move 'min_straight' in the new direction
|
||||||
|
elif label.direction != direction:
|
||||||
|
row, col, count = (
|
||||||
|
label.row + min_straight * c_row,
|
||||||
|
label.col + min_straight * c_col,
|
||||||
|
min_straight,
|
||||||
|
)
|
||||||
|
|
||||||
|
# same direction, too many count
|
||||||
|
elif label.count == max_straight:
|
||||||
|
continue
|
||||||
|
|
||||||
|
# same direction, keep going and increment count
|
||||||
|
else:
|
||||||
|
row, col, count = (
|
||||||
|
label.row + c_row,
|
||||||
|
label.col + c_col,
|
||||||
|
label.count + 1,
|
||||||
|
)
|
||||||
|
# exclude labels outside the grid or with too many moves in the same
|
||||||
|
# direction
|
||||||
|
if row not in range(0, n_rows) or col not in range(0, n_cols):
|
||||||
|
continue
|
||||||
|
|
||||||
|
distance_to = (
|
||||||
|
distance
|
||||||
|
+ sum(
|
||||||
|
grid[r][c]
|
||||||
|
for r in range(min(row, label.row), max(row, label.row) + 1)
|
||||||
|
for c in range(min(col, label.col), max(col, label.col) + 1)
|
||||||
|
)
|
||||||
|
- grid[label.row][label.col]
|
||||||
|
)
|
||||||
|
|
||||||
|
heapq.heappush(
|
||||||
|
queue,
|
||||||
|
(
|
||||||
|
distance_to + lower_bounds[row, col],
|
||||||
|
distance_to,
|
||||||
|
Label(
|
||||||
|
row=row,
|
||||||
|
col=col,
|
||||||
|
direction=direction,
|
||||||
|
count=count,
|
||||||
|
parent=label,
|
||||||
|
),
|
||||||
|
),
|
||||||
|
)
|
||||||
|
|
||||||
|
if VERBOSE:
|
||||||
|
print_shortest_path(grid, target, per_cell)
|
||||||
|
|
||||||
|
return per_cell[target][0][1]
|
||||||
|
|
||||||
|
|
||||||
|
data = [[int(c) for c in r] for r in sys.stdin.read().splitlines()]
|
||||||
|
estimates = shortest_many_paths(data)
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = shortest_path(data, 1, 3, lower_bounds=estimates)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = shortest_path(data, 4, 10, lower_bounds=estimates)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
54
src/holt59/aoc/2023/day18.py
Normal file
54
src/holt59/aoc/2023/day18.py
Normal file
@ -0,0 +1,54 @@
|
|||||||
|
import sys
|
||||||
|
from typing import Literal, TypeAlias, cast
|
||||||
|
|
||||||
|
Direction: TypeAlias = Literal["R", "L", "U", "D"]
|
||||||
|
|
||||||
|
DIRECTIONS: list[Direction] = ["R", "D", "L", "U"]
|
||||||
|
MOVES: dict[Direction, tuple[int, int]] = {
|
||||||
|
"R": (0, +1),
|
||||||
|
"L": (0, -1),
|
||||||
|
"U": (-1, 0),
|
||||||
|
"D": (+1, 0),
|
||||||
|
}
|
||||||
|
|
||||||
|
|
||||||
|
def area(corners: list[tuple[int, int]], perimeter: int) -> int:
|
||||||
|
area = abs(
|
||||||
|
sum(c0[0] * c1[1] - c0[1] * c1[0] for c0, c1 in zip(corners, corners[1::])) // 2
|
||||||
|
)
|
||||||
|
return 1 + area - perimeter // 2 + perimeter
|
||||||
|
|
||||||
|
|
||||||
|
def polygon(values: list[tuple[Direction, int]]) -> tuple[list[tuple[int, int]], int]:
|
||||||
|
perimeter = 0
|
||||||
|
corners: list[tuple[int, int]] = [(0, 0)]
|
||||||
|
for direction, amount in values:
|
||||||
|
perimeter += amount
|
||||||
|
corners.append(
|
||||||
|
(
|
||||||
|
corners[-1][0] + amount * MOVES[direction][0],
|
||||||
|
corners[-1][1] + amount * MOVES[direction][1],
|
||||||
|
)
|
||||||
|
)
|
||||||
|
return corners, perimeter
|
||||||
|
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
answer_1 = area(
|
||||||
|
*polygon([(cast(Direction, (p := line.split())[0]), int(p[1])) for line in lines])
|
||||||
|
)
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = area(
|
||||||
|
*polygon(
|
||||||
|
[
|
||||||
|
(DIRECTIONS[int((h := line.split()[-1])[-2])], int(h[2:-2], 16))
|
||||||
|
for line in lines
|
||||||
|
]
|
||||||
|
)
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
139
src/holt59/aoc/2023/day19.py
Normal file
139
src/holt59/aoc/2023/day19.py
Normal file
@ -0,0 +1,139 @@
|
|||||||
|
import logging
|
||||||
|
import operator
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from math import prod
|
||||||
|
from typing import Literal, TypeAlias, cast
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
|
||||||
|
logging.basicConfig(level=logging.INFO if VERBOSE else logging.WARNING)
|
||||||
|
|
||||||
|
Category: TypeAlias = Literal["x", "m", "a", "s"]
|
||||||
|
Part: TypeAlias = dict[Category, int]
|
||||||
|
PartWithBounds: TypeAlias = dict[Category, tuple[int, int]]
|
||||||
|
|
||||||
|
OPERATORS = {"<": operator.lt, ">": operator.gt}
|
||||||
|
|
||||||
|
# None if there is no check (last entry), otherwise (category, sense, value)
|
||||||
|
Check: TypeAlias = tuple[Category, Literal["<", ">"], int] | None
|
||||||
|
|
||||||
|
# workflow as a list of check, in specified order, with target
|
||||||
|
Workflow: TypeAlias = list[tuple[Check, str]]
|
||||||
|
|
||||||
|
|
||||||
|
def accept(workflows: dict[str, Workflow], part: Part) -> bool:
|
||||||
|
workflow = "in"
|
||||||
|
decision: bool | None = None
|
||||||
|
|
||||||
|
while decision is None:
|
||||||
|
for check, target in workflows[workflow]:
|
||||||
|
passed = check is None
|
||||||
|
if check is not None:
|
||||||
|
category, sense, value = check
|
||||||
|
passed = OPERATORS[sense](part[category], value)
|
||||||
|
|
||||||
|
if passed:
|
||||||
|
if target in workflows:
|
||||||
|
workflow = target
|
||||||
|
else:
|
||||||
|
decision = target == "A"
|
||||||
|
break
|
||||||
|
|
||||||
|
return decision
|
||||||
|
|
||||||
|
|
||||||
|
def propagate(workflows: dict[str, Workflow], start: PartWithBounds) -> int:
|
||||||
|
def _fmt(meta: PartWithBounds) -> str:
|
||||||
|
return "{" + ", ".join(f"{k}={v}" for k, v in meta.items()) + "}"
|
||||||
|
|
||||||
|
def transfer_or_accept(
|
||||||
|
target: str, meta: PartWithBounds, queue: list[tuple[PartWithBounds, str]]
|
||||||
|
) -> int:
|
||||||
|
count = 0
|
||||||
|
if target in workflows:
|
||||||
|
logging.info(f" transfer to {target}")
|
||||||
|
queue.append((meta, target))
|
||||||
|
elif target == "A":
|
||||||
|
count = prod((high - low + 1) for low, high in meta.values())
|
||||||
|
logging.info(f" accepted ({count})")
|
||||||
|
else:
|
||||||
|
logging.info(" rejected")
|
||||||
|
return count
|
||||||
|
|
||||||
|
accepted = 0
|
||||||
|
queue: list[tuple[PartWithBounds, str]] = [(start, "in")]
|
||||||
|
|
||||||
|
n_iterations = 0
|
||||||
|
|
||||||
|
while queue:
|
||||||
|
n_iterations += 1
|
||||||
|
meta, workflow = queue.pop()
|
||||||
|
logging.info(f"{workflow}: {_fmt(meta)}")
|
||||||
|
for check, target in workflows[workflow]:
|
||||||
|
if check is None:
|
||||||
|
logging.info(" end-of-workflow")
|
||||||
|
accepted += transfer_or_accept(target, meta, queue)
|
||||||
|
continue
|
||||||
|
|
||||||
|
category, sense, value = check
|
||||||
|
bounds, op = meta[category], OPERATORS[sense]
|
||||||
|
|
||||||
|
logging.info(f" checking {_fmt(meta)} against {category} {sense} {value}")
|
||||||
|
|
||||||
|
if not op(bounds[0], value) and not op(bounds[1], value):
|
||||||
|
logging.info(" reject, always false")
|
||||||
|
continue
|
||||||
|
|
||||||
|
if op(meta[category][0], value) and op(meta[category][1], value):
|
||||||
|
logging.info(" accept, always true")
|
||||||
|
accepted += transfer_or_accept(target, meta, queue)
|
||||||
|
break
|
||||||
|
|
||||||
|
meta2 = meta.copy()
|
||||||
|
low, high = meta[category]
|
||||||
|
if sense == "<":
|
||||||
|
meta[category], meta2[category] = (value, high), (low, value - 1)
|
||||||
|
else:
|
||||||
|
meta[category], meta2[category] = (low, value), (value + 1, high)
|
||||||
|
logging.info(f" split {_fmt(meta2)} ({target}), {_fmt(meta)}")
|
||||||
|
|
||||||
|
accepted += transfer_or_accept(target, meta2, queue)
|
||||||
|
|
||||||
|
logging.info(f"run took {n_iterations} iterations")
|
||||||
|
return accepted
|
||||||
|
|
||||||
|
|
||||||
|
workflows_s, parts_s = sys.stdin.read().strip().split("\n\n")
|
||||||
|
|
||||||
|
workflows: dict[str, Workflow] = {}
|
||||||
|
for workflow_s in workflows_s.split("\n"):
|
||||||
|
name, block_s = workflow_s.split("{")
|
||||||
|
workflows[name] = []
|
||||||
|
|
||||||
|
for block in block_s[:-1].split(","):
|
||||||
|
check: Check
|
||||||
|
if (i := block.find(":")) >= 0:
|
||||||
|
check, target = (
|
||||||
|
cast(Category, block[0]),
|
||||||
|
cast(Literal["<", ">"], block[1]),
|
||||||
|
int(block[2:i]),
|
||||||
|
), block[i + 1 :]
|
||||||
|
else:
|
||||||
|
check, target = None, block
|
||||||
|
workflows[name].append((check, target))
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
parts: list[Part] = [
|
||||||
|
{cast(Category, s[0]): int(s[2:]) for s in part_s[1:-1].split(",")}
|
||||||
|
for part_s in parts_s.split("\n")
|
||||||
|
]
|
||||||
|
answer_1 = sum(sum(part.values()) for part in parts if accept(workflows, part))
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
answer_2 = propagate(
|
||||||
|
workflows, {cast(Category, c): (1, 4000) for c in ["x", "m", "a", "s"]}
|
||||||
|
)
|
||||||
|
print(f"answer 2 is {answer_2}")
|
@ -1,6 +1,5 @@
|
|||||||
import operator
|
import math
|
||||||
import sys
|
import sys
|
||||||
from functools import reduce
|
|
||||||
from typing import Literal, TypeAlias, cast
|
from typing import Literal, TypeAlias, cast
|
||||||
|
|
||||||
CubeType: TypeAlias = Literal["red", "blue", "green"]
|
CubeType: TypeAlias = Literal["red", "blue", "green"]
|
||||||
@ -36,9 +35,8 @@ print(f"answer 1 is {answer_1}")
|
|||||||
|
|
||||||
# part 2
|
# part 2
|
||||||
answer_2 = sum(
|
answer_2 = sum(
|
||||||
reduce(
|
math.prod(
|
||||||
operator.mul,
|
max(cube_set.get(cube, 0) for cube_set in set_of_cubes) for cube in MAX_CUBES
|
||||||
(max(cube_set.get(cube, 0) for cube_set in set_of_cubes) for cube in MAX_CUBES),
|
|
||||||
)
|
)
|
||||||
for set_of_cubes in games.values()
|
for set_of_cubes in games.values()
|
||||||
)
|
)
|
161
src/holt59/aoc/2023/day20.py
Normal file
161
src/holt59/aoc/2023/day20.py
Normal file
@ -0,0 +1,161 @@
|
|||||||
|
import logging
|
||||||
|
import os
|
||||||
|
import sys
|
||||||
|
from collections import defaultdict
|
||||||
|
from math import lcm
|
||||||
|
from typing import Literal, TypeAlias
|
||||||
|
|
||||||
|
VERBOSE = os.getenv("AOC_VERBOSE") == "True"
|
||||||
|
logging.basicConfig(level=logging.INFO if VERBOSE else logging.WARNING)
|
||||||
|
|
||||||
|
|
||||||
|
ModuleType: TypeAlias = Literal["broadcaster", "conjunction", "flip-flop"]
|
||||||
|
PulseType: TypeAlias = Literal["high", "low"]
|
||||||
|
|
||||||
|
modules: dict[str, tuple[ModuleType, list[str]]] = {}
|
||||||
|
|
||||||
|
lines = sys.stdin.read().splitlines()
|
||||||
|
|
||||||
|
for line in lines:
|
||||||
|
name, outputs_s = line.split(" -> ")
|
||||||
|
outputs = outputs_s.split(", ")
|
||||||
|
if name == "broadcaster":
|
||||||
|
modules["broadcaster"] = ("broadcaster", outputs)
|
||||||
|
else:
|
||||||
|
modules[name[1:]] = (
|
||||||
|
"conjunction" if name.startswith("&") else "flip-flop",
|
||||||
|
outputs,
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
def process(
|
||||||
|
start: tuple[str, str, PulseType],
|
||||||
|
flip_flop_states: dict[str, Literal["on", "off"]],
|
||||||
|
conjunction_states: dict[str, dict[str, PulseType]],
|
||||||
|
) -> tuple[dict[PulseType, int], dict[str, dict[PulseType, int]]]:
|
||||||
|
pulses: list[tuple[str, str, PulseType]] = [start]
|
||||||
|
counts: dict[PulseType, int] = {"low": 0, "high": 0}
|
||||||
|
inputs: dict[str, dict[PulseType, int]] = defaultdict(lambda: {"low": 0, "high": 0})
|
||||||
|
|
||||||
|
logging.info("starting process... ")
|
||||||
|
|
||||||
|
while pulses:
|
||||||
|
input, name, pulse = pulses.pop(0)
|
||||||
|
logging.info(f"{input} -{pulse}-> {name}")
|
||||||
|
counts[pulse] += 1
|
||||||
|
|
||||||
|
inputs[name][pulse] += 1
|
||||||
|
|
||||||
|
if name not in modules:
|
||||||
|
continue
|
||||||
|
|
||||||
|
type, outputs = modules[name]
|
||||||
|
|
||||||
|
if type == "broadcaster":
|
||||||
|
...
|
||||||
|
|
||||||
|
elif type == "flip-flop":
|
||||||
|
if pulse == "high":
|
||||||
|
continue
|
||||||
|
|
||||||
|
if flip_flop_states[name] == "off":
|
||||||
|
flip_flop_states[name] = "on"
|
||||||
|
pulse = "high"
|
||||||
|
else:
|
||||||
|
flip_flop_states[name] = "off"
|
||||||
|
pulse = "low"
|
||||||
|
|
||||||
|
else:
|
||||||
|
conjunction_states[name][input] = pulse
|
||||||
|
|
||||||
|
if all(state == "high" for state in conjunction_states[name].values()):
|
||||||
|
pulse = "low"
|
||||||
|
else:
|
||||||
|
pulse = "high"
|
||||||
|
|
||||||
|
pulses.extend((name, output, pulse) for output in outputs)
|
||||||
|
|
||||||
|
return counts, inputs
|
||||||
|
|
||||||
|
|
||||||
|
with open("./day20.dot", "w") as fp:
|
||||||
|
fp.write("digraph G {\n")
|
||||||
|
fp.write("rx [shape=circle, color=red, style=filled];\n")
|
||||||
|
for name, (type, outputs) in modules.items():
|
||||||
|
if type == "conjunction":
|
||||||
|
shape = "diamond"
|
||||||
|
elif type == "flip-flop":
|
||||||
|
shape = "box"
|
||||||
|
else:
|
||||||
|
shape = "circle"
|
||||||
|
fp.write(f"{name} [shape={shape}];\n")
|
||||||
|
for name, (type, outputs) in modules.items():
|
||||||
|
for output in outputs:
|
||||||
|
fp.write(f"{name} -> {output};\n")
|
||||||
|
fp.write("}\n")
|
||||||
|
|
||||||
|
# part 1
|
||||||
|
flip_flop_states: dict[str, Literal["on", "off"]] = {
|
||||||
|
name: "off" for name, (type, _) in modules.items() if type == "flip-flop"
|
||||||
|
}
|
||||||
|
conjunction_states: dict[str, dict[str, PulseType]] = {
|
||||||
|
name: {input: "low" for input, (_, outputs) in modules.items() if name in outputs}
|
||||||
|
for name, (type, _) in modules.items()
|
||||||
|
if type == "conjunction"
|
||||||
|
}
|
||||||
|
counts: dict[PulseType, int] = {"low": 0, "high": 0}
|
||||||
|
for _ in range(1000):
|
||||||
|
result, _ = process(
|
||||||
|
("button", "broadcaster", "low"), flip_flop_states, conjunction_states
|
||||||
|
)
|
||||||
|
for pulse in ("low", "high"):
|
||||||
|
counts[pulse] += result[pulse]
|
||||||
|
answer_1 = counts["low"] * counts["high"]
|
||||||
|
print(f"answer 1 is {answer_1}")
|
||||||
|
|
||||||
|
# part 2
|
||||||
|
|
||||||
|
# reset states
|
||||||
|
for name in flip_flop_states:
|
||||||
|
flip_flop_states[name] = "off"
|
||||||
|
|
||||||
|
for name in conjunction_states:
|
||||||
|
for input in conjunction_states[name]:
|
||||||
|
conjunction_states[name][input] = "low"
|
||||||
|
|
||||||
|
# find the conjunction connected to rx
|
||||||
|
to_rx = [name for name, (_, outputs) in modules.items() if "rx" in outputs]
|
||||||
|
assert len(to_rx) == 1, "cannot handle multiple module inputs for rx"
|
||||||
|
assert (
|
||||||
|
modules[to_rx[0]][0] == "conjunction"
|
||||||
|
), "can only handle conjunction as input to rx"
|
||||||
|
|
||||||
|
to_rx_inputs = [name for name, (_, outputs) in modules.items() if to_rx[0] in outputs]
|
||||||
|
assert all(
|
||||||
|
modules[i][0] == "conjunction" and len(modules[i][1]) == 1 for i in to_rx_inputs
|
||||||
|
), "can only handle inversion as second-order inputs to rx"
|
||||||
|
|
||||||
|
|
||||||
|
count = 1
|
||||||
|
cycles: dict[str, int] = {}
|
||||||
|
second: dict[str, int] = {}
|
||||||
|
while len(second) != len(to_rx_inputs):
|
||||||
|
_, inputs = process(
|
||||||
|
("button", "broadcaster", "low"), flip_flop_states, conjunction_states
|
||||||
|
)
|
||||||
|
|
||||||
|
for node in to_rx_inputs:
|
||||||
|
if inputs[node]["low"] == 1:
|
||||||
|
if node not in cycles:
|
||||||
|
cycles[node] = count
|
||||||
|
elif node not in second:
|
||||||
|
second[node] = count
|
||||||
|
|
||||||
|
count += 1
|
||||||
|
|
||||||
|
assert all(
|
||||||
|
second[k] == cycles[k] * 2 for k in to_rx_inputs
|
||||||
|
), "cannot only handle cycles starting at the beginning"
|
||||||
|
|
||||||
|
answer_2 = lcm(*cycles.values())
|
||||||
|
print(f"answer 2 is {answer_2}")
|
Some files were not shown because too many files have changed in this diff Show More
Loading…
Reference in New Issue
Block a user