Advent of Code, Day 18

aoc-day-18.c

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>


const char input[] = "^^^^......^...^..^....^^^.^^^.^.^^^^^^..^...^^...^^^.^^....^..^^^.^.^^...^.^...^^.^^^.^^^^.^^.^..^.^";
//const char input[] = ".^^.^.^^^^";
const uint64_t nrows = 100000000000;


typedef uint16_t row_word_t;

#define BITS(word) (sizeof(word) * 8)

#define LUT_INPUT_BITS (BITS(row_word_t) + 2)

#define LUT_SIZE (((uint32_t)1) << LUT_INPUT_BITS)

typedef struct {
  row_word_t out;
  char cnt;
} lut_t;


const int rules[] = {
      0x6, /* ^^. */
      0x3, /* .^^ */
      0x4, /* ^.. */
      0x1  /* ..^ */
};
const int nrules = 4;


static int highBitSet(row_word_t word) {
  return (((word >> (BITS(word) - 1)) & 1) != 0);
}

int shiftleft(row_word_t words[], int nwords, int newbit) {
  int carry = newbit;
  for(int i = 0; i < nwords; i++) {
    int willCarry = highBitSet(words[i]);
    words[i] = words[i] << 1;
    if(carry) words[i] |= 1;
    carry = willCarry;
  }
  return carry;
}






void printbits(row_word_t words[], int nbits) {
  for(int i = nbits - 1; i >= 0; i--) {
    int word = i / BITS(row_word_t);
    int bit = i % BITS(row_word_t);
    if(words[word] >> bit & 0x1) {
      putchar('^');
    } else {
      putchar('.');
    }
  }
  putchar('\n');
}

int main() {
  // How much space do we need?
  int nbits = strlen(input);
  int nwords = (nbits / BITS(row_word_t)) + 1;

  // Make space
  row_word_t words[nwords];
  for(int i = 0; i < nwords; i++) {
    words[i] = 0x0;
  }


  uint64_t total = 0;

  // Copy input into space
  for(int i = 0; i < nbits; i++) {
    switch(input[i]) {
    case '.':
      shiftleft(words, nwords, 0);
      break;
    case '^':
      shiftleft(words, nwords, 1);
      total++;
      break;
    }
  }


  printf("Building %i-entry LUT\n", LUT_SIZE);

  // Build the LUT with a 'slow' algorithm
  lut_t lut[LUT_SIZE];
  for(uint64_t addr = 0; addr < LUT_SIZE; addr++) {
    lut[addr].out = 0;
    lut[addr].cnt = 0;
    for(int i = BITS(row_word_t)-1; i >=0; i--) {

      // Take 3 bits
      int three = (addr >> i) & 0x07;

      // If a rule matches, this is a trap
      int trap =
	rules[0] == three |
	rules[1] == three |
	rules[2] == three |
	rules[3] == three;

      lut[addr].out = lut[addr].out << 1;
      if(trap) {
	lut[addr].out |= 0x01;
	lut[addr].cnt++;
      }
    }
  }  

  printf("Row %d: ", 0);
  printbits(words, nbits);

  row_word_t tmp[nwords];
  row_word_t *currentrow = words;
  row_word_t *nextrow = tmp;
  for(uint64_t i = 1; i < nrows; i++) {

    // This row is made of a number of words.
    for(int j = 0; j < nwords; j++) {

      // Take a word
      row_word_t word = currentrow[j];
      // use it as an address

      int addr = 0;

      // Add in the low bit from the next word
      if(j < nwords - 1) addr |= currentrow[j+1] & 0x1;

      // Get ready for the word
      addr = addr << BITS(row_word_t);

      // Put the word in, making room for the high bit from the previous word
      addr |= word;
      addr = addr << 1;

      // Shift in the high bit from the previous word
      if(j > 0) addr |= (currentrow[j-1] >> 7) & 0x1;

      // Get the result
      row_word_t out = lut[addr].out;
      total += lut[addr].cnt;

      // Mask
      if(j == nwords - 1) {
	int newout = out & ((1 << (nbits % BITS(row_word_t))) - 1);
	if(newout != out) {
	  total--;
	  out = newout;
	}
      }

      nextrow[j] = out;
    }
 
    // Print the row
    if(i%1000000 == 0) {
      printf("Row %" PRIu64 ": ", i);
      printbits(nextrow, nbits);
    }
    if(currentrow == tmp) {
      currentrow = words;
      nextrow = tmp;
    } else {
      currentrow = tmp;
      nextrow = words;
    }
  }

  uint64_t alltiles = nrows * (nbits);
  printf("Total traps: %" PRIu64 ", total tiles: %" PRIu64 ", total safe: %" PRIu64 "\n", total, alltiles, alltiles - total);
}