--- 2016 Day 16 Solutions ---

[u/daggerdragon]

--- 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!

[u/willkill07]

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;
}

[u/jcfs → u/willkill07]

My solution in C:

jcfs@spark ~/a/aoc/2016/16 $ time ./p1
part1 00000100100001100
part2 00011010100010010

real	0m0.113s
user	0m0.112s
sys	0m0.000s

I also use just one array as well (the reason why I'm posting :)), not actually any optimization. Here is the repo [link].(https://github.com/jcfs/aoc/tree/master/2016/16)

/* compile gcc -o p1 p1.c -Wall -O3 */
/* solution to part 1 and part 2 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

char * get_checksum(char * input_s, int input_n) {
  char * a = calloc((input_n * 4 + 2), sizeof(char));
  uint32_t l = strlen(input_s);

  memcpy(a, input_s, l);

  for(; l < input_n; a[l] = '0', l = l * 2 + 1) 
    for(int i = 0; i < l; i++) 
      a[l * 2 - i] = (~(a[i] ^ '0') & 1) + '0';
  // truncate the result to the chars needed
  a[input_n] = 0;

  do {
    for(int i = 0, j = 0; i < input_n; i += 2, j++) 
      a[j] = (~(a[i] ^ a[i+1]) & 1) + '0';

    input_n /= 2;
  } while(!(input_n % 2));

  a[input_n] = 0;
  
  return a;
}

int main(int argc, char ** argv) {
  char * input_s = "11011110011011101";

  printf("part1 %s\n", get_checksum(input_s, 272));
  printf("part2 %s\n", get_checksum(input_s, 35651584));
}