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.