There are definitely cleaner and faster ways to do 15 than what I did, and that was already one algorithm optimisation up from the naïve approach.
3 Likes
My partner found the last bug by just staring at the numbers… why can’t I see that this requires BigInteger?
I am reasonably happy with my optimization part1 now runs in 12ms and part2 in 1869ms, it’s a mathy solution and I for one like it when I can find a formula.
I’ve pushed my code to github. Because I’ve been meaning to play around with github anyway. So if you feel like taking a peek at some wildly chaotic java…
3 Likes
I’ve been doing all my AoC solutions in a folder where I have a number of cloned git repos, mainly because it seemed like a sensible place to put them rather than any intent to push them. Maybe I will at some point.
2 Likes
mine lives in a scratch file in my work IntelliJ… I am just copying it over to the repo for save-keeping.
2 Likes
[embarrassed look]
~/projects/adventofcode2022/
with scripts to create the day’s directory and drop in a PostScript, or Rust, blank template with just the read-input-file code.
3 Likes
Wait why? I am doing it all in a single file and manually putting the input in my Downloads directory oO… and then I manually copy the contents of the scratch to the file in the repository when I want to push to github. 
2 Likes
“Manually” is a dirty word for me. The computer exists to do the boring stuff at my command so that I can spend more time doing the fun stuff.
2 Likes
I leave the last fews days of AoC open in Notepad++ so I can crib any bits I need.
3 Likes
Day 14 part 1 was probably the quickest I’ve gone from getting the sample input working to getting the full input working. It did take me a while to get it working for the sample input though.
For part 2, I think I know the shortcut, I just need to get it working 
2 Likes
After a break for lunch I got it. The code wasn’t very neat but I’m pretty happy with the solution.
For part 2 I really wanted to avoid enlarging the board more than adding the extra lines at the bottom. Fortunately my “drop” function allowed me to drop sand from an arbitrary location so all I needed to do was figure out the new locations to drop sand on the left and right edges of the board. The rest was just maths.
2 Likes
Day 15, my solution worked nicely on the sample input then ran out of memory on the real input.
Probably shouldn’t have been trying to visualise it. Reworked my solution with what I think is the shortcut and while it comes up with the correct answer for the sample input, it doesn’t for the real input.
Time for a cuppa.
Edit: Found an off by one issue but that hasn’t got me the right answer.
Edit: The worked example showed the search area increasing but I chose to ignore it. That was a mistake. Got part 1 done now, doesn’t exactly run quickly though. ~132 seconds. I think I know how to optimise it, but not sure if I’m bothered.
3 Likes
Day 16: this was the first one at which I thought about giving up; it just became a slog.
But the major insight was the realisation that I didn’t care about moves that didn’t end in a valve opening, so I could build a distance map between the useful valves (start point and the ones with flow > 0), for which I should probably have used Floyd-Warshall but I still had Dijkstra in my head so I did that repeatedly, then use a depth-first search with exit on time constraint to find the highest result.
For part 2, instead of keeping the single highest value, I kept the highest for each path (defined as an unordered collection of useful valves and therefore keyed by bitmap), then searched out the two non-intersecting bitmaps with highest joint total.
1 Like
For day 15 part 2, I suspect I’m going to be here for a while without any more optimisation…
3 Likes
I got the answer for part 2, it took 6 minutes to come out.
My approach was to
iterate over the cells in a particular row (within the boundary). For each cell I’d determine whether I was in the field of regard of any of the sensors. If I was, I’d skip forward as many cells as required to get out of the field of regard.
Is there something I missed?
On reflection I might have maximised the field of regard for a particular cell, rather than just moving out of the field of regard of the first sensor that overlapped.
1 Like
I am sitting here, for Day 16 and I had very little time today (because it is Friday and I don’t work Fridays so it’s chores day). So it is 10:30 pm and I have barely started my mis-attempts.
3 Likes
(Day 15 part 2) I took a slightly different approach, which I suspect may reduce to the same thing:
For each sensor, build its range on the row as an interval [a, b] constrained by the boundary. Collapse all the intervals into as few as possible. If I have two or more, that’s the row with the answer.
I don’t know whether there’s a way to avoid “for each row” though.
3 Likes
Day 15 My optimization was to try and avoid having to look at every cell. Rather find a way to look at a bunch of cells at the same time. As I said I recycled code from Day 4.
3 Likes
I’ve laid the groundwork for Day 16 part 1, i.e. the structures and debugging. I’ll grasp the algorithm tomorrow.
Hopefully I’ll be able to catch up this weekend before I disappear for Xmas next week. The last bunch of days are probably going to have to wait until I’m back.
2 Likes
That is exactly what I did and I don’t think the for each row is avoidable. 2 seconds mine took which is lightning fast compared to what the subreddit reported. I wish I could math my way out of today. I don’t want to figure out how to abstract my algorithm from Day 12 to fit for today. I am right now trying to shrink the problem by optimizing my data structure. It’s not like there are a lot of “working valves” in the data. But I am not opimistic.
3 Likes