My Advent of Code 2021 🎄 solutions.
- NB: Using
elsein acasestatement can save some debugging time if the input gets messed up
- Sorting the input actually seems like a good idea. Should give it a try!
- Used spaceship operator to turn a number into +1/0/-1
- Reused self-creating Hash from last year
- Looking into Wikipedia Line article was helpful
- Alternative approach: calculate the result for each input entry; use Hash to cache the result for the same age
- Used arithmetic series formula
- However, there's a better approach: the optimal position is the median (the value with the lowest absolute distance to the data) in part 1, and the mean in part 2
- Presenting the digits as arrays of segments made it easy to derive digits from each other, but it was still manual work
- Would be interesting to make a universal solution (constaint solver?)
- Used what I guess is called flood fill algorithm
- Got tripped by Ruby's negative array indices (expected
nil) - And (more than once) by counting the previously visited cells in a recursive walkaround
- Remembered that using [x, y] for a hash containing grid elements is often more convenient than [x][y]
- That day I discovered Dijkstra's algorithm 🧐
- However, the basic version wasn't any good for the 2nd part (250k cells). An optimization also described in the Wikipedia article (adding neighbour cells into the queue as we progress and removing them after the visit) helped.
- Haven't tried A*, maybe for smth else!
- Used a class to simplify the position tracking
- TODO: rewrite using Ruby's
StringScannerclass, check out formal notation and theory on parsers
- http://twocentstudios.com/2016/08/16/calculating-the-area-of-multiple-intersecting-rectangles-with-swift/
- For the recursive solution, the order in which we process cubes is important
- Run
bundle installto install dependencies ruby day-<number>.rb- The input data is stored in
/inputsdirectory. If there's no input and the session cookie is provided through the SESSION env var — the framework will fetch the input from the AoC website on the first run.
Thanks to @Aquaj for the handy Ruby framework!