Day 16: Flawed Frequency Transmission

My approach was straightforward: create a function fft_base_pattern that can expand the base pattern for the appropriate position, then loop through the input, multiply each digit by the matching value from the base pattern, sum all the results, take the abs (since some will be negative) then return the last digit of each.

Already this is a little slow, but it gets the job done.

#!/usr/bin/env crystal
require "../lib/utils.cr"

def split(str)
  str.chars.map { |c| c.to_i }
end

def fft_base_pattern(n) # return an interator
  base = [0,1,0,-1]
  base.map { |b| [b] * (n + 1) }.flatten.cycle.skip(1)
end

def fft_phases(list : Array(Int32), n)
  n.times do
    list = list.map_with_index { |v, idx|
      list.zip(fft_base_pattern(idx)).map { |pair|
        l, p = pair
        l * p
      }.sum.abs % 10
    }
  end
  list.join[0..7]
end

# p1
input = split(Utils.get_input_file("day16/input.txt"))
puts "Part 1: %i (input size %i)" % [fft_phases(input, 100), input.size]

We're going to need to massively optimize the first part, and there's a few things that work in our favor, the first relates to how the base pattern expands for each index.

In my case it helped to generate a table of patterns for each digit:

# 10.times do |i|
#   pattern = fft_base_pattern(i)
#   puts pattern.first(10).map { |i| "%2i" % i }.join(", ")
# end
#
# 1,  0, -1,  0,  1,  0, -1,  0,  1,  0 #  1
# 0,  1,  1,  0,  0, -1, -1,  0,  0,  1 #  2
# 0,  0,  1,  1,  1,  0,  0,  0, -1, -1 #  3
# 0,  0,  0,  1,  1,  1,  1,  0,  0,  0 #  4
# 0,  0,  0,  0,  1,  1,  1,  1,  1,  0 #  5
# 0,  0,  0,  0,  0,  1,  1,  1,  1,  1 #  6 
# 0,  0,  0,  0,  0,  0,  1,  1,  1,  1 #  7
# 0,  0,  0,  0,  0,  0,  0,  1,  1,  1 #  8
# 0,  0,  0,  0,  0,  0,  0,  0,  1,  1 #  9
# 0,  0,  0,  0,  0,  0,  0,  0,  0,  1 # 10

Fortunately, my input (and I expect all of them) are constructed in such a way that the offset is more than halfway through the list. This means that 1) we can ignore the first part of the input (everything before the offset), and 2) everything after the offset is just going to be the sum of the following digits (mod 10).

Unfortunately, even with the realization that we "simply" have to sum the digits of the latter part of the input, my code was too slow, and I needed to improve it a bit more. The last change I needed to make was to pre-compute the "sum of following digits" for each value past the offset. The pre-compute step has to be fast too, and can be optimized by doing it in reverse, which allows us to easily re-use the sum of the previous position.

# p2

#input = split("03036732577212944063491565474664") * 10000
input = split(Utils.get_input_file("day16/input.txt")) * 10000
offset = input[0...7].join.to_i
puts "Offset: %i" % offset

# because of how the base pattern expands, beyond the halfway point the pattern
# for every digit n will be n-1 0s followed by 1s for the rest of the list. This
# means that the transformation for a digit n (n > size/2) is simply the sum of
# the following digits.

def p2_fast_fft_offset(numbers, offset)

  100.times do |phase|
    puts "> #{phase}" if phase % 10 == 0

    # the list of sums will the same for each digit, so we can save some time by
    # precomputing
    #
    # precomputed = numbers[offset...].map_with_index { |n,i| numbers[offset+i...].sum }
    #
    # however even precomputing like this is slow, we can do it faster in
    # reverse since that allows us to easily peek at the most recently computed value
    precomputed = [numbers.last]
    numbers[offset...numbers.size-1].reverse.each do |n|
      precomputed << precomputed.last + n
    end
    precomputed.reverse!

    next_phase = numbers[0...offset] + numbers[offset...].map_with_index { |n,i| precomputed[i] % 10 }

    numbers = next_phase
  end

  numbers[offset...offset+8].join
end

puts "Part 2: %i" % p2_fast_fft_offset(input, offset)