Christmas time is here, and that means Advent of Code and /aocg/ are back in my life to remind me what a poor programmer I am. If I ever want to find the true meaning of Rockefeller groove, I'll have to make it through all 25 days.
You may remember I concluded last year with a long list of topics to study and thorough plans for becoming a better programmer in the next year with the desire to complete AoC 2022 with ease. Well instead of doing that, I instead spent the last year in rapid mental decline! It's not all bad though, I learned C more or less this year, and think I've become a better programmer in general. I've also practiced old Advent of Code years on and off in the last couple months, so I'm hoping some of the puzzles are fresh enough on my mind for me to recognize them.
Luckily another anon is making the calendar so that's one less thing for me to worry about.
I'm planning on doing the puzzles when they come out in Python, and will follow up any interesting ones with C. Some challenges are just actually easier for me to do in C in the first place, so it wouldn't surprise me if that happens occasionally. Python's black-box nature can make it difficult to think through problems for me sometimes. I'm hoping to be able to write better C code afterward so I can have fun in the /aocg/ threads optimizing as much as possible for the inevitable bigboy inputs.
I'll be using my
usual git repo and the filename
unwashed.py (or .c or whatever else) is my initial solution. Any further
variations will be in another file, probably named washed.c or something
similar.
And for fun, I'll mention what tea I make right before each puzzle drops because I'm planning on having a different kind each day.
Merry Christmas and good luck on the challenges to any visitors! My Christmas theme has returned once again and will be on until some time after the 25th - probably New Years.
Today's tea: Cranberry Gingerale. Exceptional tea, very flavorful and Christmas-y.
Very easy day one, not that that's saying much. I spent most of my time just trying to remember how to split Python input (IOWrapper-what? Generator object-what? Fileinput object different from other file objects?). Decided to just skip the cutsie one-liners and read input using a loop instead. Once I did that and finished reading the problem I realized just how easy it was, and should have been had I not been fiddling with the input file.
from fileinput import input
elves = [[] for _ in range(500)]
i = 0
for line in input():
if line == "\n":
i += 1
continue
elves[i].append(int(line))
elves.sort(key=sum, reverse=1)
print(sum(elves[0]))
print(sum([fuck for python in elves[:3] for fuck in python]))
Afterward I worked on an input() function I could use to just forego bothering
with fileinput anymore:
# aoc.py
def input():
"Read file via argv or stdin and return as string"
if len(sys.argv) > 1:
return open(sys.argv[1]).read()
return sys.stdin.read()
# washed.py
from aoc import input
elves = [*map(lambda l: [*map(int, l.split())], input().split("\n\n"))]
Using this just skips the steps involved in using a lazy iterator. If I
need something like that, I'll be more likely to use my scan()
function anyway.
After writing my initial solution in Python I worked on the C version which only stores the three largest integers instead of the whole input list.
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
long int getn()
{
long int c, r = LONG_MIN, n = 0;
while ((c = getchar()) >= '0' && c <= '9')
r = n = n * 10 + c - '0';
return c == EOF ? LONG_MIN+1 : r;
}
void rot(long int top[3], long int sum)
{
if (sum > top[0]) {
top[2] = top[1];
top[1] = top[0];
top[0] = sum;
}
else if (sum > top[1]) {
top[2] = top[1];
top[1] = sum;
}
else if (sum > top[2])
top[2] = sum;
}
int main()
{
long int top[3];
long int n, sum = 0;
bool cont = true;
while (cont) {
switch (n = getn()) {
case LONG_MIN+1:
cont = false;
break;
case LONG_MIN:
rot(top, sum);
sum = 0;
break;
default:
sum += n;
}
}
printf("%ld\n", top[0]);
printf("%ld\n", top[0] + top[1] + top[2]);
}
Yep, for me, it's C. Going to write my own library of simple input parsing functions in C as well, but I haven't gotten to that yet.
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
1 00:12:33 6244 0 00:19:09 6553 0
My rank is a lot worse than I would have liked for a problem this easy, but it can't be helped now.
Today's tea: Sweet Potato Pie. Pleasant enough for a desserty tea, but wouldn't buy personally.
Not a super fun puzzle for me today. I'm looking forward to these getting a bit more difficult because suffering through the later challenges is something to do. Even with the easy prompt, I still managed to take a while to get this one done. My trouble this time was keeping track of the rock-paper-scissor values in my head.
from aoc import scan
defeats = {"A": 3, "B": 1, "C": 2}
defeated = {"A": 2, "B": 3, "C": 1}
def rps(a, b):
return (3 + a - b) % 3
p2 = p1 = 0
for a, b in scan(r"(\w) (\w)"):
r = rps(ord(a) - ord("A"), ord(b) - ord("X"))
p1 += ord(b)-(ord("X")-1)
if r == 0:
p1 += 3
elif r == 2:
p1 += 6
if b == "Y":
p2 += (ord(a)-(ord("A")-1)) + 3
elif b == "X":
p2 += defeats[a]
elif b == "Z":
p2 += defeated[a] + 6
print(p1)
print(p2)
Nothing interesting about this. But I have been intrigued by some of the optimized solutions I've come across tonight. My favorite one uses arrays as a table. Works because all combinations needed to solve the problem are known ahead of time and don't need to be computed. Going to try to remember this trick for the future. Here's my take on that solution:
int scores[3][3] = {
4, 1, 7,
8, 5, 2,
3, 9, 6,
};
int scores2[3][3] = {
3, 1, 2,
4, 5, 6,
8, 9, 7,
};
int main()
{
int a, b, s = 0;
int p1 = 0, p2 = 0;
while (s != EOF) {
a = getchar(), getchar(), b = getchar(), s = getchar();
p1 += scores[b - 'X'][a - 'A'];
p2 += scores2[b - 'X'][a - 'A'];
}
printf("%d\n%d\n", p1, p2);
}
My score:
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
2 00:19:37 8053 0 00:32:59 8971 0
I don't have much of an expectation for myself, but it's still a little disappointing to see a problem like this look you 30 minutes.
Today's tea: "Headache Halo", pretty good rooibos tea with subtle mintiness. Would rather have some caffeine though.
I liked the puzzle more today and am happier with the time I got. Set intersection problems in languages with built-in set intersection functions are very easy and tonight will probably be even less of a filter than yesterday I imagine?
I used fileinput again today because I wanted to just loop over the entire
input one line at a time, which made it a better fit than the input function
I wrote yesterday.
from fileinput import input
last3 = [set(), set(), set()]
p2 = p1 = 0
i = 1
for line in input():
line = line.strip()
a, b = set(line[:len(line)//2]), (line[len(line)//2:])
c = a.intersection(b)
for letter in c:
if ord(letter) >= ord("a"):
p1 += ord(letter) - (ord("a") - 1)
else:
p1 += ord(letter) - (ord("A") - 1) + 26
last3[i % 3] = set(line)
if i % 3 == 0:
c = last3[0].intersection(last3[1], last3[2])
letter = list(c)[0]
if ord(letter) >= ord("a"):
p2 += ord(letter) - (ord("a") - 1)
else:
p2 += ord(letter) - (ord("A") - 1) + 26
i += 1
print(p1)
print(p2)
I had more fun implementing this solution in C afterwards using bitwise operations.
I researched how to find the first 1 bit in an integer in a more efficient way than
looping and right shifting, and discovered the
GCC function
__builtin_ctzl which can be used for this purpose perfectly.
I'd still like to think how to forego the line array and combine the two loops into
one, but I'm not sure it can be done since you don't know the length of the line
ahead of time.
#define MAX 48
int main()
{
long int silver = 0, gold = 0;
uint64_t a = 0, b = 0;
int len = 0, x = 1, c;
char line[MAX];
uint64_t last[3];
while (1) {
while ((c = getchar()) > 'A')
line[len++] = (c - ((c >= 'a') ? ('a') : ('A' - 26)));
if (c == EOF)
break;
for (int i = 0; i < len/2; ++i) {
a |= (1UL << line[i]);
b |= (1UL << line[(len-1)-i]);
}
silver += __builtin_ctzl(a & b) + 1;
last[x % 3] = a | b;
if (x++ % 3 == 0)
gold += __builtin_ctzl(last[0] & last[1] & last[2]) + 1;
a = b = len = 0;
}
printf("%ld\n", silver);
printf("%ld\n", gold);
}
While still not impressive, I'm definitely happier with this than my result yesterday:
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
3 00:12:08 3831 0 00:21:32 4210 0
Today's tea: Hot Chocolate; another really good dessert-y tea. I actually liked this more than I usually like actual hot chocolate because it's often too sweet to be enjoyable. This was more balanced in comparison.
This puzzle shouldn't have been difficult at all, but I'm particularly bad at thinking
through these kind of range/boolean problems. I ended up making some stupid mistakes
so it took me longer. The condition I used in part 2 is unnecessarily complex, it could
have just been ((a <= c and c <= b) or (c <= a and a <= d)) but this is my code as
I wrote it at midnight:
from aoc import scan
gold = silver = 0
for a, b, c, d in scan(r"(\d+)-(\d+),(\d+)-(\d+)"):
if (a >= c and b <= d) or (c >= a and d <= b):
silver += 1
if (b >= c and b <= d) or (c >= a and c <= b) or (d >= a and d <= b):
gold += 1
print(silver)
print(gold)
I followed along with the lower-level optimizations people were doing throughout the day, but I don't see much of a point to pasting it here.
My score is disproportionately bad compared to the difficulty of the puzzle itself
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
4 00:18:26 8460 0 00:28:25 9192 0
Today's tea: Strawberry Rhubarb Parfait; A sweet herbal-ish tea that was pretty good. It tastes very much like fruit and more subtlety, yogurt.
I didn't hardcode the input into my solution, but I should have because that's what I spent the most time on. All things considered I'm pretty happy with my time on this one because it's such a tedious mess to work through parsing. I'd be more surprised if my time were better than it was.
The actual algorithm was insignificant, but I still certainly didn't handle it as elegantly as possible. Not sure if this problem will end up being interesting to optimize so I might go to bed earlier and catch up on sleep instead.
from aoc import input
from collections import deque
CRATES = 9
RANGE = 34
I = input().split("\n")
C = I[:CRATES-1]
crates = [deque() for _ in range(CRATES)]
crates2 = [deque() for _ in range(CRATES)]
ins = I[CRATES+1:len(I)-1]
for line in C:
for c, i in enumerate(range(1, RANGE + 3, 4)):
if line[i] != " ":
crates[c].append(line[i])
crates2[c].append(line[i])
for op in ins:
op = op.split()
n = int(op[1])
fr = int(op[3])
to = int(op[5])
tmp = []
for _ in range(n):
crates[to-1].appendleft(crates[fr-1].popleft())
tmp.append(crates2[fr-1].popleft())
for c in reversed(tmp):
crates2[to-1].appendleft(c)
print("".join(crate[0] for crate in crates if crate))
print("".join(crate[0] for crate in crates2 if crate))
Here's my personal stats for tonight:
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
5 00:34:00 6495 0 00:38:12 5990 0
Ok I don't know why I'm still awake but I made a visualization in curses real quick.
The actual logic isn't doing anything different from my unwashed part 1 code.
(See video below, or here).
Code is on github as visual.py.
Today's tea: Candy Cane Crush; basically just a sugary mint tea. Not bad nothing unusual since I've had mint teas before.
I'm so ill right now that I can hardly think straight and every second is excruciating and yet I solved this one in 10 minutes. Hoping these get harder soon, but I really lucked out tonight because I might not have been able to do it otherwise.
from aoc import input
from more_itertools import sliding_window
I = input().strip()
for i, group in enumerate(sliding_window(I, 4), start=1):
if len(set(group)) == 4:
break
print(i + 3)
for i, group in enumerate(sliding_window(I, 14), start=1):
if len(set(group)) == 14:
break
print(i + 13)
Here's my stats for today:
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
6 00:09:31 5800 0 00:10:23 4807 0
Today's tea: Organic Orange Spice; really tasty green tea with strong spice flavors. Mostly cinnamon but the whole thing works well.
Feeling much better compared to yesterday, less worried about being hindered by illness.
I struggled with parts of this one, but thought it was a ton of fun. Being familiar with unix file tree hierarchy structure
makes this problem obviously stand out as a tree problem, but I hate implementing those so I used
a hash table (defaultdict) instead. Turns out that's what a lot of people did so my solution isn't quite
as bad or unusual as I thought it could have been at first.
The first major problem I had was realizing that unlike the example on the page, the actual input has repeated directory names, so a simple hash table solution with directories as keys failed. Then I switched to using pseudo absolute paths, but that took me a few tries because of some stupid mistakes.
My final problem was not paying close enough attention to the instructions and doing
70000000 - root_total instead of 30000000 - (70000000 - root_total) and getting the incorrect
result for my input, but yet again, the correct result for the example.
I also wasted time in part 1 setting up data in a way that never became useful in part 2. Like making
a namedtuple to represent files even though they don't ever need to be tracked and I deleted it
while writing part 2. It's easy to waste time organizing useless data so I'll have to keep that in mind
for the coming days.
Note that in my solution I never use dirs["total"] distinctly from dirs["ctotal"] (children total) and
those keys could have been combined into one and reduced some mental overhead. But this is how
I solved it and don't want to clean up my "unwashed" code.
from fileinput import input
from collections import defaultdict
cwd = None
dirs = defaultdict(lambda: {"parent": None, "total": 0, "ctotal": 0})
listing = False
for line in input():
line = line.strip()
if line.startswith("$ cd"):
mk = line[5:]
if mk == "..":
cwd = dirs[cwd]["parent"]
else:
dirs["/" if not cwd else cwd + "/" + mk]["parent"] = cwd
cwd = "/" if not cwd else cwd + "/" + mk
listing = False
elif line.startswith("$ ls"):
listing = True
elif listing:
sz, name = line.split()
if sz == "dir":
dirs[cwd + "/" + name]["parent"] = cwd
else:
sz = int(sz)
dirs[cwd]["total"] += sz
parent = dirs[cwd]["parent"]
while parent is not None:
dirs[parent]["ctotal"] += sz
parent = dirs[parent]["parent"]
silver, gold = 0, 70000000
free = 30000000 - (gold - (dirs["/"]["total"] + dirs["/"]["ctotal"]))
for d in dirs:
if dirs[d]["total"] + dirs[d]["ctotal"] <= 100000:
silver += dirs[d]["total"] + dirs[d]["ctotal"]
if dirs[d]["total"] + dirs[d]["ctotal"] >= free:
gold = min(gold, dirs[d]["total"] + dirs[d]["ctotal"])
print(silver)
print(gold)
My rank today was not good, but I actually don't mind what I got. I'm just happy it didn't take me longer.
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
7 01:18:58 8021 0 01:32:04 7903 0
Today's tea: Mother's Little Helper; Unremarkable, but good herbal tea. Kind of minty but no strong flavors that stand out, I guess?
I made multiple stupid mistakes today that ended up really costing me. A few noteworthy ones
were using range(y, Y+1) instead of range(y+1, Y+1) and range(x-1,0,-1) instead of range(x-1,-1,-1).
I also initially wrote part 1 as comparing the sum of all the trees surrounding the current tree with the
current tree, and then I made the mistake of tallying each tree in the lines surrounding the current tree
rather than comparing the maximum (tallest) tree in each line.
For part 2 I had trouble with the wording of what trees were in view, and I screwed up the formatting of
my score function a couple times.
from aoc import input
from toolz import juxt
f = [[int(i) for i in row] for row in input().strip().split("\n")]
X, Y = len(f[0]) - 1, len(f) - 1
def up(y, x):
return max(f[i][x] for i in range(y)) < f[y][x]
def down(y, x):
return max(f[i][x] for i in range(y+1, Y+1)) < f[y][x]
def left(y, x):
return max(f[y][:x]) < f[y][x]
def right(y, x):
return max(f[y][x+1:]) < f[y][x]
check = juxt(up, down, left, right)
def score(y, x):
total = 1
xranges = ((x+1,X+1), (x-1,-1,-1))
for r in xranges:
for s, i in enumerate(range(*r), start=1):
if f[y][i] >= f[y][x]:
break
total *= s
yranges = ((y-1,-1,-1), (y+1,Y+1))
for r in yranges:
for s, i in enumerate(range(*r), start=1):
if f[i][x] >= f[y][x]:
break
total *= s
return total
silver, gold = ((X+1)*2) + (2*(Y-1)), 0
for y, row in enumerate(f[1:-1], start=1):
for x, col in enumerate(row[1:-1], start=1):
silver += any(check(y, x))
gold = max(gold, score(y, x))
print(silver)
print(gold)
All that considered, it could have been worse in terms of how long it took me. Better time than yesterday, but worse rank. I'd say that for me the problems were of similar difficulty so I don't feel like I'm doing terribly for my skill level.
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
8 00:51:08 9279 0 01:15:58 8230 0
Anyway, here's another curses visualization. Not a very interesting one this time. Lighter shades of green represent greater visibility from outside the grid. The trees on the edges are set to the lightest shade because they are entirely visibly from outside the grid, and because it looks neater that way.