Advent of Code 2023 - Day 23

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

(Snap! Build Your Own Blocks)

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 …

  1. for speeding up the process? (e.g. an alternative for brute-force exhaustive search)
  2. 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.

IME the puzzles are (in general) designed so that Part 1s can be completed using brute-force methods but some Part2s are designed to take a long time to solve that way.

The puzzle setters want us to discover alternative algorithms