Problem Statement
Part One
Through out the Chief Historian’s office, the historically significant locations are listed not by the name, but by a unique number called the location ID. To make sure they don’t miss anything, The Historians split into two groups, each searching the office and trying to create their own complete list of location IDs.
There’s just one problem: by holding the two lists up side by side (your puzzle input), it quickly becomes clear that the lists aren’t very similar. Maybe you can help The Historians reconcile their lists?
For example:
3 4
4 3
2 5
1 3
3 9
3 3
Maybe the lists are only off by a small amount! To find out, pair up the numbers and measure how far apart they are. Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.
Within each pair, figure out how far apart the two numbers are; you’ll need to add up all of those distances. For example, if you pair up a 3 from the left list with a 7 from the right list, the distance apart is 4; if you pair up a 9 with a 3, the distance apart is 6.
To find the total distance between the left list and the right list, add up the distances between all of the pairs you found.
Your actual left and right lists contain many location IDs. What is the total distance between your lists?
Part Two
Your analysis only confirmed what everyone feared: the two lists of location IDs are indeed very different.
Or are they?
The Historians can’t agree on which group made the mistakes or how to read most of the Chief’s handwriting, but in the commotion you notice an interesting detail: a lot of location IDs appear in both lists! Maybe the other numbers aren’t location IDs at all but rather misinterpreted handwriting.
This time, you’ll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.
For example, the first number in the left list is 3. It appears in the right list 3 times, so the similarity score increases by //(3 \times 3 = 9//). The third number in the left list is 2. It does not appear in the right list once, so the similarity score does not increase (\(2 \times 0 = 0\)). For the example list, the similarity score at the end of this process is \(9 + 4 + 0 + 0 + 9 + 9 = 31\).
Once again, consider your left and right lists. What is their similarity score?
My Solution
using System.Text.RegularExpressions;
namespace AoC2024;
// Creating a static class is basically the same as creating a class that
// contains only static members and a private constructor. A private constructor
// prevents the class from being instantiated. The advantage of using a static
// class is that the compiler can check to make sure that no instance members
// are accidentally added. The compiler guarantees that instances of this class
// can't be created.
//
// Static classes are sealed and therefore can't be inherited. They can't
// inherit from any class or interface except Object. Static classes can't
// contain an instance constructor. However, they can contain a static
// constructor. Non-static classes should also define a static constructor if
// the class contains static members that require non-trivial initialization.
//
// [1]: https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/static-classes-and-static-class-members
public static partial class HistorianHysteria
{
public static int PartOne(LocationIds locationIds)
{
// When you use the positional syntax for property definition, the
// compiler creates a `Deconstruct` method with an `out` parameter for
// each positional parameter provided in the record declaration. The
// method deconstructs properties defined by using positional syntax;
// it ignores properties that are defined by using standard property
// syntax.
//
// [1]: https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/record#positional-syntax-for-property-and-field-definition
var (left, right) = locationIds;
left.Sort();
right.Sort();
return left.Zip(right, (x1, x2) => int.Abs(x1 - x2)).Sum();
}
public static int PartTwo(LocationIds locationIds)
{
var (left, right) = locationIds;
// Objective: Use a functional approach. Avoid mutating values.
var rightLookupTable = right
.GroupBy(id => id)
.ToDictionary(group => group.Key, group => group.Count());
return (
from id in left
select id * rightLookupTable.GetValueOrDefault(id, 0)
).Sum();
}
public static LocationIds ParseLocationIds(
string filePath)
{
List<int> left = [];
List<int> right = [];
using StreamReader inputReader = new(filePath);
string? line;
while ((line = inputReader.ReadLine()) != null)
{
Match match = InputLineRegex().Match(line);
if (!match.Success)
throw new ArgumentException($"{line} is not well formatted");
left.Add(int.Parse(match.Groups["left"].Value));
right.Add(int.Parse(match.Groups["right"].Value));
}
return new(left, right);
}
public readonly record struct LocationIds(List<int> Left, List<int> Right);
// Using source generation provides the most efficient code.
//
// `RegexOptions.Compiled` improves on bare `new Regex()`, e.g., "match the
// input character at the current position against 'a' or 'c'" vs. "match
// the input character at the current position against the set specified in
// this set description"
//
// However, `RegexOptions.Compiled` is costly to construct and uses
// reflection. `GeneratedRegex` sidesteps these limitations while still
// being efficient.
//
// [1]: https://learn.microsoft.com/en-us/dotnet/standard/base-types/regular-expression-source-generators
[GeneratedRegex(@"(?<left>\d+)\s+(?<right>\d+)")]
private static partial Regex InputLineRegex();
}