Advent Of Code Day 10: Backtracking and Dynamic Programming

Howdy Everyone,

  Catching up on the Advent of Code, I got to day 10 today, here it is: Day 10 - Advent of Code 2020. 

Description is a little long and tedious but in the end you get the gist of it. Part 1 is looking for a simple path from 0 to max. I looked at the input size and it did not seem that large, so I thought backtracking would do the trick. Indeed a simple straightforward DFS backtracking from 0 to max works. Part 2 asks for the count of ALL paths. That's a little tricky, especially after reading this part of the description:

You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.

That should give you the hint that the "adventers" are looking for a Dynamic Programming (DP) solution. Luckily, this DP is super simple, and the way that I like to implement DP is by construction from 0..max. Basically I start solving the problems for n=0, 1, 2, ..., max, using previously solved (and stored) solutions. Also worked well. Make sure to use a long for your DP solution storage as the number of paths will grow rather quickly. Code is below, cheers, ACC.

static void Main(string[] args)
{
    FileInfo fi = new FileInfo("input.txt");
    StreamReader sr = fi.OpenText();
    Hashtable volts = new Hashtable();
    int max = 0;
    while (!sr.EndOfStream)
    {
        string str = sr.ReadLine().Trim();
        if (!String.IsNullOrEmpty(str))
        {
            int n = Int32.Parse(str);
            max = Math.Max(max, n);
            volts.Add(n, true);
        }
    }
    sr.Close();

    int[] diff = new int[4]; //Ignore diff[0]
    int totalUsed = 0;
    if (AdaptationPartOne(volts, 0, ref totalUsed, ref diff))
    {
        Console.WriteLine("Found a path!");
        for (int i = 1; i <= 3; i++)
        {
            Console.WriteLine("Diff of {0}: {1}", i, diff[i]);
        }
        long sol = diff[1];
        sol *= diff[3];
        Console.WriteLine("Solution: {0}", sol);
    }
    else
    {
        Console.WriteLine("Not path found!");
    }

    long sol2 = AdaptationPartTwo(volts, max);
    Console.WriteLine("Number of combinations: {0}", sol2);
}

public static long AdaptationPartTwo(Hashtable volts,
                                        int max)
{
    if (!volts.ContainsKey(0)) volts.Add(0, true);
    long[] dp = new long[max + 1];

    dp[0] = 1;
    for (int i = 1; i <= max; i++)
    {
        if (volts.ContainsKey(i))
        {
            for (int d = 1; d <= 3; d++)
            {
                if (i - d >= 0)
                {
                    dp[i] += dp[i - d];
                }
            }
        }
    }

    return dp[max];
}
public static bool AdaptationPartOne(Hashtable volts,
                                        int currentVoltage,
                                        ref int totalUsed,
                                        ref int[] diff)
{
    if (totalUsed == volts.Count)
    {
        //Account for the last device...
        diff[3]++;
        return true;
    }

    for (int i = 1; i <= 3; i++)
    {
        int next = currentVoltage + i;
        if (volts.ContainsKey(next) && (bool)volts[next])
        {
            volts[next] = false;
            diff[i]++;
            totalUsed++;
            if (AdaptationPartOne(volts, next, ref totalUsed, ref diff)) return true;
            totalUsed--;
            diff[i]--;
            volts[next] = true;
        }
    }

    return false;
}