Adv2015/D17.1/Program.cs

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

namespace D17._1
{
    public class ContainerList
    {
        public int Id { get; }
        public int Volume;
        public ContainerList Next;
        public ContainerList(int id) => Id = id;

        public bool Contains(int id)
        {
            var cur = this;
            bool found = false;
            while (cur != null && found == false)
            {
                if (cur.Id == id)
                    found = true;
                cur = cur.Next;
            }
            return found;
        }

        public int Count() => 1 + (Next?.Count() ?? 0);

        public override int GetHashCode() => (Id > 0 ? 1 << Id : 0) + (Next?.GetHashCode() ?? 0);

        public override bool Equals(object obj) => obj is ContainerList list && list.GetHashCode() == GetHashCode();
    }

    class Program
    {
        static void TestCombinations(List<int> containers, HashSet<(ContainerList, int)> found, ContainerList containerComb = null, int totalVolume = 0, int it = 0)
        {
            if (found.Contains((containerComb, totalVolume))) return;
            found.Add((containerComb, totalVolume));
            if (totalVolume >= 150) return;
            
            for (int i = it; i < containers.Count; i++)
            {
                if (containerComb != null && containerComb.Contains(i)) continue;

                int volume = containers[i];
                TestCombinations(containers, found, new ContainerList(i) { Next = containerComb, Volume = volume }, totalVolume + volume, it + 1);
            }
        }

        static void Main(string[] args)
        {
            List<int> containers = new List<int>();
            HashSet<(ContainerList, int volume)> found = new HashSet<(ContainerList, int)>();

            ParseFile(args[0], containers);

            TestCombinations(containers, found);

            var validCombinations = found.Where(f => f.volume == 150);

            Console.WriteLine($"The part 1 answer is : {validCombinations.Count()}");

            int[] combn = new int[containers.Count];
            int mincount = CountAllComb(validCombinations, combn);

            Console.WriteLine($"The part 2 answer is : {combn[mincount]}");
        }

        private static int CountAllComb(IEnumerable<(ContainerList, int volume)> validCombinations, int[] combn)
        {
            int mincount = combn.Length;
            foreach (var comb in validCombinations)
            {
                var count = comb.Item1.Count();
                combn[count]++;
                if (count < mincount) mincount = count;
            }

            return mincount;
        }

        private static void ParseFile(string arg, List<int> containers)
        {
            using (var file = File.OpenText(arg))
            {
                while (true)
                {
                    var line = file.ReadLine();
                    if (line == null) break;

                    containers.Add(int.Parse(line));
                }
            }
        }
    }
}