I’ve been working on AoC day 23 - it’s about finding the longest path through a forest without crossing or re-using any part of one’s path. Solving part 1 I found relatively easy: a recursive function leaving a trail that needs to be checked regularly to make sure no part of it is treaded upon.
See Part 1 sprite
Part 2 (same link, sprite = Part 2) looks really simple once you’ve solved part 1: there’s actually one less condition (limitation) to be checked. However, processing time appears to explode - with the small example puzzle it’s about 8 times that of Part 1, with the much larger “real” input data set it may be far worse (100 times? 1,000? even more?); and I haven’t yet found a way to estimate how much of the required processing has been done, so I really couldn’t say if a solution is going to be found within reasonable time. I stopped the process after some 12 hours of running.
What I already did, as an attempt to reduce processing time: check for collision with the trail (up to thousands of preceding steps!) only at junctions. Perhaps I should try to have the trail implemented as a dynamic array instead of a linked list. That’s all I can think of right now.
Any other suggestions …
- for speeding up the process? (e.g. an alternative for brute-force exhaustive search)
- for checking how much of the task has been completed?
P.S. a general observation on Advent of Code: I suspect the size of puzzle input was chosen such that e.g. efficiently coded Javascript programs will find a solution in reasonable time.Snap! however runs often much slower - except perhaps where the most time-consuming operations are performed by hyperblocks; alas not all problems can be solved using hyperblocks.