Advent of Code Day 17–Filling the Fridge

In day 17 of the Advent of Code challenge, we have 150 litres of eggnog and need to work out all the ways of using our various containers to store that amount. The brute force solution to this problem involves checking the “power set” of our containers, but the solution I show in C# and F# performs much faster than this.

Here’s my C# code, which uses a recursive function called Distribute to return all the combinations of containers whose sizes add up to exactly 150

void Main()
{
    var sizes = File.ReadAllLines("day17.txt")
        .Select(int.Parse)
        .ToList();
    var combs = Distribute(new List<int>(), sizes, 150).ToList();
    combs.Count.Dump("a");
    var min = combs.Min(p => p.Count);
    combs.Count(p => p.Count == min).Dump("b");
}

IEnumerable<List<int>> Distribute(List<int> used, List<int> pool, int amount)
{
    var remaining = amount - used.Sum();
    for (int n = 0; n < pool.Count; n++)
    {
        var s = pool[n];
        if (pool[n] > remaining) continue;
        var x = used.ToList();
        x.Add(s);
        if (s == remaining)
        {
            yield return x;
        }
        else
        {
            var y = pool.Skip(n+1).ToList();
            foreach (var d in Distribute(x, y, amount))
            {
                yield return d;
            }
        }
    }
}

And here’s a slower but more concise C# solution using power sets (note that there was a bug in the code when I showed this in the video)

var containers = new int[] { 11, 30, 47, 31, 32, 36, 3, 1, 5, 3, 32, 36, 15, 11, 46, 26, 28, 1, 19, 3 };
var powerset = Enumerable.Range(1, (1 << containers.Length) - 1)
  .Select(n => containers.Where((_, bit) => ((1 << bit) & n) != 0).ToList());
var solutions = powerset.Where(c => c.Sum() == 150).ToArray();
solutions.Length.Dump("a");
var min = solutions.Min(s => s.Count);
solutions.Count(s => s.Count == min).Dump("b");

And here’s my F# solution which uses the recursive method again for performance, and also enjoys other performance benefits due to F#’s immutable lists:

let containers = "day17.txt" |> File.ReadAllLines |> Seq.map int |> Seq.toList

let rec distribute used pool target runningTotal = seq {
    match pool with 
    | h::tail ->
        if h + runningTotal = target then 
            yield h::used |> List.toArray
        elif h + runningTotal < target then 
            yield! distribute (h::used) tail target (h + runningTotal)
        yield! distribute used tail target runningTotal
    | _ -> ()
    }

let perms = distribute [] containers 150 0 |> Seq.toArray

perms.Length |> printfn "a: %d"
let m = perms |> Seq.map (fun f -> f.Length) |> Seq.min
perms |> Seq.filter (fun a -> a.Length = m) |> Seq.length |> printfn "b: %d"