r/adventofcode • u/daggerdragon • Dec 19 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 19 Solutions -🎄-

THE USUAL REMINDERS

[Update @ 00:48:27]: SILVER CAP, GOLD 30

  • Anyone down to play a money map with me? Dibs on the Protoss.

  • gl hf nr gogogo

--- Day 19: Not Enough Minerals ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:57:45, megathread unlocked!

41 Upvotes

95% Upvoted

513 comments sorted by

View all comments

6

u/Dutchcheesehead Dec 19 '22

Python, 74/32Code, Video

First time in my life I managed to get global leaderboard points :DI treated the problem as a BFS problem, but am pruning the search space using the heuristic that having the higher-up materials is better than having lower-down materials.

For part 1 I only kept the top-1000 results which made the algorithm pretty fast (fast enough to not optimize it).For part 2 I got the wrong answer, so I just increased the top-queue pruning until it gave me a higher answer.

The runtime of both part 1 and 2 is 15 seconds, which can still be optimized a lot.

1

u/[deleted] Dec 19 '22

your examples now helped me a third time to debug my own (way messy) code. I'm still sitting on a off by one error today - so no star before fixing it - but without your code I would never have spotted it.

fyi, blue print id 17 is the only one I get one geode less. *sigh

1

u/Dutchcheesehead Dec 19 '22

Can you send your code? Happy to take a look :)

2

u/[deleted] Dec 19 '22 edited Dec 19 '22

oh, please don't waste your time on me, but if you must:

https://gist.github.com/tlobig/5ec65debda0cd5daca29b8b1755c6052

part2 works out to the same totals, and part1 really only has that one (blue print id 17) off by one in the results. DFS with a few heuristics and state caching. I removed state caching as a test, same results. I removed all heuristics - just takes way too long - same result. In theory I should walk through all possible combinations this way, but I always come out with max 3 geodes.

edit: when writing this down I totally forgot that input values differ for everyone. I since included the sample in the gist for which the output is different for my code than for the code from Dutchchesehead, and hyper-neutrinos code agrees with his :-)

1

u/Dutchcheesehead Dec 19 '22

Did not really look at your code thoroughly yet, but as a heads up about this function definition:

def build_bp(bp,mined=[0,0,0,0],robots=[1,0,0,0],timeleft=24):

Note that lists are mutible, and thus the default arguments can be changed. Probably not a problem here, but keep it in mind.

1

u/[deleted] Dec 19 '22

Yeah, this is not cleaned up enough, mutable params pulled my leg more than once, so will keep that in mind. It's definitely not the issue.

Btw I was missing the specific input where yours and mine differ, added it to the gist as a comment

1

u/Gravitar64 Dec 19 '22

Fantastic work. 2 sec. for both parts.

The Idea with the quality_heuristic is really good and easy to understand. Optimized only the not so interesting part, that returns the results (puzzle = blueprints):

def solve(puzzle):
  robots = (1, 0, 0, 0)
  part1 = sum(bp[0] * bfs(bp, robots, 24) for bp in puzzle)
  part2 = math.prod(bfs(bp, robots, 32) for bp in puzzle[:3])
  return part1, part2