This year, I’m posting my solutions to the puzzles in the Advent of Code.
Click the link to view the puzzle and code, along with a link to the solution on Github.
And now, on with the solution:
Day 16, part 1
Simplified problem:
Starting with a string of 0 and 1 characters, process the input based on the following rules until the length of the string is greater than or equal to [value] (in this case, 272).
- 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
with1
and all1
s with0
. - The resulting data is “a”, then a single
0
, then “b”.
Once the string is long enough, calculate a checksum based on the following rules:
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
or11
), the next checksum character is a1
. If the characters do not match (01
or10
), the next checksum character is a0
. 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.
The checksum is calculated using the first [value] characters of the string.
What is the checksum of the data?
Day 16, Part 2
What is the checksum of the data using a string of length [largervalue] (in this case, 35651584)?
Solution
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 |
class Program { #region Fields // Puzzle input - Part 1 private const int DiskLengthPart1 = 272; // Puzzle input - Part 2 private const int DiskLengthPart2 = 35651584; private static readonly string _input = "11011110011011101"; #endregion static void Main(string[] args) { Console.WriteLine(TimeResult(1, DiskLengthPart1)); Console.WriteLine(TimeResult(2, DiskLengthPart2)); Console.ReadKey(); } private static string TimeResult(int part, int diskLength) { Stopwatch sw = Stopwatch.StartNew(); GetChecksum(part, diskLength); sw.Stop(); return $"Part {part} completed in {new TimeSpan(sw.ElapsedTicks):g}."; } private static void GetChecksum(int part, int diskLength) { string input = _input; // Generate random data until we have at least enough to fill the disk. while (input.Length < diskLength) { input = $"{input}0{new string(input.Reverse().ToArray()).Replace('1', '-').Replace('0', '1').Replace('-', '0')}"; } // Generate the checksum string checksum = GenerateChecksum(input.Substring(0, diskLength)); Console.WriteLine($"Part {part}: Found checksum {checksum}."); } /// <summary> /// Generates the checksum. /// </summary> /// <returns></returns> private static string GenerateChecksum(string input) { // Only use enough data to fill the disk. string data = input; // Keep calculating a checksum until we have an odd number of characters. while (data.Length % 2 == 0) { var checksum = new StringBuilder(); // Check each pair of characters and generate a new checksum. for (var i = 0; i < data.Length - 1; i += 2) { checksum.Append(data[i].Equals(data[i + 1]) ? '1' : '0'); } // Update the data to calculate a checksum from. data = checksum.ToString(); } // Checksum length is an odd number - return the value. return data; } } |
You can find the full solution on Github