With day 14 part 2 I had parallelised my search to saturate every core before I realised that my search function had a bug. That being said, the important thing I learned was that synchronous functions fulfill protocols with async functions. Which makes sense, but I had thought I would have to async every Day class when I only actually had to do the one.
I'm surprised this works, even after knowing what the tree looks like. I wouldn't have thought that the points in the Christmas tree are any more compact than in a "random" point cloud.
My early programmatic approaches were to look for either:
- Highly symmetric frames.
- Frames with an unusually high count of rows sorted in increasing order.
Both seemed like the two things tree pictures have in common: trees are obviously symmetric, and typically pyramid shaped.
Still, neither approach worked: I assumed symmetry would be along the midpoint (since Part 1 was all about splitting the grid in quadrants), so the first approach had no chance of working. For the second one, there's apparently random frames that have a higher count of lines in increasing order than the christmas tree frame.
Even when treating Day 14 Part 2 as a "signal discovery" puzzle, with no upper bound in the number of frames, there's no definitive answer without manual inspection of the frame.
I believe the upper limit was given by the modulo nature of the bathroom: bathroom.width * bathroom.height.
Or I might just assumed this limit and got lucky. 
Hmm yeah youâre right. Since particles donât interact with each other, their period canât be greater than width*height iterations. So it was possible to think of an upper bound, limit the iteration count to that upper bound, and pick the most âcoherentâ result from that interval using that âcoherence estimatorâ, without any visual inspection. Cool!
I did something similar, but with a simpler heuristic: I assumed that the points in the image of the tree would be relatively dense, so I calculated the total number of adjacencies (robots right next to each other) for each time step, and reported the step where this value took its maximum on 1 ..< 101*103.
This is a dumber heuristic, but produces a really clear result (the desired step has 4x the adjacencies of any step before it).
1 Like
For day 15 part 2 I had to resort to looking at someone else's solution, printing the score for every iteration, then running diff -u my_result.txt real_result.txt to find the point of divergence to find the issue.
Turns out my robot was force pushing boxes connected to one blocked box and one unblocked box.
I was undoing the initial failure, but because my box moving function was recursive I wasn't undoing cascading moves from that point. In the end I just decided to make a copy of the layout in that case and operate on that.
I wrote a canMove(boxAt: ...) function that recursively checked all the tiles that would be affected by a push and returned false if any of the branches encountered a wall/#.
Then, if the check passed, the function that actually moved the boxes was free to assume that moving the boxes was safe, avoiding to have to undo any changes (that would have been even even messier than what I came up with).
Still, I ended up with very spaghetti-y looking code today 
Partially because I created separate enum types for the tile types in the Part 1 / Part 2, which led to a lot of copy-pasting of functions.
1 Like
I think what I really like most about AoC is actually the cleaning up of the janky code and the inefficient algorithms after the fact.
Just took Day 16 part 2 from ~5s down to ~0.1s primarily by changing from eagerly tracking sets of squares in the path while determining the best route(s), to instead only keeping breadcrumbs back to the previous square(s) in the current route and then following them all back up into a single set at the end.
2 Likes
This test case helped me find my problem with 15 pt 2. The folks on the reddit who post alternative test cases are a real help! The "solves testdata but not realdata" pain is real!
Haven't had time to fix it yet, but I know what it is!
In part 1 I just swapped the box I was touching with the first available space between me and the nearest wall in the right direction (if there was a space). That got way messier in part 2.
TIL: Sometimes you need to be a bit patient (Day 17):
1610698 395 [1, 1, 5, 5, 5, 3, 0]
12885584 396 [4, 1, 1, 5, 5, 5, 3, 0]
112810663 9726388 [3, 4, 1, 1, 5, 5, 5, 3, 0]
902485308 9726393 [0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
7219882466 9726396 [5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
57759059733 9726402 [7, 5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
462072477864 9726403 [3, 7, 5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
3696579822968 9726460 [1, 3, 7, 5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
29572638583749 9726466 [4, 1, 3, 7, 5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
236581108670061 9726536 [2, 4, 1, 3, 7, 5, 0, 3, 4, 1, 1, 5, 5, 5, 3, 0]
The second number shows a 'loop count'. Meaning that matching from the 8th to the 9th digit took 9725992. That was really unexpected for me.
I had the test running while I went and did something else. Lo and behold, when I come back I actually have an answer (and a passing test 
)
FWIW, you can directly compute the answer for part 2 if you analyze the program a bit; it's actually has the shortest running time of any part so far for me.
1 Like
Almost the shortest in lines of code too (my Day 1 and Day 3 are ever so slightly smaller). A really clever problem, I think.
Day 17 part 1 had me stumped, but not for the usual reasons. After fixing a bug with my division instructions, I just couldn't get the right answer. I checked with three different versions, and they all gave the same answer.
...I had read what do you get if you use commas to join the values it output into a single string as turning 1,2,3 to 123. Whoops!
1 Like
A bit 
For me Day 17 Part 2 was the hardest of any days, by almost an order of magnitude over any other day.
It doesn't help that I miscalculated at first how large the solution would be, so I spent a lot of time trying to speed up the brute force approach.
Me too. Even worse, I tried the input it with commas once and got a "wrong answer" (I guess I didn't copy the entire sequence or something), so I spent a bunch of time trying to find a bug that wasn't there
Not the first time I fail to read carefully though. I also spent quite a while trying to find a bug in the maze problem (Day 16?) the root of which was that when I read "the Reindeer starts facing East" I then put the start position facing to the left.
2 Likes
Commas. They'll get ya.
Day 17 Part 2 possible gotcha
I did not get so lucky when I let my first Part 2 solution run for awhile!
After retooling, some of the lowest numbers that looked promising ended up being dead ends. Bailing when finding the first and lowest match for a given program step won't work for all of the puzzle inputs!
1 Like
Lots of map questions this year!
How do people like storing/working with their maps for AoC?
- Transforming into nested arrays?
- Keeping as a single array/buffer and doing X,Y to index conversion?
- Do you have a point type?
- Dictionaries: <location,value> or <value,location>
- Do you leave the objects as String.Element or do you make enums? Something else?
- Is there a datatype in swift-collections (or elsewhere) that works out well for you over arrays or dictionaries?
Granted a lot of this depends on the question, but do folks have a go-to? Is it their go to because it's easy or performant? How does this differ from what your go-to would be for a "Real World" solution?
I'm trying a new-to-me way which is working almost exclusively with sets/set operators. Standard, unordered sets which has made for some hilarious magically-changing-answers which were a fantastic clue the logic was wrong. But "bounds checking" is a lot easier when if the point just isn't in the remaining pile, it cant be valid. Might be slow though.
(P.S. the ability to work with myDictionary.keys with non-mutating set operators without making a copy would be nice! Would it be hard?)
Is anyone using the shiny new possible "Vector" as underlying storage? Hows it going?
Yes, a point type can help a lot. Arrays can be good if you can preallocate. For unknown size you'll want to use a Dictionary as a sparse map. You could make something custom around a dictionary to track minimum and maximum points too.
One of Swift's biggest missing pieces for AoC is a performant graph type, as many mapping problems can be expressed as graphs. I've seen some Graph types but they lack either the necessary algorithms or just don't scale well enough.
Always integrate swift-collections and swift-algorithms, they can be useful, though they're not a full solution.
I've stopped doing AoC, as it was too time consuming, and Swift made it less fun since I spent most of my time trying to find the right collection type or algorithm that other languages already have, rather than solving the problem. And when you try to implement them manually they're always suboptimal, so you run into performance issues no one else has, and those are impossible to fix unless you really know what you're doing with Instruments traces.
I have a Grid type, that just uses nested arrays as its underlying storage.
There is a point type, which is also the index type for the Grid as a Collection. So you can access squares in the grid with grid[point] and also look at all points with grid.indices, etc.
Unmentioned in your questions: I also have a Direction type, which is just an enum, but enables walking in directions and turning clockwise/counter-clockwise etc, which are common AoC problem elements.
In about half the problems I leave the grid squares as just Character (String.Element) and in the more complicated ones I end up making the squares structs or enums. The Grid type is generic over its Elements (squares) with some handy shortcuts where Element == Character.
When you are doing path-finding, Djikstra's algorithm requires a Heap to do it in a performant way. I used to have my own Heap type, but these days I use swift-collections for it. Thus far I haven't needed any other datatype in swift-collections or elsewhere.
3 Likes
Is there a language you think gets a Graph type right? What makes it special?
Yes! Also a direction type!
My Djiksta-esque solution of the year uses Set<PathElement>.min() to fetch from the "queue." Yeah... it choked on the real data! (My weird self imposed compiling situation makes using swift-collections and swift-algorithms hard for this year)