In general your solutions are more elegant.
Great use of available libraries
Like your solutions for day3 (spiral memory), day11 (hex grid)
In [1]:
digits = '91212129'
In [2]:
L = len(digits)
sum([int(digits[i]) for i in range(L) if digits[i] == digits[(i+1) % L]])
Out[2]:
In [3]:
def solve(captcha):
captcha = list(map(int, captcha))
prev_val = captcha[-1]
repeated = 0
for v in captcha:
if v == prev_val:
repeated += v
prev_val = v
return repeated
solve(digits)
Out[3]:
In [24]:
import numpy as np
def number_to_coordinates(n):
q = int(np.sqrt(n))
r = n - q ** 2
if q % 2 != 0:
x = (q - 1) // 2 + min(1, r) + min(q - r + 1, 0)
y = - (q - 1) // 2 + min(max(r - 1, 0), q)
else:
x = 1 - (q // 2) - min(1, r) - min(q - r + 1, 0)
y = q // 2 - min(max(r - 1, 0), q)
return x, y
def spiral_manhattan(n):
x, y = number_to_coordinates(n)
return abs(x) + abs(y)
spiral_manhattan(1024)
Out[24]:
In [26]:
import math
def get_side_size(point):
side_size = math.ceil(math.sqrt(point))
if side_size % 2 == 0:
side_size += 1
return side_size
def get_displacement(point, ring):
distances = []
for i in [1,3,5,7]:
distances.append(abs(point-i*ring))
return min(distances)
def distance(point):
if point == 1:
return 0
else:
side_size = get_side_size(point)
radius = (side_size - 1) // 2
rescaled = point - (side_size-2)**2
displacement = get_displacement(rescaled, radius)
return displacement + radius
distance(1024)
Out[26]:
In [5]:
instructions = [0, 3, 0, 1, -3]
In [6]:
class Maze(object):
def __init__(self, curr_pos, state):
self.curr_pos = curr_pos
self.state = state.copy()
self.length = len(self.state)
def evolve(self):
self.state[self.curr_pos] += 1
self.curr_pos += self.state[self.curr_pos] - 1
def outside(self):
return (self.curr_pos >= self.length) or (self.curr_pos < 0)
def steps_maze(l):
maze = Maze(0, l)
count = 0
while not maze.outside():
maze.evolve()
count += 1
return count, maze.state
steps_maze(instructions)
Out[6]:
In [7]:
def steps2exit(instructions):
position = 0
steps = 0
try:
while True:
jump = instructions[position]
instructions[position] = jump + 1
position += jump
steps += 1
except IndexError:
return steps
steps2exit(instructions)
Out[7]:
In [16]:
%%timeit
steps_maze(instructions)
In [17]:
%%timeit
steps2exit(instructions)
In [9]:
banks = [0, 2, 7, 0]
In [10]:
def reallocate(val, pos, n):
l = [val // n] * n
r = val % n
for i in range(r):
l[(pos + i + 1) % n] += 1
return l
def update(b):
blocks = sorted(list(enumerate(b)), key=lambda v: (v[1], -v[0]), reverse=True)
pos = blocks[0][0]
val = blocks[0][1]
c = [b[i] if i != pos else 0 for i in range(len(b))]
l = reallocate(val, pos, len(b))
for i, v in enumerate(c):
c[i] += l[i]
return c
def count_until_loop(b):
count = 0
previous = set()
h = hash(tuple(b))
while h not in previous:
previous.add(h)
count += 1
b = update(b)
h = hash(tuple(b))
return count
count_until_loop(banks)
Out[10]:
In [11]:
class Memory:
def __init__(self, banks):
self.banks = banks
self.states = []
def _find_fullest(self):
blocks = max(self.banks)
return self.banks.index(blocks), blocks
def _redistribue(self):
pos, blocks = self._find_fullest()
self.banks[pos] = 0
while blocks > 0:
pos += 1
if pos >= len(self.banks):
pos = 0
self.banks[pos] += 1
blocks -= 1
def realloate_till_loop(self):
redistributions = 0
self.states.append(self.banks.copy())
while True:
self._redistribue()
redistributions += 1
configuration = self.banks.copy()
if configuration in self.states:
break
else:
self.states.append(configuration)
return redistributions
Memory(banks).realloate_till_loop()
Out[11]:
In [18]:
%%timeit
count_until_loop(banks)
In [19]:
%%timeit
Memory(banks).realloate_till_loop()
In [22]:
def pick_cherry(leaves):
while leaves:
leaf = leaves.pop()
parent = parents[leaf]
offspring = children[parent]
try:
for child in offspring:
assert(children[child] == [])
return parent
except AssertionError:
pass
In [ ]:
class Unbalanced(Exception):
pass
In [23]:
def apply_instructions(registers):
for reg, leap, cond in instructions:
bool_str = 'registers["{0}"]'.format(cond[0]) + ''.join(cond[1:])
update_str = 'if {0}: registers["{1}"] += {2} '.format(bool_str, reg, leap)
exec(update_str)
In [ ]:
import operator
comparisons = {'>': operator.gt, '>=': operator.ge, '<': operator.lt,
'<=': operator.le, '==': operator.eq, '!=': operator.ne}
def process(instruction):
reg, operation, val, condition = parse(instruction)
cond_reg, cond_op, cond_val = condition
if cond_op(registers[cond_reg], cond_val):
registers[reg] = operation(registers[reg], val)
In [29]:
def connected(node, pipes):
neighbors = pipes[node]
pending = list(neighbors)
while pending:
alice = pending.pop(0)
for bob in pipes[alice]:
if bob in neighbors:
pass # ---> continue
else:
neighbors.add(bob)
pending.append(bob)
return neighbors
In [31]:
def parse_scanners(input_file):
scanners = defaultdict(int)
with open(input_file, 'rt') as f_input:
csv_reader = csv.reader(f_input, delimiter=' ')
for l in csv_reader:
scanners[int(l[0].rstrip(':'))] = int(l[1].rstrip())
return scanners
In [32]:
def parse(lines):
layers_depth = {}
for line in lines:
l = line.strip().split(': ')
layers_depth[int(l[0])] = int(l[1])
return layers_depth
And do not need to do too many things
In [34]:
test_input = """0: 3
1: 2
4: 4
6: 4""".splitlines()
layers = parse(test_input)
In [38]:
import collections
def tick(lrank, time):
r = time % (2 * (lrank - 1))
return (r <= lrank - 1) * r + (r > lrank - 1) * (2 * (lrank - 1) - r)
def get_state(time, scanners):
state = dict(zip(list(scanners.keys()), [0] * len(scanners)))
if time == 0:
return state
elif time > 0:
for t in range(time + 1):
for scanner in scanners:
state[scanner] = tick(scanners[scanner], t)
return state
def trip_severity(scanners):
severity = 0
layers = max(list(scanners.keys()))
for t in range(layers + 1):
if scanners[t] != 0:
tick_before = tick(scanners[t], t)
tick_now = tick(scanners[t], t + 1)
if (tick_before == 0):
severity += scanners[t] * t
return severity
scanners = collections.defaultdict(int)
scanners.update(layers)
trip_severity(scanners)
Out[38]:
In [39]:
def severity(layers_depth, start_time=0):
severity_ = 0
for i, depth in layers_depth.items():
if (start_time + i) % ((depth-1) * 2) == 0:
severity_ += i*depth
return severity_
severity(layers)
Out[39]:
In [41]:
class FancyGen(object):
def __init__(self, start, factor):
self.start = start
self.factor = factor
self.q = 2147483647
def __iter__(self):
self.a = self.start
return self
def __next__(self):
n = (self.a * self.factor) % self.q
self.a = n
return n
def compare_lowest_bits(n, m):
n = n % (2 ** 16)
m = m % (2 ** 16)
return n == m
def duel(starta, startb):
N = 40 * 10 ** 6
count = 0
gena = iter(FancyGen(starta, 16807))
genb = iter(FancyGen(startb, 48271))
for _ in range(N):
if compare_lowest_bits(next(gena), next(genb)):
count += 1
return count
In [42]:
%%timeit
duel(65, 8921)
In [47]:
def generator(start_value, factor):
val = start_value
while True:
val = val * factor % 2147483647
yield val
def compare(start_A, start_B, rounds):
matches = 0
for i, values in enumerate(zip(generator(start_A, 16807), generator(start_B, 48271))):
if i >= rounds:
return matches
else:
vA, vB = values
if vA.to_bytes(100, 'big')[-2:] == vB.to_bytes(100, 'big')[-2:]:
matches += 1
In [48]:
%%timeit
compare(65, 8921, 40*10**6)
In [49]:
import re
import numpy as np
import copy
def shuffle(p, moves):
s = copy.copy(p)
for move in moves:
spin = re.search('s(\d+)', move)
swapx = re.search('x(\d+)\/(\d+)', move)
swapp = re.search('p(\w)\/(\w)', move)
if spin:
s = np.roll(s, int(spin.group(1)))
if swapx:
a = int(swapx.group(1))
b = int(swapx.group(2))
s[a], s[b] = s[b], s[a]
if swapp:
a = swapp.group(1)
b = swapp.group(2)
a = ''.join(s).index(a)
b = ''.join(s).index(b)
s[a], s[b] = s[b], s[a]
return ''.join(s)
In [57]:
%%timeit
shuffle(list('abcde'), ['s1', 'x3/4', 'pe/b'])
In [51]:
def parse(instruction):
name = instruction[0]
params = instruction[1:]
if name == 's':
params = [int(params)]
else:
params = params.split('/')
if name == 'x':
params = list(map(int, params))
return name, params
class Programs:
def __init__(self, progs):
self.progs = progs
self.length = len(self.progs)
self.instructions_dict = {'s': self.spin, 'x': self.exchange, 'p': self.partner}
def spin(self, pos):
pos = pos % self.length
if pos > 0:
tmp = self.progs[-pos:]
progs = tmp + self.progs
self.progs = progs[:self.length]
def exchange(self, pos1, pos2):
v1 = self.progs[pos1]
v2 = self.progs[pos2]
self.progs = self.progs[:pos1] + v2 + self.progs[pos1+1:]
self.progs = self.progs[:pos2] + v1 + self.progs[pos2+1:]
def partner(self, prog1, prog2):
self.exchange(self.progs.index(prog1), self.progs.index(prog2))
def dance(self, instructions):
for inst, params in instructions:
self.instructions_dict[inst](*params)
return p.progs
In [58]:
%%timeit
p = Programs('abcde')
p.dance([parse(inst) for inst in ['s1', 'x3/4', 'pe/b']])
In [54]:
import re
import numpy as np
import copy
regex1 = re.compile('s(\d+)')
regex2 = re.compile('x(\d+)\/(\d+)')
regex3 = re.compile('p(\w)\/(\w)')
def shuffle2(p, moves):
s = copy.copy(p)
for move in moves:
spin = regex1.search(move)
swapx = regex2.search(move)
swapp = regex3.search(move)
if spin:
s = np.roll(s, int(spin.group(1)))
if swapx:
a = int(swapx.group(1))
b = int(swapx.group(2))
s[a], s[b] = s[b], s[a]
if swapp:
a = swapp.group(1)
b = swapp.group(2)
a = ''.join(s).index(a)
b = ''.join(s).index(b)
s[a], s[b] = s[b], s[a]
return ''.join(s)
In [59]:
%%timeit
shuffle2(list('abcde'), ['s1', 'x3/4', 'pe/b'])
In [62]:
test_input = """..#
#..
...""".splitlines()
In [71]:
import numpy as np
from collections import defaultdict
def parse_grid(f_input):
grid = defaultdict(lambda: '.')
size = 0
for l in f_input:
hash_row = {hash(np.array([size, i], dtype=np.int16).tostring()): v for i, v in enumerate(list(l.rstrip()))}
grid.update(hash_row)
size += 1
return grid, size
class Virus(object):
def __init__(self, grid, size):
self.grid = grid # enclosing the hashes and states of infected positions
self.pos = np.array([(size - 1) // 2, (size - 1) // 2], dtype=np.int16) # initially in the center of a positive grid
self.facing = np.array([-1, 0], dtype=np.int16) # initially facing up in our coords
self.count_infect = 0
def burst(self):
hash_pos = hash(self.pos.tostring())
rotation = np.array([[0, -1], [1, 0]], dtype=np.int16)
self.facing = np.dot(rotation, self.facing)
if self.grid[hash_pos] == '#':
self.grid[hash_pos] = '.'
self.facing *= -1
else:
self.grid[hash_pos] = '#'
self.count_infect += 1
self.pos += self.facing
def count_infect(grid, size, n):
test_virus = Virus(grid, size)
for _ in range(n):
test_virus.burst()
return test_virus.count_infect
grid, size = parse_grid(test_input)
In [72]:
%%timeit
count_infect(grid, size, 10000)
In [69]:
directions = 'nesw'
directions2move = {'n': (0, 1), 's': (0, -1), 'e': (1, 0), 'w': (-1, 0)}
def parse(lines):
nodes = []
size = len(lines[0].strip())
v = size // 2
for i, line in enumerate(lines):
for j, c in enumerate(line.strip()):
if c == '#':
nodes.append((j-v, (i-v)*(-1)))
return set(nodes)
def burst(infected_nodes, pos, direction):
x, y = pos
# next direction
if pos in infected_nodes:
i = (directions.index(direction) + 1) % 4
infected_nodes.remove(pos)
else:
i = (directions.index(direction) - 1) % 4
infected_nodes.add(pos)
next_direction = directions[i]
# next position
a, b = directions2move[next_direction]
next_pos = (x+a, y+b)
return infected_nodes, next_pos, next_direction
def count_infections(initial_status, iterations):
count = 0
status = initial_status
pos = (0,0)
direction = 'n'
for _ in range(iterations):
prev_size = len(status)
status, pos, direction = burst(status, pos, direction)
count += 1 if len(status) > prev_size else 0 # should be 0 or 1
return count
nodes = parse(test_input)
In [73]:
%%timeit
count_infections(nodes, 10**4)
In [84]:
def is_prime(x):
if x >= 2:
for y in range(2,x):
if not ( x % y ):
return False
else:
return False
return True
def run_coprocessor(alpha):
loop = False
a, b = alpha, 79
c = b
d, e, f, g, h = 0, 0, 0, 0, 0
if a != 0:
b *= 100
b += 100000
c = b
c += 17000
while (g != 0) or not loop:
loop = True
f = 1
d = 2
e = 2
if not is_prime(b):
f = 0
e = b
d = b
if f == 0:
h += 1
g = b
g = g - c
if g == 0:
return a, b, c, d, e, f, g, h
else:
b += 17
In [85]:
run_coprocessor(1)
In [86]:
def isprime(value):
for i in range(2, value):
if (value % i) == 0:
return False
return True
def count_primes(init, end, step):
count = 0
for i in range(init, end+1, step):
if isprime(i):
count += 1
return count
def part2():
b = 106500
c = 123500
h = (c-b)/17 # each loop b increases 17 until it matches c
h += 1 # there is an extra loop when b == c ??
h -= count_primes(b, c, 17) # on primes, f is set to 0 and h not increased
return int(h)
In [87]:
part2()
In [ ]: