Adv2016/D11.1/Program.cs

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

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 NElements = Enum.GetValues(typeof(EnumElement)).Length;
            public Floor()
            {
                for (int i = 0; i < Objects.Length; ++i)
                    Objects[i] = new bool[NElements];
            }

            public object Clone()
            {
                var floor = new Floor();

                for (var i = 0; i < Objects.Length; i++)
                    Objects[i].CopyTo(floor.Objects[i], 0);

                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 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;

                /*
                 * Firts hash method takes into account wich microship and generator element is
                 * present on the floor.
                 * 
                 * The following methods just relies on the fact that it does not matter
                 * which generators or microships are on the floor but that there are
                 * paired microship/generators (it does not matter wich ones) and unpaired
                 * microships and generators (still, it does not matter which ones)
                 *
                 * * ==> ENORMOUS performance gain : ~8s => 150ms
                 */

                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 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[] AllElements = Enum.GetValues(typeof(EnumElement)) as EnumElement[];
        static readonly int[] ElevatorDirections = new[] { -1, +1 };

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

            queue.Enqueue((startFacility, 0));

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

                if (facility.IsOk())  return step;

                foreach (((EnumType, EnumElement) first, (EnumType, EnumElement)? second) in GetCandidates(facility))
                {
                    foreach (var direction in ElevatorDirections)
                    {
                        if (facility.Elevator + direction < 0 || facility.Elevator + direction >= facility.Floors.Length) continue;

                        Facility nfacility = BuildNewFacility(facility, first, second, direction);
                        if (nfacility == null) continue;

                        int hash = nfacility.GetHashCode() ^ nfacility.Elevator;

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

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

            throw new Exception();
        }

        private static Facility BuildNewFacility(Facility facility, (EnumType t, EnumElement e) first, (EnumType t, EnumElement e)? second, int direction)
        {
            /* Slight optimisation 
             * Before cloning the entire facility, ensures that the next state for the current floor
             * is valid as cloning a single floor is less consuming.
             */
            var clone = facility.Floors[facility.Elevator + direction].Clone() as Facility.Floor;

            clone.Set(first.t, first.e, true);
            if (second.HasValue) clone.Set(second.Value.t, second.Value.e, true);

            if (clone.IsValid() == false) return null;

            // -----------

            var nfacility = facility.Clone() as Facility;

            nfacility.CurrentFloor.Set(first.t, first.e, false);
            if (second.HasValue) nfacility.CurrentFloor.Set(second.Value.t, second.Value.e, false);

            nfacility.Elevator += direction;

            nfacility.Floors[nfacility.Elevator] = clone;

            return nfacility;
        }

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

            foreach (EnumElement element in AllElements)
            {
                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();

            var answer = RunFacilityTest(facility);
            Console.WriteLine($"The answer is : {answer}");

            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();

            var answer = RunFacilityTest(facility);
            Console.WriteLine($"The answer is : {answer}");

            sw.Stop();

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