Day 12 is here, time for recursion again! There are probably some fancy path finding algorithms out there, but I'm not very good with algorithms. Or, atleast I don't know them by name and use case.

Today we're making our way through a cave system, and we need to find all the possible, valid paths that we might take. Our input will help us map out the cave system:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

This describes the way the different caves are connected. Uppercase means it's a large cave, lower case means it's a small cave. This makes a difference since large caves can be visited as many times as you like, small caves have some restrictions. For Part 1, we can only visit each small cave once per path. For Part 2, we can visit one small cave twice, and the rest of them once per path. The input above describes cave that looks like this:

    start
    /   \
c--A-----b--d
    \   /
     end

For both parts, we need to find out how many valid paths there is through the cave system (from start to end), given the limitations of small caves mentioned above.

First, lets create a map of the cave system:

var input = File.ReadAllLines("input.txt");

var map = new Dictionary<string, List<string>>();
foreach (var line in input)
{
    var values = line.Split('-');

    if (map.ContainsKey(values[0]))
    {
        map[values[0]].Add(values[1]);
    }
    else
    {
        map.Add(values[0], new List<string> { values[1] });
    }

    if (map.ContainsKey(values[1]))
    {
        map[values[1]].Add(values[0]);
    }
    else
    {
        map.Add(values[1], new List<string> { values[0] });
    }
}

Using this, we can always use any part of the cave as key, and find all connections to that part.

We're going to solve this in almost the same way for both parts. We'll pass a bool to the function that checks if the next step is a valid step in the current path to perform different checks depending om which part we want to solve, that's the only difference.

private static List<List<string>> BuildPaths(Dictionary<string, List<string>> map, List<string> currentPath, bool isPart1)
{
    var lastStep = currentPath.Last();
    if (lastStep == "end")
    {
        return new List<List<string>> { currentPath };
    }

    var possibleSteps = map[lastStep].Where(x => currentPath.IsValidStepPart(x, isPart1));

    if (!possibleSteps.Any())
    {
        return new List<List<string>>();
    }

    return possibleSteps
        .Select(step => new List<List<string>> { currentPath, new List<string> { step } }.SelectMany(x => x).ToList())
        .SelectMany(x => BuildPaths(map, x, isPart1)).ToList();
}

So we start by passing our map and a list containing "start" as the currentPath. If the last step is "end", we're done and we can return the path. If there are no more possible steps and we haven't reached "end", we'll return an empty list as this isn't a valid path. Finally, for any possible steps left we'll add that step to the current path and keep on building on those paths until they eventually reach "end" or fail.

The logic for deciding if a step is valid is quite simple, but differs slightly between Part 1 and Part 2:

public static bool IsValidStepPart(this IEnumerable<string> path, string step, bool isPart1)
{
    if (step.All(c => char.IsUpper(c)))
    {
        return true;
    }

    if (isPart1)
    {
        return !path.Contains(step);
    }
    else
    {
        if (step == "start")
        {
            return false;
        }

        return !path.Contains(step) || path.Where(IsLower).Count() == path.Where(IsLower).Distinct().Count();
    }
}

If it's a large cave (meaning, if it's uppercase), it's always fine since we can visit those as much as we want. If it's Part 1, we need to check if the path already contains the current step, which will be a small cave if e reach this point. If it's Part 2, we need to make sure we're not returning to start. We'll also check if the path contains the step. If it doesn't, we're fine. If it does, we need to make sure that we haven't already visited another cave twice. We do that by comparing the count of small caves with the distinct count of small caves. These will be the same until after we've visited one small cave twice.