https://romanx.co.uk/20222022-08-25T08:22:42Zhttps://romanx.co.uk/posts/advent-of-code-2021-day-12Advent of Code 2021 - Passage Pathing2022-04-29T13:15:00Z<p>Another day and another delay.
Hopefully someone out there in the internet is finding these useful if not i'm finding it helpful going back over my solutions with fresh eyes so I guess we'll keep on keeping on.</p>
<p>For day 12 we have a graph problem.
We need to find all the paths from beginning to end of a cave system applying some rules on if a path is still valid or we should stop.
If you feel like joining me you can find this challenge <a href="https://adventofcode.com/2021/day/12">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-twelve/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing">Parsing</h1>
<p>We're going to start here by taking our input and turning it into a map from the cave id to the cave itself.
So it'll look something like this:</p>
<pre><code>start -> Cave { Id: start, CaveType: Entrance, Connections: [A, b] }
A -> Cave { Id: A, CaveType: Large, Connections: [start, c, b, end] }
b -> Cave { Id: b, CaveType: Small, Connections: [start, A, d, end] }
c -> Cave { Id: c, CaveType: Small, Connections: [A] }
d -> Cave { Id: d, CaveType: Small, Connections: [b] }
end -> Cave { Id: end, CaveType: Exit, Connections: [A, b] }
</code></pre>
<p>This way we can make our code look a little cleaner and use immutable data structures during our graph search which hopefully should make it easier to reason about.
It has to be done in a two stage process since the mapping we're provided may not be in the correct order, so the target node may not appear before the source node.</p>
<pre><code class="language-csharp">var map = new Dictionary<string, List<string>>();
foreach (var line in lines)
{
var split = line.Split('-');
var start = split[0];
var end = split[1];
// Try add them to our map above or the default if it's not already there
map.TryAdd(start, new List<string>());
map.TryAdd(end, new List<string>());
// Add the start to the end and the end to the start
map[start].Add(end);
map[end].Add(start);
}
</code></pre>
<p>Now we've got that mapping we can make it something nicer to deal with in code, in this case a readonly record struct and an enumeration for the CaveType.</p>
<pre><code class="language-csharp">readonly record struct Cave(string Id, CaveType CaveType, string[] Connections);
enum CaveType
{
Entrance,
Exit,
Small,
Large
}
</code></pre>
<p>And finally the mapping from our Dictionary of strings to these types</p>
<pre><code class="language-csharp">var result = new Dictionary<string, Cave>();
foreach (var (id, connections) in map)
{
var caveType = id switch
{
"start" => CaveType.Entrance,
"end" => CaveType.Exit,
// This is a little hack but based on our input data
// if the first char is lower then the rest is too
_ when char.IsLower(id[0]) => CaveType.Small,
_ => CaveType.Large,
};
result[id] = new Cave(id, caveType, connections.ToArray());
}
</code></pre>
<h1 id="the-actual-work">The Actual Work</h1>
<p>Now we're going to split this into the algorithm for finding the number of paths through the graph which is the main task for this day.
The function for finding all the paths is very similar to <a href="https://romanx.co.uk/posts/advent-of-code-2021-day-9">day 9</a> and the flood fill to find the basins in that it's an adapted breadth first search.</p>
<p>One of the differences is that we have some state for each route through the graph since we need to avoid visiting small caves twice.
We're going to do this by keeping track of which small caves we've already visited.
Our state is going to look like this</p>
<pre><code class="language-csharp">record CaveRoute(
string[] Path,
Dictionary<Cave, int> SmallCaveVisits);
</code></pre>
<p>Now we've got our state we can define our search.
Our search is going to take a function which accepts both the target cave and the current state.
We're going to use this function to decide if we can make the transition to the target cave.</p>
<pre><code class="language-csharp">static int FindPaths(
Dictionary<string, Cave> graph,
Func<Cave, CaveRoute, bool> caveFunc)
{
var pathCount = 0;
// We're always going to begin at the entrance so find it here.
var (_, start) = graph.First(g => g.Value.CaveType is CaveType.Entrance);
var currentFrontier = new List<CaveRoute>();
var nextFrontier = new List<CaveRoute>();
// Add our starting state for our search
currentFrontier.Add(new CaveRoute(new[] { start }, new Dictionary<Cave, int>())));
while (currentFrontier.Count > 0)
{
foreach (var current in currentFrontier)
{
// [Insert step logic here]
}
// Our nice fancy shortcut for swap and clear
(currentFrontier, nextFrontier) = (nextFrontier, currentFrontier);
nextFrontier.Clear();
}
return pathCount;
}
</code></pre>
<p>Most of that should be very similar to the code from Day 9 so hopefully the comments make it clear.
The actual logic for each step is missing and we're going to add it next.
This goes into the loop for the step logic in the method above.
You can make this a method if you'd like or just in-line it.</p>
<pre><code class="language-csharp">// Lookup the current cave definition: ^1 is a shorthand for the last item in the list
Cave currentCave = current.Path[^1];
foreach (var next in currentCave.Connections)
{
// Get the target cave definition by its id.
Cave nextCave = graph[next];
// If we're at the target then yay
if (nextCave.CaveType is CaveType.Exit)
{
// You should add the current.Path to a set if you wanted
// to see the paths but we only care about the count so
// increment here.
pathCount++;
}
else if (nextCave.CaveType is CaveType.Entrance)
{
// If it's the start we can't go back so don't add another step to the frontier.
}
else if (nextCave.CaveType is CaveType.Small)
{
// Call the provided function to check if we're allowed
// to move to the next cave based on our state.
if (caveFunc(nextCave, current))
{
// If we can move to the next then we need to increment the number of times
// we've visited the cave.
int count = current.SmallCaveVisits.GetValueOrDefault(nextCave);
// Add to the frontier of the search a state with the updated path
nextFrontier.Add(current with
{
Path = current.Path.Add(nextCave),
SmallCaveVisits = current.SmallCaveVisits.SetItem(nextCave, count + 1)
});
}
}
else
{
// It must be a large cave we're in so just add to the
// frontier we visited the large cave.
nextFrontier.Add(current with
{
Path = current.Path.Add(nextCave)
});
}
}
</code></pre>
<h1 id="part-1">Part 1</h1>
<p>Now we have our FindPaths function we can actually solve Part 1!</p>
<pre><code class="language-csharp">Dictionary<string, Cave> graph = ParseCaves(lines);
var paths = FindPaths(
graph,
CaveFunction);
Console.WriteLine($"Number of paths: {paths}");
static bool CaveFunction(Cave cave, CaveRoute route)
{
// We only allow one entry to the small cave
// so if it exists then we shouldn't transition.
return route.SmallCaveVisits.ContainsKey(cave) is false;
}
</code></pre>
<p>That's a first ⭐ for the day.</p>
<h1 id="part-2">Part 2</h1>
<p>Part 2 only has a minor change from Part 1, which is that there is a different rule for transitioning in small caves.
We can now visit <strong>one</strong> small cave <em>twice</em> but only one.</p>
<pre><code class="language-csharp">Dictionary<string, Cave> graph = ParseCaves(lines);
var paths = FindPaths(
graph,
CaveFunction);
Console.WriteLine($"Number of paths: {paths}");
static bool CaveFunction(Cave cave, CaveRoute route)
{
var visitedTwice = route.SmallCaveVisits.Any(kvp => kvp.Value is 2);
// If i've not visited any twice it doesn't matter just visit it.
if (visitedTwice is false)
{
return true;
}
return route.SmallCaveVisits.ContainsKey(cave) is false;
}
</code></pre>
<p>And with that second ⭐ we're done with day 12 of Advent of code.
Most of the work was shared between the two parts thanks to our use of a function to determine if we can move to a small cave.</p>
<p>Another day and another delay.
Hopefully someone out there in the internet is finding these useful if not i'm finding it helpful going back over my solutions with fresh eyes so I guess we'll keep on keeping on.</p>https://romanx.co.uk/posts/advent-of-code-2021-day-11Advent of Code 2021 - Dumbo Octopus2022-04-01T09:27:00Z<p>So when I left off with see you tomorrow I didn't plan for it to be a few months!
Life unfortunately got in the way but I did manage to finish all of the 2021 challenges and so still plan to post write-ups of my solutions albeit with a delay.</p>
<p>So for day 11 we have a simulation of octopi flashing and finding out when we reach specific states.
Awesome.
If you feel like joining me you can find this challenge <a href="https://adventofcode.com/2021/day/11">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-eleven/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing">Parsing</h1>
<p>So we have a grid of digits from 0 to 9 which each represent an octopus.
This looks very similar to our parsing for <a href="https://romanx.co.uk/posts/advent-of-code-2021-day-9">day 9</a> so I'm going to abstract that into a helper so we can use it here.
By the time we're done we should have a <code>Dictionary<Point, int></code> representing each octopi and their flash number.</p>
<h1 id="simulating-each-step">Simulating Each Step</h1>
<p>The puzzle explains what happens each step so but we're going to go through it piece by piece together.</p>
<p>Firstly we're going to take our current map and copy it.
This makes our step method <a href="https://blog.ploeh.dk/2020/02/24/discerning-and-maintaining-purity/">pure</a> and avoids us mutating the existing state allowing us to make it easier to reason about what happened when.
When we have our copied state we then increment all the the octopi flash values by one.</p>
<pre><code class="language-csharp">var next = new Dictionary<Point, int>(current);
foreach (var point in octopi.Keys)
{
next[point]++;
}
</code></pre>
<p>Now this is where the fun starts. Each octopi that goes over a flash value of 9 needs to flash.
This will then increase the flash value of all octopi around it.
Those flashed octopi may have now gotten a flash value of 9 (or over) and so need to flash and so on.
There's a limitation here in that each octopi can only flash once per step.</p>
<p>So we're going to simulate this in waves much like finding our basins in Day 9.</p>
<pre><code class="language-csharp">// A set of all flashed positions to avoid duplicate flashes.
var flashed = new HashSet<Point2d>();
// The current set of octopi that need to flash
var current = new Queue<Point2d>(next
.Where(kvp => kvp.Value > 9)
.Select(kvp => kvp.Key));
while (current.TryDequeue(out var point))
{
if (flashed.Contains(point))
{
continue;
}
flashed.Add(point);
// Flash the octopi
}
</code></pre>
<p>So we have our set of octopi that need to flash in a queue and remove them off one by one.
If we've already seen the octopi then we've flashed them already and can skip them, otherwise we need to now add them to our flashed list.</p>
<p>Now we're going to borrow some more code from Day 9.
We need to find all the points around the current octopi and we can do this with our Direction class.
I'm going to leave this an exercise to the reader since we need to add 4 new positions <code>NorthEast</code>, <code>NorthWest</code>, <code>SouthEast</code> and <code>SouthWest</code>.
I've named the collection of all the directions as the property <code>Directions.All</code> which you'll see in the code below.</p>
<pre><code class="language-csharp">var neighbours = Direction.All.Select(dir => point + dir);
// Go through each neighbouring point
foreach (var neighbour in neighbours)
{
// If the point is in our set of octopi, otherwise it's out of the map.
if (next.ContainsKey(neighbour))
{
// Increment the flashed value for the octopi
next[neighbour]++;
// If they're now greater than 9 then add them to our queue of flashing octopi
if (next[neighbour] > 9)
{
current.Enqueue(neighbour);
}
}
}
// Set the flashes octopi back to zero.
foreach (var point in flashed)
{
builder[point] = 0;
}
</code></pre>
<h1 id="part-1">Part 1</h1>
<p>So looking at Part 1 we have to simulate 100 steps with our field of octopi and find out how many flashes ocurred overall.</p>
<pre><code class="language-csharp">var total = 0u;
Dictionary<Point, int> octopi = ParseOctopi(input);
for (var i = 0; i < 100; i++)
{
(octopi, var flashed) = Step(octopi);
total += flashed;
}
Console.WriteLine($"Number of flashes: {total}");
</code></pre>
<p>Nice and simple after the hard work in our Step method. One shiny ⭐ for us.</p>
<h1 id="part-2">Part 2</h1>
<p>For part 2 we have to keep stepping until we find a turn where every octopi flashes at once.
Since we track how many octopi flashed each turn we just need to compare that number to the total number of octopi and when they match we're find the right turn.</p>
<pre><code class="language-csharp">var octopi = input.ParseOctopi();
var turn = 0;
while (true)
{
turn++;
(octopi, var flashed) = Step(octopi);
// All of them flashed
if (flashed == octopi.Count)
{
break;
}
}
Console.WriteLine($""All flashed on turn: {turn}");
</code></pre>
<p>And with that second ⭐ we're done with day 11 of Advent of code.
Most of the work was shared between the two parts which is always nice, hopefully you enjoyed it.</p>
<p>So when I left off with see you tomorrow I didn't plan for it to be a few months!
Life unfortunately got in the way but I did manage to finish all of the 2021 challenges and so still plan to post write-ups of my solutions albeit with a delay.</p>https://romanx.co.uk/posts/advent-of-code-2021-day-10Advent of Code 2021 - Syntax Scoring2021-12-10T11:31:00Z<p>For todays challenge we have a syntax parsing challenge so if you've ever wondered how compilers do it, we get a small taste today.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/10">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-ten/Challenge.cs">you can find it here.</a></p>
<p>No parsing today since the challenges themselves are more about the parsing than anything else!</p>
<h1 id="part-1">Part 1</h1>
<p>So we're going to focus on corrupted lines here so those that aren't following the rules 🚨.
These are those that don't have a matching closing bracket to their opening brackets so we need to keep track of all the brackets that were opened.</p>
<p>We're going to track this using a stack, so for all the opening brackets <code>(</code> <code>[</code> <code>{</code> <code><</code> we're going to push the character on to the stack.
If it's not an opening bracket then it must be a closing bracket!
The bracket that is closing <em>must</em> match the last opened bracket otherwise we've got a corrupted line and we can skip out here.
Here's the code for what I just described above.</p>
<pre><code class="language-csharp">static readonly Dictionary<char, char> bracketMap = new()
{
['('] = ')',
['['] = ']',
['{'] = '}',
['<'] = '>',
};
LineResult ScoreLine(string line)
{
var chunks = new Stack<char>();
foreach (var c in line)
{
// If it's an open chunk
if (bracketMap.ContainsKey(c))
{
chunks.Push(c);
}
else
{
var current = chunks.Pop();
var close = bracketMap[current];
if (c != close)
{
return new LineResult(LineType.Corrupted, ScoreCorrupted(c));
}
}
}
return new LineResult(LineType.Incomplete, 0);
}
readonly record struct LineResult(LineType Type, long Score);
enum LineType
{
Incomplete,
Corrupted,
}
</code></pre>
<p>I'm ignoring the incomplete lines here and using a map of the opening bracket to the closing bracket since it's nice and easy to lookup.
The challenge gives us the way to score corrupted lines based on the kind of bracket that is wrong but I'll add it below since it's a nice example of <a href="https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/switch-expression">Switch Expressions</a>.</p>
<pre><code class="language-csharp">static int ScoreCorrupted(char c) => c switch
{
')' => 3,
']' => 57,
'}' => 1197,
'>' => 25137,
_ => throw new InvalidOperationException($"Not a valid scoring character: '{c}'")
};
</code></pre>
<p>Now we have our scores, getting our shiny ⭐ for part 1 becomes quite clean</p>
<pre><code class="language-csharp">var total = lines
.Select(line => ScoreLine(line))
.Where(line => line.Type is LineType.Corrupted)
.Sum(line => line.Score);
Console.WriteLine($"Error Score: {total}");
</code></pre>
<h1 id="part-2">Part 2</h1>
<p>For part 2 we've got to deal with those pesky incomplete lines.
Luckly we already have all the information we need.
The incomplete lines are those that we reach the end of the line but still have items on our stack because we've opened brackets and not closed them.
To close them off we need to take each of the items on the stack in turn, map them to their closing counterpart and those would be the missing brackets.</p>
<p>At the end of our <code>ScoreLine</code> method above, rather than returning a placeholder for incomplete lines, the logic described above becomes this:</p>
<pre><code class="language-csharp">var autocompleteScore = chunks
.Select(c => bracketMap[c])
.Aggregate(0L, (acc, c) => (acc * 5) + ScoreAutocomplete(c));
return new LineResult(LineType.Incomplete, autocompleteScore);
</code></pre>
<p>We're using aggregate to total up all our results, this is because each previous result is multiplied by <code>5</code> before adding on the score from auto-completing the bracket.
The scoring method is provided in the challenge as before but for completeness here it is</p>
<pre><code class="language-csharp">static int ScoreAutocomplete(char c) => c switch
{
')' => 1,
']' => 2,
'}' => 3,
'>' => 4,
_ => throw new InvalidOperationException($"Not a valid scoring character: '{c}'")
};
</code></pre>
<p>So then to get our second ⭐ of the day we need to take all our autocompleted lines, sort them by their score and then take the median one (the one in the middle).</p>
<pre><code class="language-csharp">var scores = lines
.Select(line => ScoreLine(line))
.Where(line => line.Type is LineType.Incomplete)
.OrderBy(x => x.Score)
.ToArray();
var median = scores[scores.Length / 2];
output.WriteProperty("Autocomplete Score", median.Score);
</code></pre>
<p>And we're done with day 10 of Advent of code.
Hopefully you're having fun with the challenges, either following along with me or using these as a comparison to how awesome you're solution is.
If you got this far on your own I'm proud of you, if you followed along with me I'm proud of you, Hell if you just got here randomly then i'm proud of you also.</p>
<p>See you tomorrow for Day 11!</p>
<p>For todays challenge we have a syntax parsing challenge so if you've ever wondered how compilers do it, we get a small taste today.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/10">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-ten/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-9Advent of Code 2021 - Smoke Basin2021-12-10T00:00:00Z<p>A nice palate clenser of a day, well if you enjoy search puzzles.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/9">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-nine/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing-input">Parsing Input</h1>
<p>We're going to be reusing our point class from <a href="https://romanx.co.uk/advent-of-code-2021-day-5">Day 5</a> so if you haven't moved that to a shared place then I'd recommend it now since we're going to be adding some more useful methods to it.</p>
<p>Let's turn our input into something useful.
We could use a multidimensional array here to model our information but I prefer using a <code>Dictionary<Point, char></code> so i'm going to do that here.</p>
<pre><code class="language-csharp">var lines = inputLines.AsArray();
Dictionary<Point, char> dict = new Dictionary<Point, char>();
for (var y = 0; y < lines.Length; y++)
{
var line = lines[y].AsSpan();
for (var x = 0; x < line.Length; x++)
{
var point = new Point(x, y);
dict[point] = line[x];
}
}
</code></pre>
<p>This is a useful method when ever we're provided with a grid of characters.
We're going to actually map this dictionary into another dictionary since for this challenge we want <code>Dictionary<Point, int></code> for our heights but I wanted to leave the original here since its useful.</p>
<pre><code class="language-csharp">var map = dict.ToDictionary(k => k.Key, v => v.Value - '0');
</code></pre>
<p>Another useful trick here in that if you have a <code>char</code> in the range of <code>0 - 9</code> and wan't to convert it to its int representation.
Rather than doing parsing tricks you can actually subtract the character <code>'0'</code>.
If this doesn't seem obvious why it works don't worry it isn't obvious.
This subtracts the ascii number for <code>'0'</code> from the other number i.e. <code>'5'</code> which becomes <code>53 - 48 = 5</code>.</p>
<h1 id="part-1">Part 1</h1>
<p>Now we've got a structure to be working with, we need to find the lowest points by looking at all the cardinal neighbours.
That is those that are Up, Down, Left and Right.
This is quite a common problem that we will face so lets come up with a nice way to do it.
A <code>Direction</code> class that we can use in combination with the <code>Point</code> class should simplify how we do this.</p>
<pre><code class="language-csharp">public enum DirectionType
{
North,
East,
South,
West,
}
public readonly record struct Direction
{
private Direction(DirectionType directionType)
{
DirectionType = directionType;
}
public DirectionType DirectionType { get; }
public static Direction North { get; } = new Direction(DirectionType.North);
public static Direction East { get; } = new Direction(DirectionType.East);
public static Direction South { get; } = new Direction(DirectionType.South);
public static Direction West { get; } = new Direction(DirectionType.West);
public static Direction[] CardinalDirections { get; } = new[]
{
North, East, South, West
}
}
</code></pre>
<p>Two notes here worth mentioning I'm using compass directions rather than grid directions since I find it easier to reason about but you can alias them easily enough.
The second is that .NET does not have rich enumerations like Java so I'm using a class with static members and a private constructor to simulate this since it makes it easier to use.</p>
<p>Now we have this useful class we can add the following operator to point and use it like this:</p>
<pre><code class="language-csharp">public readonly record struct Point
{
public static Point operator +(Point point, Direction direction) => direction.DirectionType switch
{
DirectionType.North => point + new Point(0, -1),
DirectionType.East => point + new Point(1, 0),
DirectionType.South => point + new Point(0, 1),
DirectionType.West => point + new Point(-1, 0),
_ => point
};
}
var newPoint = point + Direction.North;
</code></pre>
<p>Okay so now we have a method of getting the point in a specific direction.
We can write a helper to get the all the points in the cardinal directions from a provided point like this:</p>
<pre><code class="language-csharp">public static IEnumerable<Point> GetDirectNeighbours(Point point)
=> Direction.CardinalDirections.Select(dir => point + dir);
</code></pre>
<p>Okay so we're back to the challenge.
So our algorithm works like this:</p>
<ul>
<li>Go through each position in the height map.
<ul>
<li>Look at each cardinal neighbour.</li>
<li>If the current point is lower than all of the surrounding points.
<ul>
<li>Add to the set of lowest points.</li>
</ul>
</li>
</ul>
</li>
</ul>
<p><em>Note:</em> Since our <code>GetDirectionNeighbours</code> simply returns all the cardinal points we have to filter out those not in our height map and ignore them.</p>
<pre><code class="language-csharp">var lowPoints = new HashSet<Point>();
foreach (var (point, height) in map)
{
var neighbours = GetDirectNeighbours(point);
var lowest = neighbours // Go through all possible neighbours
.Select(n => map.TryGetValue(n, out var neighbourHeight) ? neighbourHeight : (int?)null) // Get their height or null for missing.
.Where(n => n is not null) // Remove the null items
.All(neighbourHeight => height < neighbourHeight)// Are all of the items higher than the current point's height
if (lowest)
{
lowPoints.Add(point);
}
}
</code></pre>
<p>We're using a HashSet here so we don't double count our low points since only distinct items are allowed in the set.
To get our shiny ⭐ we take all our low points and sum up their heights + 1.</p>
<pre><code class="language-csharp">var score = lowPoints
.Sum(point => 1 + map[point]);
Console.WriteLine($"Risk level {score}");
</code></pre>
<h1 id="part-2">Part 2</h1>
<p>So for part 2 we need to find the basins in the height map. We can do this by ignoring any positions with the max height of 9.
An interesting thing about the input data is that our basins are surrounded by mountains of height 9 so we can use a fill algorithm to find our basin and stop as we can't go past any neighbours of height 9.
If that didn't make sense hopefully this picture helps some. Note that the the Xs stop where the neighbours are 9 so we can't go further.</p>
<pre><code>....9XXXXX
.....9X9XX
......9.9X
.........9
..........
</code></pre>
<p>So starting with our heightmap from Part 1.
We're going to get a set of candidate points, anything that isn't height 9, and then find the basin that contains that point.
The basin we found can then be added to our list of basins and all the points in the basin can be removed from our candidate points since we already know the whole basin.
We keep doing this until there are no points left since they're all contained in one basin or another.</p>
<pre><code class="language-csharp">var candidatePoints = map
.Where(kvp => kvp.Value != 9)
.Select(kvp => kvp.Key)
.ToHashSet();
var basins = new List<HashSet<Point2d>>();
while (candidatePoints.Count > 0)
{
var current = validPoints.First();
var height = map[current];
var basin = FindBasinContainingPoint(current, map);
basins.Add(basin);
candidatePoints.ExceptWith(basin);
}
</code></pre>
<p>Since we're using a hashset of candidate points we can use <code>ExceptWith</code> to remove the points in the basin efficently.
The real logic for Part 2 contained in <code>FindBasinContainingPoint</code>.
I'm using a variation of a <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Breadth First Search</a> which returns all the points the search visited.
The variation I'm using is from RedBlobGames and optimized to not use a queue like the standard implementation.
You can find more details <a href="https://www.redblobgames.com/pathfinding/a-star/implementation.html#optimize-bfs-queue">about it here.</a></p>
<pre><code class="language-csharp">var currentFrontier = new List<Point2d>();
var nextFrontier = new List<Point2d>();
currentFrontier.Add(source);
var visited = new HashSet<Point2d>
{
source
};
while (currentFrontier.Count > 0)
{
foreach (var current in currentFrontier)
{
foreach (var next in GetDirectNeighbours(current))
{
if (map.TryGetValue(next, out var nextHeight) && nextHeight != 9)
{
if (visited.Add(next) is true)
{
nextFrontier.Add(next);
}
}
}
}
// An effecient clear and swap of two lists.
(currentFrontier, nextFrontier) = (nextFrontier, currentFrontier);
nextFrontier.Clear();
}
return visited;
</code></pre>
<p>We start with our source point and add that to our current search set and add it to our visited set since obviously we visited where we started.</p>
<p>The core of the algorithm is going through each of the current points, finding all their adjacent points that are <em>valid</em> (more on this in a second) and adding them to the next set of points we're going to look at.
The validity of points will vary, in our case they have to be in our height map and they have to be less than height <code>9</code> since we can't go past that height.</p>
<p>Working with our example from above we can show how the algorithm spreads to collect the points in the basin.
We're going to start in the top right corner.
I'm using <code>C</code> for current, <code>N</code> for next and <code>V</code> for visited.</p>
<pre><code>....9432NC ....943NCV ....94NCVV ....9NCVVV ....9CVVVV ....9VVVVV
.....9492N .....949NC .....949CV .....9N9VV .....9C9VV .....9V9VV
......9.92 -> ......9.9N -> ......9.9C -> ......9.9V -> ......9.9V -> ......9.9V
.........9 .........9 .........9 .........9 .........9 .........9
.......... .......... .......... .......... .......... ..........
</code></pre>
<p>Hopfully that's a clear diagram of how the search works.
When we run our of points in our current frontier then we can't go anywhere else so we have our final set of points we visited.</p>
<p>So to get our shiny ⭐ for the day.
We have to order the basins we found by their size going from largest to smallest, take the top 3 and then multiply their sizes together.
I'm using aggregate here for the multiplication but a loop works just as well.</p>
<pre><code class="language-csharp">var sizes = basins
.OrderByDescending(basin => basin.Count)
.Take(3)
.Aggregate(1, (seed, set) => seed * set.Count);
Console.WriteLine($"Largest Basins Multiplied {sizes}");
</code></pre>
<p>There we have it, a shiny ⭐ and we learnt something about graph search algorithms.
On to the next day.</p>
<p>A nice palate clenser of a day, well if you enjoy search puzzles.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/9">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-nine/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-8Advent of Code 2021 - Seven Segment Search2021-12-09T00:00:00Z<p>Another day and another fustrating challenge from the Elves.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/8">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-eight/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing-inputs">Parsing Inputs</h1>
<p>Our input is a set of signal patterns and some output values split by a pipe <code>|</code>.
If we take each line as we can do the following to get this into a useful shape.</p>
<pre><code class="language-csharp">var entries = new List<Entry>();
foreach (var line in lines)
{
var split = line.Split('|', StringSplitOptions.TrimEntries);
var patterns = split[0]
.Split(' ', StringSplitOptions.TrimEntries)
.Select(x => SortStringOrder(x))
.ToHashSet();
var outputValues = split[1]
.Split(' ', StringSplitOptions.TrimEntries)
.Select(x => SortStringOrder(x))
.ToArray();
builder.Add(new Entry(patterns, outputValues));
}
static string SortStringOrder(string input)
{
var characters = input.ToCharArray().AsSpan();
characters.Sort();
return new string(characters);
}
record Entry(HashSet<string> SignalPatterns, string[] OutputValues);
</code></pre>
<p>We're going to sort the signal patterns since the order of the characters doesn't represent anything besides that the signal includes that character.
This way the same values in different orders are equivalent which will become useful later.</p>
<h1 id="part-1">Part 1</h1>
<p>We're going to count the number of entries that have output values of a specific length.</p>
<pre><code class="language-csharp">var count = 0;
foreach (var entry in entries)
{
count += entry.OutputValues
.Count(static value => {
return value.Length switch
{
2 => true, // Number 1
3 => true, // Number 7
4 => true, // Number 4
7 => true, // Number 8
_ => false
}
});
}
Console.WriteLine($"Digit Count: {count}");
</code></pre>
<p>So if the length matches one of our unique values then we Count it and add it to our total.
That's our first ⭐ and now we get to the pain.</p>
<h1 id="part-2">Part 2</h1>
<p>For part 2 we have to each entry by looking at the signal patterns for that entry and working out what signals represent each number.</p>
<p>We already know how to find four of the numbers from part 1 so our decode method starts like this:</p>
<pre><code class="language-csharp">var map = new string[10];
// Easy Numbers
map[1] = signalPatterns.First(x => x.Length == 2);
map[4] = signalPatterns.First(x => x.Length == 4);
map[7] = signalPatterns.First(x => x.Length == 3);
map[8] = signalPatterns.First(x => x.Length == 7);
</code></pre>
<p>The bit that took me way to long to work out is that this is an set problem at the end of the day.
We can work out the other missing numbers by finding their overlap.
I have an array of strings here where the index is the number and the string is the signals that make up the number.</p>
<p>Here's an example of how to deduce one of the numbers.
We have to look for the number we know that has overlapping segments with our target number.
So for the target number <code>9</code> we can see that it has 4 segments overlapping with the number <code>4</code> which we know.</p>
<p>It looks like this when in the seven segment display:</p>
<pre><code> 9: 4:
aaaa ....
b c b c
b c b c
dddd dddd
. f . f
. f . f
gggg ....
</code></pre>
<p>Going back to code, to deduce the pattern for the number 9, it has to be a length of 6 (so we have 6 segments lit) and it must intersect with the pattern for number 4 with 4 signals overlapping (all of them).</p>
<pre><code class="language-csharp">map[9] = signalPatterns.First(x =>
x.Length == 6 &&
map[4].Intersect(x).Count() == 4);
</code></pre>
<p>Rather than going through one by one, here are the rest with comments:</p>
<pre><code class="language-csharp">
// - Must be length 6
// - Must not be the same pattern as the number 9
// - Overlaps with the pattern for number 1 by 2 signals.
map[0] = signalPatterns.First(x =>
x.Length == 6 &&
x != map[9] &&
map[1].Intersect(x).Count() == 2);
// - Must be length 6
// - Must not be the same pattern as the number 9 or number 0.
map[6] = signalPatterns.First(x =>
x.Length == 6 &&
x != map[9] &&
x != map[0]);
// - Must be of length 5
// - Overlaps entirely with the pattern for number 1.
map[3] = signalPatterns.First(x =>
x.Length == 5 &&
map[1].Intersect(x).Count() == 2);
// - Must be of length 5
// - Must not be the same pattern as the number 3
// - The candidate signal must overlap entirely with the signal for 9.
map[5] = signalPatterns.First(x =>
x.Length == 5 &&
x != map[3] &&
map[9].Intersect(x).Count() == 5);
// - Must be of length 5
// - Must not be the same pattern as the number 3 or number 5.
map[2] = signalPatterns.First(x =>
x.Length == 5 &&
x != map[3] &&
x != map[5]);
</code></pre>
<p>Now we have our signal map, decoding the the entry is quite easy.
We can use <code>Array.IndexOf</code> to get the number from the signal, the actual input is scrambled but since we sorted our characters they will all be the same order so this lookup works neatly.
For each entry we have to multiply the value by 10 to move it into the right column.</p>
<pre><code class="language-csharp">var decoded = DecodeDisplay(entry.SignalPatterns);
var result = 0;
foreach (var item in entry.OutputValues)
{
result = (result * 10) + Array.IndexOf(decoded, item);
}
</code></pre>
<p>Now we can calculate the our result by adding up the value from all the decoded entries like so:</p>
<pre><code class="language-csharp">var result = entries
.Sum(entry => DecodeEntry(entry));
Console.WriteLine($"Result: {result}");
</code></pre>
<p>And there's our second ⭐ for a fustrating challenge.</p>
<p>Another day and another fustrating challenge from the Elves.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/8">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-eight/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-7Advent of Code 2021 - The Treachery of Whales2021-12-07T00:00:00Z<p>Another counting puzzle but seems a little easier for me to understand.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/7">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-seven/Challenge.cs">you can find it here.</a></p>
<h1 id="part-1">Part 1</h1>
<p>By now I'm sure you're an expert at parsing inputs like this but take the content, split it by <code>,</code> and turn it into integers (note my actual input fit into this size so hopefully yours will to, otherwise use <code>long</code>!)</p>
<p>So my first note is that it can be any number between the smallest crab position and the largest since anything outside of that will simply use more fuel so we can limit our search to <code>>= lowestCrabPosition && <= highestCrabPosition</code></p>
<pre><code class="language-csharp">var min = crabs.Min();
var max = crabs.Max();
var leastFuelUsed = Enumerable.Range(min, max)
.Min(position => CalculateTotalCost(position, crabs));
</code></pre>
<p>I decided to be lazy here and use some linq methods to find the min and max but we could have used a loop.
We can get the numbers between min and max in a sequence by using <code>Enumerable.Range</code>.
Since we wan't the lowest fuel position I'm going to use Min to find only return the lowest from our calculations.
Continuing my lazy day I'm going to pass in all the crabs and the position we're checking and call it a day.</p>
<pre><code class="language-csharp">static int CalculateTotalCost(int target, IEnumerable<int> crabs)
{
return crabs.Sum(crab => Math.Abs(crab - target));
}
</code></pre>
<p>For calculating the cost for the position we go through each of the crabs and find out how far they would have to move from their current position to the target.
We use <code>Math.Abs</code> here since they could be going right-to-left which would be negative but we only care about the while part of the number so we'll strip the sign.</p>
<p>We Sum all the crabs together and we have our cost for the target.
Combined with our Min in the first method we have our leastFuelUsed and we just have to print it out and get our shiny star ⭐.</p>
<h1 id="part-2">Part 2</h1>
<p>Turns out our fuel calculation was wrong, darn.
No worries we can just adjust our calculation to use the new formula.
The sequence for a few numbers looks like this</p>
<pre><code>1 -> 1: 0
1 -> 2: 1
1 -> 3: 3
1 -> 4: 6
1 -> 5: 10
</code></pre>
<p>The formula for this is <code>(N * (N + 1)) / 2</code>. You can also think of it as <code>Enumerable.Range(1, Math.Abs(crab - target)).Sum()</code> since it equates to the same thing but the formula is definately faster.
With our new formula the <code>CalculateTotalCost</code> method becomes this:</p>
<pre><code class="language-csharp">static int CalculateTotalCost(int target, IEnumerable<int> crabs)
{
return crabs
.Sum(crab =>
{
var distance = Math.Abs(crab - target);
return (distance * (distance + 1)) / 2;
});
}
</code></pre>
<p>The rest of our original code stays the same and we get our answer for the second ⭐ of the day. Super!</p>
<p>Another counting puzzle but seems a little easier for me to understand.
If you feel like joining me you can find todays challenge <a href="https://adventofcode.com/2021/day/7">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-seven/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-6Advent of Code 2021 - Lanternfish2021-12-06T00:00:00Z<p>We have a counting problem today and I don't like Math.
If you feel like joining me in my struggle you can find todays challenge <a href="https://adventofcode.com/2021/day/6">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-six/Challenge.cs">you can find it here.</a></p>
<p>This challenge lead me down a path by hinting that we should model the lantern fish growth rate which suggested to me some kind of Math-y function which I'm poor at.
After struggling for awhile and after completing Part 1 in a brute force approach and realising that this really was an exponential problem I looked for help elsewhere.</p>
<p>I follow <a href="https://twitter.com/bradwilson">@BradWilson</a> of <a href="https://xunit.net/">xuint</a> fame on twitter and know he streams himself doing these challenges so looked to him for some help.
He had a lovely little solution which I'm going to go through with you so we can all learn together. Thanks Brad!</p>
<h1 id="part-1">Part 1</h1>
<p>We have to count the number of fish over a period of days as they multiply.
The trick that Brad realised that I didn't is that the fish only live for a short period of time.
A maximum of 8 days infact.
This means the fish can only be in one of 9 buckets (0-9).</p>
<pre><code class="language-csharp">var fishes = input.Split(',').Select(int.Parse);
var fishCounts = new long[9] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
foreach (var fish in fishes)
{
fishCounts[fish]++;
}
</code></pre>
<p>So we create some buckets, and increment the bucket when there is a fish at that time of it's life.
We increment here since there can be more than one fish in our starting set at the same time of it's life.</p>
<p>Once we have our starting set we have to simulate the days passing.</p>
<pre><code class="language-csharp">for (var i = 0; i < days; i++)
{
// Get the fish that have offspring this day
var newFish = fishCounts[0];
// Loop through every age above zero and shuffle them down.
for (var age = 1; age < fishCounts.Length; age++)
{
fishCounts[age - 1] = fishCounts[age];
}
// Set the new fish at count of 8;
fishCounts[8] = newFish;
// Add the fish that had offspring back to position 6 as the cycle begins again.
fishCounts[6] += newFish;
}
</code></pre>
<p>At the end of our number of days our array contains all the fish on a given part of their lifecycle.
To get the total number of fish we add up all the buckets and there we have it.</p>
<pre><code class="language-csharp">var days = 80;
// Previous Code Here
var count = fishCounts.Sum();
Console.WriteLine($"Fishes after {days} days: {count}");
</code></pre>
<h1 id="part-2">Part 2</h1>
<p>Since we came up with a really efficent method of representing a lot of fish it's quite simple to calulcate the number of fish on day 256.</p>
<pre><code class="language-csharp">var days = 256;
// Previous Code Here
var count = fishCounts.Sum();
Console.WriteLine($"Fishes after {days} days: {count}");
</code></pre>
<p>There we have it, two lovely ⭐ without any of that compilated algebra malarkey.
If you did solve this by calculating the growth function I'd love to see how you do it!</p>
<p>We have a counting problem today and I don't like Math.
If you feel like joining me in my struggle you can find todays challenge <a href="https://adventofcode.com/2021/day/6">here</a> and follow along or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-six/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-5Advent of Code 2021 - Hydrothermal Venture!2021-12-06T00:00:00Z<p>Today we've got to avoid some hydrothermal vents if possible.
We definately don't want to go over those big ones though.</p>
<p>You can find todays challenge <a href="https://adventofcode.com/2021/day/5">here</a> and follow along with me or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-five/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing-inputs">Parsing Inputs</h1>
<p>The submarine has nicely provided us a list of nearby lines of vents.
These are in the form of <code>0,9 -> 5,9</code> being the start and end of the line.
They can be going horizontal or vertical.
The lines can also overlapping forming a super-vent! That's actually a made up name but they're <em>bad</em> alright so we have to find them.</p>
<p>The first thing here is we're going to need something to represent a Point or <code>(x, y)</code>.
I would suggest puting this in a common location since you may need this a few times during advent of code.
It's just a feeling.
Here's a nice simple Point readonly struct with some useful operations.</p>
<pre><code class="language-csharp">public readonly record struct Point(int X, int Y)
{
public static Point operator +(Point left, Point right)
=> new(left.X + right.X, left.Y + right.Y);
public static Point operator -(Point left, Point right)
=> new(left.X - right.X, left.Y - right.Y);
public static Point Parse(string value)
{
var split = value.Split(",");
if (split.Length != 2)
{
throw new InvalidOperationException($"Cannot convert '{value}' to Point");
}
return new Point(
int.Parse(split[0]),
int.Parse(split[1]));
}
}
</code></pre>
<p>This has an X and Y coordinate, the ability to add two points together and subtract two points (not useful here but nice for symmetry) and lastly a parse method which expects a string in the form <code>x,y</code>.
I've added some error handling in the parse method since the last thing you want is this to be the thing causing your logic to be incorrect.</p>
<p>Next up we're going to create a type to represent a line of vents.</p>
<pre><code class="language-csharp">record VentLine(Point start, Point end)
{
public IEnumerable<Point2d> Points => CalculatePoints();
private IEnumerable<Point2d> CalculatePoints()
{
throw new NotImplementedException();
}
}
</code></pre>
<p>I've got a placeholder for creating the points inbetween the start and end since we're going to need it to find out where the lines are overlapping.</p>
<p>Now to our parsing of the input, assuming we're loading the information from the file and going through it line by line.</p>
<pre><code class="language-csharp">var ventLines = new List<VentLine>();
foreach (var line in lines)
{
var split = line.Split("->", StringSplitOptions.TrimEntries);
var start = Point.Parse(split[0]);
var end = Point.Parse(split[1]);
ventLines.Add(new VentLine(start, end));
}
</code></pre>
<h1 id="part-1">Part 1</h1>
<p>Now we have something to be working with part 1 gives us a key bit of information we haven't yet accounted for.
It says to <em>"only consider horizontal and vertical lines"</em> which means that the input <strong>must</strong> include lines that are not horizontal or vertical!</p>
<p>So we have to change our parsing logic a little.
For now we're going to drop those that aren't valid on the floor and we can pick them up later.</p>
<pre><code class="language-csharp">var ventLines = new List<VentLine>();
foreach (var line in lines)
{
var split = line.Split("->", StringSplitOptions.TrimEntries);
var start = Point.Parse(split[0]);
var end = Point.Parse(split[1]);
if (start.Y == end.Y)
{
return new GridLine(start, end, LineType.Horizontal);
}
else if (start.X == end.X)
{
return new GridLine(start, end, LineType.Vertical);
}
}
enum LineType
{
Unknown, // Always have a default case!
Horizontal,
Vertical,
Diagonal,
}
</code></pre>
<p>We've added an enumeration for the type of line, this will be useful for filtering out lines we care about in each part.</p>
<p>Next we have to work out what points are actually contined within the line.
Coming back to our <code>VentLine.Points</code> method we left broken earlier.
So an interesting difficulty here is that lines can be going right-to-left and bottom-to-top so we have to account for that also depending on the start and end positions of the line.</p>
<p>I decided to go with calculating an adjustment value that we can use to update our position on the line going from the start until we reach the end.
Since we're going point by point our adjustment is only ever going to be <code>+1</code> or <code>-1</code> on either axis.
We can work out if we're going <code>+</code> or <code>-</code> by comparing the start and end together like so.</p>
<pre><code class="language-csharp">var x = (End.X - Start.X) switch
{
0 => 0,
> 0 => 1,
< 0 => -1,
};
</code></pre>
<p>This is using new C# 10 features allowing us to perform greater than <code>></code> or less than <code><</code> expressions in our switch comparison.</p>
<p>Calculating the adjustment value for the <code>y</code> axis is identical but with the axis changed from <code>X</code> to <code>Y</code> so I'll leave that in your capable hands.
Now we have these two values we can make a <code>Point</code> representing our adjustment.</p>
<p>Now we have the adjustment it is a case of stepping along the line. We're going to use C#s yield feature allowing us to lazily return the values rather than building them up in memory.
It could be a very long line!?
I don't know <code>¯\_(ツ)_/¯</code></p>
<pre><code class="language-csharp">var adjustment = new Point(x, y);
var start = Start;
while (start != End)
{
yield return start;
start += adjustment;
}
yield return End;
</code></pre>
<p>We first yield the start of the line then we add our adjustment to get the next position along the line and so on and so forth until we reach the end.
Since our condition is when start is not equal to end we have to lastly return the End position.</p>
<p>Now we've got all our points we can work out where our lines overlap.
We're going to do this using linq and grouping and it may look like a load of noise but we'll go through it.</p>
<pre><code class="language-csharp">var numberOfOverlappingVents = ventLines
.Where(v => v.Type is LineType.Horizontal or LineType.Vertical)
.SelectMany(i => i.Points)
.GroupBy(i => i)
.Where(i => i.Count() >= 2)
.Select(i => i.Key)
.Count();
Console.WriteLine($"Number of Overlapping Vents: {numberOfOverlappingVents}");
</code></pre>
<p>So step by step here is what this word soup does:</p>
<ul>
<li><code>Where</code> filter the vent lines down to only those we know are Horizontal or Vertical</li>
<li><code>SelectMany</code> takes every point from each vents and returns them as one big list.</li>
<li><code>GroupBy</code> Take the one big list and put it into buckets based on the point. Because the same point can be shared by more than one vent that will be where they overlap.</li>
<li><code>Where</code> Now we have the points grouped up we only want the ones where the buckets have 2 or more in it. So nothing on its lonesome.</li>
<li><code>Select</code> Now we only want the point itself and don't care about the buckets we grouped them into since they're all the same.</li>
<li><code>Count</code> We don't actually care about which points, just how many so let's just get a count of them.</li>
</ul>
<p>And then we have the count of the overlapping points between the <em>horizonal</em> and <em>vertical</em> lines! Hurrah a ⭐ for us.</p>
<h1 id="part-2">Part 2</h1>
<p>So for part 2 we now need to consider the diagonal lines we dropped on the floor.
The input tells us kindly that all the inputs will be either horizontal, vertical or diagonal at exactly 45 degress.
This means we don't <em>have</em> to deal with any logic to verify the other lines are truly diagonal and just trust the input.
I'm going to but if you don't want to then feel free to look into calculating the slope of a line and using that to drop lines or error as you see fit.</p>
<p>If we go back to our parsing code we're going to adjust it slightly for the Vent Lines that are diagonal.</p>
<pre><code class="language-csharp">var ventLines = new List<VentLine>();
foreach (var line in lines)
{
var split = line.Split("->", StringSplitOptions.TrimEntries);
var start = Point.Parse(split[0]);
var end = Point.Parse(split[1]);
if (start.Y == end.Y)
{
return new GridLine(start, end, LineType.Horizontal);
}
else if (start.X == end.X)
{
return new GridLine(start, end, LineType.Vertical);
}
else
{
return new GridLine(start, end, LineType.Diagonal);
}
}
</code></pre>
<p>And with an anticlimatic boom that's part 2 completed besides actually calculating the overlapping vents again but this time including the diagonal lines.</p>
<pre><code class="language-csharp">var numberOfOverlappingVents = ventLines
.SelectMany(i => i.Points)
.GroupBy(i => i)
.Where(i => i.Count() >= 2)
.Select(i => i.Key)
.Count();
Console.WriteLine($"Number of Overlapping Vents: {numberOfOverlappingVents}");
</code></pre>
<p>The same logic as before without the filtering of any kind of vent lines. Nice and clean and shiny ⭐ for us.</p>
<p>Today we've got to avoid some hydrothermal vents if possible.
We definately don't want to go over those big ones though.</p>https://romanx.co.uk/posts/advent-of-code-2021-day-4Advent of Code 2021 - Giant Squid!2021-12-05T00:00:00Z<p>Welcome all, this is my new friend the Giant Squid.
Today we decided to play some bingo with them and see who would win first.
You can find todays challenge <a href="https://adventofcode.com/2021/day/4">here</a> and follow along with me or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-four/Challenge.cs">you can find it here.</a></p>
<h1 id="parsing-inputs">Parsing Inputs</h1>
<p>We're not going to have much of a parsing section today since most of the problem here is solved by parsing the input into something that can be used for solving the problem.</p>
<p>I will mention that when handling the input I broke it up into separate sections delimited by empty lines, you can think of these as paragraphs.</p>
<p>Now you have a list of paragraphs you can treat them individually so the first item is the sequence of numbers we've been given and everything after is a grid to be parsed.</p>
<h1 id="part-1">Part 1</h1>
<p>I actually went a different way with this at first and then revised my solution after completing both parts since it both made more sense and I understood the problem better.</p>
<p>Initially I wen't with a simple solution of parsing out each of the grids, then drawing each number in turn and marking them off on all the grids.
After marking the number on each grid I checked if it had won and if so stopped and basked in my glory.</p>
<p>When looking at this again, I realised that the sequence of numbers we were given reflected each turn that would be played.
So when parsing the inputs I could also look at when each number would be marked off in the turn order and create a map of this from <code>number -> turn</code></p>
<pre><code class="language-csharp">var numbersAndTurn = paragraphs[0]
.Split(',')
.Select(int.Parse)
.Index(startIndex: 1)
.ToDictionary(x => x.Value, x => x.Key);
var grids = new List<BingoGrid>();
var scratch = new (int Turn, int Number)[5, 5];
foreach (var grid in paragraphs[1..])
{
grids.Add(ParseGrid(grid, scratch, numbersAndTurn));
}
readonly record struct BingoGrid(int WinningTurn, int FinalScore);
</code></pre>
<p>Now we have a map of numbers to the turn that they will be marked.
Using this we can loop through the rest of the paragraphs and parse the grids individually.
I'm trying to be conservitive with memory here by reusing the same 5x5 grid when calculating the turn that a grid wins on and what it's final score is.</p>
<p>The next bit is where the real logic of the challenge comes into focus in the <code>ParseGrid</code> method.</p>
<pre><code class="language-csharp">var span = scratch.AsSpan2D(); // Microsoft.Toolkit.HighPerformance
for (var y = 0; y < grid.Length; y++)
{
var row = grid[y].Split(' ', StringSplitOptions.RemoveEmptyEntries);
for (var x = 0; x < row.Length; x++)
{
var number = int.Parse(row[x]);
span[x, y] = (numbersOnTurn[number], number);
}
}
</code></pre>
<p>Hopefully the logic here is quite clear, we go through each line in the grid, split it on a space and then go through each number individually.
It's worth nothing that the way the grids are formatted on the input we will still have some leading/trailing whitespace but <code>int.Parse</code> doesn't care about this so we'll move on with our lives.</p>
<p>Once we have the number we will set it in the grid as a <a href="https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/value-tuples">tuple</a> of two <code>ints</code> comprising of the Turn and the Number itself.
This allows us the group the two pieces of information together for each piece of the grid.
Another option would be to use a class or struct but I find this clearer for local calculations.</p>
<p>Now we have this information we can go through each row and column finding out when they would be completed.
The earliest turn that a row or column is completed is the winning turn for the grid.</p>
<pre><code class="language-csharp">var winningTurns = new List<int>(10);
for (var y = 0; y < span.Height; y++)
{
var last = -1;
foreach (var (turn, _) in span.GetRow(y)) // Microsoft.Toolkit.HighPerformance
{
last = Math.Max(turn, last);
}
winningTurns.Add(last);
}
for (var x = 0; x < span.Width; x++)
{
var last = -1;
foreach (var (turn, _) in span.GetColumn(x)) // Microsoft.Toolkit.HighPerformance
{
last = Math.Max(turn, last);
}
winningTurns.Add(last);
}
var winningTurn = winningTurns.Min();
</code></pre>
<p>To find the winning turns we loop through each of the rows and columns.
The <code>Span2d</code> type I'm using here give nice helpers for iterating over a row or a column although you could write these yourself on a standard multidimensional array. See the section on Span2d below for more information.</p>
<p>Here i'm keeping track of all winning turns but you could easily rewrite this to perform the same logic with <code>Math.Min</code> as I am finding the last number marked in the column/row with <code>Math.Max</code>.
It's easy to miss the edge case here with the <code>-1</code> this is since we know that no cell will ever be less than turn 1 so we can make sure we always get the maximum here since they will all be above it.</p>
<p>Now we have the turn that the grid won on we can calculate the score and the last number that got set.</p>
<pre><code class="language-csharp">var winningNumber = numbersOnTurn
.First(x => x.Value == winningTurn)
.Key;
var score = 0;
for (var y = 0; y < span.Height; y++)
{
foreach (var (turn, number) in span.GetRow(y))
{
if (turn > winningTurn)
{
score += number;
}
}
}
return new BingoGrid(winningTurn, winningNumber * score);
</code></pre>
<p>Since we have a map of number to turn going the other direction is a bit of a pain so i've used some simple Linq here.
An alternative would be to create another dictionary going the other direction and if this were a bottleneck that would be a good fix.
For here though? It's good enough.</p>
<p>The same with calculating the score.
I kept wracking my brain to figure out a way to do it while finding the earliest turn above but without keeping a score for each candidate turn I couldn't think of one so I decided to do the simple.</p>
<p>Loop through our grid, find any that are set after the winning turn (which means they must be unmarked when we won) and add them to our score.
The final score is multiplying the score together with the number that we last marked to win the game.</p>
<pre><code class="language-csharp">var winner = grids.MinBy(grid => grid.WinningTurn);
Console.WriteLine($"Winning Turn {winner.WinningTurn}");
Console.WriteLine($"Winner Score {winner.FinalScore}");
</code></pre>
<p>So actually completing part 1 after all that madness? Nice and clean.
We're using the newly added <code>MinBy</code> linq operator in .NET 6 which finds us the minimum by a given value in collection while but without changing the type of the collection.
Here's our lovely shiny ⭐ for part 1.</p>
<h2 id="part-2">Part 2</h2>
<p>Well for us all our hard work above pays off, we now need to find the last grid to win.</p>
<pre><code class="language-csharp">var worstGrid = grids.MaxBy(grid => grid.WinningTurn);
Console.WriteLine($"Last Winning Turn {worstGrid.WinningTurn}");
Console.WriteLine($"Last Winner Score {worstGrid.FinalScore}");
</code></pre>
<p>We get to use the sibling of the <code>MinBy</code> operator the <code>MaxBy</code> operator! It does the exact opposite of before.</p>
<p>Here's our well earned ⭐ for part 2.</p>
<hr />
<h3 id="microsoft.toolkit.highperformance-span2d">Microsoft.Toolkit.HighPerformance - Span2d</h3>
<p>The eagle-eyed among you may have noticed a method called <code>AsSpan2D()</code> with a comment next to it.
This is an extension method provided by the <code>Microsoft.Toolkit.HighPerformance</code> nuget package that has some lovely helpers for dealing with common tasks that often have performance sensitive characteristics.
One of these tasks is dealing with data in a 2d multidimensional grid so <code>int[,]</code> not <code>int[][]</code> which is known as a <a href="https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/arrays/jagged-arrays">Jagged array</a></p>
<p>For more information on this package I'd recommend taking a look at the <a href="https://docs.microsoft.com/en-us/windows/communitytoolkit/high-performance/introduction">introduction</a> and having a play yourself.</p>
<p>I will try to make it clear when I'm using one of the methods from libraries.</p>
<p>Welcome all, this is my new friend the Giant Squid.
Today we decided to play some bingo with them and see who would win first.
You can find todays challenge <a href="https://adventofcode.com/2021/day/4">here</a> and follow along with me or if you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-four/Challenge.cs">you can find it here.</a></p>https://romanx.co.uk/posts/advent-of-code-2021-day-3Advent of Code 2021 - Binary Diagnostic!2021-12-03T00:00:00Z<p>Lets lead with the fact I'm not that good at binary and I find these problems harder than I feel I should. I did solve it however and you can find todays challenge <a href="https://adventofcode.com/2021/day/2">here</a> and follow along with me.</p>
<p>If you'd rather just read the code then <a href="https://github.com/Romanx/AdventOfCode/blob/main/src/years/2021/day-three/Challenge.cs">you can find it here.</a></p>
<h1 id="part-1">Part 1</h1>
<p>We're going to skip parsing today since we're going to read our data as characters and get some information on the input as we go for the problem.
I'm not sure if there's a nice binary method of finding the most common bit in a position based on a set of binary values so instead I decided to create my own map of the information upfront and reuse it.</p>
<p><em>Note:</em> It's worth adding that I rewrote these methods multiple times through part 1 and part 2 as my assumptions proved wrong.
Don't worry too much if you have to rewrite parts of what you've already done, just keep an eye you don't start getting different results since it's hard to work backwards to where something broke.</p>
<p>Two approaches of calculating the position information struck me at first and both seemed equally as much work (in terms of execution).</p>
<ul>
<li>You loop through each number in turn and then through each position in the number.</li>
<li>You loop through each position and then you loop through each number in turn.</li>
</ul>
<p>I ended up on the latter approach after getting to part 2 and seeing it would better for reuse there.
I'm using a readonly record struct again here for ease.</p>
<pre><code class="language-csharp">static PositionInfo CalculatePositionInfo(int index, IEnumerable<string> numbers)
{
var zeroes = 0;
var ones = 0;
foreach (var number in numbers)
{
var span = number.AsSpan();
var value = span[index];
if (value is '1')
{
ones++;
}
else
{
zeroes++;
}
}
return new PositionInfo(ones, zeroes);
}
readonly record struct PositionInfo(int NumberOfOnes, int NumberOfZeros);
</code></pre>
<p>Now we can calculate the position info for a specific index in the set of numbers.
We can use this to calculate a map of position to info.</p>
<pre><code class="language-csharp">static Dictionary<int, PositionInfo> ParseBitIndexCounts(IEnumerable<string> lines)
{
var dictionary = new Dictionary<int, PositionInfo>();
var arr = lines.ToArray();
var numberLength = arr[0].Length;
for (var i = 0; i < numberLength; i++)
{
var info = CalculatePositionInfo(i, arr);
dictionary[i] = info;
}
return dictionary;
}
</code></pre>
<p>With this map we can calculate the information we need for part 1.</p>
<pre><code class="language-csharp">var bitInformation = ParseBitIndexCounts(numbers);
var gammaRateBits = CalculateGammaRate(bitInformation);
var gammaRateValue = Convert.ToInt32(gammaRateBits, 2);
var epsilonRateBits = CalculateEpsilonRate(gammaRateValue, bitInformation.Count);
var epsilonRateValue = Convert.ToInt32(epsilonRateBits, 2);
Console.WriteLine($"Gamma Rate Bits {gammaRateBits}");
Console.WriteLine($"Epsilon Rate Bits {epsilonRateBits}");
Console.WriteLine($"Gamma Rate Value {gammaRateValue}");
Console.WriteLine($"Epsilon Rate Value {epsilonRateValue}");
Console.WriteLine($"Power Consumption {gammaRateValue * epsilonRateValue}");
static string CalculateGammaRate(Dictionary<int, PositionInfo> bitIndexCounts)
{
Span<char> gammaRate = new char[bitIndexCounts.Count];
foreach (var (index, info) in bitIndexCounts)
{
gammaRate[index] = info.NumberOfOnes > info.NumberOfZeros
? '1'
: '0';
}
return new string(gammaRate);
}
static string CalculateEpsilonRate(int gammaRate, int length)
{
var str = Convert.ToString(~gammaRate, 2);
return str[^length..];
}
</code></pre>
<p>Some of this code is used for debugging.
But is useful to see how the problem is solved.
To calculate the gamma rate we loop through the information map we generated, and set the values in an array.
We're using a <code>Span<char></code> here since we're going to be using this bit representation to get a decimal value and there's a useful overload that takes a <code>ReadOnlySpan<char></code>.</p>
<p>To convert a binary string into a decimal representation we can use a useful method <code>Convert.ToInt32(string, int)</code> the second parameter hints what base the binary string is in allowing us to parse base 2 strings i.e. binary.</p>
<p>To calculate the Epsilon Rate it is the binary inverted representation of the Gamma Rate. We could loop through and turn all the <code>'0'</code>s to <code>'1'</code>s or since we have the decimal representation we can use the Bitwise complement operator <code>~</code> operator to reverse all the bits for us.</p>
<p>I'm converting the inverted value into a string so we can make the binary value is correct but we could just short circuit that and use the inverted value direct.</p>
<p>Multiply the two together and we have our result. One glorious ⭐ for our radar antenna.</p>
<h1 id="part-2">Part 2</h1>
<p>For part 2 we have to narrow our input to find the Oxygen generator and C02 scrubber ratings.
Each of these have a bit critera to determine which bit value we're looking to filter our candidate values by.</p>
<pre><code class="language-csharp">static int FindTargetValue(
string[] numbers,
Func<int, string, PositionInfo, bool> criteriaFunction)
{
var index = 0;
var workingSet = new List<string>(numbers);
while (workingSet.Count > 1)
{
var scratch = new List<string>(workingSet);
var info = CalculatePositionInfo(index, scratch);
foreach (var number in workingSet)
{
if (criteriaFunction(index, number, info) is false)
{
scratch.Remove(number);
}
}
workingSet = scratch;
index++;
}
return Convert.ToInt32(workingSet[0], 2);
}
</code></pre>
<p>To find the target value we loop through each position and reduce the working set of numbers down by the criteria provided.
We have two sets of numbers since if you try to remove from a set that you're iterating over you'll get an exception so we copy the list and remove anything that doesn't match our critera and then make the result the next working set and move to the next index.
Once we have a single result then we conver the binary result to decimal value which is the number we were looking for.</p>
<pre><code class="language-csharp">static bool OxygenCriteria(int index, string number, PositionInfo info)
{
if (info.NumberOfOnes >= info.NumberOfZeros)
{
return number[index] == '1';
}
else
{
return number[index] == '0';
}
}
static bool ScrubberCriteria(int index, string number, PositionInfo info)
{
if (info.NumberOfZeros <= info.NumberOfOnes)
{
return number[index] == '0';
}
else
{
return number[index] == '1';
}
}
</code></pre>
<p>Here are our two critera functions.
We take the index, the number we're looking at and the information for the position.
The comparision here is important since if the number of zeroes and ones match then depending on the critera we wan't to set either <code>'0'</code> or <code>'1'</code>.</p>
<p>Now we have the criteria functions and the function to search for the value that match the criteria in full. Our solution part 2 becomes quite simple excluding the functions above.</p>
<pre><code class="language-csharp">var oxygenRating = FindTargetValue(numbers, OxygenCriteria);
var scrubberRating = FindTargetValue(numbers, ScrubberCriteria);
Console.WriteLine($"Oxygen Rating {oxygenRating}");
Console.WriteLine($"CO2 scrubber rating {scrubberRating}");
Console.WriteLine($"Life Support Rating {oxygenRating * scrubberRating}");
</code></pre>
<p>And there we get the second ⭐ of the day.
I think there is probably a neat bit operation method of doing part 1 and I'd be interested to see it but I'm quite happy with the solution I ended up with.</p>
<p>Lets lead with the fact I'm not that good at binary and I find these problems harder than I feel I should. I did solve it however and you can find todays challenge <a href="https://adventofcode.com/2021/day/2">here</a> and follow along with me.</p>