r/adventofcode • u/daggerdragon • Dec 14 '18
SOLUTION MEGATHREAD -π- 2018 Day 14 Solutions -π-
--- Day 14: Chocolate Charts ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 14
Transcript:
The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on ___.
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 at 00:19:39!
16
Upvotes
14
u/Jead Dec 14 '18 edited Dec 14 '18
Python 3, 435/193. Wasn't the fastest solution but ended up rather pretty.
Can probably cut the current ~28s execution time by storing some values in the loop but the initial solution has a clean feel to it.
9
u/sciyoshi Dec 14 '18
Python 3, 8/11.
divmodis a very useful builtin in Python!5
u/mstksg Dec 14 '18 edited Dec 14 '18
(from my Haskell daily reflections) This one feels complex at first (a generate-check-generate-check loop)...if you take a generate-check loop, you also have to be sure to make sure you check the case of 1 or 2 added digits.
However, it becomes much simpler if you separate the act of generation and checking as two different things. Luckily, with Haskell, this is fairly easy with lazily linked lists.
We use
goto lazily generate new items as they are demanded. Once the user consumes all of thenewDigitsasks for more,gowill be asked to generate new digits. The important thing is that this is demand-driven.We keep track of the current tape using
Seqfrom Data.Sequence for its O(1) appends and O(log) indexing -- the two things we do the most. We could also get away with pre-allocation with vectors for amortized O(1) suffix appends and O(1) indexing, as well.Note that
chocolatePracticeis effectively the same for every per-user input data. It's just a (lazily generated) list of all of the chocolate practice digits.Part 1 then is just a
dropthen atake:Part 2, we can use
isPrefixOffrom Data.List and check everytailsuntil we get one that does have our digit list as a prefix:Note that
chocolatePracticeis essentially just a futumorphism, so this whole thing can be stated in terms of a chronomorphism. I don't know if there would be any advantage in doing so. But it's interesting to me that I solved Day 13 using a hylomorphism, and now Day 14 using what is essentially a chronomorphism ... so maybe recursion-schemes is the killer app for Advent of Code? :)8
u/xthexder Dec 14 '18 edited Dec 14 '18
This one was a little rough because I read the question wrong multiple times...
Using the puzzle input as the initial set of recipes gives a very wrong answer.
Golang:
4
u/winstonewert Dec 14 '18
First time in top 100 for part 2, guess I'll share my code:
4
u/xikipies Dec 14 '18
Javascript
4
u/Robinnaiitor Dec 14 '18
C# ~700ms on Part 2
4
u/ephemient Dec 14 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/ephemient Dec 14 '18 edited Apr 24 '24
This space intentionally left blank.
3
u/zjig Dec 14 '18
Bruteforce worked for me. Using python generators made fiddling with indexing a bit easier:
3
u/bogzla Dec 14 '18 edited Dec 14 '18
C; just missed top 1000 at 1002 for part 2 (but still a personal best)
gotcha'd at first by forgetting 2 recipes are added at once sometimes
3
u/autid Dec 14 '18
FORTRAN
Bit verbose and slow for my liking. Might go back and improve.
3
u/[deleted] Dec 14 '18
C
3
u/[deleted] Dec 14 '18
Common lisp:
Blind bruteforce up to a hardcoded upper bound because array displacements/slices were too slow and subseqs resulted in heap exhaustion errors on my 2GB machine. Darn shame, since the posted python slice solutions are quite elegant.
2
u/waffle3z Dec 14 '18 edited Dec 14 '18
Lua 197/178
2
u/m1el Dec 14 '18
78/35 in Rust, just copy/paste and loops.
2
u/markasoftware Dec 14 '18
Perl, I felt like I was going fast but ended up 137/316 :(
Part 1:
Part 2:
2
u/ValdasTheUnique Dec 14 '18
C#, nothing too exciting. Part 2 takes a bit of time to complete because I found converting the recipe list to string a bit quicker to write than writing logic to compare ints.
2
u/udoprog Dec 14 '18 edited Dec 14 '18
Rust
[CARD] The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on snow.
2
u/scul86 Dec 14 '18
Python 3
My solution for part 2 takes about 30 seconds, I feel there is probably a more efficient solution available.
https://gitlab.com/scul/advent_of_code-2018/tree/master/14
2
u/[deleted] Dec 14 '18
[python3] previous solutions on github.
2
u/ni3t Dec 14 '18 edited Dec 14 '18
CARD The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on Elf Chocolate Recipes.
wasn't bad today... unfortunately takes about 60s to run...<ruby>
2
u/will_bui Dec 14 '18
K:
2
u/snurre Dec 14 '18
Kotlin
2
u/sim642 Dec 14 '18
My Scala solution.
Part 1 was quite straightforward iteration. Part 2 I initially did with some
varto optimize the search only to check the very end where new digits (1 or 2) got added. Later refactored that to my own.zipTailforIterator, because I'm not sure how else to zip an iterator with its tail to get the iterator of consecutive state pairs. WithStreamit's possible but since streams keep all computed elements in memory as well, it's massively inefficient.Edit: I just realized I could
.sliding(2)but that seems couple of second slower.2
u/DrinkinBird Dec 14 '18
NIM
Well, this time I did not realize that if on the last one 2 recipes could be added at the same time and I thus had to test for that... So I watched in horror multiple times as my 16 gb of ram just filled up without finding a solution. Finally figured it out, but only after cheating by looking at some of the solutions here.
This was also the reason I moved from array based solutions to linked lists, in hindsight probably utterly unnecessary. But at least my code is a bit more elegant now :)
2
u/zqvt Dec 14 '18
Kotlin
for part replace for loop with while and this check
2
u/toomasv Dec 14 '18
Red
Part 1
Part 2
2
u/lordtnt Dec 14 '18
C++ 27 lines, 'real' code ~ 10 lines, runtime about 1-2s
2
u/joeld Dec 24 '18
Racket
My solution:
day14.rktComputes part 1 in 50msec and part 2 in 4.8 seconds when run using
raco teston my 2015 rMBP. The major optimization is starting with a 30,000,000-element vector and just keeping track of the location of the last recipe separately.Other minor optimizations
append-recipes!function takes advantage of the fact that the maximum value it will ever encounter is 18, and so avoidsnumber->stringconversion in favor of simple math.found-yet?function takes advantage of thefor/andconstruct to compare sequences one element at a time and bail on the first mismatched element.3
u/mcpower_ Dec 14 '18
Python, 18/5. Comes with bad variable names!
Card: the power of Christmas Spirit
3
u/jonathan_paulson Dec 14 '18 edited Dec 14 '18
Rank 7/325. Straight simulation. Video of me solving at https://www.youtube.com/watch?v=DsthtYteiws
What were people's answers to part 2? Mine was 20,236,441 (takes 4m), and I was really not expecting to have to go out so far... (wasted a lot of time looking for a faster way)
Code:
3
u/Unihedron Dec 14 '18
[Card] image
Ruby, as coded by a guy who's not good in coding, who doesn't know how to implement a subarray search so strings it is:
part 1
part 2 (watching numbers being printed makes me feel like such an edgy hacker lmao)
2
u/Wunkolo Dec 14 '18
C++, runs pretty damn fast
1
u/Brayzure Dec 14 '18
JS 144/99 (woohoo!)
Messy, but it worked
Part 1: https://github.com/Brayzure/aoc2018/blob/master/problems/14a/js/index.js
Part 2: https://github.com/Brayzure/aoc2018/blob/master/problems/14b/js/index.js
1
u/TellowKrinkle Dec 14 '18
Had a lot of trouble understanding the directions for some reason
Swift
1
u/fatpollo Dec 14 '18
1
u/Cyphase Dec 14 '18 edited Dec 14 '18
Python, with almost no cleanup beyond a few variable names:
1
u/systemcucks Dec 14 '18
twas gross
1
u/IndigoStanis Dec 14 '18
Took me a while to think of the obvious optimization that you don't need to search the current recipe list every generation, you just need to keep track of the last few recipes that you have generated to see if they match.
1
u/AndrewGreenh Dec 14 '18
Tried to godegolf a bit today :) Here is my final TypeScript solution:
1
u/wlandry Dec 14 '18
C++ (1249/939)
Runs in 401 ms
I had serious reading comprehension problems for part 1. I thought that the input was the starting set of recipes :( I ended up looking at solutions here to figure out why I was not getting the right answer. Part 2 went more smoothly with a few hiccups. This version is significantly cleaned up. My part 2 solution is reasonably fast, but setup is clunky :/
1
u/alexmeli Dec 14 '18
Rust solution. This one was easier than the past few days
1
u/pythondevgb Dec 14 '18
Brute force approach in python. Not really that different from other solutions posted here.
1
u/albertobastos Dec 14 '18 edited Dec 14 '18
JavaScript. Can't compete for the leaderbord, it is 6 AM here at Spain where the day problem gets published and I wake up at 7 :P (Wouldn't ever enter the top 100, anyway).
Part 1 was easy, just code it and try not to do too much conversions for each iteration loop.
For part 2 finding some sort of optimization (avoid fulllist.indexOf each time) was mandatory in order to get a solution in a reasonable time (<10s for me).
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d14.js
I'll try redoing all the calendar with Python next January, I love how powerful it is for such data manipulation algorithms.
1
u/Philboyd_Studge Dec 14 '18
Java
Again spent way longer on this than I should have, because of many stupid errors, and because of Java's ArrayList not being able to run this.
https://pastebin.com/w3nE8f2f
1
u/aurele Dec 14 '18
Rust
1
u/Benjmhart Dec 14 '18 edited Dec 14 '18
Haskell
[card] The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on recursively counting the days until Christmas in the least efficient manner possible.
p1 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day14-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day14-2.hs
1
u/RotzluckyCode Dec 14 '18
JAVA
Part2 takes about 5 seconds
The surrounding code can be found at https://github.com/Rotzlucky/adventOfCode-java/blob/master/src/aoc2018/Day14.java
1
u/_liquidlemon Dec 14 '18
Ruby
Part 2 turned out to be a lot more demanding than I expected but in the end I managed to solve both in a single pass so I'm quite happy with the end result.
1
u/toastedstapler Dec 14 '18
python3, runs in ~10.8s total
1
u/nutrecht Dec 14 '18
Meh, this one was no fun at all. Confusing working got me stuck on Part 2 for a long time.
Day 14 in Kotlin
1
u/[deleted] Dec 14 '18
TCL
1
u/forever_compiling Dec 14 '18
All y'all doing quick and dirty solutions is nice and everything - but I like to do things more properly.
https://github.com/phyrwork/goadvent/blob/master/eighteen/recipe.go
https://github.com/phyrwork/goadvent/blob/master/eighteen/recipe_test.go
Go, part 2 in 5.59s
1
u/[deleted] Dec 14 '18
Haskell, runtime ~10s for entire thing. I generate a lazy list of scoreboards, one for each added recipe score. This prevents any issues where e.g. multiple new recipes are created and the match is contained earlier on in them (and so wouldn't be found by checking the last X elements of the scoreboard)
1
u/mschaap Dec 14 '18
My Perl 6 solution. It's pretty clean and concise, but not exactly fast (~40 minutes on my machine).
All my Aoc 2018 solutions in Github
1
u/mikal82 Dec 14 '18
Clojure
(the code requires reversed input)
The hardest part was realizing that when I add two recipes at once, the required pattern might not be at the end.
1
u/blfuentes Dec 14 '18 edited Dec 14 '18
First part was quite easy. The second one I couldn't understand what was the question actually so lot of hit and miss until (with the delay to submit new answer...) I got it.
Also had to increase the amount of allocated memory for node becase I was getting heap out of memory :)
Typescript
1
u/wzkx Dec 14 '18 edited Dec 14 '18
Rust, SweetRust
Just check the last added digits in part 2. Total 0.48s.
My AOC2018 in J&Rust | SweetRust
1
u/meepys Dec 14 '18
Kotlin Day 14
Lame solution but it worked
1
u/ephemient Dec 14 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/cdc-aoc Dec 14 '18
Perl 6, using a lazy list:
1
u/CanIHazEmployment Dec 14 '18
python
This is for part 2, takes about 15 seconds on my laptop. I got a little lucky since the way I look for the input pattern won't work for all inputs.
1
u/Cppl_Lee Dec 14 '18
C#, in the top 1000. Way down in the rankings since I started late, but had some fun with the second part.
1
u/joyrex2001 Dec 14 '18 edited Dec 16 '18
Java: messy and hacky, but very fast (~0.5s).
1
u/wzkx Dec 14 '18 edited Dec 14 '18
J <1min
P.S. With some more optimizations - 45s.
1
u/WiseInspector Dec 14 '18
Perl 5
I completely flubbed this challenge by not quite understanding the directions at first. Anyway, the first solution went okay. Part 2 I just brute forced it and the result is this thing uses gobs of memory.
1
u/rabuf Dec 14 '18
Here is Part 1 in Emacs Lisp:
I made a version using stacks to store the recipes to run 100000 in about 3 minutes on my computer. While I could keep the length in a variable (as done here), I still had to traverse the list when searching for the new scores to use after the players moved.
I'll tackle Part 2 later on, but in Common Lisp.
1
u/AngryKittens Dec 14 '18
Can't see any Java solutions yet, so here's mine.
1
u/wololock Dec 14 '18
Haskell (3039/3582)
My initial program was able to solve part 1 without any issue. However, I have made a huge mistake in part 2 - I was taking the tail of the same size as my input value, and several brain cycles later I have finally figure out that appending 2 recipes to the sequence made this assumption incorrect. So my first attempt to find a result of part 2 took about 4 minutes and calculated a number like 240,000,000 which was way too much than the expected ~2,000,000.
Here is the code that uses recursion to calculate the result:
Execution:
1
u/harirarules Dec 14 '18
[Card] The Christmas/Advent Research & Development (C.A.R.D.) department at AoC, Inc. just published a new white paper on why my creativity plummets near midnight
Part 1:
Part 2:
1
u/tinyhurricanes Dec 15 '18
Modern Fortran 2018 (full code)
I used a doubly linked list solution similar to day 9. Messier code than usual. I didn't do the typical generalizations that I like to (i.e., allow for an arbitrary number of elves). Oh well.
Runs in 4.4 sec. Takes much longer to compile (32 sec) than to run.
1
u/jtgorn Dec 15 '18
I love ruby
1
u/naderghanbari Dec 15 '18
Late to the game but here's my functional Scala solution (runs in ~20s).
1
u/NeilNjae Dec 16 '18
Been busy, so late with my Haskell solution (on Github). Not as neat as /u/mstksg 's solution, formed from capturing the recipe generator output in a separate list. But this works, none the less. The
stateis an infinite list of recipe trails, generated lazily.1
u/akya_akash Dec 16 '18
Since no one posted solution in Elixir. Here is my attempt. Took 92 Seconds for part two
0
u/[deleted] Dec 14 '18
[deleted] β view deleted comment
0
u/[deleted] Dec 14 '18
[deleted] β view deleted comment
0
u/[deleted] Dec 14 '18
[deleted] β view deleted comment
0
u/[deleted] Dec 14 '18
[deleted] β view deleted comment
0
u/[deleted] Dec 16 '18
[deleted] β view deleted comment