this post was submitted on 16 Dec 2024
7 points (76.9% liked)
Advent Of Code
920 readers
42 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 2024
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. [2024 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
I tried to compartmentalize it. the search is on its own function, and while that
fill_in_dead_ends
function is extremely large, it is a lot of replicated code. match k case statement could just be removed. A lot of the code is extremely verbose and has an air of being "unrolled" for purposes of me just tweaking each part of the process individually to see what could be done. The entire large af match case all seemingly ended up being very similar code. I could condense it down a lot. however, I know doing so would impact performance unless plenty of time is spent on tweaking it. So unrolled copy pasta was good.The real shining star is the
find_next_dead_end
function because the regex before took 99% of the time of about ~300 ms seconds. Even with this fast iterative function, thefind_next_dead_end
still takes about 75% of the time for the entire thing to finish filling in dead ends. This is because as the search ran deeper into the string, it would start slowing down because it was like O(n*m) time complexity, where n in line width and m is line count being searched through until next match. My approach was to store the relative position for each search which conveniently was thecurr_row,curr_col
. Another aspect to reduce cost/time complexity on the logic that would make sure it filled in newly created dead-ends was to simply check if the current search for the next dead end was from the start after it finished checking the final line. Looking at the line by line profiler from iPython, the entire function spends most of the time at thewhile('.' in r[:first_loc]):
andfirst_loc = r[:first_loc].rindex('.')
which is funny because that is still fast at over 11k+ hits on the same line with only a 5-5.5 microsecond impact for each time it ran the lines.though I could likely remove that strange logic by moving it into the
find_next_dead_end
instead of having that strange if elif else statement in thefill_in_dead_ends
logic.there is so much possible to make it improved, but it was quick and dirty.
Now that I am thinking about it, there would be a way to make the regex faster by simply string slicing lines off the search, so that the regex doesn't spend time looking at the same start of string.