Advent of Code Day 13–Optimal Seating Plan

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