I'm going to try to do all of the Advent of Code programming/algorithm challenges this year. I'm not a particularly good programmer, but I do currently have plenty of free time, so my current plan is put in as much time as I need or can stand into finishing the challenges everyday. My current primary study focus is C so I am planning to do all of them in C after I first do them in Python as quickly as I can.
I've been reading the book "Algorithmic Thinking" lately which has been helpful for me as an introduction to the terminology and problem solving steps of solving algorithmic challenges. It's a C-based book which is good because ultimately I want to get more comfortable at reading and writing in C.
I'll be posting and hanging around in the
/aocg/ threads, so
I'll post my time
command results with the provided inputs as well as the
big boy inputs posted in the threads.
Archivist Anon
is back this year and is collecting the input files and code submissions from
the threads.
198336
and
993406
seem to be the two primary private leaderboards.
I think I'm going to include my solutions in this post, but even if I don't keep up with doing that I also have a git repo where all of them will be kept and updated.
Oh great more water this year..! Even day 1 took me longer than I was expecting it to! Here's my "unwashed" Python code:
f = [int(l.strip()) for l in __import__('fileinput').input(files=('input'))] la = 0 t = 0 for c, l in enumerate(f): if l > la and c: t += 1 la = l print(t) ps = 0 t = 0 for i in range(c): cs = sum(f[i:i+3]) if ps and cs > ps: t += 1 ps = cs print(t)
And here's my day 1 stats. IT'S ALL DOWNHILL FROM HERE!!!! Now for drinks!
-------Part 1-------- -------Part 2-------- Day Time Rank Score Time Rank Score 1 00:06:59 3888 0 00:18:51 4711 0
I just wrote the solution for day 1 in C, using advice from No.84550907 who explains that you don't need to calculate the sum of every group of three in the array, because only one integer is different between them them. So you can just compare those indexes without iteration.
>If you're comparing the sums of indexes 0, 1, 2 and 1, 2, 3, then all you are really comparing is if index 3 is greater than index 0.
#include <stdio.h> #define SIZE 2000 int main() { int depths[SIZE]; int part1 = 0, last = 0; for (int i = 0; i < SIZE; ++i) { scanf("%d", &depths[i]); if (i && depths[i] > last) { ++part1; } last = depths[i]; } printf("%d\n", part1); int part2 = 0; for (int i = 0; i < SIZE-3; ++i) { if (depths[i+3] > depths[i]) { ++part2; } } printf("%d\n", part2); }
List slicing as I used in python has a O(k) time complexity, where k is the number of elements being iterated. In this case, only 1 array lookup is reduced which is trivial, but it's a fun trick either way. I tried to create a solution that doesn't use arrays at all, but I couldn't figure out how to do it for part 2.
Somewhat noteworthy: the documentation for the itertools
python library includes
a recipe for
creating a sliding_window()
function that you could use for creating a shorter solution
like this one I found on IRC.
Lainchan webring resident Aurora
has an example
of what a similar python solution could look like that doesn't need the imports or helper function.
Today was easier than yesterday? Whatever I'll take it. Here's my unwashed code:
f = [l.strip() for l in __import__('fileinput').input(files=('input'))] h = 0 dp = 0 for l in f: d, i = l.split() i = int(i) if d == "forward": h += i elif d == "down": dp += i elif d == "up": dp -= i print(h * dp) h = 0 dp = 0 a = 0 for l in f: d, i = l.split() i = int(i) if d == "forward": h += i dp += i * a elif d == "down": a += i elif d == "up": a -= i print(h * dp)
I lost a little bit of time to the fact that I had read the problem to require
dp *= a
on part 2 rather than dp += i * a
. But still, my stats
were actually better today than yesterday, go figure.
-------Part 1-------- -------Part 2-------- Day Time Rank Score Time Rank Score 2 00:03:47 1827 0 00:06:35 1895 0
It was obvious even before finishing part 2 that these solutions could be found in one input iteration without a need for the second loop, so I've already created a second version:
a = h = h2 = dp = dp2 = 0 for l in f: d, i = l.split()[0], int(l.split()[1]) match d: case "forward": h, h2 = (x + i for x in (h, h2)) dp2 += i * a case "down": dp, a = (x + i for x in (dp, a)) case "up": dp, a = (x - i for x in (dp, a)) print(h * dp) print(h2 * dp2)
For extra fun I used the new Python 3.10 match-case syntax. Arch Linux still hasn't
updated to it yet unfortunately, but it's on the AUR. I love this new feature and I'm looking
forward to finding more uses for it in the future too. Anon
No.84567076
showed a way to make even better use of the pattern matching syntax. I
updated the file in my git repo to reflect this idea. I will definitely spend some time tomorrow
practicing with match
even more.
I did my C version as well even though I should be sleeping:
#include <stdio.h> int main() { int horiz = 0, depth = 0, depth2 = 0, all = 0, value = 0; char line[11]; for (int i = 0; i < 1000; ++i) { fgets(line, 11, stdin); sscanf(line, "%*[^0123456789]%d", &value); switch (line[0]) { case 'f': horiz += value; depth2 += value * all; break; case 'd': depth += value; all += value; break; case 'u': depth -= value; all -= value; break; } } printf("%d\n", horiz * depth); printf("%d\n", horiz * depth2); }
I tried and failed to find a way to get input without creating an array,
but from my research it appears doing so isn't even considered good practice.
My first attempt was using scanf to get input but I couldn't get it working consistently.
I also realized in re-writing the problem in C that the h2
variable
I was maintaining in my Python versions was unnecessary.
I made a cute visualization for part 2 in Python using the curses library. You'd need to play with the h_limit and d_limit variables to get it looking nice in your terminal. Code is here.
I don't know why but I really struggled with this problem. Not a great sign to be doing this bad after only three days lol.
f = [l.strip() for l in __import__('fileinput').input(files=('input'))] d = {i: [0, 0] for i in range(12)} def pd(f=f, d=d): for n in f: for i, b in enumerate(n): d[i][int(b)] += 1 pd() gr = int("".join([str(int(i[1] > i[0])) for i in d.values()]), 2) ep = int("".join([str(int(i[1] < i[0])) for i in d.values()]), 2) print(ep * gr) d2 = d f2 = f.copy() e2 = e = 0 for i in range(12): if len(f) > 2: f = [l for l in f if l[i] == str(int(d[i][1] >= d[i][0]))] d = {i: [0, 0] for i in range(12)} pd(f, d) e += 1 if len(f2) > 2: f2 = [l for l in f2 if l[i] == str(int(d2[i][1] < d2[i][0]))] d2 = {i: [0, 0] for i in range(12)} pd(f2, d2) e2 += 1 o = int(f[0] if f[0][e] == 1 else f[1], 2) if len(f) > 1 else int(f[0], 2) c = int(f2[0] if f2[0][e2] == 0 else f2[1], 2) if len(f2) > 1 else int(f2[0], 2) print(o * c)
It took me a moment to fully understand part 1, and even longer to understand part 2. I think my biggest mistake was probably that I tried too hard to get part 2 working using the foundation I set for part 1. In particular, I should have abandoned the dictionary I used for part 1 instead of figuring out how to use it for part 2. It would have benefit me more to have just restarted and come at it from a new perspective.
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 3 00:24:05 8387 0 02:55:10 15462 0
OUCH! It hurts to see this .･ﾟﾟ･(／ω＼)･ﾟﾟ･.
This one was a bit of a challenge, and I enjoyed it more than yesterday. It took extra time to parse the input which I was not expecting. Nice to see an input formatting that makes you scramble instead of using your pre-pasted input parsing functions :p As I was still working out part 1, I got a bit lost in my multi-nested for loops which I would say was my biggest time loss. Also on part 2 I had initially been checking for the last overall win not the last board to win a single time. I can already see flaws in my solution and interesting solutions other people have shared online. I lose a lot of efficiency by attempting to break the problem down into logical steps (more iterations) instead of coming up with good ideas for parsing more at once quickly. I will have fun redoing this one. Anyway, here's my unwashed code:
from collections import defaultdict f = open('input').read().strip().split("\n\n") dd = defaultdict(list) w = defaultdict(list) p = [int(i) for i in f[0].split(",")] p1, p2 = [0, 0, 0], [[], 0, 0] for i, b in enumerate(f[1:]): for r in b.splitlines(): dd[i].append([int(x) for x in r.split()]) for i, ins in enumerate(p): for bi, b in enumerate(dd.values()): for ri, r in enumerate(b): if ins in r: w[bi].append((ri, r.index(ins))) h = [x[0] for x in w[bi]] v = [x[1] for x in w[bi]] for y in range(5): if h.count(y) == 5 or v.count(y) == 5: if not p1[1]: p1[0], p1[1], p1[2] = bi, i + 1, ins if bi not in p2[0]: p2[0].append(bi) p2[1], p2[2] = i + 1, ins print(sum(i for r in dd[p1[0]] for i in r if i not in p[:p1[1]]) * p1[2]) print(sum(i for r in dd[p2[0][-1]] for i in r if i not in p[:p2[1]]) * p2[2])
I use a defaultdict to avoid having to think about populating the dictionary with empty lists before appending to them. And here's my ranking for today. Better than yesterday but still not good. I'd really like to be able to do these in under an hour :(
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 4 01:28:38 8142 0 02:00:21 8335 0
My worst one yet. I'm starting to feel the discouragement at this point. I'm even a couple days behind on doing my C implementations. All things considered I'm not unhappy with this code, but I had a terrible time visualizing this one and thinking it through. Now that I'm done, I can safely say I owe part of that confusion to a debug function I wrote during part 1 that printed the same graphical grid of lines as shown in the prompt. I don't know where I was going wrong with it (because I already deleted it) but I was wrongfully basing my solution on its output. I finished the challenge within minutes of realizing that my part 1 and part 2 were incompatible as I had written them. Ahhhhhh! I can tell this month is going to be very difficult for me, and I'm realizing now that there's a fair chance it'll venture outside my skill level to figure out. Will keep trying!
from collections import defaultdict f = [[(*(map(int, i.split(','))),) for i in l.split() if ',' in i] for l in __import__('fileinput').input(files=('input'))] p1, p2 = defaultdict(int), defaultdict(int) for l in f: x1, y1, x2, y2 = *l[0], *l[1] if x1 == x2: for i in range(min(y1, y2), max(y1, y2) + 1): p1[(x2, i)] += 1 p2[(x2, i)] += 1 elif y1 == y2: for i in range(min(x1, x2), max(x1, x2) + 1): p1[(i, y1)] += 1 p2[(i, y1)] += 1 else: for i in range(max(abs(y1 - y2), abs(x1 - x2)) + 1): x, y = x1 - i if x1 > x2 else x1 + i, y1 - i if y1 > y2 else y1 + i p2[(x, y)] += 1 print(sum(1 for i in p1.values() if i > 1)) print(sum(1 for i in p2.values() if i > 1))
And my ranking (yep, actually that bad):
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 5 01:17:40 8500 0 04:52:51 16075 0
After yesterday's discouragement my goal for today was simply for it to take less time than yesterday's challenge took me. And while it's still embarrassing how long it took, I did meet that goal:
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 6 00:18:49 6334 0 03:29:16 15867 0
For part 1 I wrote a basic brute forcing solution that maintained a list of fish and continuously updated their timers, but it got completely destroyed during part 2. Seeing pypy simply output "Killed" for when I tried anyway made me smile. It was clear that there would have to be a way to compute the numbers in the input. I spent way too long trying to think of a math formula that could return how find the correct number of resulting fish from a given starting position but this had a couple problems: I'm really, really bad at math and wasn't able to find a way to do it, and that I remembered that even if I did I would have to figure out a way to take into consideration what day a newly spawned fish was starting at. At this point I just returned to thinking in terms of basic programming logic which I'm more familiar with. I tried to break down the problem in some comments:
> # how many fish will a given timer create in n remaining days?
> # then, how many fish will those new fish create in n remaining days,
> # excluding the previous? etc
Then after much fumbling I ended up accepting my fate and that it seems like a problem
best suited to recursion (that is, the answer to the question is an instance of the same
question). The first stupid mistake I made was that my range function was always starting from
0, and instead of the function providing the start of the range it provided the end, so each
recursive call started on day 1 and messed up the results. My biggest problem after that was
that initially I was maintaining a global variable inside the function. This worked well with the
sample inputs (18 days, 5 initial fish), but as I kept testing it the program took forever. My heart
sank because I thought I had gone through all the trouble into thinking this through only for it
to also be too slow, but I did the standard python codelet solution: lru_cache
to the rescue! At that point, the program finished instantly, but with an incorrect answer!
Cached function calls weren't called again, so the global variable wasn't being updated. I had a
surprising difficulty trying to think through how to maintain the new number of fish found per
function call. Not sure now why I was struggling because it feels obvious, but it took me a bit to
figure out. Overall, I had a lot of fun with this one and I am happy with how my code turned out.
I still hope I'll get better at solving these problems quicker.
from functools import lru_cache lf = [int(i) for i in open("input").read().strip().split(",")] @lru_cache(2048) def r(t, s=0): f = 0 for i in range(s, 256): if not t: t = 7 f += 1 f += r(8, i+1) t -= 1 return f print(sum(r(i) for i in lf) + len(lf))
I figured out pretty quickly that I could solve part 1 with the median of the input list and adding up how many steps it would take to get there for each given number. This is absolutely the limit of my ability to comprehend math, unfortunately. For part 2, I had to abandon trying to think this through, and decided to just brute force it instead of trying to find a math solution I couldn't understand.
f = sorted(int(i) for i in open("input").read().strip().split(",")) m = f[len(f) // 2] l, p1, p2 = 0, 0, [0 for x in range(f[-1] + 1)] for cr in f: p1 += abs(m - cr) for i in range(f[-1] + 1): for cr in f: p2[i] += sum(range(1, abs(cr - i) + 1)) if l and l < p2[i]: break l = p2[i] print(p1) print(min(i for i in p2 if i > 0))
I tried looking up if there was a better way to add up a range up of numbers,
which I've since learned is called a series, in Python but I couldn't find anything
interesting. This part 2 works, but the range loop is very inefficient. I tried to improve
it slightly by checking for whether it would even be possible for a smaller result to
follow, which helped a lot but it still takes about a second and a half to run on my
machine (compared to about 13 seconds without this check). After seeing other
solutions posted, I found
No.84646327 to be particularly helpful in reducing the time my solution takes by
changing a single line: p2[i] += (abs(cr - i) + 1) * abs(cr - i) // 2
which
is the formula I was trying to think of before giving up. This is still clearly not a great
answer since it's basically incompatible with the bigboy inputs, but I'm happy enough
with how today ended up. Luckily it didn't take me quite as long as previous days either:
I'll update this once the personal stats page isn't broken and doesn't say
"This page has been temporarily disabled. Sorry!". I kept my program running all
night on the bigboy input and it still hasn't finished executing lol. Also here's my stats
from last night:
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 7 00:07:34 3112 0 00:50:49 10182 0
Today's challenge was very time consuming, but not very difficult. I had to spend quite a while just rereading the prompt over and over trying to fully grasp the rules. I then had to restart more than once from having realized I missed a rule. Most significantly, I forgot that each "word" in the input is in arbitrary order and that even the "1" needs to have its two segment's order verified. The whole process of thinking through this one was something of throwing shit at the wall for me. I enjoyed it, but it also doesn't feel like one you're likely to learn much from. At first I felt really bad about my code, but after seeing other people's solutions it seems pretty on par. I'm not sure it's possible to create a solution for this one that isn't ugly as hell. It seems like the alternative to doing this was just validating possible permutations of a given word, but I have no idea which method is more efficient.
f = [l.strip() for l in __import__('fileinput').input()] p1 = p2 = 0 for i in f: for w in i.split(" | ")[-1].split(): if len(w) in (2, 4, 3, 7): p1 += 1 print(p1) format = { (0, 1, 2, 4, 5, 6): 0, (2, 5): 1, (0, 2, 3, 4, 6): 2, (0, 2, 3, 5, 6): 3, (1, 2, 3, 5): 4, (0, 1, 3, 5, 6): 5, (0, 1, 3, 4, 5, 6): 6, (0, 2, 5): 7, (0, 1, 2, 3, 4, 5, 6): 8, (0, 1, 2, 3, 5, 6): 9, } def map_segments(sp): d = {} for w in sorted(sp.split(), key=len): if len(w) == 2: for z in sp.split(): if len(z) == 6 and (w[0] not in z or w[1] not in z): if z.count(w[0]): d[2] = w[1] d[5] = w[0] else: d[2] = w[0] d[5] = w[1] break elif len(w) == 3: for c in w: if not (c == d[2] or c == d[5]): d[0] = c break elif len(w) == 4: w = w.replace(d[2], "").replace(d[5], "") for z in sp.split(): if len(z) == 5 and d[5] not in z: if z.count(w[0]): d[1] = w[1] d[3] = w[0] else: d[1] = w[0] d[3] = w[1] break elif len(w) == 5 and d[2] not in w: w = w.replace(d[0], "").replace(d[1], "") w = w.replace(d[3], "").replace(d[5], "") d[6] = w elif len(w) == 7: w = w.replace(d[0], "").replace(d[1], "") w = w.replace(d[2], "").replace(d[3], "") w = w.replace(d[5], "").replace(d[6], "") d[4] = w return d for l in f: sp, _, ov = l.partition(" | ") keys = map_segments(sp) aux = "" for w in ov.split(): aux += str(format[tuple(sorted(k for k, v in keys.items() if v in w))]) p2 += int(aux) print(p2)
I don't think this is very readable code, but to be fair it's not doing anything particularly interesting. Here's my awful ranking for today:
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 8 00:13:46 3494 0 04:49:01 12981 0
Oh, also this is a rare time that my first solution actually runs decently on the bigboy input. Here are my results, not that this is anything unusual or impressive for the prompt:
159946 498570828 real 0m1.287s user 0m1.286s sys 0m0.000s
I had a lot of difficulty getting on the right track for solving today's part 2 challenge, but once I did I solved it pretty quickly. My first ideas were not adequately thought out and even had I finished them they would not have worked. At some point a possible solution clicked and I used sets for storing validated coordinates. My code chugging on the bigboy input (to put it lightly.. 11m31.382s) makes it clear enough that this is not a good solution, but I'm happy enough that I found one. Every day that I'm not filtered feels lucky lol. Here's my unwashed code despite inefficiencies being already obvious to me:
from functools import reduce from operator import mul f = [[int(i) for i in l.strip()] for l in __import__('fileinput').input()] p1 = p2 = 0 t, lp = [], [] for y, l in enumerate(f): for x, i in enumerate(l): if (not y or f[y - 1][x] > i) and (y == len(f) - 1 or f[y + 1][x] > i): if (not x or f[y][x - 1] > i) and (x == len(l) - 1 or f[y][x + 1] > i): p1 += (i + 1) lp.append((y, x)) print(p1) def check_pos(y, x): aux = [] if y and f[y - 1][x] != 9: aux.append((y - 1, x)) if y < len(f) - 1 and f[y + 1][x] != 9: aux.append((y + 1, x)) if x and f[y][x - 1] != 9: aux.append((y, x - 1)) if x < len(f[y]) - 1 and f[y][x + 1] != 9: aux.append((y, x + 1)) return aux for c in lp: y, x = c b = set() b.add((y, x)) aux = check_pos(y, x) for c in aux: b.add(c) prev = 0 while True: aux = [] for c in b: aux.extend(check_pos(c[0], c[1])) for c in aux: b.add(c) if len(b) == prev: break prev = len(b) t.append(len(b)) print(reduce(mul, sorted(t)[-3:], 1))
And here's my ranking for today:
-------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 9 00:28:40 6433 0 03:58:10 13527 0
I created a curses visualization out of my solution instead of going to sleep, which was fun as usual. Makes me want to do more of these. The code for it is here.
I'm already drunk and forgot to write something for today so here goes
nothing: today's problem ended up being one of the easiest so far, but it took me
way too long to realize this while I was completely over-complicating everything.
It took me a lot of testing and re-reading the prompt to fully understand what
it considered to be a corrupt input vs. an incomplete input. At some point I realized
I should be validating single characters at a time instead of thinking in terms of
separating valid, matched chunks and looking for problems within them. That is,
the first closing pair that doesn't have an existing opening pair is the corruption.
This is an example of a problem that is made way more difficult by my desire
to think of tricks to solve problems instead of first using obvious and easy
to implement solutions. Need to try to drill in that a correct answer is more important
than a better one in this context. I was getting hung up in looking for a way to
.count()
the different characters in the line instead of parsing it.
Here's my
slightly washed code:
f = [l.strip() for l in __import__('fileinput').input()] op = {"(": ")", "[": "]", "{": "}", "<": ">"} scp = {")": 3, "]": 57, "}": 1197, ">": 25137} acp = {")": 1, "]": 2, "}": 3, ">": 4} cl = {c: o for o, c in op.items()} p1, p2 = 0, [] for l in f: cc = [] for c in l: if c in op: cc.append(c) else: if not cl[c] == cc[-1]: p1 += scp[c] break else: cc.pop() else: t, cc = 0, [] for c in reversed(l): if c in cl: cc.append(c) elif op[c] in cc: cc.pop() else: t *= 5 t += acp[op[c]] p2.append(t) print(p1) print(sorted(p2)[len(p2) // 2])
I know there is a way to combine these into a single iteration per line, but I absolutely don't feel like dealing with thinking about it yet tonight (this morning...). I tried to count the characters again in part 2, and that actually works quite well, until you re-read the prompt and realize it specifically prevents this strategy by adding math to the end that has to be done in the correct order I'm pretty sure. I also realized that I actually have done a very similar, and actually even more complex problem to this in the K&R C programming language book.
> Exercise 1-24.
> Write a program to check a C program for rudimentary syntax errors like unbalanced parentheses, brackets, and braces.
> Don't forget about quotes, both single and double, escape sequences, and comments.
> (This program is hard if you do it in full generality.)
I'm a bit sad I spent so much time over-thinking the problem, because it ended up being pretty easy. My rank suffered today, especially for part one:
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 10 01:27:30 10795 0 02:34:59 12711 0
Still, I've made it to double-digits without being filtered and I'm always glad to have solved the problem and enjoy doing so.
Today was a really interesting one, but also pretty easy. For whatever reason, I had the biggest difficultly in getting my 2D list bounds checking working correctly. Nothing else was particularly difficult but that was tedious for me and required being reworked a bit. I tried putting each index check in loop wrapped in a try/except block, but due to my function using recursion that ended up changing the results incorrectly by modifying indexes out of order. I'm very sure there's better ways to solve this challenge, but here's my (logically) unwashed code:
f = [[int(i) for i in l.strip()] for l in __import__('fileinput').input()] p1 = 0 def fl(y, x): global p1 if (y, x) in af: return af.add((y, x)) f[y][x] = 0 if i < 100: p1 += 1 if y: if f[y - 1][x] < 9 and (y - 1, x) not in af: f[y - 1][x] += 1 else: fl(y - 1, x) if y < len(f) - 1: if f[y + 1][x] < 9 and (y + 1, x) not in af: f[y + 1][x] += 1 else: fl(y + 1, x) if x: if f[y][x - 1] < 9 and (y, x - 1) not in af: f[y][x - 1] += 1 else: fl(y, x - 1) if x < len(f[y]) - 1: if f[y][x + 1] < 9 and (y, x + 1) not in af: f[y][x + 1] += 1 else: fl(y, x + 1) if y and x: if f[y - 1][x - 1] < 9 and (y - 1, x - 1) not in af: f[y - 1][x - 1] += 1 else: fl(y - 1, x - 1) if y < len(f) - 1 and x: if f[y + 1][x - 1] < 9 and (y + 1, x - 1) not in af: f[y + 1][x - 1] += 1 else: fl(y + 1, x - 1) if y and x < len(f[y]) - 1: if f[y - 1][x + 1] < 9 and (y - 1, x + 1) not in af: f[y - 1][x + 1] += 1 else: fl(y - 1, x + 1) if y < len(f) - 1 and x < len(f[y]) - 1: if f[y + 1][x + 1] < 9 and (y + 1, x + 1) not in af: f[y + 1][x + 1] += 1 else: fl(y + 1, x + 1) i = 0 while True: af = set() s = 0 for y, l in enumerate(f): if l.count(0) == len(l): s += 1 for x, o in enumerate(l): if o < 9 and (y, x) not in af: f[y][x] += 1 elif o == 9: fl(y, x) if s == len(f): print("part 2:", i) if i > 100: break i += 1 print("part 1:", p1)
And I placed better today on the leaderboard than I have for a while. Otherwise not much to say about today.
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 11 02:06:09 8506 0 02:14:24 8477 0
I stayed up creating another curses visualization, code is here. I'm so very tired :')
Finally finished part two. Better 21 hours late than never, right?
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 12 14:12:40 26647 0 21:51:37 29996 0
These last almost 24 hours have taught me one thing more than anything else: I fucking hate graph problems! But for that reason it's also clear I need to practice with them more. When I first started this problem I didn't expect it to be as difficult for me as it ended up being.. I quickly fell into the same trap I have been falling into repeatedly lately of trying to think of a "smarter"/mathematical solution when it's either not possible or at least beyond my skill level to be attempting. At first I was trying to figure out how to add up permutations of the graph nodes with something along the lines of `perm(num_of_small_cave_siblings, 1..num_of_small_cave_siblings)` which seemed like it would work, but I wasn't able to think through how this would be incorporated into a solution considering you still need to track the specific relation between nodes so it wouldn't have even worked out I think. Trying to use use methods beyond my skills and understanding is definitely hurting more than even just brute forcing would have. I cluttered my whole file with ascii graphs similar to the one one the prompt, lines trying to think through the queue append/pop process, and commented out failed attempts at getting even close to figuring out how to create the recursive function I knew I needed. I did what I should have done way sooner: give up on throwing shit at the wall and actually do some research. What I found to be helpful for me in putting together the pieces of how to proceed was this video. My biggest problem with part 1 was that, while I knew vaguely the concept of dfs traversing using a queue, I had no idea how to implement it or where to keep my queue to prevent it from being overwritten by the recursive function. This ended up being a simple one-line fix that was spotted for me by some helpful anons on /g/.
The struggle didn't stop there, and I had almost just as much trouble with part 2. Similar to part 1, I initially read the problem incorrectly (more than once even) and was assuming that the problem was simply to just treat small caves as big caves and re-run the same function, but obviously that ended up being very wrong. Implementing part 2 from the code created during part 1 should have been easy, but I failed at that too. Again, I was very lucky to receive help from an anon who showed me the issue with my logic as I had attempted to implement it. Here's my final code, almost a full day in the making:
from collections import defaultdict f = [(l.strip().split("-")) for l in __import__('fileinput').input()] p = defaultdict(list) for l, r in f: p[l].append(r) p[r].append(l) t = 0 def dfs(current, visited): global t visited = visited.copy() # courtesy of No.84738641 <3 <3 if current in visited and any(v >= 2 for v in visited.values()): # if current in visited: return if current == "end": t += 1 return if current.islower(): visited[current] += 1 # visited.add(current) neighbors = p[current] for next in neighbors: if next == "start": continue dfs(next, visited) for e in p["start"]: # visited = set() visited = defaultdict(int) dfs(e, visited) print(t)
I seriously owe by ability to finish this today to the anons who helped me, thank you :') However, this does not bode well for my ability to proceed much further. I will keep trying but my days without being fully filtered might be numbered (-ω-、)
All I can hope is that the reason I did as bad as I did was sleep deprivation. For the same reason, I have very low expectations for tonight's challenge. If I don't understand how to work through the problem quickly I might just wait and do it tomorrow because having skipped an entire night of sleep was probably already not a good idea.
I had a lot of fun with today's. After the uncertainty caused from my ability to do yesterday's smoothly I'm happy today's was easier was more relaxing. I also thought the idea of implementing origami in code was really interesting and creative too. I started off taking it really slow and not worrying about going fast or anything. Just carefully reading the prompt and trying to "reverse engineer" the example inputs to make sure I understood the math needed correctly. During this process I created a couple functions for testing purposes: one that prints a grid like in the prompts, and another for representing a given fold. Then when I more carefully read the final challenge for part 1 I realize all I had to do was execute the fold function once for the answer to part 1. Then I realized part 2 is simply displaying the results from the grid drawing function I had already wrote! For me it was one of the easiest days for this reason, even if I still took my time on it.
from collections import defaultdict f = [l for l in open(0).read().split("\n\n")] ds = [l.split(",") for l in f[0].split("\n")] ds = [(int(x), int(y)) for x, y in ds] fi = [l.split(" ")[-1].split("=") for l in f[1].split("\n") if l.strip()] fi = [(c, int(i)) for c, i in fi if i and c] maxx, maxy, tp = 0, 0, defaultdict(int) for c in ds: maxx = max(c[0], maxx) maxy = max(c[1], maxy) tp[(c[0], c[1])] = 1 def fold(d, n): global maxx, maxy mx = maxy if d == "y" else maxx for c in tp.copy(): cc = c[1] if d == "y" else c[0] if cc > n % mx: newc = abs(cc - (n % mx) * 2) newc = (c[0], newc) if d == "y" else (newc, c[1]) if tp.get(newc): tp[newc] += 1 else: tp[newc] = 1 del tp[c] if d == "y": maxy -= (n - 1) else: maxx -= (n - 1) def draw_paper(): for y in range(maxy+1): for x in range(maxx+1): if (x, y) in tp: print("#", end="") else: print(".", end="") print() for c, i in enumerate(fi, start=1): fold(*i) if c == 1: print(len(tp)) if c == len(fi): draw_paper()
I really thought it was fun, however the part 2 prompt kind of makes the idea of doing a curses visualization unnecessary :') I spent frankly way too much time getting the input into a structure as I intended. Sometimes nested list comprehensions are just too confusing for me so I ended up breaking them down more. A surprising amount of time was just spent doing that alone. Here's my ranking:
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 13 02:10:12 9813 0 02:15:11 9015 0
And now I am absolutely desperate for sleep! Didn't sleep at all which is not something I'm very compatible with. Even with this being an easy day I'm a little surprised I did it in one sitting giving the circumstances.
Oh also one more thing! According to the AoC website, I've now surpassed how many days I made it last year, so that's fun! Definitive progress I guess.
This one kicked my ass and I didn't particularly enjoy doing it. Maybe it's my inability to sleep
well lately but I just felt like I could not be bothered for this one. Part 1 itself took me a while
because I was hoping to think of a better way than modifying an increasingly large list or string.
I spent way, way too long trying to figure out how to use regex to do this, but I could not because
of the overlapping strings. I tried doing compile("|".join(pi))
and then
sub(lambda m: m[0][0] + pi[m[0]] + m[0][1], pt)
on that, but the sub function does
not support overlapping matches, so it produced a string that was too small on each step. I installed
the "regex" third-party module that supports a "overlapped=True" keyword argument in theory,
but it also doesn't support sub()! I tried using look ahead syntax but I'm glad I didn't waste even
more time on it than I did because it obviously wouldn't have worked for part 2 anyway. I included
my part 1 code as comments for novelty sake, but my first version of it actually copied the list
into an auxiliary list and then used "".join() on that, making 2 additional copies of the list per
step. I set this to run part 2 without paying attention and like you'd expect it consumed my
remaining memory and froze my computer causing it to need to be hard reset.
from collections import defaultdict f = [l.strip() for l in __import__('fileinput').input() if l.strip()] pt, pi = defaultdict(int), dict([r.split(" -> ") for r in f[1:]]) ch = defaultdict(int) for i in range(len(f[0]) - 1): pt[f[0][i] + f[0][i + 1]] += 1 ch[f[0][i]] += 1 ch[f[0][i+1]] += 1 for i in range(40): aux = pt.copy() for k, v in aux.items(): ch[pi[k]] += aux[k] pt[k] -= aux[k] pt[k[0] + pi[k]] += aux[k] pt[pi[k] + k[1]] += aux[k] if i in (9, 39): s = sorted(ch, key=lambda x: ch[x]) print(ch[s[-1]] - ch[s[0]]) # pt = list(f[0]) # for _ in range(10): # if not _ % 5: # print(_) # r = {} # for i, x in enumerate(pt): # if i < len(pt) - 1 and "".join(pt[i:i+2]) in pi: # r[i] = pi[pt[i] + pt[i + 1]] # test = 0 # for i, m in r.items(): # pt.insert(i + 1 + test, m) # test += 1 # mc = lc = 0 # for c in set(pt): # if (t := pt.count(c)) > mc: # mc = t # if t < lc or not lc: # lc = t # print(mc - lc)
Not sure how much this matters on days where I go to bed before trying to finish, but here's my rank:
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 14 03:42:46 16264 0 12:45:59 21883 0
Day 17? Why am I two days out of order? That's because I'm still working on them damn it! I will finish them soon and update them after this one. My days are truly numbered!!! Well not if any more days are as easy as today's was. At first I saw this shit about trajectories and velocity and whatever and I thought it'd be the end of me for sure, even excluding the last couple days which I've not finished, but what do you know today was actually super easy to brute force. Maybe it was a freebie after a more involved day, or it was just not thought out. Apparently part 1 has a O(1) solution too? Seems weird for so late in the month. Here's my code for today, not that it's anything special:
from argparse import ArgumentParser parser = ArgumentParser() parser.add_argument("-v", "--verbose", action="store_true", default=False) parser.add_argument("input", nargs="*") args = parser.parse_args() f = [l for l in __import__('fileinput').input(files=args.input if len(args.input) > 0 else ("-", ))][0].strip() y = tuple(map(int, f.split("=")[-1].split(".."))) x = (int((sp:=(f.split("=")[-2].split("..")))[0]), int(sp[1].split(",")[0])) ta = (x, y) maxes = [] def step(): p[0] += v[0] p[1] += v[1] if v[0] < 0: v[0] += 1 elif v[0] > 0: v[0] -= 1 v[1] -= 1 for mx in range(-500, 501): for my in range(-500, 501): v = [mx, my] maxy = 0 p = [0, 0] if args.verbose: print("[!] starting on initial velocity", v, end="\r", flush=True) for _ in range(500): step() if p[1] > maxy: maxy = p[1] if p[0] >= ta[0][0] and p[0] <= ta[0][1]: if p[1] >= ta[1][0] and p[1] <= ta[1][1]: maxes.append(maxy) if args.verbose: print("[+] found matching velocity", v, "highest y was", maxy) break if args.verbose: print() print(max(maxes)) print(len(maxes))
Yep, pure brute force. I selected the ranges arbitrarily. There was no science to it. This problem took me a little bit to re-read and understand what it was asking, but once you grasp it there's no challenge in just taking the few minutes to try more iterations than is even possible given the input bounds. It seems there are more interesting ways to determine what bounds are worth checking based on this reply I got on /g/, but I didn't even bother changing anything. Here's my rank for today if it matters at this point:
Day Time Rank Score Time Rank Score 17 01:50:30 5831 0 02:28:50 5861 0
First time I've gotten a rank this high in a while, which probably indicates that quite a few people have been filtered by now. By many definitions I'd be filtered as well, but I'm not giving up and I'm definitely going to finish the 2 that I've started. Day 16 in particular is one I'm having fun with.
It's been a bit since I updated this, and that's because I'm days behind. I'm probably not going to be able to finish before Christmas. Still, I start on every new one when they come out because it's fun, and I can get a head start in writing out pseudo-code or thinking through a problem or parsing the input to make the problem easier to come back to when I catch up.
After staring at today's problem for a while I could not think of any way to define the rules in a programmatic way, so I started looking for consistencies by moving the letters around by hand. Before too long it was pretty clear that this would not actually be a difficult one to do entirely by hand without code. Part 1 took me longer to figure out and a little trial-and-error (I had one incorrect answer), but part 2 somehow I got on my first try. It ended up being the case that prioritizing C and D to hit exactly their best case scenarios and move any others around them accordingly was the easiest method. My work is shown as I wrote it here, but I won't be pasting it in this post because it's so long. Apparently my input was relatively easy, which is unfortunate if that's true that people had different difficulty input to a problem.
--------Part 1-------- --------Part 2-------- Day Time Rank Score Time Rank Score 23 03:23:51 2987 0 04:20:57 1687 0
Kinda funny this ended up being my best part 2 rank from the whole month.
UPDATE (Dec 4): I starting making a calendar on /g/ since no one else had started a very good one yet. Not sure if I'll follow it through, but hoping other anons use it as a template.
UPDATE (Dec 27): I didn't finish the calendar, because it was never my intention to make OC for each day, but rather to curate the OC posted in the thread into a calendar. Since no one was really making any, and what was being made wasn't great (my own included), it just didn't get finished. Hopefully someone else takes the reins next year. I only did this year because no one else was as I had said before. I'll do it again if no one else is, but it's kind of stressful to deal with because most people in the threads just end up complaining and arguing about the content anyway. I remember there was a lot of drama in 2020 about it which I was trying to avoid.
The month ending is bittersweet, because I really enjoy "showtime" each night and the hectic push for solving the problem each day. The issue is, I really suck at this! As expected, I was beginning to really struggle half-way through the month due to lacking a lot of fundamental skills needed for doing the later problems. The difficulty progression this year felt quite weird as it went from consistently easy (but still time consuming for me personally) problems to tedious and difficult problems abruptly towards the end of the month. Then there would randomly be a day like 17 and 23 that were uncharacteristically easy before going back to difficult the next day.
Something I've discovered is that once I get behind at all there's a good chance I won't catch up. This month seriously impacted my ability to sleep, and I have been constantly sleep deprived. I need to make sure I can do each problem in a single day or else falling behind and getting to overwhelmed to catch up is inevitable. My biggest goal for AoC next year is simple: study and practice enough to be able to do easier challenges in about/under an hour, and more difficult challenges in about/under two hours. This should be adequate for not destroying my ability to sleep for the whole month while not being unrealistic.
Part of my self-study routine over the next year is going to include topics that AoC has highlighted my failure to be able to do. There's two kinds of problems that can be described in that way:
what I consider to be fundamental skills and problem solving ability that would include things like breaking down problems based on proofs, recognizing appropriate algorithm use cases, and basic math skills.
more specialized sub-topics like computational geometry, graphs, and dynamic programming that aren't necessarily broadly applicable skills but come up during AoC. I don't mind studying this stuff, but I really don't need to spend months going too deep into textbooks to thoroughly understand them. To my understanding, the AoC problems for these sort of things are pretty basic if you actually understand the theory behind them before hand.
The first category I intend on learning through the following books:
Doing Math with Python: this book hopefully will go over some math that I am currently unable/too uneducated to be able to do. I don't even have high school-level experience with math, so I am really starting from scratch here. I am competent at thinking through programming logic, so using a book that covers the topics I'm unfamiliar with but using a medium I'm more comfortable with seems ideal. It should also provide insight into math/scientific Python libraries/functions that I've never gone through before.
How to Prove It: I'm fascinated with the idea of learning proofs, because even if I don't fully understand the entire process of getting to a conclusion, having the ability to break down a programming challenge into its fundamental attributes seems like a key to problem solving. Even proofs on rudimentary things like numbers, counting, sets, and so on, seems highly beneficial to me.
Book of Proof: this one was initially recommended to me by someone on /g/, and I now own a copy of it so I'll probably try going through it to the extent I'll be able to as well. I'm interested in the more programmatic/structured approach described in the preface to "How to Prove It" and how it's appealing to compsci students directly. I'll try both resources and determine what I can get out of them.
Mathematical Notation: A Guide for Engineers and Scientists: I already purchased this guidebook recently to have on hand. It's nothing exciting, but my hope is that I'll be able to refer to it to better understand any mathematical notation I encounter that I don't know (which currently, is all of it).
For the second category I'm less sure what to do. My current plan is to just go through competitive programming/puzzle books instead of going deep in theory, because the topics are less applicable to what my core interests are, so I don't want to waste time learning them in depth just for a few AoC problems at the end of the year. My current ideas are this:
Algorithmic Thinking: as I said at the start of this post at the beginning of the month, I already started reading this one. I'd like to come back to it for the same reasons I already stated: it's C-based which is what I'm primarily focused on studying this year. Since it doesn't use libraries or any abstract built-in data structures (as in Python or C++), it provides a more fundamental insight into the qualities and implementation of what data structures and algorithms best apply to a given problem.
Guide to Competitive Programming: pretty self explanatory. The author of "Algorithmic Thinking" advocates that it's a good resource to follow his book up with.
Algorithmic Puzzles: is just one I found online, but haven't really looked into yet. Could be another similar resource if I wanted more puzzles to be guided through.
Additionally, some online resources I've been recommended for getting better at these algorithmic puzzles include Kattis, Rosalind's Algorithmic Heights and Bioinformatics Armory problems, Red Blob Games tutorials, and the resources given by betaveros in a blog post about AoC.
At this point, if I want a better education on algorithms then I can either turn to the legendary "Learning Algorithms" book, which given the knowledge obtained from the above resources, should be more approachable if I wanted. Some books Anons have recommended me or that I've found online and set aside include "Dynamic Programming and Optimal Control", "Dynamic Programming for Computing Contests", "3D Math Primer for Graphics and Game Development", and "Computational Geometry". I'm not currently planning on going through any of these necessarily, but are worth keeping in mind if I want to.
Dynamic programming and the use of recursion is one of the things I struggled with the most this month that I consider to be important to understand better than I do in particular.
My primary goal this year of doing the problems in C very quickly fell short, because for the first part of the month I considered figuring out how to interpret input to be more difficult than the problems themselves. As I learn C, which as I said will be my primary focus for 2022, I do want to be able to do challenges like this in it as well, but it become clear very quickly that I started off the month over-estimating my ability to do these challenges, so doing them in C on top of trying to do them at all was not going to happen, unfortunately.
Also kind of random, but some anon in the /aocg/ has inspired me to attempt to pick up Awk in my spare time next year, and if I do I might also do them in Awk as well. It would just be for fun, so there's a good chance I'll change my mind, but it's something I'm going to consider.
I still intend on coming back to problems I missed, and likewise I plan on doing some of the previous years too for practice. I don't plan on updating this post as I do, but my git repo will continue to be updated. I also plan on making a personalized Python library while I do the previous years so I can save time on some implementation details next year when going for speed. The source for that will also be in the git repo as I work on it. Updates to my study process will likewise not be in this post but in my "Path To Competence" post.
Hope anyone else reading this who did these challenges did a better job of it than me, and I look forward to trying again next year.