Adv2016/D11.1/Program.cs

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

namespace D11._1
{
    public enum EnumElement
    {
        Strontium = 0,
        Plutonium = 1,
        Thulium = 2,
        Ruthenium = 3,
        Curium = 4,
        Elerium = 5,
        Dilithium = 6
    }

    public enum EnumType
    {
        Generator = 0,
        Microship = 1
    }

    public class Facility : ICloneable
    {
        public Floor[] Floors { get; private set; }
        public int Elevator { get; set; }

        // All floors are empty except for the last one
        public bool IsOk()
        {
            for (var i = 0; i < Floors.Length - 1; ++i)
                if (Floors[i].IsEmpty() == false) return false;
            return true;
        }

        public Facility()
        {
            Floors = new Floor[4];
            for (var i = 0; i < 4; ++i)
                Floors[i] = new Floor();
        }

        public Floor CurrentFloor => Floors[Elevator];

        public class Floor : ICloneable
        {
            public bool[][] Objects = new bool[2][];

            public bool IsEmpty()
            {
                for (var i = 0; i < Objects[0].Length; ++i)
                    if (Objects[(int)EnumType.Generator][i] || Objects[(int)EnumType.Microship][i]) return false;
                return true;
            }

            public bool IsValid()
            {
                int generators = 0;
                int unpluggedMicroships = 0;

                for (var i = 0; i < Objects[0].Length; ++i)
                {
                    if (Objects[(int)EnumType.Generator][i]) generators++;
                    if (Objects[(int)EnumType.Generator][i] && Objects[(int)EnumType.Microship][i]) continue;
                    if (Objects[(int)EnumType.Microship][i]) unpluggedMicroships++;
                }

                return generators >= 0 && unpluggedMicroships == 0;
            }

            static readonly int nelement = Enum.GetValues(typeof(EnumElement)).Length;
            public Floor()
            {
                for (int i = 0; i < Objects.Length; ++i)
                    Objects[i] = new bool[nelement];
            }

            public object Clone()
            {
                var floor = new Floor();
                for (var i = 0; i < Objects.Length; i++)
                    for (var j = 0; j < Objects[i].Length; ++j)
                        floor.Objects[i][j] = Objects[i][j];
                return floor;
            }

            public bool Set(EnumType type, EnumElement element, bool value) => Objects[(int)type][(int)element] = value;
            public bool Add(EnumType type, EnumElement element) => Set(type, element, true);

            public override bool Equals(object obj) => obj is Floor floor && floor.GetHashCode() == GetHashCode();

            public override int GetHashCode()
            {
                //int h1 = 0, h2 = 0;

                //for (var i = 0; i < Objects[0].Length; ++i)
                //{
                //    h1 += (Objects[0][i] ? 1 : 0) << i;
                //    h2 += (Objects[1][i] ? 1 : 0) << i;
                //}

                //return h1 * 100 + h2;

                int paired = 0, unpairedGen = 0, unpairedMicroship = 0;

                for (var i = 0; i < Objects[0].Length; ++i)
                {
                    if (Objects[(int)EnumType.Microship][i] && Objects[(int)EnumType.Generator][i])
                    {
                        paired++;
                        continue;
                    }
                    if (Objects[(int)EnumType.Microship][i]) unpairedMicroship++;
                    if (Objects[(int)EnumType.Generator][i]) unpairedGen++;
                }

                return (((paired << 3) + unpairedGen) << 3) + unpairedMicroship;
            }
        }

        public override bool Equals(object obj) => obj is Facility facility && facility.GetHashCode() == GetHashCode() && facility.Elevator == Elevator;

        public override int GetHashCode()
        {
            int hash = 0;
            foreach (var floor in Floors) hash = HashCode.Combine(hash, floor.GetHashCode());
            return hash;
        }

        public object Clone()
        {
            var nf = new Facility
            {
                Elevator = this.Elevator,
                Floors = new Floor[Floors.Length]
            };

            for (var i = 0; i < Floors.Length; ++i) nf.Floors[i] = (Floor) Floors[i].Clone();
            return nf;
        }
    }

    class Program
    {
        static readonly EnumElement[] aelement = Enum.GetValues(typeof(EnumElement)) as EnumElement[];

        static void RunFacilityTest(Facility startFacility)
        {
            var upd = new [] { -1, +1 };
            var cmp = Comparer<(Facility, int)>.Create((a, b) => a.Item2.CompareTo(b.Item2));

            var queue = new Queue<(Facility facility, int step)>();
            var tested = new HashSet<Facility>();

            queue.Enqueue((startFacility, 0));

            while (queue.Count > 0)
            {
                (Facility facility, int step) = queue.Dequeue();

                if (facility.IsOk())
                {
                    Console.WriteLine($"The answer is : {step}");
                    break;
                }

                foreach (((EnumType t, EnumElement e) c1, (EnumType t, EnumElement e)? c2) in GetCandidates(facility))
                {
                    foreach (var direction in upd)
                    {
                        if (facility.Elevator + direction < 0 || facility.Elevator + direction >= facility.Floors.Length) continue;

                        Facility nfacility = BuildNewFacility(facility, c1, c2, direction);
                        if (nfacility.CurrentFloor.IsValid() == false) continue;

                        if (tested.Contains(nfacility)) continue;
                        tested.Add(nfacility);

                        queue.Enqueue((nfacility, step + 1));
                    }
                }
            }
        }

        private static Facility BuildNewFacility(Facility facility, (EnumType t, EnumElement e) c1, (EnumType t, EnumElement e)? c2, int d)
        {
            var nfacility = facility.Clone() as Facility;
            nfacility.CurrentFloor.Objects[(int)c1.t][(int)c1.e] = false;
            if (c2.HasValue) nfacility.CurrentFloor.Objects[(int)c2?.t][(int)c2?.e] = false;

            nfacility.Elevator += d;

            nfacility.CurrentFloor.Objects[(int)c1.t][(int)c1.e] = true;
            if (c2.HasValue) nfacility.CurrentFloor.Objects[(int)c2?.t][(int)c2?.e] = true;
            return nfacility;
        }

        private static HashSet<((EnumType, EnumElement), (EnumType, EnumElement)?)> GetCandidates(Facility facility)
        {
            var all = new List<(EnumType, EnumElement)>();

            foreach (EnumElement element in aelement)
            {
                if (facility.CurrentFloor.Objects[(int)EnumType.Generator][(int)element]) all.Add((EnumType.Generator, element));
                if (facility.CurrentFloor.Objects[(int)EnumType.Microship][(int)element]) all.Add((EnumType.Microship, element));
            }

            var comb = new HashSet<((EnumType, EnumElement), (EnumType, EnumElement)?)>();

            foreach ((EnumType t1, EnumElement e1) in all)
            {
                foreach ((EnumType t2, EnumElement e2) in all)
                {
                    if (t1 == t2 && e1 == e2)
                    {
                        comb.Add(((t1, e1), null));
                        continue;
                    }

                    if (comb.Contains(((t2, e2), (t1, e1)))) continue;

                    comb.Add(((t1, e1), (t2, e2)));
                }
            }

            return comb;
        }

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

            Console.WriteLine(  "=== PART 1 ========");
            Part1();
            Console.WriteLine("\n=== PART 2 ========");
            Part2();
        }

        private static void Part1()
        {
            var facility = new Facility();

            BaseFacility(facility);

            var sw = Stopwatch.StartNew();

            RunFacilityTest(facility);

            sw.Stop();

            Console.WriteLine($"\nExecution time : {sw.ElapsedMilliseconds}ms");
        }

        private static void BaseFacility(Facility facility)
        {
            facility.Floors[0].Add(EnumType.Generator, EnumElement.Strontium);
            facility.Floors[0].Add(EnumType.Microship, EnumElement.Strontium);
            facility.Floors[0].Add(EnumType.Generator, EnumElement.Plutonium);
            facility.Floors[0].Add(EnumType.Microship, EnumElement.Plutonium);

            facility.Floors[1].Add(EnumType.Generator, EnumElement.Thulium);
            facility.Floors[1].Add(EnumType.Generator, EnumElement.Ruthenium);
            facility.Floors[1].Add(EnumType.Microship, EnumElement.Ruthenium);
            facility.Floors[1].Add(EnumType.Generator, EnumElement.Curium);
            facility.Floors[1].Add(EnumType.Microship, EnumElement.Curium);

            facility.Floors[2].Add(EnumType.Microship, EnumElement.Thulium);
        }

        private static void Part2()
        {
            var facility = new Facility();

            BaseFacility(facility);

            facility.Floors[0].Add(EnumType.Generator, EnumElement.Elerium);
            facility.Floors[0].Add(EnumType.Microship, EnumElement.Elerium);
            facility.Floors[0].Add(EnumType.Generator, EnumElement.Dilithium);
            facility.Floors[0].Add(EnumType.Microship, EnumElement.Dilithium);

            var sw = Stopwatch.StartNew();

            RunFacilityTest(facility);

            sw.Stop();

            Console.WriteLine($"\nExecution time : {sw.ElapsedMilliseconds}ms");
        }
    }
}