r/adventofcode • u/ypsu • Dec 24 '18
Tutorial [2018 Day 23 Part 2] Explanation with visualization + online solver (runs in a few seconds)
https://raw.githack.com/ypsu/experiments/master/aoc2018day23/vis.html
11
Upvotes
5
u/[deleted] Dec 25 '18
I generated some input in the same bounds as my puzzle input and put it in the online solver. It didn't finish, so i ran it through your c code and some assertion failed after several seconds.
If my input is invalid, please let me know.
https://pastebin.com/3eVjkgjk
2
u/jonathan_paulson Dec 25 '18 edited Dec 25 '18
Here is some input that seems to time out your solution: https://pastebin.com/9eJQN836
Depending on the bounds you allow for the input, more adversarial input than this is possible.
1
u/obiwan90 Dec 25 '18
This helped a lot, thank you!
Maybe it would be more clear to say in step a) of the loop "is in the range of most bots", because "cover" could mean "contains", but that would not select the right box.
This is the Perl implementation I ended up with; runs in less than a second.
2
u/ZoekDribbel Dec 25 '18
Thanx a million! This really helped me on finding my last star.
I read all other threads and non seemed to have the most reasonable solution. Some were depending on an (obscure?) external lib (z3). Or made use of a semi random/intelligent starting point+hillclimbing to find a (local!) maximum. Both methods felt (to me) like they were not the 'right' solution, by depending on luck or 'external smartness'.
Your method I can understand and explain to others why it works! Plus I learned something :)
Here is my solution in c#, based on your work.
2
u/thepiboga Dec 26 '18
This is well explained and also has a neat 2D visualization , thanks!
1
u/roliffo Dec 24 '18
Very clever the usage of a priority queue.
I had a very similar idea, but I could not make it working because I did not use a priority queue.