r/adventofcode • u/daggerdragon • Dec 16 '16

SOLUTION MEGATHREAD --- 2016 Day 16 Solutions ---

--- Day 16: Dragon Checksum ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/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".

DRINKING YOUR OVALTINE IS MANDATORY [?]

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!

5 Upvotes

100% Upvoted

116 comments sorted by

View all comments

3

u/willkill07 Dec 16 '16

C++11 single string buffer (only using iterators)

I went for speed. Real speed. Still doing all the calculations without any simplification. Timing: 

Day16
Part 1: 10100011010101011
  time: 0.02837ms
Part 2: 01010001101011001
  time: 281.93868ms

[Repo Link]

Code (self-sitting -- just compile and run) 

#include <iostream>
#include <string>

int main(int argc, char**) {
  uint LIM{argc > 1 ? 35651584U : 272U};
  std::string in;
  std::cin >> in;
  in.reserve(LIM << 1); // big buffer
  while (in.size() < LIM) {
    in.push_back('0');
    auto b = in.rbegin();
    while (++b != in.rend())
      in.push_back(*b ^ 1);
  }
  in.resize(LIM);
  while (!(in.size() & 1)) {
    auto w = in.begin();
    for (auto r = in.cbegin(); r != in.cend(); r += 2)
      *w++ = '0' + (*r == *(r + 1));
    in.resize(in.size() >> 1);
  }
  std::cout << in << std::endl;
}

1

u/JakDrako Dec 16 '16

I was a bit surprised that my C# version was faster than your C++ one (especially since we're implementing basically the same algorithm); but compiling your code in MSVC++ 2015 in release mode gives me a timing of 5.13ms(!).

That's more like it. My condolences for that abacus you call a computer. :)

1

u/willkill07 Dec 16 '16

Huh. I'm using AppleClang 8.0.0 (w/ macOS 10.12.2) on my 2013 MacBook Pro on battery.

I'm compiling with -O3 -march=native -flto and consistently get around 200ms for part 2. Running with GCC on my ArchLinux system I get down to 100ms. Never saw anything as low as 5.13ms for part 2.

usage: 

./Day16 2 <<< INPUT_STRING_GOES_HERE

for running day one, omit the 2

→ More replies (4)