Code

AoC 2016 Advent of Code (Python)

By telleropnul, December 31, 2016

Advent of Code (AoC) is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. Go check it out: Advent of Code

Input files: adventofcode2016inputs.zip

2016 Day 25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def execute(a):
    data = open('input').read().splitlines()
    register = {'a': a, 'b': 0, 'c': 0, 'd': 0}
    line = 0
    transmitted = [1]
 
    interpret = lambda val: register[val] if val.isalpha() else int(val)
 
    while line < len(data):
        instr, x, *y = data[line].split()
        y = y[0] if y else None
 
        if instr == 'out':
            x_ = interpret(x)
            if x_ not in {0, 1} or x_ == transmitted[-1]:
                return False
            else:
                transmitted.append(x_)
            if len(transmitted) > 10:
                return True
 
        if instr == 'cpy':
            register[y] = interpret(x)
 
        if instr == 'inc':
            register[x] += 1
 
        if instr == 'dec':
            register[x] -= 1
 
        if instr == 'jnz':
            if interpret(x) != 0:
                line += interpret(y)
                continue
 
        line += 1
 
 
i = 0
while True:
    result = execute(i)
    if result:
        break
    i += 1
 
print("Let me try every number, starting from zero, brute forcing it.")
print("The number I was looking for is:", i)

2016 Day 24 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from collections import deque
from itertools import permutations
 
maze = open('input').read().splitlines()
 
def bfs(start, goal):
    DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque([(start, 0)])
    seen = set(start)
 
    while que:
        (x, y), steps = que.popleft()
        if (x, y) == goal:
            return steps
        for dx, dy in DELTAS:
            nx, ny = (x+dx, y+dy)
            if not (nx, ny) in seen and maze[ny][nx] != '#':
                que.append(((nx, ny), steps+1))
                seen.add((nx, ny))
 
 
def find_shortest(second_part=False):
    min_dist = 1e9
    for path in permutations(range(1, len(coordinates))):
        path_dist = distances[0][path[0]]
        for a, b in zip(path, path[1:]):
            path_dist += distances[a][b]
        if second_part:
            path_dist += distances[b][0]
        min_dist = min(min_dist, path_dist)
    return min_dist
 
 
coordinates = {}
for y, row in enumerate(maze[1:-1], 1):
    for x, value in enumerate(row[1:-1], 1):
        if value.isdigit():
            coordinates[value] = (x, y)
 
distances = [[0 for _ in range(len(coordinates))] for _ in range(len(coordinates))]
 
points = sorted(coordinates.keys())
for start in points[:-1]:
    st = int(start)
    for goal in points[st+1:]:
        dist = bfs(coordinates[start], coordinates[goal])
        gl = int(goal)
        distances[st][gl] = distances[gl][st] = dist
 
print (find_shortest())
print (find_shortest(2))

2016 Day 23 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

def isInt(s):
    if s[0] in ('-', '+'):
        return s[1:].isdigit()
    return s.isdigit()
 
reg = {'a':12,'b':0,'c':0,'d':0}
 
data = open('input').read().splitlines()
data = [x.split(' ') for x in data]
 
i = 0
 
while i < len(data):
    d = data[i]
    if d[0] == 'cpy':
        t = d[1]
        r = d[2]
        ### Optimization no. 1 ###
        if not isInt(t) and not isInt(r):
            d1 = data[i+1]
            d2 = data[i+2]
            d3 = data[i+3]
 
            if d1[0] == 'dec' and d2[0] == 'inc' and d3[0] == 'jnz' and d3[2] == '-2':
                reg[d[1]] = reg[d[1]] * 2
                reg[d[2]] = 0
                i += 4
                continue
        ### End Optimization no. 1 ###
        if isInt(t) and isInt(r):
            i += 1
            continue
        if isInt(t):
            t = int(t)
        else:
            t = reg[t]
        reg[r] = t
 
    if d[0] == 'inc':
        ### Optimization no. 2 ###
        d1 = data[i+1]
        d2 = data[i+2]
        d3 = data[i+3]
        d4 = data[i+4]
        if d1[0] == 'dec' and d2[0] == 'jnz' and d2[2] == '-2' and d3[0] == 'dec' and d4[0] == 'jnz' and d4[2] == '-5':
            reg[d[1]] = reg[d[1]] + (reg[d1[1]] * reg[d3[1]])
            reg[d1[1]] = 0
            reg[d3[1]] = 0
            i += 5
            continue
        ### End Optimization no. 2 ###
        if d[1] in reg:
            reg[d[1]] = reg[d[1]] + 1
 
    if d[0] == 'dec':
        if d[1] in reg:
            reg[d[1]] = reg[d[1]] - 1
 
    if d[0] == 'tgl':
        oset = i+reg[d[1]]
        if oset > len(data)-1:
            i += 1
            continue
 
        gt = data[oset]
        if len(gt) == 2: 
            if gt[0] == 'inc':
                data[oset][0] = 'dec'
            else:
                data[oset][0] = 'inc'
        if len(gt) == 3:
            if gt[0] == 'jnz':
                data[oset][0] = 'cpy'
            else:
                data[oset][0] = 'jnz'
        i += 1
        continue
 
    if d[0] == 'jnz':
        t = d[1]
        r = d[2]
        if isInt(t):
            t = int(t)
        else:
            t = reg[t]
        if isInt(r):
            r = int(r)
        else:
            r = reg[r]
        if t != 0:
            i = i + r
        else:
            i += 1
    else:
        i += 1
 
print(reg)

2016 Day 23 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

def isInt(s):
    if s[0] in ('-', '+'):
        return s[1:].isdigit()
    return s.isdigit()
 
reg = {'a':7,'b':0,'c':0,'d':0}
 
data = open('input').read().splitlines()
data = [x.split(' ') for x in data]
 
i = 0
 
while i < len(data):
    d = data[i]
    if d[0] == 'cpy':
        t = d[1]
        r = d[2]
 
        if isInt(t) and isInt(r):
            i += 1
            continue
        if isInt(t):
            t = int(t)
        else:
            t = reg[t]
        reg[r] = t
 
    if d[0] == 'inc':
        if d[1] in reg:
            reg[d[1]] = reg[d[1]] + 1
 
    if d[0] == 'dec':
        if d[1] in reg:
            reg[d[1]] = reg[d[1]] - 1
 
    if d[0] == 'tgl':
        oset = i+reg[d[1]]
        if oset > len(data)-1:
            i += 1
            continue
 
        gt = data[oset]
        if len(gt) == 2: 
            if gt[0] == 'inc':
                data[oset][0] = 'dec'
            else:
                data[oset][0] = 'inc'
        if len(gt) == 3:
            if gt[0] == 'jnz':
                data[oset][0] = 'cpy'
            else:
                data[oset][0] = 'jnz'
        i += 1
        continue
 
    if d[0] == 'jnz':
        t = d[1]
        r = d[2]
        if isInt(t):
            t = int(t)
        else:
            t = reg[t]
        if isInt(r):
            r = int(r)
        else:
            r = reg[r]
        if t != 0:
            i = i + r
        else:
            i += 1
    else:
        i += 1
 
print(reg)

2016 Day 22 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

import re
 
from collections import deque
from dataclasses import dataclass
 
START: complex = 0j
LINE_PATTERN: re.Pattern = re.compile(r".*x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T.*")
 
State = tuple[complex, complex]
 
@dataclass
class Node:
    coord: complex
    size: int
    used: int
 
    @property
    def avail(self) -> int:
        return self.size - self.used
 
    @classmethod
    def from_line(cls, line: str) -> "Node":
        match = LINE_PATTERN.match(line)
        if not match:
            raise Exception(f"wat: {line}")
 
        x, y, size, used, avail = [int(x) for x in match.groups()]
        if size != used + avail:
            raise Exception(f"wat2: {line}")
 
        return cls(x + 1j * y, size, used)
 
 
def get_neighbours(empty_space: complex, max_coord: complex, immovables: set[complex]) -> list[complex]:
    maybe_neighbours = set(
        empty_space + dx + 1j * dy
        for dx in (-1, 0, 1)
        for dy in (-1, 0, 1)
        if 0 <= empty_space.real + dx <= max_coord.real
        and 0 <= empty_space.imag + dy <= max_coord.imag
        and (dx == 0) != (dy == 0)
    )
    return maybe_neighbours.difference(immovables)
 
 
def solve(nodes: list[Node]) -> int:
    movable_capacity: int = 0
    empty_space: complex = 0j
 
    for node in nodes:
        if node.used == 0:
            movable_capacity = node.size
            empty_space = node.coord
            break
 
    immovables: set[complex] = set()
    max_coord: complex = 0j
    for node in nodes:
        if node.used > movable_capacity:
            immovables.add(node.coord)
        max_coord = max(max_coord.real, node.coord.real) + 1j * max(
            max_coord.imag, node.coord.imag
        )
 
    goal = max_coord.real + 0j
 
    state = (goal, empty_space)
    to_visit: deque = deque([state])
    visited: dict[State, int] = {state: 0}
 
    while to_visit:
        state = to_visit.popleft()
        goal, empty_space = state
        steps = visited[state]
        new_steps = steps + 1
        empty_neighbours = get_neighbours(empty_space, max_coord, immovables)
        for empty_neighbour in empty_neighbours:
            if empty_neighbour == goal:
                if empty_space == 0j:
                    print("Finished!")
                    return new_steps
                new_state = (empty_space, goal)
            else:
                new_state = (goal, empty_neighbour)
 
            if new_state not in visited:
                visited[new_state] = new_steps
                to_visit.append(new_state)
 
    print("Finished search without finding solution")
 
 
data = open('input').read().splitlines()
data = data[2:]
nodes: list[Node] = ([Node.from_line(d) for d in data])
print(nodes)
 
print("solution:", solve(nodes))

2016 Day 22 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import re
 
data = open('input').read().splitlines()
data = data[2:]
 
nodes = []
pattern = "^\/dev\/grid\/node-x(?P<x>[0-9]+)-y(?P<y>[0-9]+)\s+(?P<size>[0-9]+)T\s+(?P<used>[0-9]+)T\s+(?P<available>[0-9]+)T\s+(?P<use>[0-9]+)%"
 
for line in data:
    match = re.match(pattern, line)
    nodes.append (match.groupdict())
#print (nodes)
 
minX = min(nodes, key=lambda d: int(d["x"]))["x"]
maxX = max(nodes, key=lambda d: int(d["x"]))["x"]
minY = min(nodes, key=lambda d: int(d["y"]))["y"]
maxY = max(nodes, key=lambda d: int(d["y"]))["y"]
 
total_pairs = 0
for node in nodes:
  for node2 in nodes:
    if node["x"] != node2["x"] or node["y"] != node2["y"]:
      if int(node["used"]) != 0:
        if int(node["used"]) <= int(node2["available"]):
          total_pairs+=1
 
print(total_pairs)

2016 Day 21 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

DATA = open('input').read().splitlines()
 
class Scrambler:
    def __init__(self, pw):
        self.pw = pw
 
    def __repr__(self):
        return ''.join(self.pw)
 
    def swap_positions(self, x_pos, y_pos):
        self.pw[x_pos], self.pw[y_pos] = self.pw[y_pos], self.pw[x_pos]
 
    def swap_letters(self, x, y):
        self.swap_positions(self.pw.index(x), self.pw.index(y))
 
    def rotate(self, x_pos):
        x_pos %= len(self.pw)
        self.pw = self.pw[-x_pos:] + self.pw[:-x_pos]
 
    def rotate_letter(self, x):
        x_pos = self.pw.index(x)
        if x_pos >= 4:
            x_pos += 1
        self.rotate(x_pos + 1)
 
    def derotate_letter(self, x):
        x_pos = self.pw.index(x)
        if x_pos % 2:
            rot = - (x_pos + 1) // 2
        elif x_pos:
            rot = (6 - x_pos) // 2
        else:
            rot = -1
        self.rotate(rot)
 
    def reverse(self, x_pos, y_pos):
        y_pos += 1
        tmp = self.pw[x_pos:y_pos]
        tmp.reverse()
        self.pw[x_pos:y_pos] = tmp
 
    def move(self, x_pos, y_pos):
        self.pw.insert(y_pos, self.pw.pop(x_pos))
 
    def scramble(self, direction=1):
        for instruction in DATA[::direction]:
            line = instruction.split()
            if instruction.startswith('swap'):
                x, y = line[2], line[-1]
                if line[1] == 'position':
                    self.swap_positions(int(x), int(y))
                else:
                    self.swap_letters(x, y)
            elif instruction.startswith('rotate'):
                if line[1] == 'based':
                    if direction > 0:
                        self.rotate_letter(line[-1])
                    else:
                        self.derotate_letter(line[-1])
                else:
                    x_pos = int(line[2])
                    if line[1] == 'left':
                        x_pos *= -1
                    if direction < 0:
                        x_pos *= -1
                    self.rotate(x_pos)
            else:
                x_pos = int(line[2])
                y_pos = int(line[-1])
                if instruction.startswith('reverse'):
                    self.reverse(x_pos, y_pos)
                else:
                    if direction < 0:
                        x_pos, y_pos = y_pos, x_pos
                    self.move(x_pos, y_pos)
        return self
 
    def unscramble(self):
        return self.scramble(-1)
 
 
plain = list('abcdefgh')
hashed = list('fbgdceah')
 
print(Scrambler(plain).scramble())
print(Scrambler(hashed).unscramble())

2016 Day 20 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

data = open('input').read().splitlines()
data = [x.split('-') for x in data]
data = [(int(x),int(y)) for x,y in data]
data = sorted(data)
 
def find_lowest(ips):
    nr_available = 0
    lowest_available = 0
    the_lowest = 0
 
    for (low, high) in ips:
        if low > lowest_available:
            nr_available += low - lowest_available
            if not the_lowest:
                the_lowest = lowest_available
        lowest_available = max(lowest_available, high + 1)
    return the_lowest, nr_available
 
print(find_lowest(data))

2016 Day 19 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import numpy as np
 
data = open('input').read().strip()
data = 3014387
 
def find_elf(elves):
    if len(elves) <= 2:
        return elves[0] + 1
    if len(elves) % 2:
        return find_elf(np.roll(elves[::2], 1))
    else:
        return find_elf(elves[::2])
 
 
def new_rules(elves):
    n = len(elves)
    if n <= 2:
        return elves[0] + 1
    across = n // 2
    if n % 2:
        removed = n - (n+1)//3
        new = np.roll(elves, -across)[1::3]
    else:
        removed = n - n//3
        new = np.roll(elves, -across)[2::3]
    return new_rules(np.roll(new, across-removed))
 
 
elf_circle = np.arange(data)
 
print(find_elf(elf_circle))
print(new_rules(elf_circle))

2016 Day 18 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

data = open('input').read().strip()
 
def count_safes(row, total_lines):
    safe = 0
    for i in range(total_lines):
        if i == 40:
            first_solution = safe
        safe += row.count('.')
        old = '.' + row + '.'
        row = ''
        for left, right in zip(old, old[2:]):
            row += '^' if left != right else '.'
    return first_solution, safe
 
print (count_safes(data, 400000))

2016 Day 17 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from collections import deque
from hashlib import md5
 
INPUT = 'pslxynzg'
VAULT = 3+3j
 
def find_vault():
    solutions = []
    que = deque([(0+0j, '')])
 
    while que:
        pos, path = que.popleft()
 
        if pos == VAULT:
            solutions.append(path)
            continue
 
        u, d, l, r = md5((INPUT+path).encode()).hexdigest()[:4]
 
        if u > 'a' and pos.imag > 0:
            que.append((pos-1j, path+'U'))
        if d > 'a' and pos.imag < 3:
            que.append((pos+1j, path+'D'))
        if l > 'a' and pos.real > 0:
            que.append((pos-1, path+'L'))
        if r > 'a' and pos.real < 3:
            que.append((pos+1, path+'R'))
 
    return solutions[0], len(solutions[-1])
 
print (find_vault())

2016 Day 16 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

DATA = '01111010110010011'
START = list(map(int, DATA))
DISK_1 = 272
DISK_2 = 35651584
 
 
def fill_disk(data, disk_size):
    while len(data) < disk_size:
        new = [1-i for i in reversed(data)]
        data.append(0)
        data.extend(new)
    return data[:disk_size]
 
 
def create_checksum(data):
    while len(data) % 2 == 0:
        data = [a == b for a, b in zip(data[::2], data[1::2])]
    return ''.join(map(str, map(int, data)))
 
 
first = create_checksum(fill_disk(START, DISK_1))
print("Disk no. 1 checksum is:", first, '\n...')
 
second = create_checksum(fill_disk(START, DISK_2))
print("Disk no. 2 checksum is", second)

2016 Day 15 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import re
 
data = open('input').read().splitlines()
 
discs = []
for i, line in enumerate(data, 1):
    settings = re.search(r'(\d+) positions; .+ (\d+)', line)
    slots = int(settings.group(1))
    position = int(settings.group(2)) + i
    discs.append((slots, position))
 
 
def wait_a_sec(discs):
    time = 0
    while True:
        if not sum((position+time)%slot for (slot, position) in discs):
            return time
        time += 1
 
 
first = wait_a_sec(discs)
 
print(f"I should wait {first} seconds for the perfect arrangement.")
print(f"That's {first//3600} hours.")
print("....")
 
# a new disc with 11 positions and starting at position 0 has appeared
# exactly one second below the previously-bottom disc
discs.append((11, 0+7))
second = wait_a_sec(discs)
 
print(f"I should wait {second} seconds for the perfect arrangement.")
print(f"That's {second//86400} days.")

2016 Day 14 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

from hashlib import md5
 
SALT = 'ahsbgdzn'
 
def find_keys(second_part=False):
    triplets = {}
    valid_keys = set()
    index = 0
 
    while len(valid_keys) < 64 or index < max(valid_keys) + 1000:
        hex_ = md5((SALT+str(index)).encode()).hexdigest()
 
        if second_part:
            for _ in range(2016):
                hex_ = md5(hex_.encode()).hexdigest()
 
        found_triplet = False
        for a, b, c in zip(hex_, hex_[1:], hex_[2:]):
            if a == b == c:
                if 5*a in hex_:
                    for k, v in triplets.items():
                        if a == v and k < index <= 1000+k:
                            valid_keys.add(k)
                if not found_triplet:
                    triplets[index] = a
                    found_triplet = True
        index += 1
    return sorted(valid_keys)[63]
 
 
print("I need to contact Santa, and I need MD5 keys for that.")
print(f"He said to use 64th key, which is {find_keys()}.")
print("....")
print("Wait, he said to encript this 2016 times!")
print(f"Then the 64th key is {find_keys('second')}.")

2016 Day 13 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

from collections import deque
 
INPUT = 1350
GOAL = (31, 39)
START = (1, 1)
DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
 
formula = lambda x, y: x*x + 3*x + 2*x*y + y + y*y + INPUT
 
 
def run_through_maze(second_part=False):
    que = deque([(START, 0)])
    seen = set()
 
    while que:
        (x, y), steps = que.popleft()
 
        if not second_part and (x, y) == GOAL:
            return steps
        if second_part and steps > 50:
            return len(seen)
 
        seen.add((x, y))
 
        for dx, dy in DELTAS:
            nx, ny = (x+dx, y+dy)
            if not ((nx, ny) in seen
                    or any(n < 0 for n in (nx, ny))
                    or bin(formula(nx, ny)).count('1') % 2):
                que.append(((nx, ny), steps+1))
 
print(f"{run_through_maze()} steps to cubicle {GOAL}.")
print(f"{run_through_maze('second')} different cubicles in 50 steps.")

2016 Day 12 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

reg = {'a':0,'b':0,'c':0,'d':0}
 
# set c to 1 for part b.  long runtime.
#reg = {'a':0,'b':0,'c':1,'d':0}
 
data = open('input').read().splitlines()
i = 0
while i < len(data):
    d = data[i].split(' ')
    match d[0]:
        case "cpy":
            reg[d[2]] = int(d[1]) if d[1].isnumeric() else reg[d[1]]
        case "inc":
            reg[d[1]] += 1
        case "dec":
            reg[d[1]] -= 1
        case "jnz":
            if d[1].isnumeric():
                if d[1] != '0':
                    i += int(d[2]) - 1
            elif reg[d[1]] != 0:
                i += int(d[2]) - 1
    i+=1
print(reg)

2016 Day 11 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

import itertools
 
part_b = True
 
# Detect if this state is not valid
def invalid_state(state):
    for chip_index, chip_floor in enumerate(state[0]):
        gen_floor = state[1][chip_index]
        # If chip and generator are both on the same floor
        if chip_floor == gen_floor:
            # this particular chip is safe
            continue
        # Since this chip's generator is on another floor,
        # If there are any generators on this chip's floor
        if chip_floor in state[1]:
            # This chip will get damaged by the generator, so the state is invalid
            return True
 
    # No chips have generators that are a threat, thus the state is valid (hence, not invalid)
    return False
 
 
# This orders chips in ascending order and re-orders the generators to continue to match the chips
def sort_state(state):
    new_state_0 = sorted(state[0])
    new_state_1 = [x for _,x in sorted(zip(state[0],state[1]))]
    return tuple(new_state_0), tuple(new_state_1), state[2]
 
 
with open('input') as f:
    floor_num_lookup = {'first': 1, 'second': 2, 'third': 3, 'fourth': 4}
 
    # Used to store data coming from the text file, before re-processing it later
    initial_state_gens = dict()
    initial_state_chips = dict()
 
    for i in range(1,5):
        initial_state_chips[i] = []
 
    # Pull in each line from the input file
    for in_string in f:
        in_string = in_string.rstrip()
        print(in_string)
 
        # Get floor number from input line
        _, floor_num_str, _, _, in_string = in_string.split(' ', 4)
        floor_num = floor_num_lookup[floor_num_str]
 
        # Loop through all devices on this line (they're all on the same floor)
        # Fill in initial_state_gens and initial_state_chips
        while True:
            # Find the index of the next device
            i_chip = in_string.find('-compatible microchip')
            i_gen = in_string.find(' generator')
            if i_chip == i_gen == -1:
                # both find commands returned -1, thus neither string was found
                break
            if i_chip == -1:
                i_right = i_gen
            elif i_gen == -1:
                i_right = i_chip
            else:
                i_right = min(i_gen, i_chip)
 
            index_str = in_string[2:i_right]
            if in_string[i_right] == '-':
                initial_state_chips[floor_num].append(index_str)
            else:
                initial_state_gens[index_str] = floor_num
            in_string = in_string[in_string.find('a ', 1):]
print()
print(initial_state_chips)
print(initial_state_gens)
print()
 
# Defining indices in current_state_L (note the _L indicates it has lists ... without the L has tuples)
# index 0:  ordered list of floor numbers with a chip
# index 1:  list of floor numbers with a generator
# (each generator is at the same index as its matching chip)
# index 2:  elevator floor
current_state_L = [[], [], 1]
for floor_chip in range(1, 5):
    for element in initial_state_chips[floor_chip]:
        floor_gen = initial_state_gens[element]
        current_state_L[0].append(floor_chip)
        current_state_L[1].append(floor_gen)
 
if part_b:
    print('Since this is a part B problem, two pairs of matching chips and generators are added to the first floor')
    print('The instructions call them elerium and dilithium, but the names do not impact the resulting count\n')
    current_state_L[0].insert(0,1)
    current_state_L[0].insert(0,1)
    current_state_L[1].insert(0,1)
    current_state_L[1].insert(0,1)
 
# Convert from using lists to using tuples
current_state = tuple(
    [
        tuple(current_state_L[0]),
        tuple(current_state_L[1]),
        current_state_L[2]
    ]
)
del current_state_L
 
known_states = dict()
current_time = 0
known_states[current_state] = current_time
next_elevator_floor_map = {1:[2], 2:[1,3], 3:[2,4], 4:[3]}
 
while True:
    states_to_check = [k for k, v in known_states.items() if v == current_time]
    current_time += 1
    for current_state in states_to_check:
        # Identify elevator's current floor
        this_ele_fl = current_state[2]
        # List all devices on the same floor as the elevator
        devices_on_this_fl = set()
        for chip_index, value in enumerate(current_state[0]):
            if value == this_ele_fl:
                devices_on_this_fl.add((0,chip_index))
        del chip_index, value
 
        for index, value in enumerate(current_state[1]):
            if value == this_ele_fl:
                devices_on_this_fl.add((1,index))
        del index, value
        # Looping through all valid next elevator floors
        for next_ele_fl in next_elevator_floor_map[current_state[2]]: 
            # Use itertools to consider all possible single devices, plus all pairs of devices
            device_move_options = list(itertools.permutations(devices_on_this_fl, 2))
            device_move_options += list(itertools.permutations(devices_on_this_fl, 1))
            for move in device_move_options:
                # Construct potential new state
                new_state = [
                    list([x for x in current_state[0]]),
                    list([x for x in current_state[1]]),
                    next_ele_fl
                ]
                for move_piece in move:
                    new_state[move_piece[0]][move_piece[1]] = next_ele_fl
 
                # re-sort and convert to tuple
                new_state = sort_state(new_state)
 
                # Verify that new state isn't already in known_states
                if new_state in known_states:
                    continue
                # Check if it is invalid
                if invalid_state(new_state):
                    continue
                # Check if it has solved the problem
                # check if this is the answer ... if yes ... output the solution
                if set(new_state[0]) == {4} and set(new_state[1]) == {4}:
                    print(f'{current_time} steps are required\n')
                    exit()
 
                known_states[new_state] = current_time

2016 Day 10 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from collections import defaultdict
 
data = open('input').read().splitlines()
 
initial = [line.split() for line in data if line.startswith('value')]
commands = [line.split() for line in data if not line.startswith('value')]
 
connections = {}
for line in commands:
    name, lower, higher = line[1], line[5:7], line[-2:]
    connections[name] = (lower, higher)
#print(connections)
 
bots = defaultdict(list)
outputs = defaultdict(list)
stack = []
 
def add_value(name, value):
    bots[name].append(value)
    if len(bots[name]) == 2:
        stack.append(name)
 
 
def send_value(connection, value):
    out_type, out_name = connection
    if out_type == 'bot':
        add_value(out_name, value)
    else:
        outputs[out_name].append(value)
 
 
for line in initial:
    value, name = int(line[1]), line[-1]
    add_value(name, value)
 
 
while stack:
    name = stack.pop()
    low_value, high_value = sorted(bots[name])
    if low_value == 17 and high_value == 61:
        wanted_bot = name
    lower_connection, higher_connection = connections[name]
    send_value(lower_connection, low_value)
    send_value(higher_connection, high_value)
 
print (wanted_bot)
 
a, b, c = (outputs[i][0] for i in '012')
print (a,"*",b,"*",c,"=",a*b*c)

2016 Day 09 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

data = open('input').read().strip()
 
def calc(s):
    result = 0
    i = 0
    while i < len(s):
        c = s[i]
        if c == '(':
            j = s.index(')', i+1)
            marker = s[i+1:j]
            [ml, mr] = [int(x) for x in marker.split('x')]
            i = j + 1
            result += calc(s[i:i+ml]) * mr
            i += ml
        else:
            result += 1
            i += 1
    return result
 
print(calc(data))

2016 Day 09 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

data = open('input').read().strip()
 
result = 0
i = 0
while i < len(data):
    c = data[i]
    if c == '(':
        j = data.index( ')', i+1 )
        marker = data[i+1:j]
        [ml, mr] = [int(x) for x in marker.split('x')]
        i = j + 1
        result += ml * mr
        i += ml
    else:
        result += 1
        i += 1
print(result)

2016 Day 08 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import numpy as np
import re
 
data = open('input').read().splitlines()
'''
x = left/right = column index
y = up/down    = row index
'''
grid = np.zeros((6, 50), dtype="int16")
for d in data:
    nums = [int(num) for num in re.findall(r"\d+", d)]
    if "rect" in d:
        x = nums[0]
        y = nums[1]
        grid[:y, :x] = 1
    elif "row" in d:
        y = nums[0]
        val = nums[1]
       #grid[y,:] = np.roll(grid[y,:], val)
        grid[y] = np.roll(grid[y], val)
    elif "col" in d:
        x = nums[0]
        val = nums[1]
        grid[:,x] = np.roll(grid[:,x], val)
print(grid.sum())
 
aa=[]
for i in range(0, len(grid.T)):
    aa.append(''.join([str(x) for x in grid.T[i]]))
    print(aa[i])
for a in aa:
    a=a.replace("1","█")
    a=a.replace("0","░")
    print(a)

2016 Day 07 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import re
data = open('input').read().splitlines()
data = [re.split(r'\[|\]', d) for d in data]
supernet = [' '.join(d[::2]) for d in data]
hypernet = [' '.join(d[1::2]) for d in data]
print(supernet[5])
print(hypernet[5])
 
def babs(str):
    babs = []
    for i in range(len(str) - 2):
        tri = list(str[i:i+3])
        if tri[0] != tri[1] and tri[0] == tri[2]:
            babs.append(tri)
    return babs
 
num = 0
for i in range(len(data)):
    for bab in babs(hypernet[i]):
        aba = bab[1] + bab[0] + bab[1]
        if aba in supernet[i]:
            num += 1
            break
print(num)

2016 Day 07 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import re
data = open('input').read().splitlines()
print(data[5])
data = [re.split(r'\[|\]', d) for d in data]
print(data[5])
'''
[initial:end:indexjump]
[::2]  = [0::2] = index #0 to end step 2 = returns even list items
[1::2] =          index #1 to end step 2 = returns odd list items
'''
supernet = [' '.join(d[::2]) for d in data]
hypernet = [' '.join(d[1::2]) for d in data]
print(supernet[5])
print(hypernet[5])
 
def abba(str):
    for i in range(len(str)-3):
        if str[i] != str[i+1] and str[i] == str[i+3] and str[i+1] == str[i+2]:
           return True
    return False
 
num = 0
for i in range(len(data)):
    if abba(supernet[i]) and not abba(hypernet[i]):
        num += 1
print(num)

2016 Day 06 Part 01 + 02

1
2
3
4
5
6
7

from collections import Counter
 
data = open('input').read().splitlines()
data = list(zip(*data)) # transpose items (rows -> cols and cols -> rows)
most  = "" .join([Counter(d).most_common()[0][0] for d in data])
least = "" .join([Counter(d).most_common()[-1][0] for d in data])
print(most, least)

2016 Day 05 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import hashlib
 
data = open('input').read().strip()
#print(data)
 
num = 0
pwd = 'xxxxxxxx'
 
while True:
    str2hash = data + str(num)
    result = hashlib.md5(str2hash.encode())
    if result.hexdigest()[0:5] == "00000":
        pos=result.hexdigest()[5:6]
        val=result.hexdigest()[6:7]
        if pos.isnumeric():
            pos=int(pos)
            if pos in range(0,8) and pwd[pos] == 'x':
                pwd = pwd[0:pos] + val + pwd[pos+1:]
                print(pwd)
                if 'x' not in pwd:
                    break
    num += 1

2016 Day 05 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import hashlib
 
data = open('input').read().strip()
 
num = 0
pwd = ""
 
while True:
    str2hash = data + str(num)
    result = hashlib.md5(str2hash.encode())
    if result.hexdigest()[0:5] == "00000":
        pwd+=result.hexdigest()[5:6]
        if len(pwd) == 8:
            break
    num += 1
print(pwd)

2016 Day 04 Part 01 + 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from collections import Counter
import re
from string import ascii_lowercase as lower
 
data = open('input').read().splitlines()
 
rooms = 0
searched_rooms = []
for line in data:
    beginning, end = line.split("[")
    beginning = " ".join(beginning.split("-")[:-1])
    room_data = [(v, k) for k, v in Counter(re.findall("[a-z]", beginning)).items()]
    room_sorted = sorted(room_data, key=lambda y: (-y[0], y[1]))
    room_code = [code[1] for code in room_sorted[:5]]
    room_id = int("".join(re.findall("[0-9]", line)))
    checksum = re.findall("[a-z]", end)
    if room_code == checksum:
        rooms += room_id
        real_name = "".join([lower[(lower.index(sb) + room_id) % 26] if sb in lower else " " for sb in beginning])
        if "north" in real_name:
            searched_rooms.append((real_name, room_id))
print(rooms)
print(searched_rooms[0][1])

2016 Day 03 Part 02

1
2
3
4
5
6
7
8
9
10
11
12

data = open('input').read().splitlines()
data = [ [int(y) for y in x.strip().split('  ') if y != ''] for x in data]
 
triangles = 0
for row in range(0, len(data), 3):
    for col in range(3):
        x = data[row][col]
        y = data[row + 1][col]
        z = data[row + 2][col]
        if x + y > z and x + z > y and y + z > x:
            triangles += 1
print(triangles)

2016 Day 03 Part 01

1
2
3
4
5
6
7
8
9

data = open('input').read().splitlines()
data = [ [int(y) for y in x.strip().split('  ') if y != ''] for x in data]
 
triangles = 0
for d in data:
    x,y,z = d
    if x + y > z and x + z > y and y + z > x:
    	triangles += 1
print(triangles)

2016 Day 02 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

data = open('input').read().split()
 
keypad = [
          "       ",
          "   1   ",
          "  234  ",
          " 56789 ",
          "  ABC  ",
          "   D   ",
          "       "
         ]
x, y = 1, 3
r = ""
for d in data:
    for c in d:
        if c == 'L':
            mx, my = -1, 0
        elif c == 'R':
            mx, my = 1, 0
        elif c == 'U':
            mx, my = 0, -1
        elif c == 'D':
            mx, my = 0, 1
        nx, ny = x + mx, y + my
        if keypad[ny][nx] != ' ':
            x, y = nx, ny
    r += keypad[y][x]
print(r)

2016 Day 02 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

data = open('input').read().split()
 
keypad = [
          "     ",
          " 123 ",
          " 456 ",
          " 789 ",
          "     "
         ]
x = y = 2
r = ""
for d in data:
    for c in d:
        if c == 'L':
            mx, my = -1, 0
        elif c == 'R':
            mx, my = 1, 0
        elif c == 'U':
            mx, my = 0, -1
        elif c == 'D':
            mx, my = 0, 1
        nx, ny = x + mx, y + my
        if keypad[ny][nx] != ' ':
            x, y = nx, ny
    r += keypad[y][x]
print(r)

2016 Day 01 Part 02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

data = open('input').read().split(', ')
data = [(d[:1],int(d[1:])) for d in data]
steps = [ (0, 1), (1, 0), (0, -1), (-1, 0) ] # Up, Right, Down, Left
facing = 0
pos = (0,0)
visited = []
 
for turn, step in data:
    facing += 1 if turn == 'R' else -1
    facing %= 4
    while step > 0:
        pos = pos[0] + steps[facing][0], pos[1] + steps[facing][1]
        if pos in visited:
            print (abs(pos[0]) + abs(pos[1]))
            exit()
        visited.append(pos)
        step -= 1

2016 Day 01 Part 01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

data = open('input').read().split(', ')
data = [(d[:1],int(d[1:])) for d in data]
 
'''
steps:
    y+1
x-1 pos x+1
    y-1
 
facing:
North: 0
East:  1
South: 2
West:  3
'''
 
steps = [ (0, 1), (1, 0), (0, -1), (-1, 0) ] # Up, Right, Down, Left
facing = 0
pos = (0,0)
 
for turn, step in data:
    facing += 1 if turn == 'R' else -1
    facing %= 4
    while step > 0:
        pos = pos[0] + steps[facing][0], pos[1] + steps[facing][1]
        step -= 1
print (abs(pos[0]) + abs(pos[1]))