Skip to content

Instantly share code, notes, and snippets.

@jackdreilly
Created February 6, 2021 14:40
Show Gist options
  • Save jackdreilly/3b69027a1415e55adc7ff8462c0c832e to your computer and use it in GitHub Desktop.
Save jackdreilly/3b69027a1415e55adc7ff8462c0c832e to your computer and use it in GitHub Desktop.
from parse import parse
store = {}
zeroer, orer = None, None
with open("data/14.txt") as fn:
for line in fn.readlines():
line = line.strip()
r = parse("mem[{}] = {}", line)
if r:
i, v = map(int, r)
store[i] = (v & zeroer) | orer
if not r:
(mask,) = parse("mask = {}", line)
zeroer = int("0b" + "".join("1" if x == "X" else "0" for x in mask), 2)
orer = int("0b" + "".join("0" if x in "X0" else "1" for x in mask), 2)
print(sum(store.values()))
from parse import parse
store = {}
def looper(ander, orer, child):
if not len(child):
yield tuple(int("0b" + x, 2) for x in (ander, orer))
return
letter, rest = child[0], child[1:]
if letter == "X":
for b in ("0", "1"):
yield from looper(ander + b, orer + b, rest)
return
yield from looper(ander + "1", orer + letter, rest)
with open("data/14.txt") as fn:
for line in fn.readlines():
r = parse("mem[{}] = {}", line.strip())
if r:
i, v = map(int, r)
for ander, orer in masks:
store[(i & ander) | orer] = v
continue
masks = list(looper("", "", parse("mask = {}", line.strip())[0]))
print(sum(store.values()))
starts = [0,13,16,17,1,10,6]
nums = {v: k for k, v in enumerate(starts[:-1])}
last = starts[-1]
for i in range(len(nums), 30000000 - 1):
next = 0 if last not in nums else i - nums[last]
nums[last] = i
last = next
print(last)
from parse import parse
import itertools
import math
with open("data/16.txt") as fn:
ranges = []
mine = None
while True:
line = fn.readline().strip()
if not line:
fn.readline()
mine = list(map(int, fn.readline().strip().split(",")))
fn.readline()
fn.readline()
break
p = parse("{}: {}-{} or {}-{}", line)
ranges.append((p[0], list(map(int, p[1:]))))
theirs = [list(map(int, line.strip().split(","))) for line in fn.readlines()]
keepers = [
x
for x in theirs
if all(any(a <= y <= b or c <= y <= d for _, (a, b, c, d) in ranges) for y in x)
] + [mine]
zips = list(zip(*keepers))
candidates = {
k: tuple(
i for i, vs in enumerate(zips) if all(a <= y <= b or c <= y <= d for y in vs)
)
for k, (a, b, c, d) in ranges
}
inverted = {
k: {b for _, b in v}
for k, v in itertools.groupby(
sorted(
((v, k) for k, vs in candidates.items() for v in vs), key=lambda a: a[0]
),
lambda a: a[0],
)
}
sln = {}
for k, v in sorted(inverted.items(), key=lambda a: len(a[1])):
sln[next(iter(v.difference(set(sln.keys()))))] = k
print(math.prod(mine[i] for k, i in sln.items() if "departure" in k))
with open("data/17.txt") as fn:
r = fn.read().strip()
dim = 5
cubes = {
(x, y) + tuple([0] * (dim - 2))
for x, row in enumerate(r.split("\n"))
for y, col in enumerate(row)
if col == "#"
}
def perms(i):
if not i:
yield tuple()
return
for j in range(-1, 2):
for p in perms(i - 1):
yield (j, *p)
_perms = list(perms(dim))
perms = lambda cube: {tuple(map(sum, zip(cube, perm))) for perm in _perms}
for _ in range(6):
cubes = {
cube
for ct, cube in [
(len(perms(cube).intersection(cubes)), cube)
for cube in {perm_cube for cube in cubes for perm_cube in perms(cube)}
]
if (cube in cubes and ct in {3, 4}) or ct == 3
}
print(len(cubes))
with open("data/18.txt") as fn:
r = [x.strip() for x in fn.readlines()]
class Stack:
def __init__(self, parent=None):
self.l = []
self.parent = parent
self.v = None
self.op = None
def run(self, x):
if not self.op:
self.v = x
return
if self.op == "*":
self.v *= x
return
self.v += x
def child(self):
self.l.append(Stack(self))
return self.l[-1]
def construct(self):
return [x.construct() if isinstance(x, Stack) else x for x in self.l]
def solve(x):
stack = Stack()
while len(x):
c, o = x.find(")"), x.find("(")
if c < 0 and o < 0:
s = [y.strip() for y in x.split(" ")]
for ss in s:
if not len(ss):
continue
if ss in {"+", "*"}:
stack.op = ss
continue
stack.run(int(ss))
break
c, o = [99999 if x < 0 else x for x in (c, o)]
if min(o, c) > 0:
s = [y.strip() for y in x[: min(o, c)].split(" ")]
for ss in s:
if not len(ss):
continue
if ss in {"+", "*"}:
stack.op = ss
continue
stack.run(int(ss))
x = x[min(o, c) + 1 :]
if o < c:
stack = stack.child()
continue
stack.parent.run(stack.v)
stack = stack.parent
return stack.v
print(sum(map(solve, r)))
with open("data/18.txt") as fn:
r = [x.strip() for x in fn.readlines()]
class Stack:
def __init__(self, parent=None):
self.l = []
self.parent = parent
self.v = None
self.op = None
def run(self, x):
if not self.op:
self.v = x
return
if self.op == "*":
self.v *= x
return
self.v += x
def child(self):
self.l.append(Stack(self))
return self.l[-1]
def construct(self):
return [x.construct() if isinstance(x, Stack) else x for x in self.l]
def find_nth(haystack, needle, n):
start = haystack.find(needle)
while start >= 0 and n > 1:
start = haystack.find(needle, start + len(needle))
n -= 1
return start
def rewrite(x):
for i in range(len([1 for xx in x if xx == "+"])):
j = find_nth(x, "+", i+1)
l, r = j, j
brace = 0
seal = False
while l != 0 and (brace != 0 or (str(x[l]) not in "1234567890" and not seal)):
if x[l] == ")":
brace += 1
seal = True
if x[l] == "(":
brace -= 1
seal = True
l -= 1
while l != 0 and x[l] in "1234567890":
l -= 1
brace = 0
seal = False
while r != len(x) and (brace != 0 or (str(x[r]) not in "1234567890" and not seal)):
if x[r] == ")":
brace += 1
seal = True
if x[r] == "(":
brace -= 1
seal = True
r += 1
while r != len(x) and x[r] in "1234567890":
r += 1
print(i, j, l, r)
x = f"{x[:l]} ({x[l:j-1]} + {x[j+1:r]}) {x[r:]}"
print(x)
return x
def solve(x):
stack = Stack()
while len(x):
c, o = x.find(")"), x.find("(")
if c < 0 and o < 0:
s = [y.strip() for y in x.split(" ")]
for ss in s:
if not len(ss):
continue
if ss in {"+", "*"}:
stack.op = ss
continue
stack.run(int(ss))
break
c, o = [99999 if x < 0 else x for x in (c, o)]
if min(o, c) > 0:
s = [y.strip() for y in x[: min(o, c)].split(" ")]
for ss in s:
if not len(ss):
continue
if ss in {"+", "*"}:
stack.op = ss
continue
stack.run(int(ss))
x = x[min(o, c) + 1 :]
if o < c:
stack = stack.child()
continue
stack.parent.run(stack.v)
stack = stack.parent
return stack.v
print(sum(map(solve, map(rewrite,r))))
from parse import parse
with open("data/19.txt") as fn:
rules = {}
guesses = []
for line in fn.readlines():
if not line.strip():
continue
a = parse("{}: {}", line.strip())
if a:
key, rest = a
key = int(key)
if '"' in rest:
rules[key] = parse('"{}"', rest)[0]
else:
rules[key] = [
[int(y) for y in x.split(" ") if y.strip()] for x in a[1].split("|")
]
else:
guesses.append(line.strip())
def all_match(_guess):
def match(guess, rule):
rule = rules[rule]
if isinstance(rule, str):
return guess[0] == rule, guess[1:]
for or_cond in rule:
new_guess = guess
fail = False
for _rule in or_cond:
matches, rest = match(new_guess, _rule)
if not matches:
fail = True
break
new_guess = rest
if not fail:
return True, new_guess
return False, ""
a, b = match(_guess, 0)
return a and not b
print(sum(all_match(guess) for guess in guesses))
from parse import parse
with open("data/19.txt") as fn:
rules = {}
guesses = []
for line in fn.readlines():
if not line.strip():
continue
a = parse("{}: {}", line.strip())
if a:
key, rest = a
key = int(key)
if '"' in rest:
rules[key] = parse('"{}"', rest)[0]
else:
rules[key] = [
[int(y) for y in x.split(" ") if y.strip()] for x in a[1].split("|")
]
else:
guesses.append(line.strip())
rules[8] = [[42], [42, 8]]
rules[11] = [[42, 31], [42, 11, 31]]
def all_match(_guess):
def match(guesses, __rule):
rule = rules[__rule]
for guess in guesses:
if not guess:
return
if isinstance(rule, str):
if guess[0] == rule:
yield guess[1:]
continue
for or_cond in rule:
new_guesses = [guess]
fail = False
for _rule in or_cond:
new_guesses = list(match(new_guesses, _rule))
if not new_guesses:
fail = True
break
if not fail:
yield from new_guesses
return any(not x for x in match([_guess], 0))
print(sum(map(all_match, guesses)))
from parse import parse
with open("data/19.jack.txt") as fn:
rules = {}
guesses = []
for line in fn.readlines():
if not line.strip():
continue
a = parse("{}: {}", line.strip())
if a:
key, rest = a
key = int(key)
if '"' in rest:
rules[key] = parse('"{}"', rest)[0]
else:
rules[key] = [
[int(y) for y in x.split(" ") if y.strip()] for x in a[1].split("|")
]
else:
guesses.append(line.strip())
rules[8] = [[42], [42, 8]]
rules[11] = [[42, 31], [42, 11, 31]]
def all_match(_guess):
def match(guess, __rule):
if not guess:
return False, ""
rule = rules[__rule]
if isinstance(rule, str):
return guess[0] == rule, guess[1:]
for or_cond in rule:
new_guess = guess
fail = False
for _rule in or_cond:
matches, rest = match(new_guess, _rule)
if not matches:
fail = True
break
new_guess = rest
if not fail:
return True, new_guess
return False, ""
a, b = match(_guess, 0)
return a and not b
print(list(map(all_match,guesses)))
# print(sum(all_match(guess) for guess in guesses))
from parse import parse
with open("data/20a.txt") as fn:
tiles = {}
try:
while True:
id = int(parse("Tile {}:", fn.readline().strip())[0])
tiles[id] = [fn.readline().strip() for _ in range(10)]
fn.readline()
except:
pass
def rotate_matrix(m):
return [
"".join(m[j][i] for j in range(len(m))) for i in range(len(m[0]) - 1, -1, -1)
]
def get(tile, rotation, flip, side):
if flip:
tile = [x[::-1] for x in tile]
for _ in range((-rotation + 4) % 4):
tile = rotate_matrix(tile)
if side == 0:
return tile[0]
if side == 2:
return tile[-1]
if side == 1:
return "".join(row[-1] for row in tile)
return "".join(row[0] for row in tile)
assert get(tiles[1567], 0, 0, 0) == ".####.##.#"
assert get(tiles[1567], 1, 0, 1) == ".####.##.#"
assert get(tiles[1567], 2, 0, 2) == ".####.##.#"[::-1]
assert get(tiles[1567], 3, 0, 3) == ".####.##.#"[::-1]
assert get(tiles[1567], 0, 0, 2) == "#.#.#..##."
assert get(tiles[1567], 2, 0, 0) == "#.#.#..##."[::-1]
assert get(tiles[1567], 0, 0, 1) == "#....##.#."
assert get(tiles[1567], 3, 0, 0) == "#....##.#."
assert get(tiles[1567], 1, 0, 2) == "#....##.#."[::-1]
assert get(tiles[1567], 0, 0, 3) == ".....###.#"
assert get(tiles[1567], 3, 0, 2) == ".....###.#"
assert get(tiles[1567], 1, 0, 0) == ".....###.#"[::-1]
from collections import defaultdict, Counter
matches = defaultdict(set)
inverse = {}
for id, tile in tiles.items():
for rotation in range(4):
for flip in range(0, 2):
for side in range(4):
a, b = get(tile, rotation, flip, side), (id, rotation, flip, side)
matches[a].add(b)
inverse[b] = a
tiles = set(tiles)
size = int(len(tiles) ** 0.5)
def search(state):
n = len(state)
if n == len(tiles):
return state
row = n // size
col = n % size
lc, tc = None, None
existing = {t for t, _, __ in state.values()}
tc = inverse.get((*state.get((row - 1, col), (-1, -1)), 2), None)
lc = inverse.get((*state.get((row, col - 1), (-1, -1)), 1), None)
tc = {
(a, b, f)
for a, b, f, c in matches.get(tc, set())
if c == 0 and a not in existing
}
lc = {
(a, b, f)
for a, b, f, c in matches.get(lc, set())
if c == 3 and a not in existing
}
if not row and not col:
candidates = [
(tile_id, rotation, flip)
for tile_id in tiles
for flip in range(2)
for rotation in range(4)
]
elif not row or not col:
candidates = {*list(tc or set()), *list(lc or set())}
else:
candidates = tc.intersection(lc)
for tile_id, rotation, flip in candidates:
new_state = {**state, (row, col): (tile_id, rotation, flip)}
solution = search(new_state)
if solution:
return solution
sln = search({})
import math
print(
math.prod(
sln[a][0]
for a in (
(0, 0),
(size - 1, 0),
(size - 1, size - 1),
(0, size - 1),
)
)
)
from parse import parse
import math
tile_pixel_size = 10
with open("data/20a.txt") as fn:
tiles = {}
try:
while True:
id = int(parse("Tile {}:", fn.readline().strip())[0])
tiles[id] = [fn.readline().strip() for _ in range(tile_pixel_size)]
fn.readline()
except:
pass
def rotate_matrix(m):
return [
"".join(m[j][i] for j in range(len(m))) for i in range(len(m[0]) - 1, -1, -1)
]
def get(tile, rotation, flip, side=None):
if flip:
tile = [x[::-1] for x in tile]
for _ in range((-rotation + 4) % 4):
tile = rotate_matrix(tile)
if side is None:
return tile
if side == 0:
return tile[0]
if side == 2:
return tile[-1]
if side == 1:
return "".join(row[-1] for row in tile)
return "".join(row[0] for row in tile)
assert get(tiles[1567], 0, 0, 0) == ".####.##.#"
assert get(tiles[1567], 1, 0, 1) == ".####.##.#"
assert get(tiles[1567], 2, 0, 2) == ".####.##.#"[::-1]
assert get(tiles[1567], 3, 0, 3) == ".####.##.#"[::-1]
assert get(tiles[1567], 0, 0, 2) == "#.#.#..##."
assert get(tiles[1567], 2, 0, 0) == "#.#.#..##."[::-1]
assert get(tiles[1567], 0, 0, 1) == "#....##.#."
assert get(tiles[1567], 3, 0, 0) == "#....##.#."
assert get(tiles[1567], 1, 0, 2) == "#....##.#."[::-1]
assert get(tiles[1567], 0, 0, 3) == ".....###.#"
assert get(tiles[1567], 3, 0, 2) == ".....###.#"
assert get(tiles[1567], 1, 0, 0) == ".....###.#"[::-1]
from collections import defaultdict, Counter
matches = defaultdict(set)
inverse = {}
for id, tile in tiles.items():
for rotation in range(4):
for flip in range(0, 2):
for side in range(4):
a, b = get(tile, rotation, flip, side), (id, rotation, flip, side)
matches[a].add(b)
inverse[b] = a
size = int(len(tiles) ** 0.5)
def search(state):
n = len(state)
if n == len(tiles):
return state
row = n // size
col = n % size
lc, tc = None, None
existing = {t for t, _, __ in state.values()}
tc = inverse.get((*state.get((row - 1, col), (-1, -1)), 2), None)
lc = inverse.get((*state.get((row, col - 1), (-1, -1)), 1), None)
tc = {
(a, b, f)
for a, b, f, c in matches.get(tc, set())
if c == 0 and a not in existing
}
lc = {
(a, b, f)
for a, b, f, c in matches.get(lc, set())
if c == 3 and a not in existing
}
if not row and not col:
candidates = [
(tile_id, rotation, flip)
for tile_id in tiles
for flip in range(2)
for rotation in range(4)
]
elif not row or not col:
candidates = {*list(tc or set()), *list(lc or set())}
else:
candidates = tc.intersection(lc)
for tile_id, rotation, flip in candidates:
new_state = {**state, (row, col): (tile_id, rotation, flip)}
solution = search(new_state)
if solution:
return solution
sln = search({})
print(
math.prod(
sln[a][0]
for a in (
(0, 0),
(size - 1, 0),
(size - 1, size - 1),
(0, size - 1),
)
)
)
grid = [
"".join(
[
get(tiles[sln[(row, column)][0]], *sln[(row, column)][1:],)[
pixel_row
][pixel_column]
for column in range(size)
for pixel_column in range(1, tile_pixel_size - 1)
]
)
for row in range(size)
for pixel_row in range(1, tile_pixel_size - 1)
]
monster = """ #
# ## ## ###
# # # # # # """.split(
"\n"
)
indices = {
(i, j) for i, row in enumerate(monster) for j, col in enumerate(row) if col == "#"
}
n, m = len(monster), len(monster[0])
for rotate in range(4):
for flip in range(2):
g = get(grid, rotate, flip)
if sum(
1
for i in range(len(g) - n + 1)
for j in range(len(g[0]) - m + 1)
if all(g[i + ii][j + jj] == "#" for ii, jj in indices)
):
grid = get(grid, rotate, flip)
break
print(
len(
{
(i, j)
for i, row in enumerate(grid)
for j, col in enumerate(row)
if col == "#"
}.difference(
{
(i + ii, j + jj)
for i in range(len(grid) - n + 1)
for j in range(len(grid[0]) - m + 1)
if all(grid[i + ii][j + jj] == "#" for ii, jj in indices)
for ii, jj in indices
}
)
)
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment