Advent of Code Day 15–Cookie Calorie Counting

In day 15 of the Advent of Code challenge we’re trying to make the most delicious cookie possible, using 100 teaspoons of ingredients. In today’s video I explain how I solved this challenge in C# using LINQ as well as an F# version of the solution

My C# code isn’t particularly optimal. I went for an Ingredient class and I did decide to overload the + and * operators as a way to make the cookie scoring simpler. However, as I said in the video, my initial solution to distributing the 100 teaspoons between the 4 ingredients was over-complicated. I made a solution (the Distribute method) that worked for any number of ingredients, but had I just made one that worked for 4, the code could be greatly simplified. The Distribute4 method shows how this can be done.

void Main()
{
    var realInput = new[] { 
        "Frosting: capacity 4, durability -2, flavor 0, texture 0, calories 5",
        "Candy: capacity 0, durability 5, flavor -1, texture 0, calories 8",
        "Butterscotch: capacity -1, durability 0, flavor 5, texture 0, calories 6",
        "Sugar: capacity 0, durability 0, flavor -2, texture 2, calories 1"
    };
    var ingredients = realInput
        .Select(i => i.Replace(",", "").Replace(":", "").Split(' '))
        .Select(p =>
    new Ingredient
        {
            Capacity = int.Parse(p[2]),
            Durability = int.Parse(p[4]),
            Flavor = int.Parse(p[6]),
            Texture = int.Parse(p[8]),
            Calories = int.Parse(p[10])
        }
    )
    .ToArray();

    var scores = Distribute4(100) // or Distribute(new int[ingredients.Length], 100, 0)
                    .Select(r => ScoreCookie(ingredients, r))
                    .ToArray();

    scores.Max(r => r.Item1).Dump("a"); //18965440
    scores.Where(r => r.Item2 == 500).Max(r => r.Item1).Dump("b"); //18965440
}

Tuple<int,int> ScoreCookie(Ingredient[] ingredients, int[] amounts)
{
    var p = ingredients
                .Zip(amounts, (ing, amount) => ing * amount)
                .Aggregate((a, b) => a + b);
    return Tuple.Create(p.Score, p.Calories);
}

class Ingredient
{
    public int Capacity { get; set; }
    public int Durability { get; set; }
    public int Flavor { get; set; }
    public int Texture { get; set; }
    public int Calories { get; set; }
    public static Ingredient operator +(Ingredient x, Ingredient y)
    {
        return new Ingredient { 
            Capacity = x.Capacity + y.Capacity,
            Durability = x.Durability + y.Durability,
            Flavor = x.Flavor + y.Flavor,
            Texture = x.Texture + y.Texture,
            Calories = x.Calories + y.Calories
        };
    }
    public static Ingredient operator *(Ingredient x, int n)
    {
        return new Ingredient { 
            Capacity = x.Capacity * n,
            Durability = x.Durability * n,
            Flavor = x.Flavor * n,
            Texture = x.Texture * n,
            Calories = x.Calories * n
        };
    }
    public int Score
    {
        get { return Math.Max(0, Capacity) * Math.Max(0, Texture) * Math.Max(0, Flavor) * Math.Max(0, Durability); }
    }
}

IEnumerable<int[]> Distribute(int[] start, int target, int len)
{
    var remaining = target - start.Sum();
    if (len == start.Length - 1)
    {
        var x = start.ToArray();
        x[len] = remaining;
        yield return x;
    }
    else
    {
        for (int n = 0; n < remaining; n++)
        {
            var x = start.ToArray();
            x[len] = n;
            foreach (var d in Distribute(x, target, len + 1))
            {
                yield return d;
            }
        }
    }
}

IEnumerable<int[]> Distribute4(int max)
{
    for (int a = 0; a <= max; a++)
    for (int b = 0; b <= max - a; b++)
    for (int c = 0; c <= max - a - b; c++)
    yield return new[] { a, b, c, max - a - b - c};
}

As for F#, I decided against an Ingredient type, and went just for arrays of integers. This meant I needed to work out how to multiply every value in an array by a single number and how to add together several integer arrays with the same number of elements. This is done with Seq.reduce and Array.map2. As with the C# solution I overthought distributing the teaspoons between the ingredients. The F# distribute is a bit nicer than the C# one, but I also show a distribute4 which is what I probably should have used.

let input = [|"Frosting: capacity 4, durability -2, flavor 0, texture 0, calories 5";
    "Candy: capacity 0, durability 5, flavor -1, texture 0, calories 8";
    "Butterscotch: capacity -1, durability 0, flavor 5, texture 0, calories 6";
    "Sugar: capacity 0, durability 0, flavor -2, texture 2, calories 1"|]

let ingredients = input |> Array.map (fun f -> [| for m in Regex.Matches(f,"\-?\d+") -> int m.Value |]) 

let rec distribute state total maxlen = seq {
    let remaining = total - (Seq.sum state)
    
    match List.length state with
        | l when l = maxlen - 1 -> yield remaining::state
        | _ -> for n in 0..remaining do yield! distribute (n::state) total maxlen
}            

let scoreCookie amounts = 
    let p = ingredients 
            |> Seq.zip amounts 
            |> Seq.map (fun (amount, ing) -> ing |> Array.map ((*) amount))
            |> Seq.reduce (Array.map2 (+)) 
    let score = (max 0 p.[0]) * (max 0 p.[1]) * (max 0 p.[2]) * (max 0 p.[3])
    (score, p.[4])

let scores = 
    distribute [] 100 ingredients.Length
    |> Seq.map scoreCookie
    |> Seq.toArray
    
scores 
    |> Seq.map fst
    |> Seq.max
    |> printfn "a: %d" //18965440

scores 
    |> Seq.maxBy (fun (s,c) -> match c with | 500 -> s | _ -> 0)
    |> fst
    |> printfn "b: %d" // 15862900

// improvements:
let distribute4 m = 
    seq { for a in 0 .. m do 
          for b in 0 .. (m-a) do 
          for c in 0 .. (m-a-b) do 
          yield [|a;b;c;m-a-b-c|] }

As always, let me know in the comments how you would have tackled this problem.