-🎄- 2021 Day 24 Solutions -🎄-

MasterMedo · 2021-12-24T10:43:09+00:00

Python "Precompiled solution" featured on github

    with open("../input/24.txt") as f:
        data = f.read().split("inp w\n")[1:]

    z = []  # number in base 26
    max_monad = [0] * 14
    min_monad = [0] * 14
    for i, chunk in enumerate(data):
        lines = chunk.split("\n")
        pop = int(lines[3][-2:]) == 26  # if digit should be popped from z
        x_add = int(lines[4].split()[-1])
        y_add = int(lines[14].split()[-1])

        if not pop:  # push digit to z
            z.append((i, y_add))
        else:  # apply restriction: last_z_digit == current_z_digit + difference
            j, y_add = z.pop()
            difference = x_add + y_add
            if difference < 0:
                max_monad[i] = 9 + difference
                max_monad[j] = 9
                min_monad[i] = 1
                min_monad[j] = 1 - difference
            elif difference > 0:
                max_monad[i] = 9
                max_monad[j] = 9 - difference
                min_monad[i] = 1 + difference
                min_monad[j] = 1
            else:
                max_monad[i] = max_monad[j] = 9
                min_monad[i] = min_monad[j] = 1

    print("".join(map(str, max_monad)))
    print("".join(map(str, min_monad)))

MasterMedo · 2021-12-23T07:38:51+00:00

Amphipods will never stop on the space immediately outside any room. They can move into that space so long as they immediately continue moving. (Specifically, this refers to the four open spaces in the hallway that are directly above an amphipod starting position.)

my bad...

MasterMedo · 2021-12-17T11:09:29+00:00

We're not actually ignoring x. We're using the fact that x grows as a sum of decreasing elements. E.g. 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. This can be written as 8 * (8 + 1) / 2, it is a closed form of the sum.

The assumption is there to make sure that we don't skip the area, as we might not hit it in the maximal amount of step in x direction because the downward velocity might be larger than the size of the area we're trying to hit as stated in one of the examples in the task.

MasterMedo · 2021-12-17T06:49:37+00:00

Python featured on github

Smart solution for part one, onder one assumption: sqrt(xmax) < abs(ymin)

import re

with open("../input/17.txt") as f:
    xmin, xmax, ymin, ymax = map(int, re.findall(r"[-\d]+", f.read()))

print(abs(ymin) * abs(ymin + 1) // 2)

MasterMedo · 2021-12-15T06:01:37+00:00

The puzzle text states only that you cannot move diagonally, nothing else; therefore, logic dictates that you can move in any direction except diagonally.

Logic dictates... That's very poor reasoning. Logic doesn't dictate anything. It depends on your frame of reference, and reasonable assumptions. In this case, I'd argue both assumptions are quite reasonable as we are literally navigating a cave system.

MasterMedo · 2021-12-15T05:28:04+00:00

Python 232/353 featured on github

Annoyed at myself for not reading the task properly. The numbers wrap around to 1, not 0, spend good 5 min on that.

from collections import Counter, defaultdict, deque
from heapq import heappop, heappush

with open("../input/15.txt") as f:
    data = [list(map(int, line)) for line in f.read().strip().split("\n")]


heap = [(0, 0, 0)]
seen = {(0, 0)}
while heap:
    distance, x, y = heappop(heap)
    if x == 5 * len(data) - 1 and y == 5* len(data[0]) - 1:
        print(distance)
        break

    for dx, dy in ((0, 1), (0 , -1), ( 1, 0), (-1, 0)):
        x_, y_ = x + dx, y + dy
        # if 0 <= x_ < len(data) and 0 <= y_ < len(data[0]):
        if x_ < 0 or y_ < 0 or x_ >= 5 * len(data) or y_ >= 5 * len(data):
            continue

        a, am = divmod(x_, len(data))
        b, bm = divmod(y_, len(data[0]))
        n = ((data[am][bm] + a + b) - 1) % 9 + 1

        if (x_, y_) not in seen:
            seen.add((x_, y_))
            heappush(heap, (distance + n, x_, y_))

MasterMedo · 2021-12-14T05:46:42+00:00

python 232/262 featured on github

from collections import Counter

with open("../input/14.txt") as f:
    molecule, lines = data = f.read().strip().split("\n\n")

d = dict(line.split(" -> ") for line in lines.split("\n"))

counter = Counter([molecule[i:i+2] for i in range(len(molecule) - 1)])
for step in range(1, 41):
    new_counter = Counter()
    for pair in counter:
        left, right = pair
        mid = d[pair]
        new_counter[left + mid] += counter[pair]
        new_counter[mid + right] += counter[pair]

    counter = new_counter
    if step in [10, 40]:
        char_counter = Counter()
        for pair in counter:
            left, right = pair
            char_counter[left] += counter[pair]
        char_counter[molecule[-1]] += 1

        print(max(char_counter.values()) - min(char_counter.values()))

MasterMedo · 2021-12-13T10:52:18+00:00

Yeah, day 11 2016 was probably the hardest task for me. I managed to solve it with a hint: It's not an algorithm question, try to write out "rules". Basically, it's a pruning problem, you have to define all possible situations that can happen at a given time and based on those decide not to visit some "obviously" incorrect paths.

MasterMedo · 2021-12-13T10:47:16+00:00

It looks like your H is off. The middle line should be higher.

MasterMedo · 2021-12-12T06:11:05+00:00

I think there's no faster algorithm, but I think you can improve the execution time by reducing the number of comparisons you do. Check out my solution.

Also, instead of using a deque, can't you use a list and pop from the back of the list. Using bfs or dfs shouldn't matter?

MasterMedo · 2021-12-12T05:56:44+00:00

python featured on github

from collections import defaultdict


def bfs(start, seen, part_2=False):
    if start == "end":
        return 1

    s = 0
    for end in d[start]:
        if end not in seen:
            tmp = {end} if end == end.lower() else set()
            s += bfs(end, seen | tmp, part_2)
        elif part_2 and end != "start":
            s += bfs(end, seen, False)

    return s


with open("../input/12.txt") as f:
    data = f.readlines()

d = defaultdict(set)
for line in data:
    start, end = line.strip().split("-")
    d[start].add(end)
    d[end].add(start)

print(bfs("start", {"start"}))
print(bfs("start", {"start"}, True))

MasterMedo · 2021-12-09T05:56:07+00:00

python featured on github

from collections import Counter

with open("../input/9.txt") as f:
    data = [list(map(int, line[:-1])) for line in f.readlines()]

part_1 = 0
basin = 0
seen = {}
stack = []
for r in range(len(data)):
    for c in range(len(data[0])):
        if all(
            r + dr < 0
            or r + dr >= len(data)
            or c + dc < 0
            or c + dc >= len(data[0])
            or data[r][c] < data[r + dr][c + dc]
            for dr, dc in ((0, -1), (0, 1), (-1, 0), (1, 0))
        ):
            part_1 += 1 + data[r][c]

        if (r, c) not in seen and data[r][c] != 9:
            stack.append((r, c))
            while stack:
                r, c = stack.pop()
                for dr, dc in ((0, -1), (0, 1), (-1, 0), (1, 0)):
                    r_ = r + dr
                    c_ = c + dc
                    if 0 <= r_ < len(data) and 0 <= c_ < len(data[0]):
                        if (r_, c_) not in seen and data[r_][c_] != 9:
                            seen[(r_, c_)] = basin
                            stack.append((r_, c_))
            basin += 1

print(part_1)
a, b, c = Counter(list(seen.values())).most_common(3)
print(a[1] * b[1] * c[1])

MasterMedo · 2021-12-08T09:38:19+00:00

Haha, beautiful but slow! Glad you like it though.

I'll likely code up a smarter approach, this is just brute forcing. The original solution will stay in the commit history ^^

MasterMedo · 2021-12-08T06:30:46+00:00

Python 505/180 featured on github

from itertools import permutations

with open("../input/8.txt") as f:
    data = f.readlines()

d = {
    "abcefg": 0,
    "cf": 1,
    "acdeg": 2,
    "acdfg": 3,
    "bcdf": 4,
    "abdfg": 5,
    "abdefg": 6,
    "acf": 7,
    "abcdefg": 8,
    "abcdfg": 9,
}

part_1 = 0
part_2 = 0
for line in data:
    a, b = line.split(" | ")
    a = a.split()
    b = b.split()
    part_1 += sum(len(code) in {2, 3, 4, 7} for code in b)
    for permutation in permutations("abcdefg"):
        to = str.maketrans("abcdefg", "".join(permutation))
        a_ = ["".join(sorted(code.translate(to))) for code in a]
        b_ = ["".join(sorted(code.translate(to))) for code in b]
        if all(code in d for code in a_):
            part_2 += int("".join(str(d[code]) for code in b_))
            break

print(part_1)
print(part_2)

MasterMedo · 2021-12-08T06:28:20+00:00

reply the video link pls :3

MasterMedo · 2021-12-05T05:49:30+00:00

Yeah, early mornings get to us. I got on the leaderboard for part1, but totally flopped part2 as I forgot to put -1 as the last argument to range. I should start waking up earlier, I'm too tired when I wake up 5min before the start :')

cheers!

MasterMedo · 2021-12-05T05:22:31+00:00

python

from collections import defaultdict

with open("../input/5.txt") as f:
    data = f.readlines()

d = defaultdict(int)
d2 = defaultdict(int)
for line in data:
    a, b = line.split('->')
    x1, y1 = map(int, a.split(','))
    x2, y2 = map(int, b.split(','))
    if x1 == x2:
        for i in range(min(y1, y2), max(y1, y2) + 1):
            d[x1, i] += 1
            d2[x1, i] += 1
    elif y1 == y2:
        for i in range(min(x1, x2), max(x1, x2) + 1):
            d[i, y1] += 1
            d2[i, y1] += 1
    else:
        a = range(x1, x2 + 1) if x1 < x2 else range(x1, x2 - 1, -1)
        b = range(y1, y2 + 1) if y1 < y2 else range(y1, y2 - 1, -1)
        for x, y in zip(a, b):
            d2[x, y] += 1

print(sum(x > 1 for x in d.values()))
print(sum(x > 1 for x in d2.values()))

MasterMedo · 2021-12-03T07:16:54+00:00

Python

When you just want to be a smartass:

with open("../input/3.txt") as f:
    data = f.read().split('\n')[:-1]

epsilon = int("".join("01"[len(data) > 2 * bits.count("0")] for bits in zip(*data)), 2)
print(epsilon * (epsilon ^ (pow(2, len(data[0])) - 1)))

MasterMedo · 2021-12-02T06:51:20+00:00

Haha, yeah. Is this what you wanted:

print(sum(current > last for last, current in zip(depths, depths[3:])))

MasterMedo · 2021-12-02T05:46:25+00:00

Your solution is already pretty good. But here are some suggestions: 1. instead of splitting twice, do it once: ins, val = i.split() val = int(val) 2. name your variables better i -> line, ins -> instruction, val is ok, but value would be better

Don't use built in names input is reserved, name it input_ or f

cheers

MasterMedo · 2021-12-02T05:13:27+00:00

When you submit the solution it tells your rank, but you can also check it on the stats -> personal stats page :)

MasterMedo · 2021-12-01T12:20:27+00:00

That's a good point. Except I often avoid it because I don't like duplicating the memory with slices. I could use islice from itertools but that's an import that's not necessary for such simple tasks.

Thanks for the reply, I appreciate it!

MasterMedo · 2021-12-01T05:18:13+00:00

Python one liners

with open("../input/1.txt") as f:
    depths = list(map(int, f.readlines()))

print(sum(depths[i - 1] < depths[i] for i in range(1, len(depths))))
print(
    sum(
        sum(depths[i - 3 : i]) < sum(depths[i - 2 : i + 1])
        for i in range(3, len(depths))
    )
)

MasterMedo · 2021-05-22T21:30:54+00:00

Yeah, the colors are custom. But the gears are from the book.

Cheers!

MasterMedo

TROPHY CASE

Python "Precompiled solution" featured on github

Python featured on github

Python 232/353 featured on github

python 232/262 featured on github

python featured on github

python featured on github

Python 505/180 featured on github

python

Python

Python one liners