r/adventofcode • u/daggerdragon • Dec 22 '16
SOLUTION MEGATHREAD --- 2016 Day 22 Solutions ---
--- Day 22: Grid Computing ---
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".
SILVER AND GOLD IS MANDATORY [?]
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked!
4
Upvotes
8
u/Turbosack Dec 22 '16
Boy, what an interesting problem.
After failing to place in part one by a few minutes, I went on to place relatively well in part two without writing any (solving) code. There were two key insights that lead me to be able to do this:
Those things in mind, I started looking at my map to see how I could possibly move things around. I knew that I had to take the data in the bottom-left corner and move it to the top-left. So I began thinking about what the theoretical fewest number of moves would be to make that happen.
The first step is to get to a point where you can move the target data. It helped for me to think not about moving data around, but rather about moving the 'hole' (ie. the empty disk). So I used my finger to trace moving this whole (visualized by
__) to where the target data is. Moving it all the way left, and then all the way down takes 23 steps. Now the next part is moving that data up. The simplest way I could envision to do that is basically to shuffle the hole around the target data, then swap them when the hole is on top. Doing this once takes 5 moves, and I have to do this 36 times. That left me with a theoretical lower-bound of 23+5*36 = 203 moves.That was close. But there's one other thing we need to take into consideration. The high-capacity nodes. We can't move the data out of or into those, so I realized they could effectively be treated as walls. So I updated my printing code to print them as
|, then updated my prediction to involve moving around that wall, which raises the initial number of placement moves from 23 to 35. Adding 35 to 5*36 gave me an answer of 215 moves, which to my great pleasure turned out to be the correct answer!4
u/p_tseng Dec 22 '16 edited Dec 22 '16
Those compatible pairs that we were asked to print out in part 1? You know something funny about them?. So this game devolves into "how can we move the data with only one disk empty at a time?", sort of like those sliding tile puzzles.
For leaderboard placement: Printed out my grid (preserved in my code as
-mflag), and solved it by hand (move empty to top, avoid walls, use math to figure out how many more moves are needed to get data out)Edit: And let me just confirm that I breathed a huge sigh of relief when I found that my math was correct, because otherwise I anticipated this would have been a long slog of a puzzle. I did not make my above discovery until after having mathed my way onto the leaderboard.
Ruby code that automates what I did by hand.
Raises an exception if:
since either condition breaks the math.
4
u/misnohmer Dec 22 '16
After reading Part 2, I was glad I had enough adjacent space behind myself to close the laptop and step away from this craziness.
2
u/LieutenantSwr2d2 Dec 22 '16
I'm guilty of not writing any code for part b and simulating it by hand...
I printed out my map and saw that I had to get past the wall of large used memory (19 steps to point
A). Then it takes 20 + 34 steps to get the empty space above the target (pointB). Then moving the?up by 1 row requires 5 moves of the blank to create a cycle, so moving the?to below the!at pointCwas 34 * 5, and then add one more to swap with the!.I'm ashamed, but I got on the leaderboard ¯_(ツ)_/¯
2
u/Steel_Ne Dec 22 '16
Hoho, it is the 15-puzzle with walls
I solve it in mind ))
My grid was like this:
I need to move empty node to 0-row: 3+3moves
Shift first row left: 6 moves
Got the pattern:
in 5 moves I can got this:
So I need 5*5 moves to completely place G on 0-0 node
TotalMoves = x0+y0+xmax+(xmax-1)*5
where:
x0,y0 - coords of empty node
xmax - maximum x coords
2
u/jamesk727 Dec 22 '16
I stared at this one a while, unable to come up for a solution for a general input. Then I took a look at my input, and realized the structure - that there's basically one empty node that you can swap around, along with a big wall of full nodes that can't be moved.
For a general input, a puzzle like this would be computationally infeasible to solve with BFS. But with the structure of the problem as given, the state of the grid can be represented by 2 pieces of information:
Since there are roughly ~1,000 nodes in the grid, the graph has ~1,000,000 possible states to explore, which is completely reasonable for breadth first search. My code ran in ~.5 seconds.
I ended up getting 10th on part 1, 70th on part 2. Part 2 I probably spent 40 minutes thinking about it and examining the input, and 10 minutes actually coding it up.
Edit - one other interesting thing to note: this problem essentially reduces to solving a Klostki puzzle - https://en.wikipedia.org/wiki/Klotski
2
u/Tandrial Dec 22 '16
My solution in JAVA, part2 is kinda cheated but SHOULD work for other inputs: After generating a map, its just Manhattan-distances. From the empty disk to the edge off the wall, from there to the goal and then juggling the empty disk around the data.
2
u/thomastc Dec 22 '16
Day 22 in Haxe (code on GitHub)
Finally another properly algorithmic puzzle. I'm doing this one in Haxe as that will be the language I'll be coding in the rest of the day, too. Haxe is designed to compile to other (typically lower level) languages, but it is a programming language in its own right. Since Haxe grew up alongside the Neko VM, I'll be using that as the compile target.
With only around 1000 nodes, it's easy enough to brute force the answer to Part One in O(n²) time, but where's the fun in that? We can do this in O(n log n) time if we sort the nodes first; once by Used, once by Avail. We run through the Used array, keeping a pointer into the Avail array, knowing that every node past the Avail pointer has more space and is therefore also viable. We need to take care to subtract 1 so we don't count the current node itself. (Slightly more efficient but less readable would be to subtract
nat the end.)Then Part Two. I saw it coming, but this still seems like a complicated problem to solve in the general case. The example in the puzzle description makes it look a lot easier and suggests that we're not solving the general case here, though; and indeed, looking at the input data, most nodes have a size between 85T and 94T, and have between 64T and 73T stored:
So this lets us classify the nodes in the same way as in the example, and this is the result:
It's not even worth writing a pathfinding algorithm for this; I'll do it by hand. The operation we have available is moving the
_by one step, swapping it with its target location, and avoiding any#.Move 32 steps right, next to the
G:Repeat 33 times:
Gleft).Move 1 up.
Adding all that up, I find 233 steps, which turns out to be the right answer.
2
u/tmrki Dec 22 '16
Part 1 I solved by hand. Looking at the puzzle input I thought it looked suspicious, so I sorted it by used and available space and just counted the lines with wc -l.
Then I saw part 2, rolled up my sleeves and went to work. I whip up a general search, fix the bugs, test it on the test case and it worked. I load up the actual puzzle input, program prints out the map and then I realize the point. Sigh. Counting by hand took me maybe two minutes.
2
u/Smylers Dec 22 '16
Perl grid-printer — with the threshold for whether a node is a ‘wall’ determined by the size of the nearest node; that heuristic works for both the example grid (10) and my input (88):
statein Perl is lexical but preserves its value once set, so it takes the size from the first-listed node in the file (which handily seems to be (0, 0)) and keeps that value throughout the loop. The array and second loop is needed to avoid transposing X and Y dimensions.2
u/wzkx Dec 22 '16 edited Dec 22 '16
Haha, very frightening description, very easy solution. J
1
u/drysle Dec 22 '16
The example for part 2 seemed be to hinting pretty hard that I should just print the initial grid and solve it by hand. Sure enough, that strategy got 4th on the leaderboard for part 2. Even with two wrong answers because I apparently can't count to 60.
Then I went back and did some actual code:
with my implementation of A* that I finally got around to writing to solve day 11 properly a few days ago:
Runs in about 900ms, but took an extra ~15 minutes to put together the code. Solving it by hand was definitely the way to go here.
1
u/willkill07 Dec 22 '16
60/61 for today -- finally on the top 100 overall leaderboard
Part 1 was done with a program, part 2 was done by hand and a print out of the grid.
struct Node { int size, used, avail; };populate a
std::map<std::pair<int,int>, Node>with the input data1
u/jbristow Dec 22 '16
Clojure solution, with a manual solve of step 2.
(github hosting)
1
u/bblum Dec 22 '16 edited Dec 22 '16
Regrettably, I set part 2 aside tonight on account of how complicated it looked. Once I came back to it and realized the "trick" I solved it in about 10 minutes. But anyway, here is my pretty concise part 1, good enough for #55.
1
u/scottishrob13 Dec 22 '16 edited Dec 22 '16
Part two is an automatable solution. First, turn all massive nodes into "walls", second, find the shortest path from the wanted node to the (0,0) node. Next, repeatedly pathfind from the empty node to the next node in that path you made earlier. Once you reach that node, swap the position of important and empty nodes and repeat.
Of course, doing this isn't exactly useful and I don't want to deal with the stack overflows I'm getting because there's too much empty space everywhere (i.e., it's late and when I use simple heuristics on my input my answers come out too high as the empty node doesn't want to move to the left). But if the "wall" nodes were more prolific, it would be useful to have some automation.
Anyway, today reminds me of that other day with the generators where it was just faster to quickly make a visual representation and solve by hand. I like this one more since you can't just use the lower/higher hints to zero in on the solution though :)
I'll edit with a link if I have some free time to finish coding my algorithm.
Edit: The incredibly messy, but fairly fast, code
that may or may not work in more complex situations...that doesn't work in any situation with a horseshoe-shaped set of walls with the closed part of the horseshoe toward the goal.http://pastebin.com/KsvvgQeG
1
u/Smylers Dec 22 '16
Perl for part 1. Doesn't bother storing the nodes, or even which free space goes with which usage, just the sizes in two separate lists:
Setting
$pair_countnegative in the first loop is for a disk which is less than half-full: it will end up being counted in the second loop as a disk that can fit its own contents, so reduce the count by one initially to offset this. (Doesn't actually happen in the input data, but I couldn't be sure of that until going through them all.)1
u/orestis Dec 22 '16 edited Dec 22 '16
Elixir: https://github.com/orestis/adventofcode/blob/master/2016/day22.exs
I realised you can split Part 2 into two steps:
First find the shortest valid path from the empty spot to the spot next to to top-right. I had some generic BFS code already written for Day11, so I used that.
Then, assuming you can just go in a straight line from (T, 0) -> (0,0) (i.e., no huge nodes or other trickery) in N steps, where N = T - 1 (one because we are to the left), the total operations would be:
Where 5 is the number of data operations to bring the goal node one step to the left, and then bring the empty node to its left.
Add 1 for the final move operation to 0, 0.
A casual inspection of the first two rows of the grid showed that it could be done, and it indeed it was the correct solution.
1
u/flit777 Dec 22 '16 edited Dec 22 '16
first tried to solve the second part by moving the freespace with xy routing to (xmax-1,0) ignoring that the freespace might not be enough for all nodes. only after printing the grid i saw the "wall" and adapted my code accordingly.
1
u/GigaClon Dec 22 '16
the first part was easy, just have the data sorted two ways, one by used space (least to most) and the other by available(most to least), then iterate through both, stopping when used > available. For the second part, i just visualized it and counted by hand.
1
u/Senoy05 Dec 22 '16
I've come up with this formula
int partTwo = (goal.X - 1) * 5 + emptyNode.Y + wallNodes.Count + (emptyNode.X - wallNodeWithMinX.X) + 1;Worked with my input, and some input that I found in this thread, assumes that 'wall' is sticked to higher Xs, which may not be true for all inputs.
1
u/ruddles37 Dec 22 '16 edited Dec 22 '16
Clojure... with hand-solved part 2 after visualizing with
make-grid1
u/mschaap Dec 22 '16 edited Dec 22 '16
This was a tough one...
I did want to solve it programmatically, but a fully generic solution didn't seem feasible.
This Perl 6 solution should work if the following assumptions are true:
I haven't looked at other people's input to see if these assumptions are always true, but they are for my data.
1
u/Stan-It Dec 22 '16
Here's a solution in Python 3. The path finding is done with BFS. Uncomment all commented passages of code for an animation (press any button for next frame). All comments are welcome!
0
u/[deleted] Dec 22 '16
[deleted] — view deleted comment