rule 5: one code enters, 7 codes leave
NotAwfulTech
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
okay yeah so
p1 part 1 submitted, runs fine. part 2 says "wrong answer for you but right for someone else". doing a debug-print-everything run on the intermediate stages of the data after my regex all seems correct, but it's also 23h50 and it's been a looooong week. so I guess I'll take a look a fresh look at that one in the morning over coffee
part1, badly:
spoiler
import re
pattern = '\d'
cmp = re.compile(pattern)
# extremely lazy, of the ungood kind
datapath = 'data'
lines = open(datapath, 'r').read().split('\n')
candidates = []
values = []
for l in lines:
if l != '':
r = cmp.findall(l)
candidates.append(r)
values.append(int(''.join([r[0], r[-1]])))
print(candidates)
print(values)
print(sum(values))
(I really wasn't kidding about the badly)
part2:
spoiler
missed the eightwo
case
changes:
mapping = {...} # name/int pairs
pattern = f'(?=(\d|{"|".join(mapping.keys())}))'
lines = open(datapath, 'r').read().split('\n').remove('')
values = []
for l in lines:
r = cmp.findall(l)
equivs = [str(mapping.get(x, x)) for x in r]
head, tail = [equivs[0], equivs[-1]]
values.append(int(f"{head}{tail}"))
print(sum(values))
Day 7: Camel Cards
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.
Day 3: Gear Ratios
https://adventofcode.com/2023/day/3
Writeup of my solution: https://github.com/gustafe/aoc2023#day-3-gear-ratios
Starting a new comment thread for my solutions to 10-19. Double digits, baby! Code here: https://github.com/Fluxward/aoc2023/
- I have contracted some kind of sinus infection, so rn I have a -20 IQ debuff.
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, 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.)
- After this problem, I will create a new reply in the OP if it is not there already, and will discuss under that thread.
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:
- Start with an "open" set containing a part with 4 ranges from [1, 4001) and an "accepted" set that is empty.
- Start at the workflow "in"
- For each rule in the current workflow:
- If the rule accepts part of the ranges in the open set, remember those ranges in a closed set and remove them from the open set.
- Remove anything the rule rejects from the open set.
- If the rule redirects to a different workflow W, split off the applicable ranges and recurse at 3 with the current workflow as W.
- Keep in the open set anything the rule doesn't consider.
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!
11
a,b
a:
So, I've been in the habit of skipping the flavour text and glossing over the prompt. This time, it hurt me badly.
I read the problem as follows: for N galaxies, find N/2 pairings such that the sum of distances is minimal.
At this point, I was like, wow, the difficulty has ramped up. A DP? That will probably run out of memory with most approaches, requiring a BitSet. I dove in, eager to implement a janky data structure to solve this humdinger.
I wrote the whole damn thing. The bitset, the DP, everything. I ran the code, and WOAH, that number was much smaller than the sample answer. I reread the prompt and realised I had it all wrong.
It wasn't all for naught, though. A lot of the convenience stuff I'd written was fine. Also, I implemented a sparse parser, which helped for b.
b: I was hoping they were asking for what I had accidentally implemented for a. My hopes were squandered.
Anyway, this was pretty trivial with a sparse representation of the galaxies.
17, We’re in the back third now, folks!
a, b
A and B were roughly the same difficulty.
So in my first year in university, in my intro DSA class, we learned A*. Have I learned any other ways to search since? Not really. So I used A* here.
It took way longer than it should have to solve, which I blame on my ongoing illness. The main sticking point was that I implemented a class to represent the search state, and since I was going to use it as a key to a map, I implemented a hashcode for it. The rest of the A* code freely flowed from my brain (really the wikipedia pseudocode).
Cue like 40 mins plus of wondering how the test input was searching over millions of states, wondering if I’d fucked up the A* implementation, wondering if the problem was too big for A*, and wondering if it was finally time to take a days break from all the aoc nonsense.
Anyway at some point I realised I forgot to implement the corresponding equals method to my hashcode. Once I had that my code ran in seconds and everything was fine. This sickness is the worst!!!
10!
a, b
a was relatively straightforward - again, an implementation test.
b was interesting- luckily, I remembered how to test if a point lives inside a curve. The line-crossing count algorithm was a little tricky to write from scratch, but I finally got there. Also, I screwed up for like an hour when I didn't realise you were supposed to count junk pipes as part of the territory. Code wise it got messy, and I've thrown something up on my github, but might try clean it up a little later.
Update: I've cleaned up my code and made it "dartier" i.e. I use more neat dart syntactic sugar at the cost of readability.
16
So, as I've been doing the AoC things, I've been creating small libraries of convenience functions to reuse, hopefully. This time, I reused some things I wrote for problem 10, which was vindicating.
a. was a fun coding exercise. Not much more to say.
b. I lucked out by making a recursive traversal function for a), which let me specify the entry and direction of where my traversal would start. Besides that, similar to a., this was a fun coding exercise. I was surprised that my code (which just ran the function from a) on every edge tile) It only took 2s to run; I thought I might need to memoize some of the results.
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!
Day 6: Wait For It
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)
Day 8: Haunted Wasteland
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.
Day 5: If You Give A Seed A Fertilizer
https://adventofcode.com/2023/day/5
Leaderboard completion time: 26m37s, so it's the toughest problem this year so far.
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
Day 16: The Floor Will Be Lava
[Language: Perl]
https://github.com/gustafe/aoc2023/blob/main/d16-The-Floor-Will-Be-Lava.pl
Day 20: Pulse Propagation
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:
- Look for the "rx" module in your input.
- If the module that outputs to rx is a conjunction, keep track of how many button presses it takes for each input of the conjunction to change. The answer is the LCM of all those numbers.
- If the module is a FF, you can also work backwards to get it, but this was not my input so I didn't need to try this.
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)