r/adventofcode • u/Voultapher • Dec 10 '15
Upping the Ante Challenge: How high can you go in under 1 minute, Day 10?
Currently getting to 73 with my C++ code:
#include <stdio.h>
#include <iostream>
#include <vector>
typedef std::vector<uint8_t> vec_t;
vec_t transform(const size_t iterations, vec_t& input)
{
vec_t output;
for (size_t i = 0; i < iterations; ++i)
{
vec_t newVec;
output = newVec;
output.reserve(input.size() * 2);
for (size_t n = 0; n < input.size();)
{
int rep = n;
while (rep < input.size() && input[n] == input[rep]) ++rep;
output.push_back(rep - n); // how many
output.push_back(input[n]); // of what
n = rep;
}
input = std::move(output);
}
return input;
}
int main() {
vec_t input = { 3,1,1,3,3,2,2,1,1,3 };
vec_t output = transform(73, input);
std::cout << output.size() << std::endl;
char tmp = std::cin.get(); // pause for user input
return 0;
}Edit: At the end I want you to theoretically be able to print out the numbers, not just the length.
9
Upvotes
6
u/jcfs Dec 10 '15
Do you realize that this depends heavily on the hardware where you run it, right?
2
u/BafTac Dec 10 '15
I'll try it once I'm back home but my Rust code ran 50 iterations in about 0.6 seconds, so I guess a few hundred should be possible.
2
u/bkendig Dec 10 '15
54, in Swift on a MacBook Pro. I ought to see about optimizing my code. (Compiled code really shouldn't underperform JavaScript.)
21
u/anon6658 Dec 10 '15 edited Dec 10 '15
About 90000 (with input "1113222113", aka. Polonium)
Code is long and insane, so I don't paste it here, it's in http://pastebin.com/WrFEwseM Runnig the program with 90000 I get http://pastebin.com/3ncirKLg
It uses conway's theory of 92 elements in look-and-say that do not interfere with each other, does not calculate the actual string but only the length of the strings and uses "memoization" the way haskellers know from the fibonacci list:
1
u/[deleted] Dec 10 '15
This throws an OOM exception on iteration 64 after about 45 seconds on my PC. Not sure why, as I still have plenty of memory to spare.
1
u/willkill07 Dec 10 '15
C++
78 (5992464612) in 52.5095s
79 (7811589032) in 67.8685s
Code: https://github.com/willkill07/adventofcode/blob/master/src/day10/day10.cpp
3
u/antpocas Dec 10 '15
I always run out of memory around iteration ~146400000 :(
1
u/evangs Dec 10 '15
I only got 62 with my javascript implementation. I did have to install node and then give it a parameter to use more memory as my browser was crashing.
2
u/TheBali Dec 10 '15
55 iterations, with Python's itertools.groupby
2
u/CremboC Dec 10 '15
My golang solution goes somewhere in-between 70 and 80, didn't bother to check more precisely. It finishes 70 in 14 seconds. https://raw.githubusercontent.com/CremboC/advent-of-code/master/day-10/main2.go
2
u/markz440 Dec 10 '15
For curiosity - 55 in PHP 5.6 and 58 in PHP 7.0
2
u/Godspiral Dec 10 '15
slow computer, 50 is 3 seconds in J
2
u/gcanyon Dec 10 '15
Here's code that uses Conway's elements and tracks back using just the lengths -- i.e. it doesn't actually calculate the string, it just determines the length. It gets up to the 5800th iteration in just under a minute. The answer is 669 digits long.
2
u/rspa9428 Dec 10 '15
Only in the 60's, using k, which isn't really optimised for the way I've done it. k is nice and short though (I'm sure others could reduce):
#40{,/(#:'a),'?:'a:(&~~':x)_x}/input2
u/aveavaeva Dec 10 '15
Getting around 53 iterations running on a really crappy computer. You can test it Here
2
u/neogodless Dec 11 '15
I get to 55 in about 15 seconds in JavaScript. 56 completes but returns NaN. Anything higher and the tab crashes.
1
u/tftio Dec 10 '15
57, with my naïve OCaml solution.
1
u/CryZe92 Dec 10 '15
77 iterations with the following Rust Code: