Today's challenge was validating a custom sort order based on a pre-defined set of rules.
Summary of Solution
Part 1:
We were asked to validate an update (array of integers) was in the correct order, based on on a set of rules defined in the puzzle’s input.
The first thing I thought, was to store these rules in a constant Dictionary, as we don’t care about the order of the “subordinate” pages (pages in which the defined page must be before), just that the given number is before them.
public static (Dictionary<int, List<int>> Rules, List<int[]> Updates) ParseInput(string[] lines)
{
Dictionary<int, List<int>> rules = new();
List<int[]> updates = [];
foreach (var line in lines)
{
if (line.Contains('|'))
{
// Parse ordering rules
var numbers = line.Split('|');
var number1 = int.Parse(numbers[0]);
var number2 = int.Parse(numbers[1]);
HandleOrderingStorage(rules, number1, number2);
}
else if (string.IsNullOrEmpty(line))
{
// Ignore empty lines
continue;
}
else
{
// Parse updates
var numbers = line.Split(',');
updates.Add(numbers.Select(int.Parse).ToArray());
}
}
return (rules, updates);
}
private static void HandleOrderingStorage(Dictionary<int, List<int>> ordering, int number1, int number2)
{
if (!ordering.TryGetValue(number1, out var value))
{
ordering[number1] = [number2];
}
value?.Add(number2);
}
Apologies, I didn't save the solution for just Part 1. However, in Part1 we didn’t need to fix the update, so in Part 1 the CheckOrder function simply checked the order as it does now, but returned true or false, as to whether it was valid or not.
We do this by first storing the positions of all pages in a dictionary of their number and index, to make lookup easier.
public static (bool IsValid, int[] OrderedUpdate) CheckOrder(int[] input, Dictionary<int, List<int>> rules)
{
// Create a dictionary to store the position of each number in the input list for easy comparison
var positions = input.Select((num, index) => new { num, index })
.ToDictionary(x => x.num, x => x.index);
foreach (var pageRule in rules)
{
var key = pageRule.Key;
var subordinates = pageRule.Value;
if (positions.TryGetValue(key, out var keyPosition))
{
foreach (var sub in subordinates)
{
if (positions.TryGetValue(sub, out var subPosition) && subPosition < keyPosition)
{
// Invalid order found
return (false, FixOrder(input, rules));
}
}
}
}
return (true, input);
}
The concept of this logic is to find the position of the key and loop through all the subordinates for this, if the subordinate is within the input positions, check if the subordinate is before the checked number or not. If the subordinate is before the number, mark the order as invalid (false).
We can then get all the updates that are valid, and count them up
Part 2
In part 2 we needed to find all the invalid updates, fix all the invalid updates, and then find the middle value again. This is where the FixOrder / Swap methods come into play.
The method’s concept, iteratively applies swaps to put each page in its correct position according to the rules.
As we know the FixOrder method is only called on invalid updates, we can presume we need to move any subordinate value later in the update.
We can therefore use check if the subIndex is before current index, as if it is, it means it’s already been processed / swapped. As we progress iterating over the update, we continue to swap if needed, until the current page is where it belongs according to the ruleset.
private static int[] FixOrder(int[] update, Dictionary<int, List<int>> rules)
{
bool changesMade;
do
{
changesMade = false;
for (var i = 0; i < update.Length; i++)
{
var page = update[i];
if (!rules.TryGetValue(page, out var ruleSet)) continue;
foreach (var subordinate in ruleSet)
{
// if the subordinate is before or equal to the current index, move on as already processed or not needed.
var subIndex = Array.IndexOf(update, subordinate);
if (subIndex <= i) continue;
// Swap positions to ensure the page comes before its subordinate
Swap(ref update[i], ref update[subIndex]);
changesMade = true;
}
}
} while (changesMade);
return update;
}
private static void Swap(ref int a, ref int b)
{
(a, b) = (b, a);
}
As we’re returning a Tuple from the CheckOrder method, containing whether the update was valid as well as the update. In our Program.cs we can collate lists of the valid, and invalid updates before retrieving the middle item in the list (with a simple calculation of length of list / 2) taking the index at this point.
We can then run Sum() on the valid and invalid to get each of the answers requested.
using Day5_Csharp;
var input = File.ReadAllLines("input.txt");
var (orderingRules, updates) = Helpers.ParseInput(input);
var validUpdates = new List<int[]>();
var invalidUpdates = new List<int[]>();
foreach (var update in updates)
{
var (isValid, orderedUpdate) = Helpers.CheckOrder(update, orderingRules);
if (isValid)
{
validUpdates.Add(orderedUpdate);
}
else
{
invalidUpdates.Add(orderedUpdate);
}
}
// Part 1:
var part1Total = validUpdates.Sum(update => update[update.Length / 2]);
Console.WriteLine("Total Part 1: " + part1Total);
// Part 2:
var part2Total = invalidUpdates.Sum(update => update[update.Length / 2]);
Console.WriteLine("Total Part 2: " + part2Total);
As always feel free to follow here, or on twitter -> the full AoC solutions can be found on my public GitHub repo - Aoc 24 Repo
SOCIAL SHARE CARD GENERATOR