This year, I’m posting my solutions to the puzzles in the Advent of Code.
I’m changing the format of these posts: from now on, I will post the code directly, along with a link to the solution on Github.
And now, on with the solution:
Day 14, part 1
Simplified problem:
Given a specific input, add an increasing number (the index) to the end and calculate the MD5 hash. If the result meets the following criteria, we consider it a key:
- It contains three of the same character in a row, like
777. Only consider the first such triplet in a hash. - One of the next
1000hashes in the stream contains that same character five times in a row, like77777.
What is the value of index when you have found the 64th key?
Day 14, Part 2
Instead of checking the MD5 hash of your input, the input is hashed 2016 times. For example, the MD5 of abc is 900150983cd24fb0d6963f7d28e17f72. Calcuate the MD5 hash of that hash, and repeat until the input has been hashed 2016 times. Then determine whether this hash is a key.
What is the value of index when you have found the 64th key?
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 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 |
class Program { #region Fields private const string Salt = "cuanljph"; private static readonly Regex KeyRegex = new Regex(@"(.)\1{2}"); private static int _index = -1; private static readonly Regex TripletRegex = new Regex(@"(\w)\1{2}"); private static readonly List<string> HashList = new List<string>(); private static readonly List<string> KeyList = new List<string>(); private static readonly MD5 Md5Hash = MD5.Create(); #endregion static string Part1() { var keyCount = 0; Stopwatch sw = Stopwatch.StartNew(); while (keyCount != 64) { _index++; string hash = CalculateMd5Hash($"{Salt}{_index}"); Match match = KeyRegex.Match(hash); if (!match.Success) continue; // Hash contains a sequence of three characters. // Check that the same character appears in a sequence of 5 var keyMatch = new string(match.Value[0], 5); for (var i = 1; i <= 1000; i++) { int matchIndex = _index + i; string nextHash = CalculateMd5Hash($"{Salt}{matchIndex}"); // If the hash does not contain the match sequence, continue the for-loop if (!nextHash.Contains(keyMatch)) continue; // We found a matching sequence - this is a valid one-time key keyCount++; Console.WriteLine(GenerateFoundKeyMessage(1, keyCount, nextHash, i)); // Don't bother calculating any remaining hashes - we've already found what we needed. break; } } sw.Stop(); return GenerateResultMessage(1, _index, sw); } private static string GenerateResultMessage(int part, int index, Stopwatch sw) => $"Part {part}: 64th key found at index {index} in {new TimeSpan(sw.ElapsedTicks):g}."; private static string GenerateFoundKeyMessage(int part, int count, string hash, int index) => $"Part {part}: Found key {count.ToString().PadRight(3)}: {hash} (index {index})"; private static string Part2() { Stopwatch sw = Stopwatch.StartNew(); while (KeyList.Count < 64) { _index++; string hash; if (HashList.Count == _index) { string hashSource = GenerateHashInput(_index); hash = AddHash(GenerateMd5Part2(hashSource)); } else { hash = HashList[_index]; } Match triplet = TripletRegex.Match(hash); if (!triplet.Success) continue; var quintet = new string(triplet.Value[0], 5); for (var i = 1; i <= 1000; i++) { int index = _index + i; string nextHash = HashList.Count == index ? AddHash(GenerateMd5Part2(GenerateHashInput(index))) : HashList[index]; if (!nextHash.Contains(quintet)) continue; KeyList.Add(nextHash); Console.WriteLine(GenerateFoundKeyMessage(2, KeyList.Count, nextHash, index)); break; } } sw.Stop(); Md5Hash.Dispose(); return GenerateResultMessage(2, _index, sw); } private static string GenerateHashInput(int index) => $"{Salt}{index}"; private static string AddHash(string input) { string hash = GetMd5Hash(input); HashList.Add(hash); return hash; } private static string GenerateMd5Part2(string input) { for (var i = 0; i < 2016; i++) { input = GetMd5Hash(input); } return input; } private static string GetMd5Hash(string input) { // Convert the input string to a byte array and compute the hash. byte[] data = Md5Hash.ComputeHash(Encoding.UTF8.GetBytes(input)); // Create a new Stringbuilder to collect the bytes // and create a string. var sBuilder = new StringBuilder(); // Loop through each byte of the hashed data // and format each one as a hexadecimal string. foreach (byte t in data) { sBuilder.Append(t.ToString("x2")); } // Return the hexadecimal string. return sBuilder.ToString(); } static void Main(string[] args) { string part1Result = Part1(); // Reset the index for Part 2 _index = -1; string part2Result = Part2(); Console.WriteLine(part1Result); Console.WriteLine(part2Result); Console.ReadKey(); } /// <summary> /// Calculates the MD5 hash of a string. /// </summary> /// <param name="input">The input.</param> /// <returns>String representation of the MD% hash in hexadecimal.</returns> private static string CalculateMd5Hash(string input) { //Create a byte array from source data. byte[] source = Encoding.ASCII.GetBytes(input); byte[] hash = new MD5CryptoServiceProvider().ComputeHash(source); // step 2, convert byte array to hex string var sb = new StringBuilder(); foreach (byte t in hash) { sb.Append(t.ToString("X2")); } return sb.ToString().ToLower(); } } |
You can find the full solution on Github