-
Notifications
You must be signed in to change notification settings - Fork 0
/
day16.cpp
146 lines (117 loc) · 5.09 KB
/
day16.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*
--- 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 suspicious, 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?
*/
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include "main.h"
std::vector<bool> stringToBits( const std::string& startBits ) {
std::vector<bool> bits;
bits.reserve( startBits.size() );
for ( auto c : startBits ) {
bits.push_back( c == '1' ? true : false );
}
return bits;
}
std::vector<bool> dragonCurve( const std::vector<bool> input ) {
std::vector<bool> output( input );
output.reserve( input.size() * 2 + 1 );
output.push_back( false );
for ( auto iter = input.crbegin(); iter != input.crend(); ++iter ) {
output.push_back( ! *iter );
}
return output;
}
std::vector<bool> calculateChecksum( const std::vector<bool> bits ) {
assert( bits.size() % 2 == 0 );
std::vector<bool> csum( bits );
while ( csum.size() && csum.size() % 2 == 0 ) {
size_t destIndex = 0;
for ( size_t sourceIndex = 0; sourceIndex < csum.size();
sourceIndex += 2 ) {
if ( csum[ sourceIndex ] == csum[ sourceIndex + 1 ] ) {
csum[ destIndex ] = true;
} else {
csum[ destIndex ] = false;
}
destIndex ++;
}
csum.resize( destIndex );
}
return csum;
}
std::vector<bool> fillDisk( std::vector<bool> initialState, unsigned size ) {
std::vector<bool> bits( initialState );
while ( bits.size() < size ) {
bits = dragonCurve( bits );
}
bits.resize( size );
auto csum = calculateChecksum( bits );
return csum;
}
int mainfunc( std::istream& is, std::ostream& os, Part part ) {
std::string input;
is >> input;
unsigned length = part == Part::PART1 ? 272 : 35651584;
auto csum = fillDisk( stringToBits( input ), length );
for ( auto bit : csum ) {
os << ( bit ? '1' : '0' );
}
os << std::endl;
return 0;
}