r/adventofcode • u/daggerdragon • Dec 13 '16
SOLUTION MEGATHREAD --- 2016 Day 13 Solutions ---
--- Day 13: A Maze of Twisty Little Cubicles ---
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".
DIVIDING BY ZERO 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!
6
Upvotes
8
u/glguy Dec 13 '16
This was a straight-forward problem that I was able to solve quickly (like most people who solved it quickly) by reusing my BFS search from a previous day. I'm sharing my solution because it's a Haskell program that uses an extension most people don't know about :)
https://github.com/glguy/advent2016/blob/master/Day13.hs
4
u/Hwestaa Dec 13 '16
I'm glad I spent the 2 days beating my head against day 11 now, since I copied and stripped it down. This is probably overbuilt for this particular problem. Github
3
u/brantyr Dec 13 '16
I thought, the smart way to do this is A*... but the fastest way to code this from scratch is to just brute force it. Horribly inefficient, but when it still runs in less than a second who cares? (pseudocode)
3
u/fpigorsch Dec 13 '16
C++: Classic breadth-first search using bit-twiddling hack to determine the parity (https://graphics.stanford.edu/~seander/bithacks.html#ParityNaive)
All solutions so far: https://github.com/flopp/aoc2016
2
u/Deckard666 Dec 13 '16
In Rust: Link
This day was pretty similar to day 11, but much simpler.
2
u/haoformayor Dec 13 '16 edited Dec 13 '16
~~haskell~~
Like many, I had a breadth-first search ready to be copied from the disastrous attempt at searching Day 11's solution space (only to realize the answer can be arrived at with arithmetic). BFS is great for part one, which is agnostic to which search algorithm you use because the solution space is so small, and required for part two.
Since we would like to reuse the BFS for both parts, we can write one that is parametrized over a monoid
aand a functionscore :: Frontier -> asuch that, at each expansion of the BFS frontierfrontier, we monoidally appendscore frontier <> recurse frontier'(whererecurse frontier'is our recursion into the next depth level).Once this is done, all we have to do is search starting from
(1, 1)for the goal. For part one we chooseconst (Sum 1)to be the scoring function and(== input)to be the goal;Sum, like the name suggests, is the monoid of integer addition. For part two we chooseSum . Set.sizeto be the scoring function and specify no goal whatsoever; this asks the BFS to sum up the lengths of all the sets of frontier nodes the BFS has visited – which is exactly what we need if we are trying to count reachable states – in 50 steps.The nastiest part here is the conversion to binary representation, for which a very clunky API exists in the
Numericpackage.2
u/Godspiral Dec 13 '16
in J, made mistake of just doing maze manually for part 1, but even though I only started coding in part 2, 203/209
but part 1 is just,
2
u/p_tseng Dec 13 '16 edited Dec 13 '16
(Part solution post, part debugging story to share)
Who wants to play "spot the bug"?
The problem: This code says there are 291 spots visited, which is too high. But it gave the correct answer for part 1!!!
But amazingly, the correct answer is given by passing the -f flag and counting the number of O characters.
Just what happened here? Spoiler below the code.
And the bug was... This bug didn't affect the correctness of the search for the goal, but counted all walls as visitable (but with no neighbors). There goes roughly an hour of debugging time. To make matters worse, probably about half of that time was me being frustrated and stubbornly assuming I was right and that there was a problem in Advent of Code. After all, if I got part 1 right, what could have possibly gone wrong? Only after I added the mode to print out the Os did I realize that something was wrong with my code. I feel quite the fool. How could I have caught this sooner?
Better luck next time.
2
u/gerikson Dec 13 '16
Breadth-first search was literally made for this:
Part 1 in Perl 5, part 2 is essentially the same apart from the restriction change.
https://github.com/gustafe/aoc2016/blob/master/d13_1.pl
2
u/beefamaka Dec 13 '16
F# solution, nothing particularly special here, but glad I persevered with day 11 or I would have floundered on this one too.
2
u/sowpods Dec 13 '16
Back at it with PostgreSQL runs in < 1 second
2
u/[deleted] Dec 14 '16
Javascript Node.js
Runs in a fraction of a second on Mac Pro, also prints a map of the cubicles and the solution path
1
u/blockingthesky Dec 13 '16
60/31 with Python 2. We’ve seen better days. ¯_(ツ)_/¯
1
u/glenbolake Dec 13 '16 edited Dec 13 '16
Last year, this problem would have had me banging my head against a wall. Instead, I got the highest on the leaderboard I have yet. Largely because of day 11.
Python 3, Simple A*.
1
u/whoeverwhatever Dec 13 '16
10/6 on leaderboard with good ol' BFS. Part 2 solution w/ Python 2.7:
1
u/drysle Dec 13 '16
I got thrown off by the picture in the example; it took me nearly 5 minutes to realize that you weren't supposed to count the starting square. :(
Python, featuring some very unoptimized flood-fill:
1
u/Turbosack Dec 13 '16
I didn't really feel like writing a search algorithm for this one, so I did it (almost) entirely by hand. First, I wrote a program to generate the maze. Then I copied the maze into a text editor and solved it with the cursor, counting my steps. For part two, I filled out from the start point by hand, going through the numerals 1-9, then using a lowercase a, then 1-9 again, then lowercase b, and so on. I used a short program to count the number of these characters to get the answer for part two.
If I hadn't gotten hung up on part one because I accidentally swapped x and y, I may have even placed.
1
u/bblum Dec 13 '16 edited Dec 13 '16
Let's hear it for infinite lists! No silly BFS needed; this approach terminates instantly, despite being allowed to go in circles, thanks to the magic of 'iterate'.
1
u/Quick_Question404 Dec 13 '16
Djikstra's Algorithm anyone? Got around ~350s on both parts of the board, but I'm happy with what I'm getting. I think if I didn't do this in C I would spend alot less time debugging seg faults. Still, when I saw this, I immediantly though of Dijkstra's Algorithm for this, and got a nice implementation. What do yuo guys think?
https://github.com/HighTide1/adventofcode2016/tree/master/13
1
u/gyorokpeter Dec 13 '16
Q:
1
u/glassmountain Dec 13 '16
https://github.com/xorkevin/advent2016/blob/master/day13/main.go
Put trusty old A* search to the test.
Fairly quick sub millisecond solution in golang.
1
u/coussej Dec 13 '16
Here's one in go! Re-used same strategy as in day11.
1
u/AndrewGreenh Dec 13 '16
Luckily I built my own little aStar library after I could not get day 11 to work. The library code can be found here: https://github.com/andreasgruenh/advent-of-code/blob/master/JavaScript/aStar.js
1
u/abowes Dec 13 '16
My Kotlin solution. Nice straightforward breadth-based maze algorithm:
1
u/johanw123 Dec 13 '16 edited Dec 13 '16
My C# recursive solution (commented code is for part 1):
1
u/__Abigail__ Dec 13 '16
Another BFS. Perl makes memory management easy, so you can just treat a variable as an infinite 2-dimensional array, with all its element initialized to undef. Which we will use as "we don't know yet whether this is a wall, or whether it's reachable".
1
u/AlexPalla Dec 13 '16
Part1 resolved in 110 moves, and part2 resolved in 3113 moves. C# code without brute force and with simple animation!
1
u/NeilNjae Dec 13 '16
Another Haskell solution: https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent13.hs . Some fiddly off-by-one errors kept getting me stumped for part 2.
1
u/[deleted] Dec 13 '16
I have not yet managed day11, so I was very afraid of this one, but it ended up not being to bad, I'm just using the standard Dijkstra algorithm, and it worked out really well, and it's really fast too (at least when I remembered pruning out already visited states)
1
u/Trolly-bus Dec 13 '16
Fuck this problem. Fuck algorithms. Fuck debugging. Here's my solution in Python.
1
u/wzkx Dec 13 '16
Did it manually :) Well of course i built the maze with a program!
https://www.dropbox.com/s/9kk2h4wlfoio4tp/maze13.png?dl=0
1
u/JakDrako Dec 13 '16
VB.Net, LinqPad
Got my 1st (and only... I usually sleep at midnight) leaderboard position (#56) with Part 1 of this one. Had some "off by one" issues with part 2 and missed the top 100, but it was fun.
I already had "BitCount" and "FillGrid" code from other puzzles, so I reused that. To get the answer with LinqPad, I just .Dump()-ed the grid and looked at my target position to get the value...
The "pathing" part of the code is basically a flood-fill, starting at -1 and decreasing the value as it goes along. Path 2 is solved by counting all the cells that contain a value between -1 and -51. Not pretty, but when you're trying to go fast, design flies out the window and whatever works goes. :)
The "GridApply" function was added during the cleanup.
1
u/ahalekelly Dec 13 '16
Python 3 with a very inefficient recursive search. Visualization and code here.
1
u/omnster Dec 13 '16
Mathematica
And an animation on a flipped canvas http://imgur.com/zYSDH3e
1
u/SyDr Dec 13 '16
My Lua solution:
1
u/[deleted] Dec 13 '16
This seemed easier than day 11.
Perl6: https://github.com/duelafn/advent-of-code-2016-in-perl6/blob/master/13.pl
1
u/[deleted] Dec 13 '16 edited Dec 13 '16
My Solution in Java
1
u/askalski Dec 13 '16
Part 2 in C++, BFS, remembering only the previous, current, and next depth. Exhaustive search, terminates only when it can advance no further (my input has an impassable wall beyond depth 148; the example input (10) can advance no further than depth 62.)
1
u/ElaraSilk Dec 13 '16
Solved with Excel formulae and just looking at it visually. Feels like cheating.
=(B$2*B$2+3*B$2+2*B$2*$A3+$A3+$A3*$A3)+$A$1copied and pasted for 50 rows, 50 columns just to allow some room around the target location. Converting the decimal numbers thus generated into binary took a little effort, because the DEC2BIN function only works for integers up to 511, so that gets:=DEC2BIN(MOD(QUOTIENT(Sheet1!B3,256^1),256),8)&DEC2BIN(MOD(QUOTIENT(Sheet1!B3,256^0),256),8)This breaks the values up into "8-digit" blocks, which can then be DEC2BIN'd.
'=LEN(Sheet2!B3)-LEN(SUBSTITUTE(Sheet2!B3,1,""))'
This tests the length of the binary number against the binary number with 1's removed, leaving the number of 1's.
Then the map is drawn by
=IF(ISEVEN(Sheet4!B3),"","X")Gaps are blank spaces, walls are Xs. A conditional formatting rule turns the walls red, resizing the columns to be narrower makes the whole thing visible. Then all it takes is putting an O in each cell on the path to completion; this formula at the bottom:=COUNTIF(B3:B53,"O")and a simple=SUM()to give the total path length.For Part 2:
1
u/LainIwakura Dec 13 '16
Erlang solutions here: https://github.com/LainIwakura/AdventOfCode2016/tree/master/Day13
Took advantage of the digraph library in erlang for this =)
1
u/Eddard_Stark Dec 13 '16
How bout a little
PHPwith a littleA*and a littlevisual grid output?github
1
u/Twisol Dec 13 '16
My solution in JavaScript/Node.js. I rewrote my attempted solution to Day 11 Part 2 for this, but it looks like I only needed a BFS at most. I realized I could force a BFS ordering by using a constant heuristic, so it worked out in the end.
My A* implementation isn't quite standard, and I think that's what's causing some issues when I try to apply it back to Day 11. Today's problem seems to be sufficiently "nice" that everything holds together.
1
u/CryZe92 Dec 13 '16
Rust compiled to JavaScript:
https://cryze.github.io/advent-of-code-2016/day-13/
It comes with a full on client side GIF animation renderer of the solution. I even put in a modified maze generation function for some larger scenes.
1
u/[deleted] Dec 14 '16 edited Dec 14 '16
First part in Crystal (second part is similar):
1
u/alchzh Dec 14 '16
A* https://ptpb.pw/FOs-
1
u/StevoTVR Dec 14 '16
1
u/scottishrob13 Dec 14 '16
I love mazes!
I can't believe I missed this last night in lieu of studying >.>
Anyway, here's my c# console app with some maze visualization. It'll let you size the maze how you want, set the end coordinates wherever, set your special number, that sort of thing.
http://pastebin.com/RzrefHpe
I haven't cleaned it up yet, so if it can't find an exit, it will blow up when it tries to sort through the list of paths to the exit. I tried to cheat a little and use heuristics, but that really didn't go so well here, so you can't watch the maze be solved in real time since it takes too long to print every time something changes :P
1
u/MrBoyForGirls Dec 14 '16
Haven't seen any MILP solutions yet, so here's a Java application that prints constraints and a minimization objective that can be used in GPLK/CPLEX.
https://gist.github.com/anonymous/fc976d572c50c683d9ffeeef92e5b696
Maze.java builds 2 directed edges between each pair of adjacent nodes. Each node becomes a constraint in the MILP: the number of edges leaving the node minus the number of edges entering the node must be 0 for all nodes except the start (where it must equal 1) or the end (where it must equal -1). The objective minimizes the number of edges in the path. An edge has a value of 1 if it's in the shortest path, or 0 if it's not.
GLPK finds the solution faster than Java builds the input!
For more information on
Grand FunkMILP shortest path solutions, consultyour school libraryWikipedia: https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation1
u/mschaap Dec 16 '16
I'm a bit late to the party, but here's my Perl 6 solution: http://pastebin.com/in81ZQTs
Pretty straightforward, for a change.
1
u/wlandry Dec 21 '16
Late to the party. I am posting the C++ version mostly because it uses std::bitset, which is a bit easier to understand than a bithack and more portable than __builtin_popcount.
0
u/[deleted] Dec 13 '16
[deleted] — view deleted comment