# Advent of Code Day 13–Optimal Seating Plan

December 15. 2015 0 Comments

- Posted in:
- C#
- F#
- Advent of Code
- LINQ

So the day 13 Advent of Code challenge had a bit of a familiar feel to it – really it was day 9’s Travelling Santa Problem with a different spin on it. But it was still a fun challenge, and another chance in C# to use a whole host of MoreLinq methods.

Here’s my C# solution, using no less than five MoreLinq methods (`Permutations`

, `MaxBy`

, `Prepend`

, `Concat`

and `Pairwise`

)

var realInput = File.ReadAllLines("day13.txt"); var rules = realInput .Select(s => Regex.Match(s, @"(\w+) would (lose|gain) (\d+) happiness units by sitting next to (\w+)\.").Groups.Cast<Group>().Skip(1).Select(g => g.Value).ToArray()) .Select(p => new { A = p[0], B = p[3], Gain = int.Parse(p[2]) * (p[1] == "lose" ? -1 : 1) }); var people = rules.Select(r => r.A).Distinct().ToList(); var lookup = rules.ToDictionary(r => $"{r.A}-{r.B}", r => r.Gain); // part B add me people.ForEach(p => { lookup[$"Mark-{p}"] = 0; lookup[$"{p}-Mark"] = 0; }); people.Add("Mark"); people.Skip(1).Permutations() .Select(p => p.Prepend((people[0])).Concat(people[0]).Pairwise((a, b) => new { a, b })) .Select(p => new { Plan = p, Happiness = p.Sum(x => lookup[$"{x.a}-{x.b}"] + lookup[$"{x.b}-{x.a}"]) }) .MaxBy(p => p.Happiness) .Dump(); // a = 664, b = 640

And in F# I had to make do without the power of MoreLinq, but I reused the permutations function I found from day 9, and the F# library already had everything else I needed.

let parseRule rule = let p = Regex.Match(rule, @"(\w+) would (lose|gain) (\d+) happiness units by sitting next to (\w+)\.") .Groups |> Seq.cast<Group> |> Seq.skip 1 |> Seq.map (fun g -> g.Value) |> Seq.toArray (p.[0],p.[3]), (int p.[2]) * (match p.[1] with | "lose" -> -1 | _ -> 1) let rules = "day13.txt" |> File.ReadAllLines |> Seq.map parseRule |> Seq.toList // Jon Harrop F# for Scientists ( http://stackoverflow.com/a/3129136/7532 let rec distribute e = function | [] -> [[e]] | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs] let rec permute = function | [] -> [[]] | e::xs -> List.collect (distribute e) (permute xs) let findHappiestSeatingPlan rules = let people = rules |> Seq.map (fun ((a,b),g) -> a) |> Seq.distinct |> Seq.toList let lookup = rules |> dict let getPairHappiness (a,b) = if lookup.ContainsKey (a,b) then lookup.[(a,b)] + lookup.[(b,a)] else 0 let first = people.Head people.Tail |> permute |> List.map (fun p -> (first::p, seq { yield first; yield! p; yield first } |> Seq.pairwise |> Seq.sumBy getPairHappiness)) |> Seq.maxBy snd findHappiestSeatingPlan rules |> Dump // 664 findHappiestSeatingPlan ((("Mark",""),0)::rules) |> Dump // 640

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