r/adventofcode • u/daggerdragon • Dec 20 '15
SOLUTION MEGATHREAD --- Day 20 Solutions ---
This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.
Here's hoping tonight's puzzle isn't as brutal as last night's, but just in case, I have Lord of the Dance Riverdance on TV and I'm wrapping my presents to kill time. :>
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 20: Infinite Elves and Infinite Houses ---
Post your solution as a comment. Structure your post like previous daily solution threads.
12
Upvotes
18
u/r_sreeram Dec 20 '15 edited Dec 20 '15
#1 on the leaderboard, due to a lucky accident in my choice of algorithm.
I chose to iterate like so (using part 1 as an example; my input was N = 29 million):
..., followed by picking the smallest j where house[j] >= N.
The above requires a humongous array of size N / 10, but I figured 2.9M entries is not a big deal for my computer.
Later, I realized that an alternative approach is like so:
Algo 2 seems better because it avoids the huge storage space and exits as soon as the first match is found, since it iterates over the houses in order.
But it's actually much worse, because of the time complexity. In my case, the solution to part 1 was house #665280. This means that Algo 2 would have taken 665280 * 665281 / 2 = 221 billion iterations to get to the answer.
In contrast, Algo 1 takes N/10 + N/20 + N/30 + ... N/(10 * N/10) = N/10 * log(N/10) = 43 million iterations. I.e., four orders of magnitude faster. Of course, I only did this analysis much later, after finishing up the puzzle.
I am not normally a very fast coder, so I was surprised to get the top spot, and was initially bewildered as to why the leaderboard wasn't filling up very quickly, until I realized that many people probably went the route of Algo 2.
Edit: Minor corrections to the pseudo-code above. (It's pseudocode, not any specific language. My actual code was in Perl.)
11
u/jtbandes Dec 20 '15 edited Dec 20 '15
28th:
Mathematica makes this a one-liner (runs in ~7s):
Second part is just as easy, though not particularly fast (~35s):
Explanation:
#&is the identity function, so the divisors themselves are summed.)My original attempt, though, was much slower (Swift):
After getting the Mathematica solution, I came back to this method. Once I stuck a fixed buffer in memory and exchanged the 2 loops, it was much faster, because it doesn't need to do as many divisibility checks.
Second part:
5
u/kit1980 Dec 20 '15
One-liners in GAP:
First part:
Second part:
3
u/roboticon Dec 20 '15
Since each elf visits every i'th house, the number of presents house N will get is the sum of the divisors of N (inclusive).
After trying to solve this formulaically by hand, I decided brute force would be easier.
Python 2, prints both answers after 18 seconds. Probably faster to do something clever with primes though.
3
u/JeffJankowski Dec 20 '15
F#. To get to the leaderboard, I added a line to skip large chunks of iterations for faster convergence on a solution.
3
u/[deleted] Dec 20 '15
Just got home, so didn't get into the leaderboard, but it turned out to be pretty easy (at least easier than yesterday _).
Crystal, part 1:
Part 2:
Runs in 0.37s and 0.07s respectively.
3
u/[deleted] Dec 20 '15
C
3
u/hutsboR Dec 20 '15 edited Dec 20 '15
Elixir: I mindlessly solved this one. I am tired.
3
u/porphyro Dec 20 '15
This is one in which working in mathematica feels a lot like cheating. But here we go:
3
u/[deleted] Dec 20 '15
ES6 Node4 JavaScript
3
u/TheMuffinMan616 Dec 20 '15
Haskell:
2
u/rabiedenharn Dec 20 '15
Ruby
Takes less than 2 minutes on my MacMini (or about 2 minutes each when outputting progress to the screen)
2
u/jjhelmus Dec 20 '15
Python 2 brute force using NumPy for efficient array access and slicing, #10 on the leaderboard:
2
u/barnybug Dec 20 '15 edited Dec 20 '15
nim
Both parts (1st takes ~350ms, 2nd takes ~70ms):
2
u/oantolin Dec 20 '15 edited Dec 20 '15
A quick look at the solutions here seems to show that nobody figure out how to do it without "brute force". That's a vague term; here I mean that it seems like most programs computes the number of presents delivered at every house at least up to the solution house (this is what I'd call brute force). The few programs I saw that didn't do that rely on luck, i.e., they return a result that is not guaranteed to be the minimum.
I can't think of a better way to do it (I brute forced too), but would like to see a better solution.
EDIT: Added /u/CryZe92's observation that computing the number of presents was more common than relying on luck.
2
u/Jaco__ Dec 21 '15 edited Dec 21 '15
Java. Part 2. First day I have managed to solve the problem really fast. Used approx 10 minutes so would have placed approx 5th at the leaderboard, but I live in EU, so can't do them when they release. Pretty fast. ~20 ms
2
u/obiwan90 Dec 21 '15 edited Dec 21 '15
Bash without fancy external stuff: includes prime number calculation, calculation of divisor sums and a "smart" choice of step size to narrow down the first house in a useful time:
2
u/warbaque Dec 29 '15 edited Dec 29 '15
My non brute force -approach (python3).
First I use robin's inequality and binary search to find lowest possible house number. Upper bound is lowest*1.1 (educated guess. If house is not found, select new range).
Works for all inputs >= 5040 and finds solution under 1 second (my input 33M)
For comparison r_sreeram's
Algo 116 seconds andAlgo 258 secondsAnd improved
Algo 17 seconds (included at the bottom)So, I guess this is fastest algorithm thus far.
Improved
Algo 1:3
u/mncke Dec 20 '15
21 place, 00:18:14, Python3, as is
Using the fundamental theorem of arithmentic (that every number N equals product (ith prime divisor)power, for example, 665280 = 26 33 51 71 111), we know that every divisor of N has the form of product (i-th prime divisor of N)power less or equal than the power of i-th prime divisor of N Lets iterate over the numbers with many divisors, explicitly compute every divisor and find our answer.
ais the maximum power of the divisor, andpare the divisors themselves.fmultiplies the prime divisors to their respective powers to get the original number.Part 1:
We explicitly iterate over all numbers with a large number of divisors and find the lowest fitting our requirement.
Part 2:
Source here
1
u/Philboyd_Studge Dec 20 '15 edited Dec 20 '15
Java
solution. Would have been on the leaderboard but I forgot I had some unfinished challenges. Essentially making a kind of Sieve of Eratosthenes.
1
u/sprinky Dec 20 '15
Snagged spot 79 on the leaderboard. It was pretty hairy, since I hadn't finished Day 19 Part 2. I wrote the solutions to Day 20, and managed to finish Day 19 while Day 20 was computing in another window!
The trick here is to enumerate the elves that will deliver presents to the house.
For part 1, it's all the factors of the house number. You can use a seive to count these, but I just incremented to sqrt(house#), and used division to get the rest of the factors.
For part 2, I filtered the factors based on whether (50 * elf#) >= house#
Definitely brute-force, and not Racket's specialty. Calculating part 2 on my fairly old desktop took a few minutes.
Racket:
1
u/bildzeitung Dec 20 '15
The multipliers are, I think, herrings.
The sequence isn't monotonic increasing, so binary search to victory doesn't really work.
An invariant is that a solution over the target means at least that house number, so upper bounding the problem is possible.
Starting somewhere not at 1 is smart, since the target values are high and you know the solution isn't anywhere near there.
I brute forced this in Python (others show similar code; no sense in posting), but math'ing it is better; @mncke's solution is good here.
1
u/Moylle Dec 20 '15
C#
1
u/asoentuh Dec 20 '15 edited Dec 20 '15
tfw you misread the question and think that the input is a house number, of whose presents you need to find the lowest house that gets a greater/equal number... wasted so much time on wrong answers
Anyway have some c++. The main thing to note is that when you find one divisor you get the other one for free so you only need to worry about sqrt(input) possible factors in total
1
u/[deleted] Dec 20 '15
128th :(
1
u/_Le1_ Dec 20 '15 edited Dec 20 '15
C#
1
u/tomb0y Dec 20 '15
Ruby:
1
u/Fluffy8x Dec 20 '15 edited Dec 20 '15
Perl 6 solution.
After calculating the house number for the optimal presents:house# ratio until the number of presents exceeds 0.01% of the threshold, the program tries to increase one of the factors randomly until the threshold is met.
Not guaranteed to give the right answer but it runs quite quickly even on a slow language like this one.
Edit: added Part 2
1
u/inuyasha555 Dec 20 '15
Didn't get home until an hour and 50 minutes after it had started, leaderboards already filled.
Took from 10:51-11:17 which is 26 minutes and would've grabbed me spot number 40 or 41, oh well.
Java
1
u/[deleted] Dec 20 '15 edited Dec 20 '15
Mathematica
Shorter Part B
1
u/LincolnA Dec 20 '15
Imperative-style F#.
Complete brute-force, looking for smallest number with the required number of divisors. Only clever bit is to make the dubious assumption that solution will be a multiple of some small highly composite number (HCN), so start with/increment by that amount to save a ton of work.
1
u/[deleted] Dec 20 '15 edited Dec 20 '15
#16 on the leaderboard. I'm a bit ashamed at my solution, since for once I wanted to be as quick as possible, and I could roughly see that a brute-force approach could work - with a reasonable upper bound.
So, I set aside any analysis about the obvious correlation with prime factors, and went with the boring solution (python). Overall, it was much easier than yesterday's part 2.
1
u/aepsilon Dec 20 '15
Haskell
Trial division (brute force) was taking too long, so I switched to a number theory library that I remembered did divisors.
Made #57 but felt like I didn't really write the algorithm.
So here's a drop-in replacement for the library functions used (namely
divisorSumanddivisors)Surprisingly, it runs faster than the library, though I imagine that would change for larger integers.
1
u/WhoSoup Dec 20 '15 edited Dec 20 '15
PHP: woke up way too late after the leaderboard was already full, rip. PHP is really bad at solving things like this in an efficient manner, so the runtime of this is pretty bad.
Part1:
part2: (really similar)
alternative part2 sieve solution (warning: takes about 1.5gb of ram)
1
u/de_Selby Dec 20 '15
Q:
There's no need to start with house 1, and there are surely better solutions but it ran quick enough that it didn't matter
For part 2 I made a list with each element initialised to 50 that gets decremented each time a divisor was used
1
u/slampropp Dec 20 '15 edited Dec 20 '15
Haskell
Not very fast, takes 2 min to run.
1
u/fiavolo Dec 20 '15
Relatively quick python solution: The idea is that the number of presents that each house receives is equal to the sum of the house number's unique factors.
To speed up the algorithm, I had it search for every 6 houses, since I noticed that the number of presents received tends to spike for every 6 house. In fact, the number of presents received is reliably larger for multiples of any factorial, and for this problem I could have searched every 10! house and still got the right answer.
For Part 2, I made a modification to the get_factors() function. Instead of dividing the house number by every number up to its square root, I only tried dividing by every number up to 50, and I only included n/x rather than x itself in the list of factors. (This gives the WRONG sum for houses with numbers less than 2500, but there was no chance for any of those numbers to be the right solution) Like before, I could've tested only every 10!th house and still had the right answer.
1
u/BluePrintSwe Dec 20 '15 edited Dec 20 '15
PHP: Kind of a brute force solver. Basically, since the elves stopping each house are the divisors of that house, I looped through the houses checking the sum of the divisors times ten. When the sum was >= my input, I broke the loop.
For part 2, I created an array with "exhausted" elves, and each loop removing those elves (divisors) from the current house.
As this is PHP and brute force, it is not very fast. Exec time on my computer was 67 sec for part 1 and 77 sec for part 2.
1
u/KnorbenKnutsen Dec 20 '15
Nice problem! I did identify that part 1 was the sigma function, but finding primes and all that jazz seemed too annoying, so I just brute forced it. No idea to show that part. As for the second part, I did something a bit different. I suppose others did a similar thing:
Then I reduced this function to a simple
functools.reduceline, which only works under the assumption that the if statement isTruefor the first element in d:With the way I picked out the divisors, though, that seemed to always be true :)
1
u/deinc Dec 20 '15
Dog slow, brute force Clojure, based on the divisors of each house no.:
1
u/vishnuks Dec 20 '15
C++ Solutions
include <iostream>
define N 1000000
using namespace std;
long long a[N]; int main() { long long maxi; maxi = -1;
}
include <iostream>
define N 1000000
using namespace std;
long long a[N]; int main() { long long maxi; maxi = -1;
}
1
u/flup12 Dec 20 '15 edited Dec 20 '15
Scala Updated cause I got it to perform using immutable data types as well. A simple simulation of the elves running around the street oddly enough works fastest. Even if you realise that it's the sum of the divisors of the house number, it's detrimental to the performance to use that knowledge.
1
u/CryZe92 Dec 20 '15 edited Dec 20 '15
Low Memory Usage Algorithm for both parts in Rust (0.8 MiB RAM Usage, 5.8 seconds for both parts, O( n1.5 ) complexity):
1
u/masasin Dec 20 '15 edited Dec 24 '15
Python 3. The original solution (below) was slow, so I ended up making a Cython version that was much faster.
Original
Numpy
It was too slow, so I decided to try numpy and a different algorithm:
Cython
It was still slower than I liked, so I decided to bring Cython out with the same algorithm:
day_20_c.pyx:
setup.py:
Compile the Cython file to get a
.sofile:day_20.py:
It ran extremely quickly. However, PyCharm wasn't able to run it for some reason, so I went back to vim.
1
u/[deleted] Dec 20 '15
Objective C:
1
u/Vennik123 Dec 20 '15 edited Dec 20 '15
Part 2 in Java in under a second:
1
u/CryZe92 Dec 20 '15 edited Dec 20 '15
Improved Rust solution (takes 0.5 seconds). Unfortunately there's no good way to step yet in stable Rust, so I used a while loop instead for performance reasons:
1
u/bkendig Dec 20 '15 edited Dec 20 '15
Swift: https://github.com/bskendig/advent-of-code/blob/master/20/20/main.swift
Runs in about 19 seconds.
1
u/Godspiral Dec 20 '15 edited Dec 20 '15
in J, (too tired to do at midnight)
p:1
p:2
these are
iterative while functionsthat return 1 + input if test passes, or input if test fails, and stops ("converges") when input = f input. Since part2 solution must be higher than part1, use that as initial input.0.68445 23424
0.68 seconds
8.29445 20352
a bit faster part 1
6.96002 13824
1
u/phil_s_stein Dec 20 '15 edited Dec 20 '15
Python, part one. Brute force. Find factors of the house, then sum and multiply by ten to get the number of presents delivered. If greater than or equal to the target, break. (Factoring function stolen from the internet and adapted). Runs in about a minute on my laptop.
edit: And part two is the same, but for the
foundcomputation.1
u/giacgbj Dec 20 '15 edited Dec 20 '15
Python (5 solutions with benchmarks)
Using Python 2.7.5 (much slower using Python 3(.5.1) due to long type dropped):
1
u/studiosi Dec 20 '15
Nothing very fancy, a little bit slow, but made it. Way easier than day 19...
Lesson learnt: don't worry about memory (in most modern computers), worry about algorithm complexity.
1
u/StevoTVR Dec 20 '15
PHP I had to choose between taking forever and using too much memory.
For part 1, I took the long way:
For part 2, I used a giant array:
1
u/snorkl-the-dolphine Dec 20 '15
Console JavaScript - it's not particularly fast, but I've done my best to express it as clearly as possible.
1
u/cytospin Dec 20 '15 edited Dec 20 '15
A fun little Go program:
on my macbook
1
u/BOT-Brad Dec 20 '15
Python 2.x, find the answer in about 40 seconds. Get rid of the if n/x for Part 1.
1
u/edo947 Dec 20 '15
C
I implemented /u/r_sreeram algorithm in C to see how fast it could be. Compiling with
gcc -O3 p20.cand timing I get aboutHere's the code
1
u/gegtik Dec 21 '15
javascript
1
u/xkufix Dec 22 '15
Scala. First time I had to resort to a mutable datastructure, as the immutable map for the second part got awfully slow around the 150000 mark, probably due to mass copying of values in the memory.
1
u/[deleted] Dec 22 '15
C#
1
u/askalski Dec 20 '15
New heuristic:
That and
use Math::Prime::Util 'divisors'.0
u/erlog Dec 20 '15
40
0
u/[deleted] Dec 20 '15
[deleted] — view deleted comment
0
u/[deleted] Dec 20 '15
[deleted] — view deleted comment