# --- Day 16: Dragon Checksum ---
#
# You're done scanning this part of the network, but you've left traces of your presence. You need
# to overwrite some disks with random-looking data to cover your tracks and update the local
# security system with a new checksum for those disks.
#
# For the data to not be suspiscious, it needs to have certain properties; purely random data will
# be detected as tampering. To generate appropriate random data, you'll need to use a modified
# dragon curve.
#
# Start with an appropriate initial state (your puzzle input). Then, so long as you don't have
# enough data yet to fill the disk, repeat the following steps:
#
#
# Call the data you have at this point "a".
# Make a copy of "a"; call this copy "b".
# Reverse the order of the characters in "b".
# In "b", replace all instances of 0 with 1 and all 1s with 0.
# The resulting data is "a", then a single 0, then "b".
#
# For example, after a single step of this process,
#
#
# 1 becomes 100.
# 0 becomes 001.
# 11111 becomes 11111000000.
# 111100001010 becomes 1111000010100101011110000.
#
# Repeat these steps until you have enough data to fill the desired disk.
#
# Once the data has been generated, you also need to create a checksum of that data. Calculate the
# checksum only for the data that fits on the disk, even if you generated more data than that in
# the previous step.
#
# The checksum for some given data is created by considering each non-overlapping pair of
# characters in the input data.  If the two characters match (00 or 11), the next checksum
# character is a 1.  If the characters do not match (01 or 10), the next checksum character is a
# 0. This should produce a new string which is exactly half as long as the original. If the length
# of the checksum is even, repeat the process until you end up with a checksum with an odd length.
#
# For example, suppose we want to fill a disk of length 12, and when we finally generate a string
# of at least length 12, the first 12 characters are 110010110100. To generate its checksum:
#
#
# Consider each pair: 11, 00, 10, 11, 01, 00.
# These are same, same, different, same, different, same, producing 110101.
# The resulting string has length 6, which is even, so we repeat the process.
# The pairs are 11 (same), 01 (different), 01 (different).
# This produces the checksum 100, which has an odd length, so we stop.
#
# Therefore, the checksum for 110010110100 is 100.
#
# Combining all of these steps together, suppose you want to fill a disk of length 20 using an
# initial state of 10000:
#
#
# Because 10000 is too short, we first use the modified dragon curve to make it longer.
# After one round, it becomes 10000011110 (11 characters), still too short.
# After two rounds, it becomes 10000011110010000111110 (23 characters), which is enough.
# Since we only need 20, but we have 23, we get rid of all but the first 20 characters:
# 10000011110010000111.
# Next, we start calculating the checksum; after one round, we have 0111110101, which 10
# characters long (even), so we continue.
# After two rounds, we have 01100, which is 5 characters long (odd), so we are done.
#
# In this example, the correct checksum would therefore be 01100.
#
# The first disk you have to fill has length 272. Using the initial state in your puzzle input,
# what is the correct checksum?
#
# --- Part Two ---
#
# The second disk you have to fill has length 35651584. Again using the initial state in your
# puzzle input, what is the correct checksum for this disk?

require_relative 'input'

day = __FILE__[/\d+/].to_i(10)
input = Input.for_day(day)

puts "solving day #{day} from input:\n#{input}"

def expand(a)
  a + [0] + a.reverse.map{|d|1-d}
end

def expand_to(a, len)
  while a.length < len
    a = expand(a)
  end
  a.first(len)
end

CHECKDIGIT = { [0,0] => 1,
               [0,1] => 0,
               [1,0] => 0,
               [1,1] => 1,
             }
def checksum(data)
  result = data.dup
  begin
    result = result.each_slice(2).map {|pair| CHECKDIGIT[pair] }
  end while result.length.even?
  result
end

# expand checks
[
  ['1', '100'],
  ['0', '001'],
  ['11111', '11111000000'],
  ['111100001010', '1111000010100101011110000'],
].each do |i,e|
  a = expand(i.each_char.map(&:to_i))
  if a.join == e
    puts "#{i} became #{a.join}"
  else
    puts "#{i} was #{a.join} but expected #{e}"
  end
end

# checksum checks
i = '110010110100'.each_char.map(&:to_i)
c = '100'
if c == checksum(i).join
  puts "#{i} generated #{checksum(i).join}"
else
  puts "#{i} generated #{checksum(i).join} expected #{c}"
end

# full check
l = 20
i = '10000'.each_char.map(&:to_i)
expected = '01100'
c = checksum(expand_to(i, l)).join
print "#{l} for #{i} checks to #{c}"
print " but expected #{expected}" unless expected == c
puts

initial = input.chomp.each_char.map(&:to_i)
l = 272
# what is the correct checksum?
puts "checksum for #{l} starting with #{initial.join} is: "
puts checksum(expand_to(initial, l)).join

l = 35651584
puts "checksum for #{l} starting with #{initial.join} is: "
puts checksum(expand_to(initial, l)).join
