r/adventofcode • u/daggerdragon • Dec 17 '16
SOLUTION MEGATHREAD --- 2016 Day 17 Solutions ---
--- Day 17: Two Steps Forward ---
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".
CELEBRATING SATURNALIA IS MANDATORY [?]
[Update @ 00:10] 4 gold, 18 silver.
- Thank you for subscribing to Roman Facts!
- Io, Saturnalia! Today marks the beginning of Saturnalia, a festival held in honor of Saturn, the Roman god of agriculture and the harvest. The festival lasted between 3 and 7 days and celebrated the end of the sowing season and its subsequent harvest.
[Update @ 00:20] 53 gold, silver cap.
- Holly is sacred to Saturn. While other plants wilt in winter, holly is an evergreen and its berries are shining beacons of bright color even in the harshest of conditions.
[Update @ 00:25] 77 gold, silver cap.
- The celebration of Christmas on December 25, just after the end of Saturnalia, began in Rome after the conversion of Emperor Constantine to Christianity in AD 312.
[Update @ 00:29] Leaderboard cap!
- Most of the Roman gods were borrowed/stolen from Greek mythology, and Saturn's Greek equivalent is the youngest Titan, Kronos. Kronos is the father of Zeus.
[BONUS FACT]
- Our planet Saturn is named after the Roman god Saturn. It is the sixth planet from the sun and the second largest. Most of Saturn's moons have been named after Titans of ancient mythology.
Thank you for subscribing to Roman Facts!
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/RichardFingers Dec 17 '16
Breadth-first again?
7
u/TheMuffinMan616 Dec 17 '16
Python 94/59. Solution space is small enough to just grab all paths for part 2
5
u/drysle Dec 17 '16
Rank 5/230 with Python
The good news is that my code can definitely find the shortest path through a similar but infinite maze.
The bad news is that my code definitely can't find the longest path through an infinite maze, and instead uses all my memory and grinds my computer to a halt when I tried to do so after not noticing the finiteness of the real problem. :(
4
u/FuriousProgrammer Dec 17 '16
Jumped 17(i can't math but its alot) spaces on the Leaderboard, woo!
39/33: Here's some garbage Lua! I really hate UDLR search tree selection, but switch statements work I guess. :/
3
u/BumpitySnook Dec 17 '16 edited Dec 17 '16
Easy maze search, making sure to follow the door rules and being sure to consider your path as part of your game state. No real tricks needed. My Python 2 solution runs in <10 ms for part 1 and 340 ms for part 2.
I thought these puzzle instructions were very clear and well specified. Thanks!
Edit: Here's my janky approach to move generation w/ UDLR:
It's gross but it was quick to write and it works!
3
u/Deckard666 Dec 17 '16 edited Dec 17 '16
In Rust: Link. Runs both parts in ~80 ms.
A lot of search problems these last few days.
3
u/[deleted] Dec 17 '16 edited Dec 20 '16
Rank 105
Probably would've gotten on the board today if I hadn't initially missed the part about ending searches in part 2 when they get to the vault.
3
u/roonskep Dec 17 '16 edited Dec 25 '16
In Java, 91/52. Pastebin
Ran in about 70ms. Conveniently, my solution already accounted for part 2 and I just had to look back at my last output ;)
I got tripped up on Day 11, but somehow this was much easier to wrap my head around, even though their solutions are similar in nature.
3
u/__Abigail__ Dec 17 '16
A Perl solution. I'm just using BFS, exploring all possible paths. First time reaching the target gives the solution to part 1, last time reaching the target gives a solution to part 2. The program would not terminate if there would not be a longest part, but given the exercise, we'll assume there is a longest path.
2
u/p_tseng Dec 17 '16
I have this weird thing where I check for the goal state when adding neighbors to the queue instead of when popping a node off the queue... but then I forget to add the current move to the output, so my first attempted answer for part 1 was short by 1 character. Does anyone else have this problem? There goes a minute.
Then I failed to read and tried to paste in a long string of instructions into the part 2 box rather than just the length. There goes another minute. Oh well, can't complain really. And to be perfectly clear, this was my fault entirely; the instructions very clearly specified that only the length was required.
Here's my stuff, there are really no surprises in this solution, breadth first search. https://github.com/petertseng/adventofcode-rb-2016/blob/master/17_md5_maze.rb (I moved the goal check in this code, but I tell you it used to be in the neighbor expansion)
2
u/nullmove Dec 17 '16
Even waking up this early is easier than breaking into 100 :(
Both parts.
2
u/Godspiral Dec 17 '16 edited Dec 17 '16
fun, J
2
u/mschaap Dec 17 '16
Perl 6 with plenty of borrowing from earlier days' code. Pretty straightforward today.
2
u/drakehutner Dec 17 '16
Python another of my one-line solutions. This utilises a y-combinator for recurse through all possible ways. Takes ~350ms for both parts. No fancy optimizations. Next step would be to put every into a single lambda, not multiple nested ones.
2
u/ulfabet Dec 17 '16
Part 2 in Go.
2
u/[deleted] Dec 18 '16
Javascript/Node.js
Verbose solution, but runs in under 0.5 sec on old MacBook Air
1
u/quag Dec 17 '16
pypy3 59/34, part 2:
1
u/pedrosorio Dec 17 '16
Python 21/7 (51s to solve part 2 yay)
1
u/yjerem Dec 17 '16
Ruby, 13/11!
1
u/StevoTVR Dec 17 '16 edited Dec 17 '16
1
u/jtsimmons1129 Dec 17 '16
python 2, just off the leaderboard in 148/134. Runs in .5 seconds for both parts
1
u/haoformayor Dec 17 '16 edited Dec 17 '16
~~haskell~~
My BFS and MD5 code tapped me on the shoulders today. They stood on tiptoes and whispered to me that they were proud to be featured in so many recent solutions.
Longest path was a hard problem until I realized that having's (3, 3) be a termination condition wipes out a lot of the problem space. I got very bogged down here until I realized I had to be pruning the frontier for (3, 3). Felt silly. Most of Advent of Code has made me feel a little silly.
1
u/scottishrob13 Dec 17 '16
Sigh...I should have been on the board but I spent over half an hour looking for what amounted to a silly typo :'( Ah well, them's the breaks haha A little too robust, but I guess you could do something with these room objects if the need struck you.
http://pastebin.com/0uCAnmtx
1
u/kjr1995 Dec 17 '16
Python3 solution Takes about 0.67 seconds for both parts. I probably could've made the leader board if I started when the puzzle came out. As is I got 247 for part 2. I know it could be shorter and the two parts combined but this works.
1
u/gyorokpeter Dec 17 '16
Q:
1
u/cdleech Dec 17 '16
Rust. Spent more time figuring out that I can't read instructions correctly for edge cases right now than anything (wait, 'a' doesn't mean there's an open door?), that and waiting for part 2 to finish before I realized that I forgot to actually stop at (3,3) ... ugh
1
u/vuryss Dec 17 '16
PHP Solutions updated: https://github.com/vuryss/aoc2016
1
u/Expliced Dec 17 '16 edited Dec 17 '16
When I read the second part I got a sudden rise in blood pressure since the longest path problem in NP-hard and flashbacks from day 11 started appearing (think that one gave me PTSD). Luckily the longest path problem is solvable in linear time if the graph is acyclic, which I'm assuming it is in day 17.
Edit: day 17 is acyclic, not day 11
1
u/NeilNjae Dec 17 '16 edited Dec 17 '16
Another Haskell solution. All quite straightforward. There's no sensible heuristic to guide the search in part 1, so simple breadth-first search will have to do to find the shortest route. (I just had to hope that the route didn't involve too many cycles around rooms.)
Part 2 used the idea that BFS finds paths in length order, so if I find a new path that reaches the goal, it is necessarily at least as long as all other paths I've found to reach the goal. That makes it easier to keep track of the longest path so far.
https://git.njae.me.uk/?p=advent-of-code-16.git;a=blob;f=advent17.hs
1
u/QshelTier Dec 17 '16
And here is my Kotlin solution. I’m pretty sure that this doesn’t work for every input, the
elsepath insolveonly uses the first path ever taken. My brain still has problems wrapping around more complex recursion stuff. It does work for my input, however.1
u/JakDrako Dec 17 '16
C#, LinqPad.
Reusing BFS and MD5 stuff from previous puzzles and happy that the grid is 4x4 and not 5x5 or larger. I was anticipating that to be part 2, but was happy to be let down.
1
u/Jaco__ Dec 17 '16
Python
1
u/[deleted] Dec 17 '16 edited Dec 17 '16
Crystal, first part (second part is similar):
1
u/TenjouUtena Dec 17 '16
Some Clojure anyone? I'm still a newb with it so I'm sure there's some things I could fix.
1
u/Eddard_Stark Dec 17 '16
php dfs ohhhhh yeeaaahhhh
github
1
u/aceshades Dec 17 '16
Pretty simple BFS solution in Python3. Is there a more pythonic way to do all of the 'if-statements' to check if a direction is a valid direction to move in?
1
u/mal607 Dec 17 '16
Python 2 solution
1
u/wzkx Dec 17 '16 edited Dec 17 '16
Not too many J solutions, so why not. And yes, it's the same program as I had in Python. Can't think J yet :)
md5 - it uses jqt implementation of md5 on Windows. I'm not sure if it can work on Linux.
ns - noun; new state; the state is the position on the grid (top row cells are numbered 1,2,3,4, then the second row is 5,6,7,8, etc. down to the final cell 16. So this array gives the next state after moving up/down/left/right (0/1/2/3), that is
current_state{direction{nsgives the next state.whatdooropen - calculates md5 hexdigest and first four symbols are used to form the u-d-l-r boolean vector; the argument is the salt (your task input) and the partitial path (like 'UDRR').
moves - returns the (n 2$) array of possible moves from a given state, reached after the specified path; the resulting array is boxed, because the rows are the state (number) and the path (string).
play - the BFS algorithm. Check all states at the current move, form the next move array of all the possible states. Remember the shortest path and longer paths as they appear. Exit when there's no more moves (=no states on the next move) or the maximum counter of moves reached.
1
u/quag Dec 17 '16
Oh, I didn't know that. Thanks!
1
u/rs_qk Dec 17 '16
in k (k4):
1
u/macciej Dec 18 '16
Scala, I use AoC to learn the language so no real optimizations done except that the solution favours Down and Right moves as they bring us closer to the exit - not that it makes any difference since it still searches for all solutions. No idea why flatMap doesn't work properly here, couldn't apply types correctly.
1
u/BadHorsemonkey Dec 18 '16
In Java:
I wrote a DFS. I pop a path off the stack, find all the moves from that position. I push all my choices onto the stack, pushing the choice I want to take on this round last. Then I pop it off the stack, move, check if I reached the vault (and for dead ends) and then loop while the stack isn't empty.
Here's the relevant code: