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:
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:
11, 00, 10, 11, 01, 00.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:
10000 is too short, we first use the modified dragon curve to make it longer.10000011110 (11 characters), still too short.10000011110010000111110 (23 characters), which is enough.10000011110010000111.0111110101, which 10 characters long (even), so we continue.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?
At first look, this looks to be too trivial to be a problem for day 16. Surely, it is far too easy to take a string, then create a reverse of it, flip its bits, and join it together with '0' in between. And continue doing so until it is at least of the specified length, after which we discard the remaining characters. The checksum is merely a '1' or '0' depending on whether the two characters are same are not. Oh, and once you've calculated that, you also need to check if the checksum is even, because if it is, then calculate it again.
Since this is so trivial, I'll let the code speak for itself.
In [1]:
DISK_LENGTH = 272
In [2]:
def invert(string):
return ''.join(('1' if x == '0' else '0' for x in string))
In [3]:
print(invert('111100001010'))
In [4]:
def fill_disk(string):
while(len(string) < DISK_LENGTH):
string = string + '0' + invert(string[::-1])
return string[:DISK_LENGTH]
In [5]:
with open('../inputs/day16.txt', 'r') as f:
input_data = f.readline().strip()
string = fill_disk(input_data)
In [6]:
print('string length: ', len(string))
print(string)
In [7]:
def create_checksum(string):
checksum = []
for index in range(0, len(string), 2):
if string[index] == string[index + 1]:
checksum.append('1')
else:
checksum.append('0')
if len(checksum) % 2 == 0:
return create_checksum(checksum)
return ''.join(checksum)
In [8]:
checksum = create_checksum(string)
In [9]:
print('checksum length', len(checksum))
print(checksum)
In [10]:
DISK_LENGTH = 35651584
In [11]:
string = fill_disk(input_data)
In [12]:
print('string length: ', len(string))
In [13]:
checksum = create_checksum(string)
In [14]:
print('checksum length', len(checksum))
print(checksum)
== END ==