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;
}
Comments
Post a Comment
[γγ¬γΌγ ]