Sean McLemon | Advent of Code

2019-12-16 - Flawed Frequency Transmission

(original .ipynb)

Day 16 puzzle input is a long sequence of digits (mine is here) which represent a noisy input signal from a sensor. Part 1 involves applying an algorithm to process the signal and generate an output signal and returning the first 8 digits of it. Part 2 involves applying the same algorithm to your signal repeated 1000x its original length, and taking the first 8 digits (after a 7 digit offset, which is the first set of value in the signal). I did not like this one.

def pattern_for_position(position):
    return [ 0 ] * position + [ 1 ] * position + [ 0 ] * position + [ -1 ] * position
    
def pattern_generator(position):
    while True:
        for pattern in pattern_for_position(position):
            yield pattern

def final_digit(n):
    return str(n)[-1]
            
def apply_fft_phase(signal):
    signal_digits = [ int(d) for d in signal ]
    processed_signal = []
    
    # maybe use range, no need to enumerate here as we discard the element
    for i, _ in enumerate(signal_digits):
        pattern = pattern_generator(i + 1)
        
        # always skip the first one
        next(pattern)
        
        total = sum([ next(pattern) * d for d in signal_digits ])
        processed_signal.append(final_digit(total))
    
    return "".join(processed_signal)


def process_signal(signal, phases, first_digits=None):
    
    for n in range(phases):
        signal = apply_fft_phase(signal)

    if first_digits:
        return signal[:first_digits]
    
    return signal
    

assert "01029498" == process_signal("12345678", 4)
assert "24176176" == process_signal("80871224585914546619083218645595", 100, 8)
assert "73745418" == process_signal("19617804207202209144916044189917", 100, 8)
assert "52432133" == process_signal("69317163492948606335995924319873", 100, 8)

puzzle_input = open("puzzle_input/day16.txt", "r").read()

print(process_signal(puzzle_input, 100, 8))

12541048

def process_repeating_signal(signal, phases, repeating, offset=0, first_digits=None):
    
    for n in range(phases):
        signal = apply_fft_phase(signal, offset)

    if first_digits:
        return signal[offset:first_digits]
    
    return signal

assert "01029498" == process_repeating_signal("12345678", 4, 1, 0)
assert "24176176" == process_repeating_signal("80871224585914546619083218645595", 100, 1, 0, 8)
assert "73745418" == process_repeating_signal("19617804207202209144916044189917", 100, 1, 0, 8)
assert "52432133" == process_repeating_signal("69317163492948606335995924319873", 100, 1, 0, 8)

# trying the above out showed that this is an extremely slow method however it turns out that with
# large enough `offset` we can skip a WHOLE bunch of calculations mostly because when we repeat 
# the signal, the offset occurs during the [...1,1,1,1...] parts of the pattern
#
# ... and I had to look this up on Reddit :-(


# I thought an fft was already fast
def apply_fast_fft_phase(digits, offset):
    total = sum(digits[offset:])
    
    # add the 0-padding
    next_digits = [0] * offset
    
    # the first of the next digit is just the last digit of the sum of the previoufasdasdfj kill me
    next_digits.append(int(final_digit(total)))

    for n in range(offset + 2, 1 + len(digits)):
        total -= digits[n - 2]
        next_digits.append(int(final_digit(total)))

    return next_digits

def fast_process_signal(signal, phase):
    signal_digits = [ int(d) for d in signal ]
    offset = int(signal[0:7])
    
    while phase > 0:
        signal_digits = apply_fast_fft_phase(signal_digits, offset)
        phase -= 1

    return "".join([str(d) for d in signal_digits[offset:(offset+8)]])

print(fast_process_signal(puzzle_input * 10000, 100))

62858988