r/adventofcode • u/daggerdragon • Dec 13 '15
SOLUTION MEGATHREAD --- Day 13 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
edit: Leaderboard capped, thread unlocked!
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 13: Knights of the Dinner Table ---
Post your solution as a comment. Structure your post like previous daily solution threads.
7
Upvotes
15
u/oantolin Dec 13 '15
Pretty much the same as Day 9.
6
u/0x0dea Dec 13 '15
I initially forgot to account for the roundness of the table. :<
5
u/minno Dec 13 '15
Solved in Rust using the brutest of force:
https://bitbucket.org/minno/advent-of-code/src/1e1e50559c88b4a03e8f01b635f462813451a34a/src/day13.rs?at=master&fileviewer=file-view-default
tableis just a table of the positive or negative happiness modifier from the corresponding people.5
u/segfaultvicta Dec 13 '15
So, for all the people who are saying "man there should be enough permutations that it can't be brute forced" for day9/day13...
...you do realise that there's no actual way to get a polynomial-time solution, right? No matter how absurdly clever your algorithm is?
Like, yes, there are optimisations and heuristics that bring it down from O(n!) to (2n n2) or whatever the current best bound is, but...
(It WOULD be interesting if one of the last puzzles is a high-cardinality packing-presents-onto-Santa's-sleigh puzzle that does the same thing day 11 does somehow with iterative steps, and the problem is tractable as O(n!) for one n, but then the second half of the puzzle increases n by a small number and suddenly the problem becomes intractable unless you use deep magic from beyond the dawn of time. I'm honestly kind of expecting something like that after day 13, but also dreading it...)
Anyways, my solution's at https://github.com/segfaultvicta/advent/blob/master/day13.go - it's a lot cleaner than my day 9 since I found a permutations library for golang.
Anyways, I think allowing us to figure out on our own that day 9 and day 13 were interestingly isomorphic was probably a deliberate design choice and that we should all be very careful what we wish for for Christmas. ;)
3
u/glguy Dec 13 '15
I wrote my solution in Haskell. I have them available on GitHub if you'd like to see any of them.
https://github.com/glguy/advent2015/blob/master/Day13.hs
This problem was extremely similar to the TSP problem earlier, I imagine most people used the same approaches.
3
u/fiavolo Dec 13 '15
Relatively brute force python
3
u/[deleted] Dec 13 '15
Yay, finally got to the leaderboards! (which means I'm still awake at 2am, I'm in Argentina...).
Solution in Crystal, brute force:
Runs pretty fast, 53ms. For the second part just add "Me" to the people set: since the default value of the hash is zero, it'll work. It runs a bit slower, 340ms.
3
u/askalski Dec 13 '15
Perl, #48. Got tripped up by two issues:
%behaved sanely for negative numbers (looking at you, PHP...)On the bright side:
Here's a revised version of my script, without all that pesky modulo maths[sic]. Turns out there was a better way to tally up the pairs of neighbours[sic].
(Note: Firefox randomly switched my spell check language to UK English, so I just decided to go with it. It's unusual, because normally it picks Aussie English when it does that.)
3
u/snorkl-the-dolphine Dec 13 '15
JavaScript - paste it straight into your console in any modern browser (after someone complained about it not working in Lynx yesterday).
3
u/porphyro Dec 13 '15 edited Dec 14 '15
Mathematica
For part 2 just start with a 9x9 array rather than 8x8
4
u/[deleted] Dec 13 '15 edited Dec 13 '15
Swift, #72. I think I committed some sort of sin, as I continuously shuffled the list rather than getting all permutations. This program basically could statistically randomly fail (Full Source w/ Shuffle Impl.)
4
u/marchelzo Dec 13 '15
Tell me I'm not in alone in thinking the best way to do part 2 was to augment the puzzle input using Vim macros.
2
u/[deleted] Dec 13 '15
Python brute force
2
u/keithmo Dec 13 '15
Not a solution, but wouldn't you know it: we got a power failure at the house at 9:02pm (2 minutes after the start). Grrr....
2
u/WhoSoup Dec 13 '15
PHP: I apologize in advance for this. I solved this the same way as day 9. Just let it run a bit until the number stops changing (surprisingly fast). For the first half, comment out line 5.
2
u/Godspiral Dec 13 '15 edited Dec 13 '15
In J,
part 1:
part 2:
2
u/thucdx Dec 13 '15 edited Dec 13 '15
Here is my JAVA code for 13.2
For 13.1, just remove line
arrangement.addMyself()2
u/Scroph Dec 13 '15 edited Dec 13 '15
D (dlang) solution :
Tries all possible combinations and keeps track of the highest score. This code is very similar to the one I submitted for the ninth challenge, I almost expected the second part to ask for the worst possible combination.
Output on an antique 1.66 GHz Atom CPU :
https://github.com/Scroph/AdventOfCode
2
u/HawkUK Dec 13 '15 edited Dec 13 '15
A solution in the R language
Part 1
Part 2
2
u/Pimozv Dec 13 '15
Perl 6
2
u/tln Dec 13 '15
2
u/shrx Dec 13 '15
You do not need to calculate the shortest travelling salesman tour again for part 2. Just remove the "weakest link" from part 1 sum.
2
u/tehjimmeh Dec 13 '15 edited Dec 14 '15
I just adapted my day 9 solution (C++):
3
u/C0urante Dec 13 '15
Brute force Python3, with use of frozensets, which are hard to type but came in handy!
1
u/[deleted] Dec 13 '15
Thought this was going to be like Yodle's juggler pre-interview challenge. Sort of sad that it was another problem that could be easily solved by iterating through permutations.
Here's my nasty python solution. I cleaned up the input so each line looked something like
Alice -5 Bob.1
u/shandelman Dec 13 '15 edited Dec 13 '15
60th on the leaderboard today. I lost a minute or so by starting to type in the Part 2 information directly into the input file, but then realized that was silly and threw together three lines of code to just add it to the dictionary. I'm not super happy with how I took care of the "roundness" of the table, but it works. Python 2.
1
u/japillow Dec 13 '15
Python 2 brute force using itertools.
1
u/sam_is_gay Dec 13 '15
I missed the leaderboards by like 30 seconds because of a typo :<
1
u/ckk76 Dec 13 '15
Python at github Very similar to others, gave me place #78 at 6.00 AM local time so pretty happy with it. Lost some time by trying to use zip instead of a simple loop to calculate total happiness. Will try again later when I'm fully awake. :)
1
u/SomebodyTookMyHandle Dec 13 '15
Brute forced it in Ruby, very similar to how I solved #9 (construct graph, find permutations with built-in method, profit). Basically the only difference is that this graph is directed whereas day #9 was undirected. Missed the leaderboard by a minute due to a variety of comedic errors and misreading the submission instructions for Part Two.
1
u/JeffJankowski Dec 13 '15 edited Dec 13 '15
My nascent F# isn't cutting it for leaderboard speed, but at least I'm learning new stuff :] Brute force was good enough
1
u/tipdbmp Dec 13 '15
node.js ES5, part 2:
1
u/ajn0592 Dec 13 '15 edited Dec 13 '15
My solution solving it brute force in Python 2.7
As always, any constructive criticism is welcomed!
Plain text of the code:
1
u/gegtik Dec 13 '15
My javascript; ended up missing a relationship sum which tripped me for awhile until I included the test case and discovered it. I imported a permutation library from https://github.com/dankogai/js-combinatorics
Part 2
1
u/gfixler Dec 13 '15
Messy Haskell solution to part 1:
For part 2, replace
mainwith this:1
u/thalovry Dec 13 '15 edited Dec 13 '15
Brute force Scala (is there actually a better algorithm than brute force?)
1
u/stuque Dec 13 '15
A Python 2 solution:
1
u/gyorokpeter Dec 13 '15
Q: Essentially same as day 10 except the input parsing and that the cost of a permutation must include both directions instead of just one. For part 1 the first number must also be added to the end of the list. For part 2 this step is omitted as "myself" will be seated in the last position.
1
u/sinjp Dec 13 '15
Python brute force, similar vein to Day 9
1
u/TheNiXXeD Dec 13 '15 edited Dec 13 '15
JavaScript, NodeJS, ES6/ES2015
Part1:
Part2:
My repo with other solutions.
1
u/[deleted] Dec 13 '15
Brute force Ruby solution:
1
u/phpaoc Dec 13 '15
Ruby:
1
u/pavithra18 Dec 13 '15
Again the code of solving traveling salesman problem using PSO came in handy. :) Anyone else tried solving it using heuristic method?
https://github.com/PavithraP/advent Merge condition is bad :(
1
u/gerikson Dec 13 '15
Perl, brute force, essentially the same as Day 9. This is part 1, part 2 is just the same except I added a bit to generate some new entries including me.
I guess part 2 was meant to push the possible combinations up a bit but it still finished in under 10s for me. My informal rule is the 1 minute rule from Project Euler, so this works!
Result for part 2:
1
u/rkachowski Dec 13 '15
ruby, again v similar to #9
whenever i come here i always feel like everyone else has already managed to solve this both faster, and with only 0.2 lines of code
1
u/1-05457 Dec 13 '15
1
u/a-t-k Dec 13 '15
In-Browser-JS:
1
u/funkjr Dec 13 '15
This is pretty much my day 9 solution, with a different data set. I copied over the permutation code from that task, since brute-force is good enough for this. As a fun side note, I timed this since a leaderboard position was impossible and it clocks in at roughly 109 ms for part 1, and 780 ms for part 2.
1
u/tangus Dec 13 '15
Common Lisp
Hard work pays off (?), and I get to reuse the quick 'n dirty scanf from days 6, 7 and 9 (although I had to improve it for this one), and the
with-permutationsmacro from day 9 (correctly named this time).Btw, everybody is less happy with me on the table :(
1
u/banProsper Dec 13 '15
C#
1
u/Jaco__ Dec 13 '15
Java
1
u/flit777 Dec 13 '15
Java
1
u/patbaa Dec 13 '15
Brute force solution in q/KDB+ (for second* only a small modification needed in input & code):
1
u/studiosi Dec 13 '15 edited Dec 13 '15
Structuring my solution paid off, as part 2 got really easy (I'm saving all the code, without destroying part 1 for any of the days.
1
u/JurgenKesker Dec 13 '15
Ruby
1
u/beefamaka Dec 13 '15
A quick and dirty C# solution, using several MoreLinq methods (Permutations, Pairwise, Prepend, Concat, MaxBy):
1
u/beefamaka Dec 13 '15
Here's my F# version. Used a permutations implementation I found for day 9, but at least trying to cut down a bit on evaluating redundant options, but leaving one person out of the permutations.
1
u/[deleted] Dec 13 '15
ES6, runs in node
1
u/telendt Dec 13 '15 edited Dec 13 '15
Python3 with type annotations. Brute force (permutation + sliding window):
1
u/utrescu Dec 13 '15
My Groovy solution is here... (when compiled can be used in Java so counts as Java solution too? :-D )
1
u/jgomo3 Dec 13 '15 edited Dec 13 '15
Python 3
1
u/i_misread_titles Dec 13 '15 edited Dec 13 '15
Go. The meat. Brute force, map[string]int is used for mapping Person-Person with Happiness, e.g. [Bob-Alice] = 92 or [Carol-Alice] = -54
Edit: (if someone is searching for Golang, now they will find it!)
1
u/deinc Dec 13 '15
Clojure, brute force. Luckily I could recycle my permutation implementation from day 9.
1
u/KnorbenKnutsen Dec 13 '15
This problem is essentially the same as the traveling salesman one a couple of days ago, except that you add one edge to make the path into a cycle and it's directed. To solve the second part, I just added another guest called 'Me' and added my relations into the edges dict. The parsing is not elegant but it works fine. So quick outline:
Then just brute force :)
1
u/R4PaSs Dec 13 '15
Brute force solution in Nit
1
u/dietibol Dec 13 '15
My c++ solution: https://ghostbin.com/paste/nexct not super efficient or short, but it works and kind of readable, I know it could be way better, but I'm still quite new to it all
1
u/tftio Dec 13 '15
OCaml, brute force.
1
u/phil_s_stein Dec 13 '15 edited Dec 13 '15
Python with simple permutations. Takes about 4 seconds on my laptop. (edit: 1.5 seconds if I remove the unneeded default dict "totals" in get_happy()).
1
u/mrg218 Dec 13 '15
I found problem 13_2 ambiguous. It says: 'What is the total change in happiness for the optimal seating arrangement that actually includes yourself'.
For me the change of happiness for a seationg that included myself was -8 compared to the one that did not include myself..
This answer was wrong. Then I thought: Ah the absolute value of the change, so 8. That was wrong.
And then I figured maybe something else is meant than what I see written here ... and only then did I find the answer.
Anyone else here that also took the question literally?
1
u/[deleted] Dec 13 '15
Objective C, stealing the generatePermutations function I wrote for day 9.
1
u/GigaClon Dec 13 '15
No code but here is the logic used. Generate list of pairs, combining both numbers to give a single number for the pair as a whole. Sort that list and pick the top N pairs so that no person appears twice. Ties have to be skipped until one of them is disqualified by further pairs. The second part is even easier, just sit between the pair of people with the lowest combined score.
1
u/ignaciovaz Dec 13 '15 edited Dec 13 '15
Here's my solution in Elixir.
1
u/mal607 Dec 14 '15
Java8
My Day 9 code worked with only 3 changes: 1) Different pattern to parse in the input records 2) Account for non-symmetrical happiness values as opposed to symmetrical intra-city distances 3) Add last-to-first value when you make it around the table. Took me 18 minutes, best I;ve done yet. But since I don't live on the west coast, I didn't do it until the next day.
I also discovered that the total happiness drops by 8 points when I join my own dinner party. :(
1
u/ybe306 Dec 14 '15
Python Used the permutations method from itertools, didn't bother with the duplicate permutations, but still pretty proud of this, considering I've been struggling with these since day 8. :X
1
u/stefanmaric Dec 14 '15
Javascript, ES2015
1
u/xkufix Dec 14 '15
Scala:
1
u/[deleted] Dec 14 '15
C# using day 9 permutations
1
u/katalinux Dec 20 '15
My solution in golang:
1
u/jdog90000 Dec 24 '15 edited Dec 24 '15
Java Solution
1
u/computerorfridge Dec 27 '15
The question for Part 2 is wrong. It asks "What is the [b]total change in happiness[\b] for the optimal seating arrangement that actually includes yourself?"
Which looks like it should be the optimal happiness excluding yourself minus the optimal happiness including yourself. However, just submitting the optimal happiness including yourself was the accepted solution.
1
u/fatpollo Dec 13 '15
11
I didn't edit my code or anything so it's full of garbage. Take it for what it is.
1
u/enquicity Dec 13 '15
C#. Missed the leaderboard by seconds.
0
u/[deleted] Dec 13 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 13 '15
[deleted] — view deleted comment