22
❄️ - 2023 DAY 10 SOLUTIONS -❄️
(programming.dev)
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
Solution Threads
M | T | W | T | F | S | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 |
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
That's an interesting approach!
I wonder why it runs so slow, though, as far as I can tell the flooding code is just a BFS on the grid, so should be linear in number of cells?
With the fully expanded map for the actual input it ends up working a 420x420 tile grid, and it has to do both value lookups as well as mutations into that, alongside inclusion testing for the search array (which could probably be made cheaper by building it as a set). It ends up somewhat expensive simply on the number of tests.
The sample I posted the picture of runs in 0.07s wall time though.
Maybe you are adding the same point multiple times to to_visit. I don't know ruby but couldn't see a check for visited points before adding, and to_visit appears to be an array instead of set, which can store the same point multiple times.
There's a
next if [...] to_visit.include?(off_p)
, and I also only visit points that haven't been flood filled yet (next unless %w[. I].include? val
), so there shouldn't be any superfluous testing going on.Went back and did a quick test of thing, and yep, converting the to_visit array to a set pulls execution time down to ~600ms. But the code becomes much messier.
Going to move the mutation of the map down to the point where I pick a point for visitation instead, so I can re-use the check for already flooded tiles instead.