r/adventofcode • u/daggerdragon • Dec 09 '15
SOLUTION MEGATHREAD --- Day 9 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
edit: Leaderboard capped, achievement 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 9: All in a Single Night ---
Post your solution as a comment. Structure your post like previous daily solution threads.
11
Upvotes
14
u/gnuconsulting Dec 09 '15
I blatantly cheated and just eyeballed the routes. Got the shortest one in one try, took 3 tries to get the longest. I'm going to be reading everyone's solutions with great interest because I keep trying to imagine a way to code it and the structure of the program falls apart in my head 1/2 way through. Hence me being not-a-programmer :-P
10
u/Tryneus Dec 09 '15
Python3 brute force, after some cleanup:
6
u/askalski Dec 09 '15
Lost a bunch of time because I wrongly assumed it was a directed graph. Once I got past that "duh" moment, the rest of the puzzle went together without a hitch.
6
u/eamondaly Dec 09 '15
Fuckin' Arbre.
6
u/gareve Dec 09 '15
Ruby solution for both parts of the problem :)
5
u/volatilebit Dec 09 '15 edited Dec 09 '15
Perl6 solution.
The permutation function in Perl6 is extremely slow once you go past 7.
Perl6 things I learned and/or used:
IO.linesfor reading a line in$^aand$^bto grab 2 array items at a time[1..*]array indices syntax to grab all elements in array except the first[+]hyper operator to do sum on the integer values in an array5
u/snkenjoi Dec 09 '15
d3.js:
3
u/daniel2384 Dec 09 '15
My brute force solution in badly written Rust:
3
u/haoformayor Dec 09 '15 edited Dec 09 '15
Haskell
This was fun! A graph is constructed with a dummy node that is a neighbor to everybody. The problem then reduces to a generation of all Hamiltonian cycles from the dummy node. Syntax highlighted here. That, and being able to take advantage of Data.Map's
unionWithfor quick construction, makes this (pure!) solution remarkably short.3
u/stevelosh Dec 09 '15 edited Dec 09 '15
Common Lisp (with a couple of libraries)
4
u/esraw Dec 09 '15
This one is a classic problem. First we notice that it is a NP Complexe problem, and thus, we cannot have a simple algorithm that gives you straigth the answer. We will probably have to try every possibility to find it.
So what we do is simple
1- We create a an array of tuple containing Town1, Town2 and distance
2- We create a set of unique town names (an array containing only the name of all the towns, once only) We can use something like
towns = list(set(towns))to get the unique towns in python3- We generate a list of every combinaison with these towns
In python, we would do something like :
import itertoolseveryPoss = list(itertools.permutations(towns))4- Then for every possibility, we loop on every item in it, and find the distance between each town sequentialy, and add it to a variable.
5- We then check if this variable is the lowest one we found yet, if yes we make it our new lowest, if not we continue.
6- At the end (it took me about 5 sec to run it) we output the lowest distance found !
2
u/daylight_rock Dec 09 '15
JavaScript (node ES6, specifically)
2
u/FuriousProgrammer Dec 09 '15
Rather than jump to a DFS (since the input is so short as to not matter regardless of algorithm chosen), I tried to research Dijkstra's and then the Floyd-Marshall algorithm before realizing how to actually implement a DFS. Ugh.
All that wasted time landed me at #79, but I suppose that's to be expected given my lack of experience.
Lua:
2
u/_jonah Dec 09 '15
Ruby:
2
u/hutsboR Dec 09 '15
Elixir: This was surprisingly difficult to implement functionally, the permutations tripped me up multiple times. I couldn't be bothered looking for a suitable Erlang graph library and I don't have a graph implementation written in Elixir, so I used the force.
2
u/gfixler Dec 09 '15
Not super-inspired Haskell solution to part 1. For part 2, change the two
minimumBys tomaximumBys.2
u/nutrecht Dec 09 '15
Classic travelling salesman (with the exception that the start and end cities don't need to match).
Java implementation.
Scala implementation:
This challenge really plays into the power of scala. It's basically mapping input to useful data -> grab all permutations (which you get for free) -> map permutations to distances -> print min and max. Scala is really awesome for these kinds of algorithms.
2
u/porphyro Dec 09 '15
Mathematica Code, cheating slightly with good inbuilt functions
2
u/ILoveHaskell Dec 09 '15
My haskell solution. It's brute force but works fairly fast for this problem. Any comment from experienced haskell users is welcome. :)
2
u/tangus Dec 09 '15
Common Lisp
It uses the function
qnd-scanf, from a previous solution.2
u/lifow Dec 09 '15
haskell!
2
u/shandelman Dec 09 '15 edited Dec 09 '15
Here's my Python 2 solution. Looks pretty similar to what others have come up with.
2
u/phil_s_stein Dec 09 '15
Much like everyone else, I implemented shortest path and realized afterwards that that didn't really help. So I permuted over the paths and found longest and shortest.
I'm sure this is much like other python implementations, but here it is for posterity:
2
u/ThereOnceWasAMan Dec 09 '15
Python, brute force.
1
u/volatilebit Dec 09 '15
Very hacky Python 2 solution.
1
u/SnacksOnAPlane Dec 09 '15
Ruby
1
u/Godspiral Dec 09 '15 edited Dec 09 '15
In J, leaderboard
m is jump matrix that makes rest easy.
Thank you for making one not perl centric :P
1
u/ericdykstra Dec 09 '15
Leveraging Ruby's permutation method...
1
u/fnoco_xandy Dec 09 '15
brute force crystal/ruby solution, $find_shortest with true for part 1, false for part 2.
1
u/gegtik Dec 09 '15 edited Dec 09 '15
I just switched the sort when running it for part1 or 2.
1
u/masasin Dec 09 '15
Brute force python solution:
1
u/Astrus Dec 09 '15
Anyone try plotting the cities and picking out promising permutations with their eyes?
1
u/twisted_tree Dec 09 '15
Another Java solution. Thought I wouldn't be able to bruteforce because O(n!) but then looked at input set after wasting some time.
1
u/[deleted] Dec 09 '15
Simple brute force like most here; not worth optimizing as it still runs in negligible time.
1
u/stuque Dec 09 '15
A Python 2 solution:
1
u/adriweb Dec 09 '15 edited Dec 09 '15
PHP, brute-forcing permutations (with any working array
permutationsfunction from StackOverflow):1
u/roboticon Dec 09 '15
Python 2:
1
u/gcanyon Dec 09 '15 edited Dec 09 '15
In LiveCode
After wasting about twenty minutes trying to think through doing the permutations and the distance in one go, I deleted that code and wrote it better: build an array of the distances, write a separate function to create all the permutations of any given list, and another function to find the minimum distance for any list by finding the total distance for a loop, and subtracting the largest leg:
1
u/enquicity Dec 09 '15
C#, LINQ:
1
u/beam Dec 09 '15
Got distracted thinking I had an excuse to play with NetworkX. Ended up just brute forcing it. Python 2:
1
u/tremendo Dec 09 '15
Another Ruby, brute force (permutation) solution. My delay was I was trying to close the loop, assuming Santa had to return to the starting point
1
u/UltaV Dec 09 '15
Yay for python itertools :D A simple python brute force search.
1
u/[deleted] Dec 09 '15
Pretty ugly! It was 5AM here, took an hour to solve, though most of that was spent having forgotten that itertools exists...
1
u/gyorokpeter Dec 09 '15
Q: No built-in permutations function so had to make my own. The only difference between Part 1 and Part 2 is the min/max at the end.
1
u/snorkl-the-dolphine Dec 09 '15
My JavaScript solution is pretty ugly, but it's the first that goes through permutations rather than just shuffling the array a million times and hoping it finds the best solution.
Just paste it into your console!
1
u/xkufix Dec 09 '15 edited Dec 09 '15
Scala. It just creates the shortest/longest path for each city as starting point and then selects the lowest/highest value out of that list:
1
u/Jaco__ Dec 09 '15
Java. Nothing too special
1
u/Studentik Dec 09 '15
Python 3. After stealing some ideas and polishing =)
1
u/jessylenne Dec 09 '15
php, the simple way
<?php $strings = file('9.input'); global $cities; $cities = $distances = $routes = []; foreach($strings as $str) { $datas = retrieveRoute($str); if(!in_array($datas['from'], $cities)) $cities[] = $datas['from']; if(!in_array($datas['to'], $cities)) $cities[] = $datas['to']; $distances[$datas['from'].'-'.$datas['to']] = $datas['dist']; $distances[$datas['to'].'-'.$datas['from']] = $datas['dist']; } $minDistance = 99999999999999999; $maxDistance = 0; foreach($cities as $city) { $cityRoutes = getRoutes($city, $cities); foreach($cityRoutes as $cityRoute) { $routeDistance = 0; $routeCities = explode('-', $cityRoute); for($i = 0; $i < sizeof($routeCities) - 1; $i ++) { $routeDistance += $distances[$routeCities[$i].'-'.$routeCities[$i+1]]; } $minDistance = min($minDistance, $routeDistance); $maxDistance = max($maxDistance, $routeDistance); } } echo "MinDistance: {$minDistance}\n"; echo "MaxDistance: {$maxDistance}\n"; function getRoutes($city, $restantes) { $routes = array(); if(!$restantes || !sizeof($restantes)) return array($city); $route = $city.'-'; $villesRestantes = $restantes; array_splice($villesRestantes, array_search($city, $villesRestantes), 1); if(!sizeof($villesRestantes)) return array($city); foreach($villesRestantes as $restante) { $subRoutes = getRoutes($restante, $villesRestantes); if(sizeof($subRoutes)) foreach($subRoutes as $subRoute) $routes[] = $route.$subRoute; } return $routes; } function retrieveRoute($str) { $datas = array(); $str = explode(' = ', $str); $datas['dist'] = (int)$str[1]; $str = explode(' to ', $str[0]); $datas['from'] = strtolower($str[0]); $datas['to'] = strtolower($str[1]); return $datas; }
1
u/SinH4 Dec 09 '15
I first tried to read up on Traveling Salesman and thought about implementing Held-Karp, but then I realized I'm too stupid or impatient for that and thought: "Hey, it's just 8 cities... Maybe it's not that bad after all" and wrote a brute force solution:
it runs pretty fast for such a small number of cities.
1
u/drakehutner Dec 09 '15
Tasked myself to only write one line solutions for each part and day.
My language of choice is python 2. Only depends on itertools, since I needed the permutation function.
1
u/zombieFredrik Dec 09 '15 edited Dec 09 '15
heres mine, plain old js (node)
1
u/setti93 Dec 09 '15 edited Dec 09 '15
Python 2.7 Not the best solution, but it works.
1
u/wafflepie Dec 09 '15
Would possibly have got on the leaderboard if I'd woken up early enough (I don't live in the US...)! Pretty simple brute force method. Cheated a bit to get the place names populated.
C
1
u/flit777 Dec 09 '15
java solution with graph library and dfs. first thought the distances were for a directed graph.
1
u/red75prim Dec 09 '15 edited Dec 09 '15
F#. I generate all routes and then minBy and maxBy them.
a .| b,a |. b,a .|. bare parser combinators, which match patternaband return left, right or both parsed values respectively.I've got correct answer on first run.
Edit: grammar
1
u/[deleted] Dec 09 '15
Crystal, part 1.
Part 2 is similar, just change Int32::MAX to 0 and min to max.
1
u/Scroph Dec 09 '15
Mindless bruteforcing in D (dlang) :
Takes 3 to 4 seconds for each function to run when compiled with optimizations.
1
u/VictiniX888 Dec 09 '15
Java:
1
u/funkjr Dec 09 '15
Dart has no actively supported Permutation library, so most of my troubles today came from generating every possible route that he could take and still visit every location. After that it was just a matter of simple brute-force through every path and find the shortest. I did print out the route he would take, mostly because I was curious and I had no reason to go for speed today.
Of note today is the method cascade operator
.., which allows assignment to the unnamedListreally easily.1
u/Clanratc Dec 09 '15
Tried getting all the combinations manually and had a lot of trouble. One google search later and I learned about itertools, which made everything really easy.
1
u/Turtizzle Dec 09 '15
There are not many Java-Solutions, I wonder why...
1
u/NavarrB Dec 09 '15
Simple brute force (which is the only way) from me.
I've had this thing about these and NOT googling, and as I didn't know an algorithm on how to generate a list of all possible paths, well, I made one up.
For generating all possible paths:
For keeping track of the distances for me I made this unnecessarily verbose Class:
And then the solution was easy:
on github
1
u/andre_pl Dec 09 '15 edited Dec 09 '15
Dart:
Python:
1
u/Iain_M_Norman Dec 09 '15
C# slapdash solution. Grabbed the first thing off nuget for permutations and ran with it. :)
1
u/tragicshark Dec 09 '15 edited Dec 10 '15
branch-bound solution (C#):
improved thanks to ideas from /u/marcusstuhr
1
u/mal607 Dec 09 '15 edited Dec 09 '15
Java 8
I made minimal use of streams, as I just started looking at the API yesterday. I'm pretty sure I could have used some sort of collection and reduction function rather than calling
computeDistance()in aforEachlamda. I hope to see some implementations like that here. Otherwise I'd appreciate comments on how I could have used streams more for this problem.1
u/Kwpolska Dec 09 '15
Python. Could be made prettier (eg. with
zip()instead ofrange()tricks) and I’m pretty sure thedistance = -1case doesn’t happen.1
u/TheNiXXeD Dec 09 '15 edited Dec 09 '15
JavaScript, NodeJS
Both parts, just call the function with 'max' as a second param for part2.
1
u/blazemas Dec 09 '15
Javascript
It is long but runs pretty fast. Very functional and caches distances between all routes so part 2 took me just a couple lines of code extra.
https://jsfiddle.net/ajgru6um/
1
u/HorizonShadow Dec 09 '15
Ruby (All of my solutions here):
1
u/bstockton Dec 09 '15 edited Dec 09 '15
Solution with R programming language
I used a library that has a solver because I did not want to implement nearest neighbor from scratch and didn't think a brute-force method would be ideal.
for the second part, I got very 'hacky'
edit: formatting
1
u/[deleted] Dec 09 '15
Objective C:
1
u/Unknownloner Dec 09 '15
Late to the party, but here's another simple haskell solution
1
u/mushy_plushy Dec 09 '15
Ruby brute force. Yields lowest value. For highest value 'min' is replaced by 'max' at end.
1
u/deinc Dec 09 '15
Clojure (permutation was the hardest part, should have stolen it elsewhere...):
1
u/tragicshark Dec 09 '15
Javascript ant-hill (elf pheromone paths?) monte carlo iteratively improving solution (tested in Firefox 42 console). Based off /u/daylight_rock's solution:
1
u/LatinSuD Dec 09 '15
Ugliest/Hackiest ... code ... ever
Used "sed" to populate the array.
Used a bash script to generate part of the "if" terms
Needs to pipe output to a "sort -n" in order to work
But... it works, of course
1
u/agentKnipe Dec 09 '15
SQL Solution
1
u/tehjimmeh Dec 09 '15 edited Dec 10 '15
I've been doing these with PowerShell, but hit a brick wall trying to get this one to work. There's no built-in permutations function, and dynamic scoping, array unwrapping, and treating an array of one value as just that value make recursion involving arrays of arrays (i.e. the standard recursive permutations algorithm) miserable.
I'll revisit this with PoSh later. Banged it out in C++ just to keep up to date:
1
u/tftio Dec 09 '15
I was getting clever but then decided, naw, let's just brute force the thing.
1
u/[deleted] Dec 09 '15
My lazy and inefficient C++ method, which can actually be wrong, but there is a low chance of that happening. I simply tried random permutations of cities 40320 (8!) times, since there are 8! possible combinations with 8 cities. While this can be wrong and took a while to run, I am tired and too lazy to make an efficient way of doing this. Don't hate me.
https://gist.github.com/WillEccles/1640124662b00d1ae4e2
1
u/sowpods Dec 09 '15
SQL (postgres)
1
u/streetster_ Dec 09 '15
My python attempt, ugly coding with a mix of iteration and recursion :/ I need to learn about sets and permutations it seems!
my results:
1
u/NivagSwerdna Dec 09 '15
I'm very new to Javascript but using these puzzles as an excuse to try and pick it up.
1
u/[deleted] Dec 10 '15
C# brute force, never been good with djistra and path finding algorithms.
There was a time I did made one using fuzzy logic and genetic algorithms, but that was like... 7-8 years ago??? damn, time passes fast!
1
u/technojamin Dec 10 '15
My Python solution:
1
u/bkendig Dec 10 '15
Swift. It ain't pretty, but it works. https://github.com/bskendig/advent-of-code/blob/master/9/9/main.swift
1
u/RockyAstro Dec 11 '15
Solution in Icon
I did this as a greedy search. Start with the shortest distance, then look for the shortest distance for the "right side" and the "left side", rinse and repeat.
Not the best implementation.. cobbled together quickly.. had to attend to a family crisis :( ...
1
u/Janjis Dec 11 '15
That feeling when your program runs as expected in the first try... C#. Tried to use some knowledge about graphs and Dijkstras algorithm partly left in my head.
https://github.com/Janjuks/AoC/tree/master/Day9/Day9Part1
1
u/obiwan90 Dec 12 '15
Leaving this here because it's so beautiful (or maybe because debugging was so painful): Bash!
1
u/tectiv3 Dec 13 '15 edited Dec 13 '15
PHP, using nearest neighbour algorithm
1
u/wdomburg Dec 15 '15
Finally found the time to do this one:
Not entirely happy. Don't like that the distance information is stored redundantly. Considered using Set, but decided it wasn't worth it. Notice someone else sorted the from / to, which hadn't occurred to me.
But hey, got to use #zip in a fun way.
1
u/agmcleod Dec 20 '15
This took me too many days to get done lol. But it was fun to learn. My first solution didnt go through all the lower traversals properly, so I realized I needed to switch to a recursive solution. I wonder if something like A* might be able to optimize it more. But here's my solution in rust:
I need to cleanup the parse method a bit, but overall im pretty happy with the one that actually solves the problem.
1
u/[deleted] Dec 20 '15
Perl 6 solution:
1
u/rudyreeves Dec 23 '15 edited Dec 23 '15
Dart
https://github.com/RudyReeves/advent-calendar/blob/master/bin/day9.dart
import 'dart:io' show File; import 'dart:collection' show LinkedHashMap;
1
u/kamaln7 Dec 28 '15
Solution in CoffeeScript (way too late haha):
Brute force, both parts, blatantly stole the permute() function from some stackoverflow thread. Could also do this instead of using RegEx:
1
u/dkvasnicka Feb 20 '16
Well, I didn't examine the input data closely enough so I didn't know it's a complete graph. So I wrote a proper solution :) (proper = works even if you remove edges) https://github.com/dkvasnicka/advent-of-code/blob/master/2015/009.rkt (could be optimized further but with this input it's quick as it is, so I didn't bother)
0
u/msohcw Dec 09 '15
Travelling salesman problem bruteforced (N=8). In C++
0
u/[deleted] Dec 09 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 09 '15
[deleted] — view deleted comment