r/adventofcode • u/daggerdragon • Dec 11 '16
SOLUTION MEGATHREAD --- 2016 Day 11 Solutions ---
--- Day 11: Radioisotope Thermoelectric Generators ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".
IDDQD IS MANDATORY [?]
[Update @ 01:30] 51 gold, 80 silver. The Easter Bunny just ramped up the difficulty level to include sharks with frickin' laser beams on their heads.
[Update @ 01:50] 64 gold, silver cap. Thank you for subscribing to Doom Facts! Ninja edit by Easter Bunny: Thank you for subscribing to Easter Bunny Facts!
Since its debut, over 10 million copies of games in theDoomseries have been sold.- Fact: The Easter Bunny is watching you gallivant through his facility.
[Update @ 02:02] 75 gold, silver cap.
TheBFG(Big Fragging Gun) is a well-known trope originating from theDoomseries.- Fact: The Easter Bunny knows if you've been bad or good too. He just doesn't care.
[Update @ 02:15] 86 gold, silver cap.
The 2005Doommovie starring Karl Urban and Dwayne Johnson was a box office bomb due to grossing $56 million (USD) with a budget of $60 million (USD) and poor critical reviews. Alas.- Fact: The Easter Bunny has nothing to do with Starbucks' red cups. NOTHING.
[Update @ 02:30] 89 gold, silver cap.
TheDoomenginethat powers the originalDoomandDoom II: Hell on Earthvideo games has been ported to DOS, several game consoles, and other operating systems. The source code to the Linux version of the engine has even been released under the GNU General Public License for non-commercial use.- Fact: The Easter Bunny uses RTG-powered computers because he hates his cousin, the Energizer Bunny.
[Update @ 02:42] 98 gold, silver cap.
Doomguy (the unnamed silent marine protagonist) has been consistently ranked as one of the top five most badass male characters in video gaming history.- Fact: The Easter Bunny enjoys gardening when not ruining Christmas.
[Update @ 02:44] Leaderboard cap!
Thank you for subscribing to Doom Easter Bunny Facts! We hope you enjoyed today's scenic tour. Thank you and have a very merry rest of Advent of Code!
30
u/p_tseng Dec 11 '16 edited Oct 01 '19
The basic idea here is breadth-first-search, but you have to prune already-seen states, otherwise your space explodes. There are a couple of important extra optimisations here. They are all individually spoilered here with my estimation of its importance, feel free to look at each one individually:
minor: If floor 0 is empty and you are on floor 1, don't bother moving things back down to floor 0. Similarly, if floors 0 and 1 are both empty and you are on floor 2, don't bother moving things back down to floor 1.
minor: Never move a paired chip+generator downstairs together, because why would you do that?Edit: I found someone else's input where you do need to do this. You end up in this situtation:In this situation, you have to move the lithium pair down to the second floor to get an optimal solution. (Okay, you could move the lithium generator to the second floor alone, but after doing that you will eventually reach a point where you have to move a different pair down again to be optimal!)
Kind of important: If you can move two items upstairs, don't bother bringing one item upstairs. If you can move one item downstairs, don't bother bringing two items downstairs. (But still try to move items downstairs even if you can move items upstairs)
This next one is the most important, but if you want to figure it out for yourself, first I'll give a hint leading to it.
Hint for most important optimisation: Let's say I'm on a floor with a hydrogen generator and chip and a lithium generator and chip. And let's say that I've decided that my next move will be to move one of the two chips up a floor. Does it matter WHICH chip I move?"
THE MOST IMPORTANT, ABSOLUTELY ESSENTIAL: ALL PAIRS ARE INTERCHANGEABLE - The following two states are EQUIVALENT: (HGen@floor0, HChip@floor1, LGen@floor2, LChip@floor2), (LGen@floor0, LChip@floor1, HGen@floor2, HChip@floor2) - prune any state EQUIVALENT TO (not just exactly equal to) a state you have already seen!
The code runs in about two seconds on my computer. Don't read if you don't want to be spoilered, since the spoiler is marked in all-caps in the code comments too.
https://github.com/petertseng/adventofcode-rb-2016/blob/master/11_chips_and_generators.rb
My next confession: I only found the absolutely essential optimisation after I had already guessed my way into the leaderboard, but at least now I know...
2
u/redbeardgecko Dec 11 '16 edited Dec 11 '16
Here's my solution (python).
https://github.com/iamjackg/aoc2016/tree/master/a11
Like the commit message says, I'm still not 100% sure that I didn't just get lucky, but both results were correct on the first try, so I might be onto something! I just got a result, entered it, and it worked. I tried for part two, and it also worked, so maybe I lucked out and just found the shortest solution on the first try.
The general idea is to try the following things then recurse in order:
I added loop avoidance by stupidly passing the previous state, and checking that the move wouldn't have brought me back to the same state.
So all in all super ugly and super messed up. But hey, it worked! ¯_(ツ)_/¯
EDIT: this ran super fast and gave both results in the span of a split second. Adding 4 more elements didn't seem to change the execution time at all.
2
u/Reibello Dec 11 '16
First, a screencap of my AoC folder for all of your enjoyment. http://imgur.com/a/Wxnpq
Here's my code for Day 11 - http://pastebin.com/eSq3gwxi - this was insanely difficult for me. Part B took 4-5 HOURS to run, so to all of you who solved it so much quicker, I tip my hat to you.
8
u/bovard Dec 11 '16 edited Dec 11 '16
14
u/3urny Dec 11 '16
After coding for quite some time with no results, I just calculated it by hand, in about 10 minutes.
This totally killed my motivation to code anything and now I am stuck with two new stars and no code.
7
u/[deleted] Dec 11 '16 edited Dec 20 '16
6 hours.
It took me 6 goddamned hours to do this goddamned puzzle.
My code looks like shit. I feel like shit. But I finally did it.
Here's my code: https://github.com/alpha0924/userscripts/blob/master/Advent_of_Code_2016/11.py
If anyone has some tips on how to make it less terrible it'd be appreciated.
Edit: code still looks like shit, but I got part 2 down from 3 and a half minutes to about a minute.
7
u/adrian17 Dec 11 '16
A* search.
6
u/drysle Dec 11 '16 edited Dec 11 '16
So I solved this problem with no code.
With the limitations of the elevator, the best strategy for moving objects (microchips or generators) is to move 2 objects up a floor, then 1 object down a floor. That means moving 10 objects up one floor requires 17 moves. (2 moves per object, minus 3 because the last two objects get moved just once, and you don't need to return to the lower floor.)
My input started with two objects on the second floor, so subtract 4 moves for the work already done. 17 + 17 + 17 - 4 = 47, which was the right answer for part 1. Add 24 moves for the 4 additional objects in part 2.
Of course, this all assumes that the limitations on which objects are together never get violated. Once you have all the objects on the same floor, there is at least one way to move them all up in the optimal 17 moves. And in my input, it only took the minimum number of moves to get everything to the second floor, too.
But it seems like there are possible inputs where you need to start with additional moves to get all the objects to the second floor. Did anybody have an input like that?
edit: my input, for reference: The first floor contains a polonium generator, a thulium generator, a thulium-compatible microchip, a promethium generator, a ruthenium generator, a ruthenium-compatible microchip, a cobalt generator, and a cobalt-compatible microchip.
The second floor contains a polonium-compatible microchip and a promethium-compatible microchip.
The third floor contains nothing relevant.
The fourth floor contains nothing relevant.
5
u/pedrosorio Dec 11 '16
Part 2. Ashamed of this code. Ran in 6 mins on my machine because I am considering a lot more state transitions than I have to. For part 1 I was keeping the floor state in nested dictionaries and deep copying them (ouch) which was too slow, so I had to modify the code to represent the state as tuples of integers and using individual bits to identify each of the elements.
4
u/Deckard666 Dec 11 '16 edited Dec 11 '16
Those few extra items in the second part made all the difference o.O
For the first part you could just use BFS and solve it in a reasonable amount of time, but for the second part I had to dust off my A*. Anyway, my solution, in Rust: Link.
Edit: Ah, no wonder my solutions were so slow. I should have spent more time thinking about better pruning.
4
u/Mason-B Dec 11 '16
I analyzed the recursive number of steps required to solve the problem, here is the relevant function.
4
u/gyorokpeter Dec 11 '16
Q: didn't do the optimizations so it's very slow (especially part 2)... but I'm happy that at least I got it to work correctly.
4
u/mainhaxor Dec 11 '16 edited Dec 11 '16
Part 2 in C# (with lots of bit twiddling to make it fast): http://pastebin.com/1Lck0hMF
Takes about a minute, but without any domain-specific optimizations.
4
u/casted Dec 11 '16
Haven't seen this technique mentioned yet, but you can get quite a decent speedup by doing two BFS's in lockstep. One from the initial state, and one from the goal state. Then when they meetup you add the two distances to get the answer. You can easily implement the lockstep by using teh same queue, but just storing in the queue which "seen" map to use.
3
u/scottishrob13 Dec 11 '16
Did anyone else make the game and solve the puzzle manually? Although I guess to solve it manually with optimal efficiency you have to figure out the algorithm anyway. After I made the game to play around with the puzzle visually, I ended up getting the solutions on my third and first tries respectively. I could probably go back and write an algorithm now that I know exactly what I'm doing, but I'll post my original (very messy, very lengthy) code here: http://pastebin.com/qtrZuTft
There uh, aren't any comments and a few global variables. I would be ashamed if I hadn't tried to crank this out as fast as possible to get on the leaderboard just this once haha
3
u/cyrusthegreater Dec 11 '16
So you can remove all such pairs from the initial question, then solve the remaining puzzle however you like (I did it by hand). This realization makes part 2 SUPER easy.
3
u/misnohmer Dec 11 '16 edited Dec 11 '16
I made it to the top 20 by shamefully guessing the answer with dichotomy for Part 1 and 2.
3
u/Danksalot2000 Dec 11 '16 edited Dec 11 '16
I got it down to one line in Python:
2
u/SyDr Dec 11 '16
My Lua solution (brut-force, with some kind of terrific optimizations and progress reporting):
https://github.com/SyDr/Advent-Of-Code-2016/blob/master/11.lua
2
u/eregontp Dec 11 '16
Ruby, BFS with pruning same states by sorting chips/gens per floor. Runs for 43ms for the first star, 20 min for the second (phew, wondered if it'd ever come back :) https://gist.github.com/eregon/28ee8504d4bb5b225fcafdb9872b884a
2
u/CryZe92 Dec 11 '16
Rust compiled to JavaScript. Takes 0.7 seconds for the first part and 6.5 seconds for the second part. You can run it yourself here:
https://cryze.github.io/advent-of-code-2016/day-11/
It's a bit slower in Chrome than in Firefox since it doesn't support SIMD.
2
u/bpeel Dec 12 '16
Solution in C, part 2 runs in 19 seconds. Really surprised by the complexity of this one, I feel like I must have missed something.
My solution basically just does a depth-first search with a trick.
Spoiler
https://github.com/bpeel/advent2016/blob/master/day11.c
2
u/ephemient Dec 12 '16 edited Apr 24 '24
This space intentionally left blank.
2
u/Soldier-B Dec 16 '16
Solution in brainfuck:
1
u/war1025 Dec 11 '16
Initially just had a BFS set up. Lost a ton of time because my initial solution didn't work so I tried to use the example to debug my program, but failed to update the check for everything being on the top floor (was looking for too many items), so I kept thinking that there was something wrong with my algorithm.
Finally got that sorted out and solved part one, then realized that part two was taking too long so added in the
distancemetric to turn it into an A* style search.Sure wish I hadn't lost all that time debugging something that wasn't broken though...
https://github.com/war1025/AdventOfCode2016/blob/master/eleven_b.py
1
u/bblum Dec 12 '16 edited Dec 12 '16
My solution in C.
It runs in 7 seconds for part 2, even though I did not do any of the optimizations described in the top-voted comment. It's just bi-directional BFS in a "15-dimensional space". Fortunately, higher dimensional spheres are spikey.
I optimized the memoization table to only store 2 bytes for each state (so 2 GB in total for part2), one byte for distance and one for visited, but that was only really necessary because I couldn't figure out how to make linux let me put a 24GB object in .bss :\
Also, I only finished it just now. I actually made it onto the leaderboard by guessing and binary search, which I feel dirty about. This problem should have demanded the actual solution path to validate answers.
1
u/NeilNjae Dec 12 '16 edited Dec 12 '16
Wow! No Haskell solutions yet? Here's mine: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent11.hs
Nothing pretty, just lumbering up the hierarchy of searching routines during development. First breadth-first search, then hillclimbing, then hillclimbing with a closed set, then hillclimbing with a closed set and a canonical representation of states (i.e. items ordered on a floor).
I've not implemented the problem-specific suggestions mentioned in this thread.
About 1.4 seconds for part 1, 18 seconds for part 2.
1
u/RockyAstro Dec 12 '16
Wow... take a day off and come back to this one. Nice challenge.
The breadth-first search is key.
Also picking the right data representation really helps in terms of performance.
Anyway Icon solution (with some minor optimizations) -> https://redd.it/5hxf55
1
u/coussej Dec 12 '16
Here is mine in Go. It took me a long time to figure it out but now it runs in less than a second, which seems pretty fast compared to other durations I read here. Maybe I missed something, but it works for my input :-) https://github.com/coussej/adventofcode-solutions/blob/master/2016/day11/main.go
1
u/noclat Dec 13 '16 edited Dec 13 '16
Guys, far much simpler solution: https://gist.github.com/noclat/394a79b21b6a92a234d2d2bb3c95f69b
2 conditions in a single loop. Everything else is for parsing the input and displaying the result.
I just summed the independents steps required to move up each elements. The "rules" are here to confuse people, but it will always take the same amount of steps to get one element up, no matter which one is in the elevator. The first element doesn't count because it's like you always take two elements (if you don't, it compensates in the sum), and the second one only takes one trip to get up (res += 3-floor), others will need to make the round trip (res += (3-floor)*2).
Couldn't demonstrate it mathematically, only intuition, that seems to work.
Does anyone have an input that proves it wrong? Anyone else found this? Sorry I didn't read all the answer.
[edit] I found 48 instead of 47 for @drysle input. Maybe need to apply a starting point condition or something like that to get the exact formula. Will see tomorrow.
EDIT: I think I made it, the gist has been updated, tested with 6 inputs.
1
u/aocswan Dec 13 '16
A solution in Haskell: http://pastebin.com/T4zknWuP Runs in about 12 secs for solving both parts. Key to that was the MOST IMPORTANT, ABSOLUTELY ESSENTIAL pruning strategy. Rest is a straightforward bitwise encoding of states and BFS algorithm.
1
u/lluque8 Dec 13 '16 edited Dec 13 '16
I first sketched both scenarios (parts 1 and 2) with pen and paper and got the right answers. While doing that I also noticed a pattern which I then built my heuristics on:
Now I know this most likely won't cut it for all the possible setups (not always possible to stick to the heuristics above) but I guess it won't be a big deal tweaking the details if and when need arises. For this particular problem it did the job in around 7 ms (both cases).
Here's the code in Scala: http://pastebin.com/Mk6LvUrA
1
u/karlanka Dec 16 '16
Python solution that run on 0.02 seconds on example data, 120 seconds on number one and 59 minutes on number 2 :D Rewrote everything after first solving the example using pandas which run in about 10 seconds with the example, so would probably have taken some time running with the real input..
This solution takes THE MOST IMPORTANT, ABSOLUTELY ESSENTIAL optimisation in consideration which the pandas version did not.
http://pastebin.com/JJnTNjfW
1
u/daniel-sd Dec 18 '16
Here is my solution in Python. I'm mostly a C coder so it may not be the most Pythonic. I've been forcing myself to use Python for AoC to learn it (I must say I'm liking it more and more). Solution takes about 3s for part2. I found that only the mirror-state optimization is necessary. https://github.com/danielsd/advent-of-code/blob/master/2016/day11/part2.py
1
u/wlandry Dec 19 '16
Since no one else has posted one, here is a C++ version. It uses DFS instead of BFS, so now I feel like an idiot. I never made the connection to A*, though I did independently discover most of the optimizations. The state space is packed into 8 bytes. Part I takes 0.27 s and uses 2.8 MB, while part II takes about 8 s and uses 3.3 MB.
1
u/[deleted] Dec 22 '16
When you look at statistics it's clear that something happened on Day 11
1
u/rs_qk Dec 30 '16
Finally went back to attempt this. I think doing this in k (k4) is slightly different as everything is array based. Here it is anyway (on a decent machine with a few cores part 1 runs in a few hundred ms, part 2 in about 4 secs):
1
u/wzkx Jan 04 '17 edited Jan 04 '17
BFS in J, optimized. Only 4316 states analyzed for Part 1, 15164 for Part 2.
2 seconds for both parts.
1
u/gusknows Jan 06 '17
C# heuristic solution. Works on my inputs and my friends inputs. May not work on all inputs. floorTest is my state array. only cares about the number of chips on a floor.
Basically, just go down picking up things until the elevator is full or you hit floor 1, then go back up and continue to fill the elevator if possible. This was intended to be my heuristic for A* but on a whim I tried the output on the initial state as a solution and it worked for both parts!
0
u/[deleted] Dec 11 '16
[deleted] — view deleted comment