https://adventofcode.com/2023/day/3
Writeup of my solution: https://github.com/gustafe/aoc2023#day-3-gear-ratios
https://adventofcode.com/2023/day/5
Leaderboard completion time: 26m37s, so it's the toughest problem this year so far.
https://adventofcode.com/2023/day/6
Alternate spoiler name - for part 2
~~Do you remember highschool algebra?~~ Can you (or your compiler) remember highschool algebra fast enough to beat out a naïve implementation?
nice cleanser after yesterday
spoiler
it would have taken me longer to figure out the algebra than to just mush the inputs together and get the solution that way (16s runtime)
I have come up with a more horrifying way to solve Day 1 Part 1 involving C++ implementation defined behavior, but it requires launching two subprocesses for every test case so I'm not sure I have the motivation right now.
Proof of concept: https://www.animeprincess.net/blog/?p=60
https://adventofcode.com/2023/day/7
So far, my favorite puzzle. Challenging but fair. Also plays to Perl's strengths.
Leaderboard completion time: 16 minutes flat, so not a pushover.
https://adventofcode.com/2023/day/8
Not so easy at least for part two.
spoiler
Do you remember high school math, like lowest common multiple, part 2 electric boogaloo.
My solution: https://github.com/gustafe/aoc2023/blob/main/d09-Mirage-Maintenance.pl
discussion
What can I say. Shockingly simple.
I just literally followed the instructions, and got a solution in 20ms. This despite literally creating each intermediate array yet only using the ends. I'm sure I used way to much memory but you know? I'm using a $5/mo VPS for everything and unless I'm barking totally up the wrong tree I've never exceeded its memory limits.
On the subreddit I see people discussing recursion and "dynamic programming" (which is an empty signifier imho) but I really don't see the need, unless you wanna be "elegant"
spoiler
DP to me is when you use memoisation and sometimes recursion and you want to feel smarter about what you did.
I also struggle to think of the need for DP, even in a more “elegant” approach. Maybe if you wanted to do an O(n) memory solution instead of n^2, or something. Not saying this out of derision. I do like looking at elegant code, sometimes you learn something.
I feel like there’s an unreadable Perl one line solution to this problem, wanna give that a go, @gerikson?
spoiler
Part 2 only, but Part 1 is very similar.
#!/usr/bin/env jq -n -R -f
[
# For each line, get numbers eg: [ [1,2,3] ]
inputs / " " | map(tonumber) | [ . ] |
# Until latest row is all zeroes
until (.[-1] | [ .[] == 0] | all;
. += [
# Add next row, where for element(i) = prev(i+1) - prev(i)
[ .[-1][1:] , .[-1][0:-1] ] | transpose | map(.[0] - .[1])
]
)
# Get extrapolated previous element for first row
| [ .[][0] ] | reverse | reduce .[] as $i (0; $i - . )
]
# Output sum of extapolations for all lines
| add
I'm pretty sure you could make this one line and unreadable ^^.
Here's where I landed in dart
no comments
d9(bool s) {
print(getLines().fold(0, (p, e) {
int pre(List h, bool s) {
return h.every((e) => e == 0)
? 0
: (pre(List.generate(h.length - 1, (i) => h[i + 1] - h[i]), s)) *
(s ? -1 : 1) +
(s ? h.first : h.last);
}
return p + pre(stois(e), s);
}));
}
Now this is content
Starting a new comment thread for my solutions to 10-19. Double digits, baby! Code here: https://github.com/Fluxward/aoc2023/
a,b
part a: nothing to say here.
part b: Before diving into the discussion, I timed how long 1000 cycles takes to compute, and apparently, it would take 1643175 seconds or just over 19 days to compute 1 billion cycles naively. How fun!
So, how do you cut down that number? First, that number includes a sparse map representation, so you can tick that box off.
Second is intuiting that the result of performing a cycle is cyclical after a certain point. You can confirm this after you've debugged whatever implementation you have for performing cycles- run it a few times on the sample input and you'll find that the result has a cycle length of 7 after the second interaction.
Once you've got that figured out, it's a matter of implementing some kind of cycle detection and modular arithmetic to get the right answer without having to run 1000000000 cycles. For the record, mine took about 400 cycles to find the loop.
a,b
I took a very similar approach to parts a and b, with the difference that i was too lazy to do titling in each direction, and wanted to abuse regex so Instead i always titled up and rotated, which given my method of tilting up and rotating had some satisfying cancelling of transpose operations:
https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/14-b.jq
# Relevant portion
# oneCycle expects an array, of array of chars (3x3 eg: [[".","#","."],[".",".","."],["O",".","#"]])
def oneCycle:
# Tilt UP = T . MAP(scan) . T
# Rotate = T . MAP(reverse)
# Titl UP . Rotate = T . MAP(scan) . Map(reverse) | T . T = Identity
def tilt_up_rotate:
transpose # Gets subgroups # Within each group,
# starring with "#" # In order 1 "#", x "O", y "."
| map( ("#" + add) | [ scan("#[^#]*") | ["#", scan("O"), scan("\\.")] ] | add[1:])
| map(reverse)
;
# Tilt North, West, South, East
tilt_up_rotate | tilt_up_rotate | tilt_up_rotate | tilt_up_rotate
;
JQ does allow some nice sortcuts sometimes, again transpose is nice to have.
a,b, not much to say
The hardest part has finding the right dart ascii library to use (by default dart treats everything as UTF-16, which is horrible for this sort of thing) and the right data structure (linked hash map, which is a map that remembers insertion order.)
a,b
So, like many other problems from this year, this is one of those direct solution problems where there isn't much of a neat trick to getting the answer. You just have to implement the algorithm they specify and hope you can do it correctly.
a) I used a regex to do some parsing because I haven't looked at dart regex much and wanted to dip my toes a little.
I considered doing this "properly" with OO classes and subclasses for the different rules. I felt that it would be too difficult and just wrote something janky instead. In hindsight, this was probably the wrong choice, especially since grappling with all the nullable types I had in my single rule class became a little too complex for my melting brain (it is HOT in Australia right now; also my conjunctivae are infected from my sinus infection. So my current IQ is like down 40 IQ points from its normal value of probably -12)
b) There may have been a trick here to simplify the programming (not the processing). Again, I felt that directly implementing the specified algorithm was the only real way forward. In brief:
Because this is AOC, I assumed that the input would be nice and wouldn't have anything problematic like overlapping ranges, and I was right. I had a very stupid off by one error that took me a while to find as well.
The code I have up as of this comment is pretty long and boring, I might try clean it up later.
update: have cleaned up the code.
Replying in OP: Yeah, Lemmy punishes old threads/posts a bit too much for my taste ^^.
Good note for next year!
a,b
a. while you can brute force this one in time, one simple trick to make it faster is to treat the symbols as bits and interpret the grid as numbers. It then becomes a matter of locating the reflection point.
b. It's not much of a difference to solve b. The trick here is that if you did the bit stuff I suggested above, you'd quickly realise that a smudge interpreted as a binary number is a power of two. Finding a smudge is equivalent to if the bitwise XOR of two numbers is a power of 2, which can be done with some bitwise magic.
[Language: Perl]
https://github.com/gustafe/aoc2023/blob/main/d16-The-Floor-Will-Be-Lava.pl
It feels weird to kick one of these threads off, but hey, here we go.
Code as always: https://github.com/Fluxward/aoc2023/blob/main/20.dart
a,b
A
So following from yesterday where I was punished by not going full OO, I decided, hey, this is a problem in which I can do some OOP, so I did. This took very long to do but I regret nothing. If you look at my code, feel free to click your tongue and shake your head at every opportunity I missed to use a design pattern.
Anyway, after a slight snafu with misunderstanding the FF logic and not spotting that some modules can be dummy modules, it all just worked, and I got my answer.
B
This was a bit of a headscratcher, but the answer was surprisingly simple.
First, the answer. Here's how to do it:
Getting here was a bit weird. I hoped that I could just run the code from A and spit out the answer when rx went low, but as of time of writing I've been running it now on a separate machine for about an hour and still no result.
My next instinct was to simply work it out from pen and paper. I thought it might be possible (it probably is) but decided to at least experimentally see if the states of the modules connected to rx were cyclic first. I did, and that was enough for me to get to the answer.
My answer was about 230 trillion BPs, which, extrapolating on how long execution is taking on my other machine, might take just under 137 years to calculate naively. Fun!
Completed when waiting for the second leg of my Christmas holidays flight. (It was a long wait, can I blame jet-lag?).
Have a more compact implementation of LCM/GCD, something tells me it will come in handy In future editions. (I’ve also progressively been doing past years)
Starting this thread having only solved a.
A
Pretty straightforward. Could probably be done in a few lines with the right syntactic sugar.
B
This is some game of life thing that I've never implemented or seen an implementation of, so I am altogether lost.
My current code (https://github.com/Fluxward/aoc2023/blob/main/21.dart) has a memoisation based approach but my current ailments are preventing me from really thinking about this properly so I am bowing out until I have the wherewithal.
This is the hardest problem of the year so far, based on leaderboard completion times. I'm busy wrapping up work for this year, and looking for a new job, so this will have to be put on the TODO pile
Only solved by receving heavy hints from other's solution, and it still took me forever. By far the hardest this year.
Happy Holidays everyone. I’ve decided I am going to take a break from aoc to properly rest and recover from my mystery illness. Perhaps I will attempt solves again in the new year.
Happy holidays to you too! I decided this morning that I'm not gonna work myself up missing days, so they are on hold until after xmas for me!
Get well soon!
Happy holidays!
Sorry for the necropost: I have completed all the problems! One of them completely stumped me and I had to cheat. Not going to do a writeup unless requested :)
Intimidating at first, so I went shopping for christmas presents first, which engaged my brain juices.
In hindsight this is is searching for the shortest path in a graph, making sure that each square is actually two nodes, for when approached vertically or horizontally. My shcool days are distant now, and i wonder how far from optimal my implementation is ^^.
Part two was only a small edit from part one for me, and the code actually ran faster! from ~45s -> ~20s.
https://adventofcode.com/2023/day/12
Where a curse the fact I decided to use JQ and not a "real" programming language.
spoiler
Had to resort to memoization, but sadly JQ isn't mega well suited to that. I had to refactor my part 1 function, to make including the "state" at every function call possible. I wish it were as easy as a @cache decorator, but i guess this way i had fun (for an arbitrary definition of "fun")
Further cleaned up version: https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/12-b.jq
Also lost a fair amount of time not not noticing that the sequence should be joined with "?" not with "". (that'll teach me to always run on the example before the full input, when execution time is super long).
Execution time: 17m10s (without memoization a single row was taking multiple minutes, and there's 1000 rows ^^...)
EDIT: see massive improvement by running in parallel in reply.
A nice workaround to jq single threadedness, since this is maq reduce and safe to parallelize. 17m10s -> 20s !!!
Spoiler link to commit.
https://github.com/zogwarg/advent-of-code/commit/fef153411fe0bfe0e7d5f2d07da80bcaa18c952c
Not really spoilery details: Revolves around spawing mutiple jq instances and filtering the inputs bassed on a modulo of number of instances:
# Option to run in parallel using xargs
# Eg: ( seq 0 9 | \
# xargs -P 10 -n 1 ./2023/jq/12-b.jq input.txt --argjson s 10 --argjson i \
# ) | jq -s add
# Execution time 17m10s -> 20s
if $ARGS.named.s and $ARGS.named.i then #
[inputs] | to_entries[] | select(.key % $ARGS.named.s == $ARGS.named.i) | .value / " "
else
inputs / " "
end
I use JQ at work, and never really needed this, i guess this trick is nice to have under the belt just in case.
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts