Skip to content

Advent of Code 2021

Day 01 
1
2
3
4
5
6
7
8
9
with open("day01_input.txt", "r") as f:
    data = [int(i) for i in f.read().splitlines()]

count = 0
for i in range(1, len(data)):
    if data[i] > data[i - 1]:
        count += 1

print(count)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
with open("day01_input.txt", "r") as f:
    data = [int(i) for i in f.read().splitlines()]

three_measurement_data = []
for i in range(2, len(data)):
    three_measurement_data.append(sum(data[i - 2 : i + 1]))

count = 0
for i in range(1, len(three_measurement_data)):
    if three_measurement_data[i] > three_measurement_data[i - 1]:
        count += 1

print(count)
Day 02 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
with open("day02_input.txt", "r") as f:
    data = [cmd.split() for cmd in f.read().splitlines()]

horizontal_position, depth = 0, 0

for action, value in data:
    value = int(value)
    if action == "forward":
        horizontal_position += value
    elif action == "up":
        depth -= value
    elif action == "down":
        depth += value

print(horizontal_position, depth)

print(horizontal_position * depth)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
with open("day02_input.txt", "r") as f:
    data = [cmd.split() for cmd in f.read().splitlines()]

horizontal_position, depth, aim = 0, 0, 0

for action, value in data:
    value = int(value)
    if action == "forward":
        horizontal_position += value
        depth += aim * value
    elif action == "up":
        aim -= value
    elif action == "down":
        aim += value


print(horizontal_position, depth, aim)

print(horizontal_position * depth)
Day 03 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
with open("day03_input.txt", "r") as f:
    data = f.read().splitlines()

cols = len(data[0])
rows = len(data)

gamma_rate, epsilon_rate = "", ""

for col in range(cols):
    ones = 0
    for row in range(rows):
        if data[row][col] == "1":
            ones += 1

    if ones > rows / 2:
        gamma_rate += "1"
        epsilon_rate += "0"
    else:
        gamma_rate += "0"
        epsilon_rate += "1"

print(gamma_rate, epsilon_rate)

print(int(gamma_rate, 2) * int(epsilon_rate, 2))

 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
with open("day03_input.txt", "r") as f:
    data = f.read().splitlines()

cols = len(data[0])

oxygen_generator_rating, co2_scrubber_rating = "", ""

selections = data[:]
for col in range(cols):
    ones = 0
    for row in selections:
        if row[col] == "1":
            ones += 1

    if ones >= len(selections) / 2:
        selections = [row for row in selections if row[col] == "1"]
    else:
        selections = [row for row in selections if row[col] == "0"]

    if len(selections) == 1:
        oxygen_generator_rating += selections[0]
        break

selections = data[:]
for col in range(cols):
    ones = 0
    for row in selections:
        if row[col] == "1":
            ones += 1

    if ones < len(selections) / 2:
        selections = [row for row in selections if row[col] == "1"]
    else:
        selections = [row for row in selections if row[col] == "0"]

    if len(selections) == 1:
        co2_scrubber_rating += selections[0]
        break


print(oxygen_generator_rating, co2_scrubber_rating)

print(int(oxygen_generator_rating, 2) * int(co2_scrubber_rating, 2))
Day 04 
 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
with open("day04_input.txt", "r") as f:
    lines = f.read().splitlines()


draws = lines[0].split(",")


lines = [line for line in lines[1:] if line]
boards = []
for i in range(0, len(lines) // 5):
    boards.append([])
    for j in range(5):
        boards[i].append(lines[i * 5 + j].split())


marks = {}
for i in range(len(boards)):
    marks[i] = {}
    for row in range(5):
        for col in range(5):
            marks[i][boards[i][row][col]] = (row, col)


winning_locations = []
for row in range(5):
    winning_locations.append([(row, col) for col in range(5)])
for col in range(5):
    winning_locations.append([(row, col) for row in range(5)])


def wins(locations, winning_locations=winning_locations):
    for winning_location in winning_locations:
        if all(loc in locations for loc in winning_location):
            return winning_location

    return None


plays = {}
for i in range(len(boards)):
    plays[i] = []

num_plays = {}
for i in range(len(boards)):
    count = 0
    for draw in draws:
        count += 1
        if draw in marks[i]:
            plays[i].append(marks[i][draw])

        if wins(plays[i]):
            num_plays[i] = count, len(plays[i])
            break


fastest_win = min(num_plays, key=lambda x: num_plays[x][0])
print(fastest_win)


sum_unmarked = 0
for row in range(5):
    for col in range(5):
        if (row, col) not in plays[fastest_win]:
            sum_unmarked += int(boards[fastest_win][row][col])

row, col = plays[fastest_win][-1]
num_call = int(boards[fastest_win][row][col])


print(sum_unmarked, num_call)
print(sum_unmarked * num_call)

 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
with open("day04_input.txt", "r") as f:
    lines = f.read().splitlines()


draws = lines[0].split(",")


lines = [line for line in lines[1:] if line]
boards = []
for i in range(0, len(lines) // 5):
    boards.append([])
    for j in range(5):
        boards[i].append(lines[i * 5 + j].split())


marks = {}
for i in range(len(boards)):
    marks[i] = {}
    for row in range(5):
        for col in range(5):
            marks[i][boards[i][row][col]] = (row, col)


winning_locations = []
for row in range(5):
    winning_locations.append([(row, col) for col in range(5)])
for col in range(5):
    winning_locations.append([(row, col) for row in range(5)])


def wins(locations, winning_locations=winning_locations):
    for winning_location in winning_locations:
        if all(loc in locations for loc in winning_location):
            return winning_location

    return None


plays = {}
for i in range(len(boards)):
    plays[i] = []

num_plays = {}
for i in range(len(boards)):
    count = 0
    for draw in draws:
        count += 1
        if draw in marks[i]:
            plays[i].append(marks[i][draw])

        if wins(plays[i]):
            num_plays[i] = count, len(plays[i])
            break


last_win = max(num_plays, key=lambda x: num_plays[x][0])
print(last_win)


sum_unmarked = 0
for row in range(5):
    for col in range(5):
        if (row, col) not in plays[last_win]:
            sum_unmarked += int(boards[last_win][row][col])

row, col = plays[last_win][-1]
num_call = int(boards[last_win][row][col])


print(sum_unmarked, num_call)
print(sum_unmarked * num_call)
Day 05 
 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
with open("day05_input.txt", "r") as f:
    lines = f.read().splitlines()

lines = [line.split(" -> ") for line in lines]
lines = [(tuple(line[0].split(",")), tuple(line[1].split(","))) for line in lines]
print(len(lines))

lines = [
    ((int(coord1[0]), int(coord1[1])), (int(coord2[0]), int(coord2[1])))
    for coord1, coord2 in lines
    if coord1[0] == coord2[0] or coord1[1] == coord2[1]
]
print(len(lines))

from collections import Counter

diagram = Counter()
for coord1, coord2 in lines:
    if coord1[0] == coord2[0]:
        for i in range(min(coord1[1], coord2[1]), max(coord1[1], coord2[1]) + 1):
            diagram[(coord1[0], i)] += 1
    elif coord1[1] == coord2[1]:
        for i in range(min(coord1[0], coord2[0]), max(coord1[0], coord2[0]) + 1):
            diagram[(i, coord1[1])] += 1

print(len([i for i in diagram.values() if i > 1]))

 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
with open("day05_input.txt", "r") as f:
    lines = f.read().splitlines()

lines = [line.split(" -> ") for line in lines]
lines = [(tuple(line[0].split(",")), tuple(line[1].split(","))) for line in lines]
print(len(lines))

lines = [
    ((int(coord1[0]), int(coord1[1])), (int(coord2[0]), int(coord2[1])))
    for coord1, coord2 in lines
]

from collections import Counter

diagram = Counter()
for coord1, coord2 in lines:
    if coord1[0] == coord2[0]:
        for i in range(min(coord1[1], coord2[1]), max(coord1[1], coord2[1]) + 1):
            diagram[(coord1[0], i)] += 1
    elif coord1[1] == coord2[1]:
        for i in range(min(coord1[0], coord2[0]), max(coord1[0], coord2[0]) + 1):
            diagram[(i, coord1[1])] += 1
    else:
        step_x = -1 if coord1[0] - coord2[0] > 0 else 1
        step_y = -1 if coord1[1] - coord2[1] > 0 else 1
        for x, y in zip(
            range(coord1[0], coord2[0] + (1 if step_x > 0 else -1), step_x),
            range(coord1[1], coord2[1] + (1 if step_y > 0 else -1), step_y),
        ):
            diagram[(x, y)] += 1

print(len([i for i in diagram.values() if i > 1]))
Day 06 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
with open("day06_input.txt", "r") as f:
    fish = [int(i) for i in f.read().strip().split(",")]

print(f"Initial state: {fish}")

for _ in range(80):
    new_fish = []
    for i in range(len(fish)):

        fish[i] -= 1

        if fish[i] < 0:
            fish[i] = 6
            new_fish.append(8)

    fish.extend(new_fish)

    print(f"After {str(_+1):2s} day{'s' if _ else ''}: {fish}")

print(len(fish))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
with open("day06_input.txt", "r") as f:
    fish = [int(i) for i in f.read().strip().split(",")]


from collections import Counter

fish = Counter(fish)
print(fish)

for _ in range(256):
    for i in range(-1, 9):
        if i == 8:
            fish[i] = fish[-1]
        elif i != 6:
            fish[i] = fish[i + 1]
        else:
            fish[i] = fish[-1] + fish[i + 1]


print(sum([v for k, v in fish.items() if k >= 0]))
Day 07 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
with open("day07_input.txt", "r") as f:
    crabs = [int(i) for i in f.read().strip().split(",")]

print(len(crabs))

from collections import Counter

crabs = Counter(crabs)


outcome = {}

for key in crabs:
    result = 0
    for key2 in crabs:
        result += abs(key2 - key) * crabs[key2]
    outcome[key] = result

min_key = min(outcome, key=outcome.get)
print(min_key)
print(outcome[min_key])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
with open("day07_input.txt", "r") as f:
    crabs = [int(i) for i in f.read().strip().split(",")]

print(len(crabs))

from collections import Counter

crabs = Counter(crabs)


outcome = {}

for key in range(0, max(crabs.keys()) + 1):
    result = 0
    for key2 in crabs:
        result += sum(range(1, abs(key2 - key) + 1)) * crabs[key2]
    outcome[key] = result

min_key = min(outcome, key=outcome.get)
print(min_key)
print(outcome[min_key])
Day 08 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
with open("day08_input.txt", "r") as f:
    obs = [line.split(" | ") for line in f.read().splitlines()]

count = 0
for o in obs:
    output_values = o[1].split()
    for output_value in output_values:
        if len(output_value) in [2, 3, 4, 7]:
            count += 1

print(count)

 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
with open("day08_input.txt", "r") as f:
    obs = [line.split(" | ") for line in f.read().splitlines()]


def _sorted(digit):
    return "".join(sorted(digit))


def solve(digits):
    mapping = {}
    five_segs = []
    six_segs = []

    cf, bcdf, acf, abcdefg = None, None, None, None
    for digit in digits:
        if len(digit) == 2:
            mapping[_sorted(digit)] = "1"
            cf = digit
        elif len(digit) == 3:
            mapping[_sorted(digit)] = "7"
            acf = digit
        elif len(digit) == 4:
            mapping[_sorted(digit)] = "4"
            bcdf = digit
        elif len(digit) == 7:
            mapping[_sorted(digit)] = "8"
            abcdefg = digit
        elif len(digit) == 5:
            five_segs.append(digit)
        elif len(digit) == 6:
            six_segs.append(digit)

    bd = set(bcdf) - set(cf)
    eg = set(abcdefg) - (set(cf) | set(bcdf) | set(acf))

    for digit in six_segs:
        _digit = set(digit)
        if _digit >= bd and _digit >= eg:
            mapping[_sorted(digit)] = "6"
        elif _digit >= bd:
            mapping[_sorted(digit)] = "9"
        elif _digit >= eg:
            mapping[_sorted(digit)] = "0"

    for digit in five_segs:
        _digit = set(digit)
        if _digit >= bd:
            mapping[_sorted(digit)] = "5"
        elif _digit >= eg:
            mapping[_sorted(digit)] = "2"
        else:
            mapping[_sorted(digit)] = "3"

    return mapping


count = 0
for o in obs:
    output_values = o[1].split()
    digits = o[0].split()
    mapping = solve(digits)
    value = ""
    for digit in output_values:
        value += mapping[_sorted(digit)]

    count += int(value)

print(count)
Day 09 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
with open("day09_input.txt", "r") as f:
    obs = [[int(i) for i in line] for line in f.read().splitlines()]


low_points = []
for i in range(0, len(obs)):
    for j in range(0, len(obs[i])):
        to_compare = []
        if i > 0:
            to_compare.append(obs[i - 1][j])
        if i < len(obs) - 1:
            to_compare.append(obs[i + 1][j])
        if j > 0:
            to_compare.append(obs[i][j - 1])
        if j < len(obs[i]) - 1:
            to_compare.append(obs[i][j + 1])

        if all(obs[i][j] < x for x in to_compare):
            low_points.append(obs[i][j])


print(sum(low_points) + len(low_points))

 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
with open("day09_input.txt", "r") as f:
    obs = [[int(i) for i in line] for line in f.read().splitlines()]


low_points = []
for i in range(0, len(obs)):
    for j in range(0, len(obs[i])):
        to_compare = []
        if i > 0:
            to_compare.append(obs[i - 1][j])
        if i < len(obs) - 1:
            to_compare.append(obs[i + 1][j])
        if j > 0:
            to_compare.append(obs[i][j - 1])
        if j < len(obs[i]) - 1:
            to_compare.append(obs[i][j + 1])

        if all(obs[i][j] < x for x in to_compare):
            low_points.append((i, j))

basin_sizes = []


def find_basin(i, j, points):
    points.append((i, j))

    up = i
    while True:
        if up > 0:
            if obs[up - 1][j] > obs[up][j] and obs[up - 1][j] < 9:
                find_basin(up - 1, j, points)
                up -= 1
            else:
                break
        else:
            break

    down = i
    while True:
        if down < len(obs) - 1:
            if obs[down + 1][j] > obs[down][j] and obs[down + 1][j] < 9:
                find_basin(down + 1, j, points)
                down += 1
            else:
                break
        else:
            break

    left = j
    while True:
        if left > 0:
            if obs[i][left - 1] > obs[i][left] and obs[i][left - 1] < 9:
                find_basin(i, left - 1, points)
                left -= 1
            else:
                break
        else:
            break

    right = j
    while True:
        if right < len(obs[i]) - 1:
            if obs[i][right + 1] > obs[i][right] and obs[i][right + 1] < 9:
                find_basin(i, right + 1, points)
                right += 1
            else:
                break
        else:
            break


for i, j in low_points:
    points = []
    find_basin(i, j, points)
    basin_sizes.append(len(set(points)))

import functools

print(functools.reduce(lambda x, y: x * y, sorted(basin_sizes)[-3:]))
Day 10 
 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
with open("day10_input.txt", "r") as f:
    lines = f.read().splitlines()


mapping = {
    ")": 3,
    "]": 57,
    "}": 1197,
    ">": 25137,
}

match = {
    ")": "(",
    "]": "[",
    "}": "{",
    ">": "<",
}


def check(line):
    stack = []
    for c in line:
        if c in match.values():
            stack.append(c)
        elif c in match.keys():
            if len(stack) == 0:
                return mapping[c]
            last = stack.pop()
            if last != match[c]:
                return mapping[c]

    return 0


print(sum(check(line) for line in lines))

 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
with open("day10_input.txt", "r") as f:
    lines = f.read().splitlines()


mapping = {
    "(": 1,
    "[": 2,
    "{": 3,
    "<": 4,
}

match = {
    ")": "(",
    "]": "[",
    "}": "{",
    ">": "<",
}


def check(line):
    stack = []
    for c in line:
        if c in match.values():
            stack.append(c)
        elif c in match.keys():
            if len(stack) == 0:
                return 0
            last = stack.pop()
            if last != match[c]:
                return 0

    if len(stack) == 0:
        return 0

    score = 0
    while len(stack) > 0:
        last = stack.pop()
        score *= 5
        score += mapping[last]

    return score


scores = [check(line) for line in lines]
scores = [s for s in scores if s > 0]
print(len(scores))
print(sorted(scores)[len(scores) // 2])
Day 11 
 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
with open("day11_input.txt", "r") as f:
    obs = [[int(i) for i in line] for line in f.read().splitlines()]


def increase(obs):
    for i in range(len(obs)):
        for j in range(len(obs[i])):
            obs[i][j] += 1


def has_flash(obs):
    locations = []
    for i in range(len(obs)):
        for j in range(len(obs[i])):
            if obs[i][j] > 9:
                locations.append((i, j))
    return locations


def display(obs):
    for i in range(len(obs)):
        print("".join([str(i) for i in obs[i]]))


from collections import Counter

print("Before any steps:")
display(obs)
print()

count = 0
for s in range(100):
    increase(obs)

    flashes = set()
    while True:
        locations = has_flash(obs)
        flashes.update(locations)

        if locations:
            c = Counter()
            for i, j in locations:
                obs[i][j] = 0
                if i > 0:
                    c[(i - 1, j)] += 1
                    if j > 0:
                        c[(i - 1, j - 1)] += 1
                    if j < len(obs[i]) - 1:
                        c[(i - 1, j + 1)] += 1
                if i < len(obs) - 1:
                    c[(i + 1, j)] += 1
                    if j > 0:
                        c[(i + 1, j - 1)] += 1
                    if j < len(obs[i]) - 1:
                        c[(i + 1, j + 1)] += 1
                if j > 0:
                    c[(i, j - 1)] += 1
                if j < len(obs[i]) - 1:
                    c[(i, j + 1)] += 1
            for i, j in c:
                if (i, j) not in flashes:
                    obs[i][j] += c[(i, j)]
            if c:
                continue
        break

    print(f"After step {s+1}:")
    display(obs)
    print(f"Flashes: {len(flashes)}")
    print()

    count += len(flashes)

print(f"Total flashes: {count}")

 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
with open("day11_input.txt", "r") as f:
    obs = [[int(i) for i in line] for line in f.read().splitlines()]


def increase(obs):
    for i in range(len(obs)):
        for j in range(len(obs[i])):
            obs[i][j] += 1


def has_flash(obs):
    locations = []
    for i in range(len(obs)):
        for j in range(len(obs[i])):
            if obs[i][j] > 9:
                locations.append((i, j))
    return locations


def display(obs):
    for i in range(len(obs)):
        print("".join([str(i) for i in obs[i]]))


from collections import Counter


print("Before any steps:")
display(obs)
print()


count = 0
octopuses = sum([len(obs[i]) for i in range(len(obs))])
while True:
    increase(obs)

    flashes = set()
    while True:
        locations = has_flash(obs)
        flashes.update(locations)

        if locations:
            c = Counter()
            for i, j in locations:
                obs[i][j] = 0
                if i > 0:
                    c[(i - 1, j)] += 1
                    if j > 0:
                        c[(i - 1, j - 1)] += 1
                    if j < len(obs[i]) - 1:
                        c[(i - 1, j + 1)] += 1
                if i < len(obs) - 1:
                    c[(i + 1, j)] += 1
                    if j > 0:
                        c[(i + 1, j - 1)] += 1
                    if j < len(obs[i]) - 1:
                        c[(i + 1, j + 1)] += 1
                if j > 0:
                    c[(i, j - 1)] += 1
                if j < len(obs[i]) - 1:
                    c[(i, j + 1)] += 1
            for i, j in c:
                if (i, j) not in flashes:
                    obs[i][j] += c[(i, j)]
            if c:
                continue
        break

    print(f"After step {count+1}:")
    display(obs)
    print(f"Flashes: {len(flashes)}")
    print()

    count += 1
    if len(flashes) == octopuses:
        break

print(f"Total steps: {count}")
Day 12 
 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
with open("day12_input.txt", "r") as f:
    segs = f.read().splitlines()


graph = {}
for seg in segs:
    node1, node2 = seg.split("-")
    if node1 not in graph:
        graph[node1] = [node2]
    else:
        graph[node1].append(node2)

    if node2 not in graph:
        graph[node2] = [node1]
    else:
        graph[node2].append(node1)

from pprint import pprint

pprint(graph)


paths = []


def breadth_first_search(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        paths.append(path)
    if start not in graph:
        return None
    for node in graph[start]:
        if node not in path or node.isupper():
            newpath = breadth_first_search(graph, node, end, path)
            if newpath:
                paths.append(newpath)
    return None


breadth_first_search(graph, "start", "end")

for path in paths:
    print(",".join(path))

print(len(paths))

 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
with open("day12_input.txt", "r") as f:
    segs = f.read().splitlines()


graph = {}
for seg in segs:
    node1, node2 = seg.split("-")
    if node1 not in graph:
        graph[node1] = [node2]
    else:
        graph[node1].append(node2)

    if node2 not in graph:
        graph[node2] = [node1]
    else:
        graph[node2].append(node1)

from pprint import pprint

pprint(graph)


paths = []


def remaining(path, node):
    others = [
        n for n in path if n != node and n.islower() and n not in ["start", "end"]
    ]

    return all(path.count(n) <= 1 for n in others)


def breadth_first_search(graph, start, end, path=[]):

    path = path + [start]
    if start == end:
        paths.append(path)
    if start not in graph:
        return None
    for node in graph[start]:
        if (
            node not in path
            or node.isupper()
            or (
                node not in ["start", "end"]
                and node.islower()
                and path.count(node) < 2
                and remaining(path, node)
            )
        ):
            newpath = breadth_first_search(graph, node, end, path)
            if newpath:
                paths.append(newpath)
    return None


breadth_first_search(graph, "start", "end")

for path in paths:
    print(",".join(path))

print(len(paths))
Day 13 
 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
with open("day13_input.txt", "r") as f:
    lines = f.read().splitlines()


dots = []
actions = []
for line in lines:
    if not line:
        continue
    if "," in line:
        x, y = line.split(",")
        dots.append((int(x), int(y)))
    else:
        actions.append(line.split()[-1].split("="))

previous = dots[:]

for axis, value in actions:
    result = []
    value = int(value)
    if axis == "x":
        for dot in previous:
            if dot[0] < value:
                result.append((dot[0], dot[1]))
            else:
                result.append((2 * value - dot[0], dot[1]))

    elif axis == "y":
        for dot in previous:
            if dot[1] < value:
                result.append((dot[0], dot[1]))
            else:
                result.append((dot[0], 2 * value - dot[1]))

    print(len(set(result)))

    previous = result[:]

 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
with open("day13_input.txt", "r") as f:
    lines = f.read().splitlines()


dots = []
actions = []
for line in lines:
    if not line:
        continue
    if "," in line:
        x, y = line.split(",")
        dots.append((int(x), int(y)))
    else:
        actions.append(line.split()[-1].split("="))

previous = dots[:]

for axis, value in actions:
    result = []
    value = int(value)
    if axis == "x":
        for dot in previous:
            if dot[0] < value:
                result.append((dot[0], dot[1]))
            else:
                result.append((2 * value - dot[0], dot[1]))

    elif axis == "y":
        for dot in previous:
            if dot[1] < value:
                result.append((dot[0], dot[1]))
            else:
                result.append((dot[0], 2 * value - dot[1]))

    print(len(set(result)))

    previous = result[:]

max_x = max(result, key=lambda x: x[0])[0]
max_y = max(result, key=lambda x: x[1])[1]
print(max_x, max_y)

for y in range(max_y + 1):
    for x in range(max_x + 1):
        if (x, y) in result:
            print("#", end="")
        else:
            print(" ", end="")
    print()

from PIL import Image

img = Image.new("RGB", (max_x + 1, max_y + 1), "black")
pixels = img.load()
for dot in set(result):
    pixels[dot[0], dot[1]] = (255, 255, 255)
img.show()
Day 14 
 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
with open("day14_input.txt", "r") as f:
    lines = f.read().splitlines()


template = None
pairs = []
for line in lines:
    if not line:
        continue
    if " -> " in line:
        pairs.append(line.split(" -> "))
    else:
        template = line

print(f"Template: {template}")

for i in range(10):
    segs = [template[j : j + 2] for j in range(0, len(template) - 1)]

    for k in range(len(segs)):
        for pair in pairs:
            if segs[k] == pair[0]:
                segs[k] = pair[0][0] + pair[1] + pair[0][1]

    template = segs[0]
    for seg in segs[1:]:
        template += seg[-2:]

    print(f"After step {i+1}: {template}")

from collections import Counter

counts = Counter(template).most_common()

print(counts[0][1] - counts[-1][1])

 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
with open("day14_input.txt", "r") as f:
    lines = f.read().splitlines()


template = None
pairs = []
for line in lines:
    if not line:
        continue
    if " -> " in line:
        pairs.append(line.split(" -> "))
    else:
        template = line

print(f"Template: {template}")
segs = [template[j : j + 2] for j in range(0, len(template) - 1)]

from collections import Counter

counts = Counter(segs)


for i in range(40):
    result = Counter()
    for key in counts:
        for pair in pairs:
            if key == pair[0]:
                result[key[0] + pair[1]] += counts[key]
                result[pair[1] + key[1]] += counts[pair[0]]

    counts = result


chars = Counter()
chars[template[0]] += 1

for key, value in counts.items():
    chars[key[1]] += value

chars = chars.most_common()
print(chars)
print(chars[0][1] - chars[-1][1])
Day 15 
 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
with open("day15_input.txt", "r") as f:
    risks = [[int(d) for d in line] for line in f.read().splitlines()]

rows, cols = len(risks), len(risks[0])

# reference: https://stackabuse.com/dijkstras-algorithm-in-python/

from queue import PriorityQueue


class Graph:
    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [
            [-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)
        ]
        self.visited = []

    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight


def dijkstra(graph, start_vertex):
    D = {v: float("inf") for v in range(graph.v)}
    D[start_vertex] = 0

    pq = PriorityQueue()
    pq.put((0, start_vertex))

    while not pq.empty():
        (dist, current_vertex) = pq.get()
        graph.visited.append(current_vertex)

        for neighbor in range(graph.v):
            if graph.edges[current_vertex][neighbor] != -1:
                distance = graph.edges[current_vertex][neighbor]
                if neighbor not in graph.visited:
                    old_cost = D[neighbor]
                    new_cost = D[current_vertex] + distance
                    if new_cost < old_cost:
                        pq.put((new_cost, neighbor))
                        D[neighbor] = new_cost
    return D


g = Graph(rows * cols)
for i in range(rows):
    for j in range(cols):

        if i < rows - 1:
            g.add_edge((i + 1) * cols + j, i * cols + j, risks[i][j])
            g.add_edge(i * cols + j, (i + 1) * cols + j, risks[i + 1][j])

        if j < cols - 1:
            g.add_edge(i * cols + j + 1, i * cols + j, risks[i][j])
            g.add_edge(i * cols + j, i * cols + j + 1, risks[i][j + 1])


D = dijkstra(g, 0)
print(f"Cost of shortest path is {D[rows*cols-1]}")

 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
with open("day15_input.txt", "r") as f:
    lines = [[int(d) for d in line] for line in f.read().splitlines()]

rows, cols = len(lines), len(lines[0])


lines_5x = [[0] * cols * 5 for i in range(rows * 5)]
for ii in range(5):
    for jj in range(5):
        for i in range(rows):
            for j in range(cols):
                lines_5x[ii * rows + i][jj * cols + j] = (
                    lines[i][j] + ii + jj - 1
                ) % 9 + 1


# Using the networkx library instead

import networkx as nx

g = nx.DiGraph()
rows *= 5
cols *= 5

for i in range(rows):
    for j in range(cols):
        if i < rows - 1:
            g.add_edge((i, j), (i + 1, j), weight=lines_5x[i + 1][j])
            g.add_edge((i + 1, j), (i, j), weight=lines_5x[i][j])

        if j < cols - 1:
            g.add_edge((i, j), (i, j + 1), weight=lines_5x[i][j + 1])
            g.add_edge((i, j + 1), (i, j), weight=lines_5x[i][j])

paths = nx.shortest_path(
    g,
    source=(0, 0),
    target=(rows - 1, cols - 1),
    weight="weight",
)

# print(paths)

cost = 0
for i, j in paths[1:]:
    cost += lines_5x[i][j]

print(f"Cost of shortest path is {cost}")
Day 16 
 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
with open("day16_input.txt", "r") as f:
    hexadecimal = f.read().strip()

print(f"Hex: {hexadecimal}")


def hex2bin(h):
    return bin(int(h, 16))[2:].zfill(len(h) * 4)


b = hex2bin(hexadecimal)
print(f"Bin: {b}")

print()


def decode_header(b):
    packet_version = b[:3]
    packet_type_id = b[3:6]

    return int(packet_version, 2), int(packet_type_id, 2), b[6:]


def decode_literal(b):
    value = ""

    while b:
        seg = b[:5]
        value += seg[-4:]
        b = b[5:]
        if seg[0] == "0":
            break

    return value, b


def decode_operator(b):
    length_type_id = b[:1]

    if length_type_id == "0":
        length_of_subpackets = int(b[1:16], 2)

        remaining = b[16 + length_of_subpackets :]
        b = b[16 : 16 + length_of_subpackets]
        number_of_subpackets = -1
    else:
        number_of_subpackets = int(b[1:12], 2)
        b = b[12:]
        remaining = None

    return length_type_id, number_of_subpackets, b, remaining


result = []


def decode(b):
    while b:
        if all(c == "0" for c in b):
            return

        packet_version, packet_type_id, b = decode_header(b)
        result.append(packet_version)
        print(f"packet_version: {packet_version}, packet_type_id: {packet_type_id}")
        if packet_type_id == 4:
            value, b = decode_literal(b)
            print(f"Literal value {value} is {int(value, 2)}.")
        else:
            length_type_id, number_of_subpackets, block, remaining = decode_operator(b)
            print(
                f"length_type_id: {length_type_id},",
                f"number_of_subpackets: {number_of_subpackets},",
            )
            if number_of_subpackets == -1:
                b = remaining
                decode(block)
            else:
                b = block
                return decode(b)

    return


decode(b)
print()
print(f"Result: {result} -> {sum(result)}")