0 Comments Posted in:

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.

Want to learn more about LINQ? Be sure to check out my Pluralsight course More Effective LINQ.