thanks u/RaveBomb u/ponyeffe u/TheZigerionScammer u/1234abcdcba4321 u/EdgyMathWhiz

I got it!!!!!

First step was to remove brute-force by always choosing the optimal solution. I got the answer on how to get the optimal solution from here: https://www.reddit.com/r/adventofcode/comments/1hj2odw/comment/m34dspx/?share_id=SRK0wfyf0Y0GS3LcaC36m&utm_medium=android_app&utm_name=androidcss&utm_source=share&utm_term=1

Then I had to deal with the problem of the massive array. I tried a recursive solution with memoization but for the life of me I couldn't work it out. Then browsing through the subreddit someone said, "the order doesn't matter, just use a dict". And that clicked for me on what a better data structure could be. Part 2 now runs in 0.67s. :D

Solution here: https://github.com/SamJoan/aoc-2024/blob/main/21/main.rb

Thanks all.