Advent of Code 2016, Day 16: Dragon Checksum

Part A and B

On Day 16 we need to calculate checksum of large strings.

First we need to construct this string using modified dragon curve. You can check puzzle description for details.

Once the string has desired length we can calculate the checksum. For that we take a pair of bits and replace it with 1 if both bits match (00, 11) or with 0 if bits do not match (01, 10). We continue this process until we have output string of half size. If the size is even we repeat the process until the size will be odd. That will be our checksum.

Here is my solution:

def dragon(input)
  a = input
  b = input.reverse.tr("01", "10")
  [a, "0", b].join
end

def divisions(number)
  count = 0
  while number.even?
    number /= 2
    count += 1
  end
  count
end

def checksum_chunk(input)
  while input.size.even?
    puts "Current size = #{input.size}"
    checksum = ""
    (input.size / 2).times do |i|
      puts "Current index = #{i}" if i % 100_000 == 0
      if input[2 * i] == input[2 * i + 1]
        checksum += "1"
      else
        checksum += "0"
      end
    end
    input = checksum
  end

  input
end

def checksum(input)
  divisions = divisions(input.size)
  chunk_size = 2 ** divisions
  chunks = input.size / chunk_size

  (0...chunks).to_a.map do |chunk_index|
    puts "Calculating chunk #{chunk_index}"
    checksum_chunk(input[chunk_index * chunk_size, chunk_size])
  end.join
end

# length = 35651584
length = 272
input = "10010000000110000"

while input.size < length
  input = dragon(input)
end

input = input[0, length]
puts checksum(input)

I didn’t implement any efficient solution for this task. For length 272 it is fine, but for Part B (35651584) it takes a while.

How it works. We first calculate how many times we can divide given string. For 272 we can divide it 4 times. The goal is to figure out how many even chunks we can split our string. In this case we can split 272 string into 17 chunks each of size 16 bits.

Then for each chunk we can calculate its checksum until we reach just one bit. Then we join everything together.

But as I said it is not efficient.