using System;

using System.Text;

using System.Text.RegularExpressions;

​

namespace AoC2018_AV

{

    public class Day07

    {

        public static void Main(string[] args)

        {

            #region testdata

            string test = @"Step C must be finished before step A can begin.

Step C must be finished before step F can begin.

Step A must be finished before step B can begin.

Step A must be finished before step D can begin.

Step B must be finished before step E can begin.

Step D must be finished before step E can begin.

Step F must be finished before step E can begin.";

            #endregion

​

            #region inputdata

            string input = @"Step G must be finished before step M can begin.

Step T must be finished before step E can begin.

Step P must be finished before step M can begin.

Step V must be finished before step L can begin.

Step Y must be finished before step B can begin.

Step K must be finished before step Z can begin.

Step H must be finished before step I can begin.

Step D must be finished before step U can begin.

Step C must be finished before step L can begin.

Step R must be finished before step Z can begin.

Step U must be finished before step B can begin.

Step J must be finished before step M can begin.

Step M must be finished before step E can begin.

Step I must be finished before step X can begin.

Step N must be finished before step O can begin.

Step S must be finished before step F can begin.

Step X must be finished before step A can begin.

Step F must be finished before step Q can begin.

Step B must be finished before step Z can begin.

Step Q must be finished before step W can begin.

Step L must be finished before step W can begin.

Step O must be finished before step Z can begin.

Step A must be finished before step Z can begin.

Step E must be finished before step W can begin.

Step W must be finished before step Z can begin.

Step G must be finished before step R can begin.

Step H must be finished before step A can begin.

Step A must be finished before step W can begin.

Step Y must be finished before step D can begin.

Step O must be finished before step A can begin.

Step V must be finished before step U can begin.

Step H must be finished before step W can begin.

Step K must be finished before step F can begin.

Step J must be finished before step X can begin.

Step V must be finished before step R can begin.

Step Q must be finished before step A can begin.

Step F must be finished before step B can begin.

Step G must be finished before step P can begin.

Step L must be finished before step A can begin.

Step B must be finished before step Q can begin.

Step H must be finished before step J can begin.

Step J must be finished before step L can begin.

Step F must be finished before step E can begin.

Step U must be finished before step A can begin.

Step G must be finished before step Q can begin.

Step G must be finished before step S can begin.

Step K must be finished before step J can begin.

Step N must be finished before step B can begin.

Step F must be finished before step O can begin.

Step C must be finished before step Z can begin.

Step B must be finished before step E can begin.

Step M must be finished before step S can begin.

Step A must be finished before step E can begin.

Step E must be finished before step Z can begin.

Step K must be finished before step I can begin.

Step P must be finished before step A can begin.

Step Y must be finished before step L can begin.

Step Y must be finished before step J can begin.

Step G must be finished before step N can begin.

Step Q must be finished before step L can begin.

Step D must be finished before step X can begin.

Step C must be finished before step I can begin.

Step K must be finished before step B can begin.

Step N must be finished before step F can begin.

Step D must be finished before step M can begin.

Step B must be finished before step A can begin.

Step U must be finished before step J can begin.

Step Q must be finished before step Z can begin.

Step X must be finished before step F can begin.

Step K must be finished before step X can begin.

Step U must be finished before step E can begin.

Step X must be finished before step W can begin.

Step K must be finished before step Q can begin.

Step I must be finished before step E can begin.

Step D must be finished before step J can begin.

Step P must be finished before step I can begin.

Step K must be finished before step D can begin.

Step S must be finished before step X can begin.

Step C must be finished before step R can begin.

Step P must be finished before step W can begin.

Step I must be finished before step O can begin.

Step S must be finished before step O can begin.

Step K must be finished before step C can begin.

Step N must be finished before step Q can begin.

Step L must be finished before step E can begin.

Step L must be finished before step Z can begin.

Step K must be finished before step W can begin.

Step Y must be finished before step A can begin.

Step L must be finished before step O can begin.

Step N must be finished before step W can begin.

Step R must be finished before step W can begin.

Step C must be finished before step O can begin.

Step H must be finished before step X can begin.

Step V must be finished before step Y can begin.

Step S must be finished before step W can begin.

Step V must be finished before step E can begin.

Step Q must be finished before step E can begin.

Step P must be finished before step H can begin.

Step V must be finished before step H can begin.

Step N must be finished before step Z can begin.

Step C must be finished before step A can begin.";

            #endregion

​

            Console.WriteLine(SolveA(test));

            Console.WriteLine(SolveA(input));

            Console.WriteLine();

            Console.WriteLine(SolveB(test, 2, 0));

            Console.WriteLine(SolveB(input, 5, 60));

        }

​

        public static bool FindNext(int[] ba, int doneList, out int index)

        {

            for (index = 0; index < 26; index++)

            {

                if (ba[index] == 0 && !((doneList & (1 << index)) >= 1))

                    return true;

            }

            return false;

        }

​

        public static void MarkAndClear(int[] ba, ref int doneList, int index)

        {

            for (int i = 0; i < 26; i++)

                ba[i] &= ~(1 << index);

            doneList |= (1 << index);

        }

​

        public static string SolveA(string input)

        {

            string[] lines = input.Split(new char[] { '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

            var graph = new int[26];

            var done = 0x7FFFFFFF;

​

            foreach (var line in lines)

            {

                var m = Regex.Match(line, "Step (.) must be finished before step (.) can begin.");

                var a = char.Parse(m.Groups[1].Value) - 'A';

                var b = char.Parse(m.Groups[2].Value) - 'A';

                graph[b] |= 1 << a;

                done &= ~(1 << a);

                done &= ~(1 << b);

            }

​

            var output = new StringBuilder();

            while (FindNext(graph, done, out int index))

            {

                output.Append(Convert.ToChar('A' + index));

                MarkAndClear(graph, ref done, index);

            };

​

            return output.ToString();

        }

​

        public struct Worker

        {

            public int item;

            public int work;

        }

​

        public static int SolveB(string input, int numWorkers, int overhead)

        {

            string[] lines = input.Split(new char[] { '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);

            var graph = new int[26];

            var done = 0x7FFFFFFF;

​

            foreach (var line in lines)

            {

                var m = Regex.Match(line, "Step (.) must be finished before step (.) can begin.");

                var a = char.Parse(m.Groups[1].Value) - 'A';

                var b = char.Parse(m.Groups[2].Value) - 'A';

                graph[b] |= 1 << a;

                done &= ~(1 << a);

                done &= ~(1 << b);

            }

​

            var workers = new Worker[numWorkers];

            var clock = 0;

            var workHappening = false;

            do

            {

                workHappening = false;

                for (int i = 0; i < workers.Length; i++)

                {

                    if (workers[i].work > 0)

                    {

                        workers[i].work--;

                        if (workers[i].work == 0)

                            MarkAndClear(graph, ref done, workers[i].item);

                        else

                            workHappening = true;

                    }

                }

                for (int i = 0; i < workers.Length; i++)

                {

                    if (workers[i].work == 0)

                    {

                        var anyLuck = FindNext(graph, done, out int index);

                        if (anyLuck)

                        {

                            workers[i].item = index;

                            workers[i].work = index + 1 + overhead;

                            done |= (1 << index);

                            workHappening = true;

                        }

                    }

                }

​

                //Console.Write(clock);

                //Console.Write('\t');

                //foreach (var w in workers)

                //{

                //    Console.Write(w.work == 0 ? '-' : Convert.ToChar('A' + w.item));

                //    Console.Write('\t');

                //}

                //Console.WriteLine();

​

                clock++;

            } while (workHappening);

​

            return clock - 1;

        }

    }

}

​