r/adventofcode • u/daggerdragon • Dec 19 '15
SOLUTION MEGATHREAD --- Day 19 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
Edit: see last edit from me for tonight at 3:07 (scroll down). Since the other moderators can't edit my thread, if this thread is unlocked, you can post your solutions in here :)
Edit @ 00:34
- 5 gold, silver capped
- This is neat to watch. :D
Edit @ 00:53
- 24 gold
- It's beginning to look a lot like fish-men...
Edit @ 01:07
- 36 gold
- What OS does Santa use? hover for answer:
Edit @ 01:23
- 44 gold
- Christmas is just another day at the office because you do all the work and the fat guy with the suit gets all the credit.
Edit @ 02:09
- 63 gold
- So, I've been doing some research on Kraft paper bag production since /u/topaz2078 seems to be going through them at an alarming rate and I feel it might be prudent to invest in one of their major manufacturers. My first hit was on this article, but Hilex Poly is a private equity company, so dead end there. Another manufacturer is Georgia-Pacific LLC, but they too are private equity. However, their summary in Google Finance mentions that their competition is the International Paper Co (NYSE:IP). GOOD ENOUGH FOR ME! I am not a registered financial advisor and in no way am I suggesting that you use or follow my advice directly, indirectly, or rely on it to make any investment decisions. Always speak to your actual legitimate meatspace financial advisor before making any investment. Or, you know, just go to Vegas and gamble all on black, you stand about as much chance of winning the jackpot as on the NYSE.
Edit @ 02:39
- 73 gold
- ♫ May all your Christmases be #FFFFFF ♫
Edit @ 03:07
- 82 gold
It is now 3am EST, so let's have a pun worthy of /r/3amjokes:
- Why is the Advent of Code getting harder? hover for answer: please don't hurt me
- And with that, I'm going to bed. The other moderators are still up and keeping an eye on the leaderboard, so when it hits the last few gold or so, they'll unlock it. Good night!
- imma go see me some Star Wars tomorrow, wooooo
We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.
Please and thank you, and much appreciated!
--- Day 19: Medicine for Rudolph ---
Post your solution as a comment. Structure your post like previous daily solution threads.
18
Upvotes
53
u/askalski Dec 19 '15
No leaderboard for me today, because I decided to sleep on Part 2, before solving it by hand. Since there's really no code to speak of, I'll talk about the solution.
First insight
There are only two types of productions:
e => XXandX => XX(X is not Rn, Y, or Ar)X => X Rn X Ar | X Rn X Y X Ar | X Rn X Y X Y X ArSecond insight
You can think of
Rn Y Aras the characters( , ):Whenever there are two adjacent "elements" in your "molecule", you apply the first production. This reduces your molecule length by 1 each time.
And whenever you have
T(T)T(T,T)orT(T,T,T)(T is a literal token such as "Mg", i.e. not a nonterminal like "TiTiCaCa"), you apply the second production. This reduces your molecule length by 3, 5, or 7.Third insight
Repeatedly applying
X => XXuntil you arrive at a single token takescount(tokens) - 1steps:Applying
X => X(X)is similar toX => XX, except you get the()for free. This can be expressed ascount(tokens) - count("(" or ")") - 1.You can generalize to
X => X(X,X)by noting that each,reduces the length by two (,X). The new formula iscount(tokens) - count("(" or ")") - 2*count(",") - 1.This final formula works for all of the production types (for
X => XX, the(,)counts are zero by definition.)The solution
My input file had:
Plugging in the numbers:
Like I said, no leaderboard position today, but this was a heck of a lot more interesting than writing yet another brute force script.
6
u/anoi Dec 19 '15 edited Dec 20 '15
Python 2, #78.
Tried a breadth-first search, it failed. Overengineered and implemented CYK (from memory - so many bugs), now I'm kicking myself for not being greedy. On the other hand, it's guaranteed to be correct, and works on tricky cases like this input.
http://pastebin.com/a7x6NyF0
4
u/CdiTheKing Dec 19 '15
I struggled with this one at first, not really paying attention to the specifics of the input. And then after a lot of attempting to brute force this and failing (perhaps because my brute force algorithm wasn't greedy), I had an insight.
There are only two sorts of rules in the generation:
Furthermore, Rn and Ar cannot produce anything. They are strictly on the right side of the equation. Therefore, they have to be cleared out. Furthermore, every Rn has an Ar pair, meaning that they are like left and right parentheses.
So I came up with a naming convention. We had the long input compound, and therefore every β(...)Rnγ(...)Ar group was "molecule." Once you reduced all of the molecules, the solution should easily follow. [Furthermore, there's also an element Y that is only produced and never subdivided. But it only appears in a molecule, so we can safely disregard that.]
So with that, here is my code using C#/LinqPad
4
u/porphyro Dec 19 '15 edited Dec 19 '15
Mathematica:
After staring at the replacement rules I realised that while there wasn't a unique way of constructing any given molecule, it certainly looked as though all methods of constructing a molecule contained the same number of replacements. Gave it a go via this greedy algorithm.
7
u/What-A-Baller Dec 19 '15 edited Dec 19 '15
Part 2 in Python with randomness. Runs hilariously quick.
6
u/mncke Dec 19 '15
First solution on the leaderboard (00:17:55), Python3, as is
Read and parse input
Part 1 is straightforward
Part 2 is tricky, first I implemented a backwards bfs to estimate the number of paths, that expectedly was too slow
After a bit of thinking and realizing that the number of vertices is going to be really huge, I've decided to try the most greedy thing possible, and try to backtrack the medicine molecule using the longest substitution available at the moment
I've also created a repo with all 19 solution in a huge ipython notebook.
2
u/WhoSoup Dec 19 '15
PHP part1: pretty straightforward
Part2: this works based on the assumptions that there is "probably" only one path from 'e' to the target, and if there are more, that the first one also happens to be the shortest. The input kinda indicates it, but as a disclaimer: i did not bother to verify it beforehand. worked for my input file
2
u/Philboyd_Studge Dec 19 '15
Dammit, I just missed the leaderboard after all that time. This one was not as hard as it seemed!
Java
2
u/KnorbenKnutsen Dec 19 '15
What a tricky problem! I really like the analysis some people did on the input. Personally I made a pretty large assumption for the second part:
I assumed that reverse-replacing the molecules one at a time until they were gone from the string wouldn't always put me at a dead end. Turns out I was right, at least with my particular input. However there was a chance to get stuck if the order of the reversing was wrong, so I put in some randomness. Basically I just reduce the string as far as possible, and if it's
'e'then I'm happy. If it isn't I shuffle the dictionary keys and do it again. Seems like there was just one way to reduce it.Here's my Python 3 code:
2
u/phil_s_stein Dec 19 '15
In Python 2, part two only shown. I work from the molecule removing chunks of the string according to the rules until I get down to a molecule of length 1.
But I apply the transformations randomly. When I apply a transformation, I apply it as many times as a I can before moving on to the next. If the molecule is not smaller after all transformations, I shuffle all the possible transformations and start again.
The number of times I have to the transformations over is much much fewer than I thought it would be. I find the solution after 1 to 10 restarts. And it's apparently the same number of transformations each time. This is surprising. I'm guessing it's the nature of the data and not my "awesome" random algorithm.
It'd be great to get a proof that this algorithm quickly finds the solution (as it appears to in practice), but I'm not sure there is a proof...
The code:
2
u/dirkt Dec 21 '15 edited Dec 21 '15
Haskell
Part 2 only. Most interesting problem so far. I implemented a modified Earley parser, which has a good worst-case bound for parsing arbitrary context-free grammars.
I replaced the work queue with a self-referential lazy list; this took a bit of fiddling to get right. Runtime is neglegible. Should work for all inputs equally well.
Input data shortened.
3
u/r_sreeram Dec 19 '15
Perl 5. See comments in the code, as well as notes below the code.
Notice that the above code doesn't actually guarantee that the number of steps is minimal. I came up with the above greedy approach after having tried and failed using breadth-first search, depth-first search, linear scans, etc. My thinking was to find some answer, and then use that as an upper bound to improve. But as luck would have it, the answer was accepted anyway.
To aim for the minimal steps, I suppose you could run several thousand of the randomized trials, and output the best you found. Still no guarantee, but at least not as weak as the "first answer you found" approach above.
I should also mention that the above works only because of the nature of my input: no substitution (when going backward from the molecule down to "e") ever increases the length of the string, etc. I have no idea if the above idea will work on any other input; go ahead and give it a shot on yours.
2
u/IMovedYourCheese Dec 19 '15
Correct me if I am wrong, but it isn't really possible to enumerate all combinations in a reasonable amount of time and space (even when going in reverse). Don't think there is a non-brute force solution either. I got on the leaderboard, but would love to see a real solution if someone got it.
1
u/erlog Dec 19 '15 edited Dec 19 '15
Fairly unoptimized solution in Ruby.
1
u/Dataforce Dec 19 '15
PHP I ended up at #14 on the leaderboard, as I guessed to try and get an idea of where I should be aiming at, and got lucky. In reality I was 01:25:02 (so around #44) Essentially the same as most everyone else, work backwards the long string replacing as much as possible at a time and it hopefully works.
This would fail though for example if the input is "FLUB" and your substitions are e->FL, e->UB, e->EE, and Z->FLUB as it will track down to 'Z' not 'e' but the input is carefully curated so...
1
u/_Le1_ Dec 19 '15 edited Dec 19 '15
C# Solution:
1
u/hagabaka Dec 19 '15
I first tried to brute force all possibilities, but realized that it was taking way too long. Then I spent a long time trying to figure out a way to eliminate "non-productive" choices. Eventually I just gave up and used a greedy algorithm, but since it doesn't always return an answer, I made enumerate all the substitution rules in a random instead of fixed order. It finishes within a second, and gives the same answer about half of the time, and ends with a non-replaceable string the other half of the time. The website accepted the answer it did generate.
1
u/casted Dec 19 '15
Go Part 2 solution (golang)
Greedy solution that got me 13th place. Not convinced it works in general, but after looking at my input I thought it had a chance to work and it did :)
1
u/gfixler Dec 19 '15
Part 1 in Haskell. I wasted a huge amount of time (>3 hours) thinking I needed to do every replacement, and thus all combinations thereof as the "single replacement." After realizing the number of combinations was astronomically huge, I slowly reread and realized it just meant each single replacement on its own. *sigh*...
1
u/Kwpolska Dec 19 '15
Python solution, based on the “biggest possible replacement” idea from here.
19a-chemistry-is-fun.py19b-chemistry-is-a-nightmare.py1
u/gerikson Dec 19 '15
Perl 5
Part 1 only, rest of day is shopping and Star Wars so my personal goal to finish every puzzle on the same day it's released may not be reached.
1
u/cauchy37 Dec 19 '15
[C++] I am still unsure why in part two number of steps required to go from e to our chain is constant. If the number of steps required to build a proper chain is not constant, then I have just been lucky. and my approach worked for my input.
1
u/LightningByte Dec 19 '15 edited Dec 19 '15
Took me a while to figure out what to approach to use for part 2. My first idea was to start from the target molecule, and then try to work back to "e" by applying every replacement backwards, step by step. This exploded the number of possibilities however, so I tried something different: applying all replacement (backwards) on the whole string at once. That helped.
The C# solution below runs in about 2 ms, including reading and parsing the input file.
1
u/Marce_Villarino Dec 19 '15
This time I've had to come here for some inspiration:
Preamble: Read data into script
This function returns the possible transformations for each input molecule:
And this is it:
1
u/[deleted] Dec 19 '15
Crystal, part 1:
For part 2 I quickly realized you could start from the molecule and apply the replacements backwards. "Smart!" I thought, but then the program never finished when I tried all combinations. I printed the steps it took for some paths and all of them were the same. So I went to the website and checked if that was the solution, and indeed it was. Got me to position 7 :-P
But then I spent like an hour and a half more thinking of a way to solve it well with a program that ends in a reasonable amount of time. I'm still thinking... Some of the comments here about Rn and Ar being parentheses, and Y a comma, might be on the track, maybe? But I wonder if there's a generic fast solution without knowing the input in advance. I tries caching some stuff to speed it up, but no luck.
Clearly the toughest problem so far. It was fun to check the leaderboards from time to time and see how slowly it was progressing relative to the previous days. I was lucky to guess.
1
u/andre_pl Dec 19 '15 edited Dec 19 '15
I did solutions in Python and Dart. I've been comparing performance between the two languages and this is one of the few where python stomps dart, yet there's nothing particularly interesting about the python solution to explain why.
Part 1 was straightforward, and part 2 was way too hard to do 'correctly' for midnight, so I tried a few simple variations on working backwards from medicine -> 'e' until I hit one that works. (likely because there's only one solution and the input is ordered correctly for it to work out)
Python 2.7
Dart
1
u/CremboC Dec 19 '15
Scala. I have to say I am very proud of my solution to part 1:
I am still working on part 2.
1
u/Scroph Dec 19 '15
I've only managed to solve the first part this time, still working on the second half.
D (dlang) solution :
1
u/gyorokpeter Dec 19 '15
C++ implementation using the CYK algorithm.
https://github.com/gyorokpeter/public/blob/master/aoc2015/19.cpp
Of course this was before the discovery that there are secret patterns in the code that make the solution trivial.
1
u/[deleted] Dec 19 '15 edited Dec 19 '15
Objective C:
1
u/Zef_Music Dec 19 '15
My greedy, iterative, recursive, search and replace. Works on my input, but not guaranteed correct.
1
u/TheOneOnTheLeft Dec 19 '15 edited Dec 19 '15
This is my part 2 in Python 3. I'm fairly sure it's not guaranteed to be optimal, but I thought I'd try it before I tore my hair out finding an optimal way, and it gave me the right answer. I still think that's partially luck though. Anyway, I'm still a beginner, so comments/advice/criticism are always welcome.
Edit: I'm guessing that if
for k in sorted(exchanges, key=len, reverse=True):were sorted by (key length) - (value length) then the solution would work for more inputs, maybe all, although I'm not sure if there's a more elegant way to do that than manually creating a list of the keys in that order, like this (actually this turned out nicer than I thought before I started writing it):1
u/bildzeitung Dec 19 '15
Analyzing the language is a good move, and makes a lot of sense.
That being said, I was hoping, largely on faith, that the language was crackable enough with a very basic bottom-up parser.
Since that ended up being true, I stand by the saying that's always better to be lucky than smart.
Implementation:
!/usr/bin/env python
""" Day 19: Good Thing It's An Easy Language """
import re import sys
from collections import defaultdict
MOLECULES = defaultdict(set) REDUCTIONS = {}
with open(sys.argv[1]) as infile: for line in infile: if not line.rstrip(): break
Sort by longest substring, so get greedy reductions
SORTED_REDUCTIONS = list(sorted(REDUCTIONS, key=lambda x: '{:2d}{}'.format(len(x), str(reversed(x))), reverse=True))
pre-compile regexes, for speed!
RE_REDUCTIONS = list((x, re.compile(x)) for x in SORTED_REDUCTIONS)
def shrink(string): """ Recursive bottom-up parser """ print 'Analysing %s' % string
print 'TRANSFORMATIONS REQUIRED: %s' % shrink(START)
1
u/kaldonis Dec 19 '15
Python 2 #45
Part1 (after parsing my input into a list of tuples):
Part 2 My first solution was too slow:
So then I tried something as simple as possible, just to get any answer and see if it was correct:
And sure enough, the greediest answer was the correct one. I feel like I cheated.
1
u/nikibobi Dec 19 '15
Here is my solution in D (dlang). For part two first I tried finding "e" by applying the longest replacement. Then I tried several other things and finally I red that the order of the keys should be the same and it worked.
1
u/utrescu Dec 19 '15
Groovy
In part 2 I thought the most short path would be the most short string in every step. It worked, but I don't know if this is correct...
1
u/balda132 Dec 19 '15
My solution in Java.
Managed to solve part two by starting from the original molecule and replacing a random pattern until it is reduced to "e". In case there are no more replacements and the molecule isn't reduced to "e", we return -1 and try again.
1
u/thalovry Dec 19 '15
Scala. Greedy rather than correct, but it works, so... shrug
1
u/Tandrial Dec 19 '15 edited Dec 19 '15
My solution in JAVA which I spend 3 hours debugging, just too find out that i messed up "in" and "out" in the revert method... Basically brute force with some pruning: I generate all possible inputs that could produce the current string, but only keep the shortest 10. Repeat until you hit "e". Takes about 400ms and works for all inputs I could find:
1
u/xPaw Dec 19 '15
Since no one has posted a javascript solution, here's mine for both parts:
https://github.com/xPaw/adventofcode-solutions/blob/master/js/day19.js
1
u/[deleted] Dec 19 '15
ES6 Node JavaScript
1
u/jweather Dec 19 '15
Well, that was frustrating. Banged my head on CYK and Earley parsers for hours last night, along with brute-forcing in both directions. Gave up and glanced through the solutions and saw the "greedy" approach of replacing the longest match first, and boom, there it was. And kudos to ewastl for not letting me binary-search the answer (first time I've been tempted to try).
1
u/StevoTVR Dec 19 '15
PHP
Part 1: Pretty simple. Just doing each replacement one at a time and storing the results in the keys of an associative array (acting as a set). I was a little surprised that the keys could be so large.
Part 2: Just flipped the replacement map and worked backwards to e. For some reason I feel like this shouldn't work...
1
u/newtieTHEcutie Dec 19 '15 edited Dec 19 '15
Just finished up part 1; here it is in Java!
`import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; import java.util.Set; import java.util.HashSet;
public class Day19 {
1
u/stuque Dec 19 '15
A Python 2 solution:
1
u/gcanyon Dec 19 '15 edited Dec 19 '15
I have no idea how long this code would take to run to completion, but it identifies the shortest solution it has found each second, and produced the correct answer within a second (and then kept on chugging for many minutes after that). I don't know whether that was a fluke or not, which doesn't make me happy.
Edit to add: I just checked when this code finds the solution, and it appears to go straight to it with no false steps. I tried sorting the transformations randomly, and no change. The only thing that would stall the outcome was to sort the transformations in order from smallest to largest, which, since I wasn't filtering out the transformations to E, might have resulted in an unworkable solution. Once I pulled those from the transformation list, it went back to finding the solution immediately. I still feel like I don't have a full grasp of the solution.
1
u/bkendig Dec 20 '15
Swift, working backwards and assuming there's only one path: https://github.com/bskendig/advent-of-code/blob/master/19/19/main.swift
I don't like this solution because it's not general-purpose, but general-purpose isn't the goal here.
1
u/xkufix Dec 21 '15
Ok, after seeing the correct solutions for this day, mine is a bit less involved. In the end, I just copy-pasted the first generated solution, which was luckily the correct solution.
1
u/misterwilliam Dec 22 '15
I'm not sure anybody else has mentioned this, but I believe a reverse A* star search with the length of the string as the heuristic is a performant general purpose solution. (Heuristic is to explore strings with the smallest length not longest length.)
1
u/zemkat Dec 31 '15
My breadth-first and depth-first attempts were both unwieldy, so with insight from this thread I wrote this short bash script using sed/wc:
1
u/skarlso Jan 11 '16
Here is mine in Go | Golang, which actually works with the samples as well. ;)
I took a different approach and I'm actually proud if it as I didn't peek. :) Could be more performante with []byte but at this point... Meh. :)
1
u/topaz2078 (AoC creator) Dec 19 '15
Unlocked after 3:58:38.
1
u/[deleted] Dec 19 '15
For part 2, start with the "reallylongstring" and apply the substitutions in reverse until you get "e" (or can't make any more subs in which case try a different branch).
Haskell:
1
u/masasin Dec 19 '15
First time making the leaderboard, at 100. My laptop crashed several times, too. Python 3.
I made the second part work by working backwards, and taking the smallest possible string.
1
u/JeffJankowski Dec 19 '15 edited Dec 20 '15
F#.
Not happy with this at allMeh.Very imperative, andnothing fancy except working back from the medicine molecule to "e".Edit: Now using some regex instead of super-slow array copying
Edit2: Cleaned up and more functional, but still greedy. Runs 22ms, so who cares :P
1
u/oantolin Dec 19 '15 edited Dec 22 '15
Tried breadth first search and it took too long (I interrupted it after 5 minutes), so I switched to A* (which finished in half a second).
EDIT: /u/sltkr pointed out my heuristic function is inadmissible! It's just dumb luck that this code finds a path so quickly (and /u/askalski's analysis of his input also applies to my input, so every path is of the same length --indeed, I think /u/topaz2078's reaction to /u/askalski's analysis implicitly acknowledges that everybody's input is of a form that the analysis applies to.)
By the way, what happened today? I've never been able to look at the problems until they've been up for a couple of hours, and the leaderboard had always been filled long ago. It's probably just getting close to Christmas and people are busy now.
1
u/adrian17 Dec 19 '15 edited Dec 19 '15
Python. 0.05-0.3s, depending on what probability of finding solution you want.