this post was submitted on 10 Dec 2023
24 points (96.2% liked)
Advent Of Code
770 readers
75 users here now
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.
AoC 2023
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 |
Rules/Guidelines
- Follow the programming.dev instance rules
- Keep all content related to advent of code in some way
- If what youre posting relates to a day, put in brackets the year and then day number in front of the post title (e.g. [2023 Day 10])
- When an event is running, keep solutions in the solution megathread to avoid the community getting spammed with posts
Relevant Communities
Relevant Links
Credits
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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.