Adv2015/D13.1/Program.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

namespace D13._1
{
    public class Table
    {
        Person First = null;
        Person Last = null;

        public void Sit(Person p)
        {
            p.Left = null;
            p.Right = null;

            if (Last == null)
            {
                p.Right = p;
                p.Left = p;

                Last = p;
                First = p;
                return;
            }

            p.Left = Last;
            p.Right = First;

            p.Left.Right= p;
            Last.Right = p;

            p.Right.Left= p;
            First.Left = p;

            Last = p;
        }

        public bool Contains(Person p)
        {
            bool found = false;
            var cur = First;
            while (cur != null && found == false)
            {
                if (cur == p) found = true;
                cur = cur.Right;
                if (cur == First) break;
            }
            return found;
        }

        public int Count(Dictionary<(string, string), int> preferences)
        {
            int count = 0;
            var cur = First;
            while (cur != null)
            {
                count += preferences[(cur.Name, cur.Left.Name)] + preferences[(cur.Name, cur.Right.Name)];

                cur = cur.Right;
                if (cur == First) break;
            }
            return count;
        }
    }

    public class Person
    {
        public string Name { get; }
        public Person(string name) => Name = name;
        public Person Left;
        public Person Right;

        public override bool Equals(object obj)
        {
            var person = obj as Person;
            return person != null &&
                   Name == person.Name;
        }

        public override int GetHashCode()
        {
            return HashCode.Combine(Name);
        }
    }


    public class Program
    {
        static void Main(string[] args)
        {
            if (args.Length < 1) throw new ArgumentException();
            if (File.Exists(args[0]) == false) throw new FileNotFoundException();

            var persons = new HashSet<Person>();
            var preferences = new Dictionary<(string, string), int>();

            ParseFile(args[0], persons, preferences);

            int best = SearchBestTablePlan(persons, preferences);

            Console.WriteLine($"The answer is : {best}");
        }

        public static int SearchBestTablePlan(HashSet<Person> persons, Dictionary<(string, string), int> preferences)
        {
            var permList = GetPermutations(persons, persons.Count);

            var best = 0;
            foreach (var perm in permList)
            {
                var table = new Table();
                foreach (var p in perm)
                    table.Sit(p);

                var count = table.Count(preferences);
                if (count > best) best = count;
            }

            return best;
        }

        static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });
            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(o => !t.Contains(o)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

        public static void ParseFile(string f, HashSet<Person> persons, Dictionary<(string, string), int> preferences)
        {
            var regex = new Regex(@"(?<l>\w+) would (?<v>\w+) (?<h>\d+) happiness units by sitting next to (?<r>\w+).");
            using (var file = File.OpenText(f))
            {
                while (true)
                {
                    var line = file.ReadLine();
                    if (line == null) break;

                    var result = regex.Match(line);

                    int multiplier = 0;
                    if (result.Groups["v"].Value == "lose") multiplier = -1;
                    if (result.Groups["v"].Value == "gain") multiplier = 1;

                    var happiness = int.Parse(result.Groups["h"].Value);

                    var left = result.Groups["l"].Value;
                    var right = result.Groups["r"].Value;

                    persons.Add(new Person(left));
                    persons.Add(new Person(right));

                    preferences.Add((left, right), happiness * multiplier);
                }
            }
        }
    }
}