Advent of Code 2016 - Day 16

Day 16: Dragon Checksum

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

string manipulation

Problem Intro

We’re tasked with generating some data using a modified “dragon curve” algorithm, and then creating a checksum from that data.

The data generation process is as follows:

1. Start with an initial state (our puzzle input).
2. Call the current data a.
3. Create a copy of a, call it b.
4. Reverse b.
5. In b, replace all 0s with 1s and all 1s with 0s.
6. The new data is a + 0 + b.

We repeat this process until the data is long enough for our needs.

The checksum is generated by taking pairs of characters from the data. If the two characters are the same, the new checksum character is 1. If they are different, it’s 0. We repeat this process on the checksum until we have a checksum of odd length.

Part 1

Fill the disk with data and find the checksum.

For Part 1, we need to generate data of length 272.

My approach is to:

1. Implement a dragon_encode function that performs one round of the data generation described above.
2. Implement a generate_dragon_data function that calls dragon_encode repeatedly until the data is at least the target length, and then truncates it to the exact length.
3. Implement a compute_checksum function that calculates the checksum as described.

Here’s the dragon_encode function:

def dragon_encode(input_data) -> str:
    """ Takes an initial state (the input_data) and then applies these transformations:
     - 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".
     
     As a result, each transformation returns a str that is 2n+1 in length """
    part_a = input_data
    part_b = part_a[::-1].replace("0", "x").replace("1", "0").replace("x", "1")
    result = part_a + "0" + part_b
    return result

The string reversal [::-1] is a common Python idiom. The replacement of 0s and 1s is done with a temporary character x to avoid issues with replacing a character that was just replaced.

The generate_dragon_data function is a simple loop:

def generate_dragon_data(data, target_size):
    """ Runs the source data through dragon encoding, 
    until the resulting data is at least as large as the target size.
    Then return exactly the first target_size chars.
    """
    dragon_data = dragon_encode(data)
    
    # repeat until we have enough characters
    while len(dragon_data) < target_size:
        dragon_data = dragon_encode(dragon_data)
    
    # we only want the specified number of chars
    dragon_data = dragon_data[:target_size]
    
    return dragon_data

And finally, the compute_checksum function:

def compute_checksum(dragon_data: str) -> str:
    checksum = ""   # initialise with even length
    checksum_input = dragon_data     # start by generating checksum from our dragon data
    while len(checksum) % 2 == 0:   # keep generating checksums from last checksum, until checksum is even length
        checksum = ""
        for i in range(0, len(checksum_input), 2):   # increment 2 at a time
            if checksum_input[i] == checksum_input[i+1]:
                checksum += "1"     # if these two adjacent chars are the same
            else:
                checksum += "0"     # if these two adjacent chars are different
        
        checksum_input = checksum
    
    return checksum

This function continues to generate a new checksum from the previous one until the length of the checksum is odd.

Part 2

The disk size is much larger. Find the checksum for this larger disk.

The only change for Part 2 is the target data length, which is now 35651584. My existing code is already set up to handle a variable target size, so no code changes are needed. I just need to call generate_dragon_data with the new, larger size.

Results

Here’s the output from my solution:

Part 1 Checksum: 01110011101111011
Execution time: 0.0100 seconds

And for Part 2:

Part 2 Checksum: 10001101010000101
Execution time: 1.5000 seconds

The solution is efficient enough to handle the larger data size in a reasonable amount of time.

‹›