Everybody Codes day 17
I feel that the actual challenges here are “recognise a spanning tree” and “recognise a graph segmentation”. I mean, I could have implemented the algorithms, but they’re both in pathfinding
so [shrug].
I feel that the actual challenges here are “recognise a spanning tree” and “recognise a graph segmentation”. I mean, I could have implemented the algorithms, but they’re both in pathfinding
so [shrug].
The more I do these challenges, the more it’s “oh, it’s that thing again” rather than having to figure out a new thing.
Which is good in some ways, I suppose.
This 10 year celebration for AoC is not helping that from feeling a little tired because it’s every day.
I take your point, but to me that’s still an enjoyable form of problem solving, and I’m writing a fair bit of new code too.
Yeah, not 100% on the complaining side of this one. I’m more comfortable each time and I repetition is very valuable in the learning process.
Due to a lovely 80st birthday party at which I we got to discuss AdventOfCode and One Piece almost in the same sentence… I am a bit late with Day 13.
I am so bad at Math it is surprising I made it through uni. I knew and spent an hour switching around my github project so I could search for last year’s linear equation problem. I didn’t find it and it took me … ages to get the stupid formulas right only to be ridiculed by floating points… I eventually figured that one out, too and the switch to BigDecimal paid off nicely in part 2 At least I recognized the problem type…
What I really thought was funny was the late night message my friend send “I think it’s not A*” and other people, who have previously corrected me that I was incorrectly calling something a Dijkstra algorithm (everything that finds path is a Dijkstra-variant in my algorithm book) (the guy is really nice and wasn’t mean about it) (how much can I verge away from the orignal sentence and still make sense?), also apparently thought this was a graph problem when it obviously was not.
Hammer, nail anyone?
PS: my code
Let’s face it if Dijkstra didn’t get credited he was probably bored and gave someone else the core idea to do the work on.
(AoC day 13)
You probably could solve it with minimum cost pathfinding but I started thinking about that and it seemed as though it would be Hard.
I’ve done these before so I immediately built a “position after N cycles” method rather than incrementing individually. For part 2 I generated a few hundred bitmaps and spotted the “interesting horizontal” and “interesting vertical” repetitions, then intersected the integer solutions o those to get the frame number.
One could do it without images by looking for configurations with lots of adjacent cells, but it could have been an outline. Spotting the overlapping patterns seems to be the best bet.
I tried that. I have now made a 1000 bitmaps and videos. Everything is transposed… because my matrix class is a bit special.
But I am about to give up on this one. I want to have something other than coding on my week-end.
I originally thought, “I’ll just reuse my merging-regions code from day 12”. Then I thought, “what if it’s an inverted v-pattern, like ducks in flight”, so I panicked, posted a disappointed meme picture, and went to browse AoC on Reddit (which I usually don’t do) and ended up with a spoiler.
But I was thankful for it, because it helped me revise my original plan for success without having to go so far as rendering bitmaps. I just looked for contiguous regions of 30 or more tiles.
I imagine the point of the day was to generate thousands of bitmap images.
Yeah, I thought of that (after the fact!) but it might not have had that characteristic.
I heard you like pathfinding… Basically lots of what the pathfinding
crate calls dijkstra_all
, the minimum cost from a single start to every possible finish. Then part 2 does it from 2 starts, and part 3 does it from lots of starts. I should probably have turned that inside out (from each end point to all possible starts, because starts > ends) but then I’d have needed more fiddly result processing and it’s supper time soon.
Day15 Part 1: actually learning to make images from matrixes and creating videos with ffmpeg is very helpful debugging today… I could see that my robot was “cleaning” up the warehouse nicely and boxes were being eaten because I am making a stupid mistake in the recursion
Now if only I could make a PRETTY visualization
Nice to see a grid problem that isn’t pathfinding. For part 1 I optimised the actual move action away to three cell changes (where robot was, where robot will be, where end of line will be), but I had to throw that away for part 2. Then there was lots of edge case bitching and I bet it could be done better, but it works.
I genuinely enjoyed this one, start to finish. Maybe I should make a Sokoban clone after all.
Surprisingly, I didn’t model the individual tiles as classes. Maybe I should have.
This year I’m trying to avoid recursion (because AoC likes to break recursion limits; like a DM who is tired of every party having a character with dark vision, so there’s always a reason why dark vision doesn’t work)
Part 1 was sort of iterative but I went full queue-based iteration for the movement rules in part 2
Yes, I bulld a queue of “movers” and check the contents of each while still appending to it. This is probably a sin against Dijkstra.
Quite a classic AoC style problem really. Including “final part, do it an unreasonable number of times”. Which turns out to be “the whole state isn’t going to repeat in a sensible pass count, so build a transformation map and then a cycle table”. OK I guess, but not especially fun.
For Day 15.1 I build a recursive function and had to write a unit test because I am too lazy to think it through and now I see part 2 and am despair. this is just plain evil.