Advent of code 2023 - day 5 (excel + C#)

Categories: .NET C#, programming challenge, Excel
The elves are asking for help to organize and understand their food production problem. I started this exercise with excel and switched to C# to solve the second part of the problem.

Part 1

The description of this puzzle is fairly long. Please refer to the full text here.

[...]

Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?

I first tried to tackle this problem in excel.
We can layout all maps (source category to destination category), with each category in a different sheet. Here's an example of my seed-to-soil map:

Source, destination and range are simply extracted from the input with excel substring functions (LEFT, MID, RIGHT). We use CLEAN to ensure no hidden characters are copied over and multiple by 1 to ensure it is treated as a number.
source: =CLEAN(MID(A2,LEN(C2)+2,FIND(" ",A2,LEN(C2)+2)-LEN(C2)-2))*1
destination: =CLEAN(LEFT(A2,FIND(" ",A2) - 1))*1
range: =CLEAN(RIGHT(A2,LEN(A2)-LEN(B2)-LEN(C2)-2))*1
All maps have to be sorted by source, as we will find out later.

Once all maps are laid out we can calculate the destination categories for each source category, starting with the input (seeds).

The formula for each category are very similar to one another. Only the selected sheet and columns are different. I will only cover the first one (soil) here:
=IFNA(IF(VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$D,3,TRUE)<A2,A2, A2-VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$C,2,TRUE)),A2)
This looks a bit intimidating at first, so let's cut it down into smaller pieces.

VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)
This looks for the destination value that corresponds to the source. Naturally, it is very unlikely to give an exact match. In that case it should find the row with its source the closest to, and lower than the input. VLOOKUP always returns the result before the search value. For this reason all maps should be sorted by source!

VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$D,3,TRUE)<A2
This checks if the input fits in the range [source...source+range[. If it doesn't then we know that there is no mapping for the given input and we can fall back to the input as destination:

IF(
VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$D,3,TRUE)<A2,
A2,
A2-VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$C,2,TRUE)
)

Lastly, it's still possible to find N.A. if the input is less than the first source. In that case we can also fall back to the input as destination:
=IFNA(
IF(
VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$D,3,TRUE)<A2,
A2,
A2-VLOOKUP(A2,'seed to soil'!$B:$B,1,TRUE)+VLOOKUP(A2,'seed to soil'!$B:$C,2,TRUE)
), A2)

The lowest location (column H) is the answer we're looking for.
As always the solution can be found in my GitHub repository.

Part 1 - alternative in C#

Part 2 will be done in C#, so I will cover part 1 again here in C#. Consider it an introduction to part 2.

We can represent each of the seven maps by a an instance of a class. A dictionary does not suffice because, contrary to a dictionary, we have a length in play as well. We'll have to create a custom class. Let's call it CategoryMap. Each map has a list of category ranges. 

C#
internal class CategoryMap
{
    public readonly struct CategoryRange(long source, long destination, long length)
    {
        public readonly long Source = source;
        public readonly long Destination = destination;
        public readonly long Length = length;
    }
    private readonly List<CategoryRange> _categoryRanges = new List<CategoryRange>();
    public void Add(long source, long destination, long length)
    {
        _categoryRanges.Add(new CategoryRange(source, destination, length));
    }
}

Now the input can be parsed to a list of category maps.

C#
string inputUrl = "https://adventofcode.com/2023/day/5/input";
var inputLines = await InputHelper.GetInputLines<string[]>(inputUrl, argumentSeparatorRegex: " ");

List<CategoryMap> maps = new List<CategoryMap>();
CategoryMap map = null;
foreach(var inputLine in inputLines.Skip(1))
{
    if (inputLine.Last() == "map:")
    {
        map = new CategoryMap();
        maps.Add(map);
        continue;
    }
    map.Add(long.Parse(inputLine[1]), long.Parse(inputLine[0]), long.Parse(inputLine[2]));
}

Next, we have to find the location number for each seed. We can do this by iterating over all the maps, calculating the destination category for the source category, and setting this to new source category. 

C#
long GetLocationNumber(long seed)
{
    long destinationCategory = seed;
    foreach(var map in maps)
    {
        destinationCategory = map.GetDestinationCategory(destinationCategory);
    }
    return destinationCategory;
}
C#
internal class CategoryMap
{
    //other code omitted
    public long GetDestinationCategory(long sourceCategory)
    {
        foreach (var range in _categoryRanges)
        {
            long diff = sourceCategory - range.Source;
            if (diff >= 0 && diff < range.Length)
                return range.Destination + diff;
        }
        return sourceCategory;
    }
}

All that's left now is finding the minimum location number for the given seed numbers.

C#
IReadOnlyList<long> seeds = inputLines[0].Skip(1).Select(long.Parse).ToList();
Console.WriteLine("Part 1 - lowest location number: " + seeds.Min(GetLocationNumber));

Part 2

Everyone will starve if you only plant such a small number of seeds. Re-reading the almanac, it looks like the seeds: line actually describes ranges of seed numbers.

The values on the initial seeds: line come in pairs. Within each pair, the first value is the start of the range and the second value is the length of the range. So, in the first line of the example above:

seeds: 79 14 55 13

This line describes two ranges of seed numbers to be planted in the garden. The first range starts with seed number 79 and contains 14 values: 79, 80, ..., 91, 92. The second range starts with seed number 55 and contains 13 values: 55, 56, ..., 66, 67.

Now, rather than considering four seed numbers, you need to consider a total of 27 seed numbers.

In the above example, the lowest location number can be obtained from seed number 82, which corresponds to soil 84, fertilizer 84, water 84, light 77, temperature 45, humidity 46, and location 46. So, the lowest location number is 46.

Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?

What this means is that we will now work with category ranges instead of category numbers. We have to calculate all the location number ranges for a given list of seed ranges. This also means that as we are iterating over all the maps, the amount of category ranges increased exponentially because one source category range can map to multiple destination category ranges.

C#
IReadOnlyList<(long, long)> GetLocationNumberRanges((long, long) seedRange)
{
    List<(long, long)> destinationCategoryRanges = new List<(long, long)>() { seedRange };
    foreach (var map in maps)
    {
        var destinationCategoryRangesCopy = new List<(long, long)>(destinationCategoryRanges);
        destinationCategoryRanges.Clear();
        foreach (var destinationCategoryRange in destinationCategoryRangesCopy)
        {
            destinationCategoryRanges.AddRange(
                map.GetDestinationCategoryRanges(destinationCategoryRange));
        }
    }
    return destinationCategoryRanges;
}

The algorithm to calculate destination category ranges for a source category range works as follows:

  1. Initialize variables "sourceCategory" and "sourceRange" (length) from the method parameter.
  2. Initialize variable "destinationCategoryRanges" to an empty list. This will hold all found destination category ranges.
  3. Sort all category ranges in the map by source.
  4. While sourceRange is greater than 0:
    1. Based on sourceCategory and sourceRange, try to find a destination category range from _categoryRanges that fits.
    2. If no possible destination category range is found, use the source category as destination category, with length up until the next fitting _categoryRanges. To find the first fitting _categoryRanges for the remaining length it's important to have it sorted by Source.
    3. Add the found destination category range to destinationCategoryRanges.
    4. Increase sourceCategory by the found length and decrease sourceRange by the found length.
C#
internal class CategoryMap
{
    //other code omitted
    public IReadOnlyList<(long, long)> GetDestinationCategoryRanges((long sourceCategory, long sourceRange) sourceCategoryRange)
    {
        List<(long, long)> destinationCategoryRanges = new List<(long, long)>();
        long sourceCategory = sourceCategoryRange.sourceCategory;
        long sourceRange = sourceCategoryRange.sourceRange;

        var sortedCategoryRanges = _categoryRanges.OrderBy(x => x.Source).ToList();
        while (sourceRange > 0)
        {
            bool found = false;
            foreach (var categoryRange in sortedCategoryRanges)
            {
                long diff = sourceCategory - categoryRange.Source;
                if (diff >= 0 && diff < categoryRange.Length)
                {
                    long destination = categoryRange.Destination + diff;
                    long length = Math.Min(categoryRange.Length - diff, sourceRange);
                    destinationCategoryRanges.Add((destination, length));
                    found = true;
                    sourceCategory += length;
                    sourceRange -= length;
                    break;
                }
            }
            if (!found)
            {
                long destination = sourceCategory, length;
                int nextCategoryRangeIndex = sortedCategoryRanges.IndexWhere(x => x.Source > sourceCategory);
                if (nextCategoryRangeIndex == -1) //no more number ranges will cover the remaining sourceCategoryRange
                    length = sourceRange;
                else
                    length = sortedCategoryRanges[nextCategoryRangeIndex].Source - sourceCategory;
                destinationCategoryRanges.Add((destination, length));
                sourceCategory += length;
                sourceRange -= length;
            }
        }
        return destinationCategoryRanges;
    }
}

We can now find the lowest location number for any of the seed ranges.

C#
List<(long, long)> seedRanges = new List<(long, long)>();
for(int i = 0; i < seeds.Count-1; i+= 2)
{
    seedRanges.Add((seeds[i], seeds[i + 1]));
}
Console.WriteLine("Part 2 - lowest location number: " 
    + seedRanges.Min(x => GetLocationNumberRanges(x).Select(y => y.Item1).Min()));