// do something here

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace BridgeAtNight
{
    public class BridgeState
    {
        public List<int> peopleOnLeft;
        public List<int> peopleOnRight;
        public int totalTime;
        public string peopleMovement;
 
        public BridgeState(int[] people)
        {
            totalTime = 0;
            peopleMovement = "";
            peopleOnLeft = new List<int>(people);
            peopleOnRight = new List<int>();
        }
 
        public void MoveLeftToRight(int leftToRight1, int leftToRight2)
        {
            peopleMovement = peopleMovement + string.Format("{0}>> {1}>> ", leftToRight1, leftToRight2);
            totalTime += Math.Max(leftToRight1, leftToRight2);
 
            peopleOnRight.Add(leftToRight1);
            peopleOnRight.Add(leftToRight2);
            peopleOnRight.Sort();
 
            peopleOnLeft.Remove(leftToRight1);
            peopleOnLeft.Remove(leftToRight2);
        }
 
        public void MoveRightToLeft(int rightToLeft)
        {
            peopleMovement = peopleMovement + string.Format("{0}<< ", rightToLeft);
            totalTime += rightToLeft;
 
            peopleOnLeft.Add(rightToLeft);
            peopleOnLeft.Sort();
 
            peopleOnRight.Remove(rightToLeft);
        }
 
        public void SolveWithNaivete()
        {
            peopleOnLeft.Sort();
            while (peopleOnLeft.Count > 1)
            {
                // move 2 people from the left to the right
                int leftToRight1 = peopleOnLeft[0];
                int leftToRight2 = peopleOnLeft[1];
                MoveLeftToRight(leftToRight1, leftToRight2);
 
                // move 1 person from right to left if there are any remaining people on the left
                if (peopleOnLeft.Count > 0)
                {
                    int rightToLeft = peopleOnRight[0];
                    MoveRightToLeft(rightToLeft);
                }
            }
 
            Console.WriteLine("Solution with naivete:");
            Console.WriteLine(string.Format("Time: {0} minutes", totalTime));
            Console.WriteLine(string.Format("Sequence: {0}", peopleMovement));
        }
 
        public void SolveRandomly()
        {
            Random rnd = new Random();
            while (peopleOnLeft.Count > 1)
            {
                // move 2 people from the left to the right
                var leftToRightRandom = peopleOnLeft.OrderBy(x => rnd.Next()).Take(2).ToList();
                int leftToRight1 = leftToRightRandom[0];
                int leftToRight2 = leftToRightRandom[1];
                MoveLeftToRight(leftToRight1, leftToRight2);
 
                // move 1 person from right to left if there are any remaining people on the left
                if (peopleOnLeft.Count > 0)
                {
                    var rightToLeftRandom = peopleOnRight.OrderBy(x => rnd.Next()).Take(1).ToList();
                    int rightToLeft = rightToLeftRandom[0];
                    MoveRightToLeft(rightToLeft);
                }
            }
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            BridgeState naiveBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
            naiveBridgeState.SolveWithNaivete();
 
            List<string> bestTimeResults = new List<string>();
            int bestTime = 999999;
            for (int idx = 1; idx < 1000000; idx++)
            {
                BridgeState randomBridgeState = new BridgeState(new int[] { 1, 2, 5, 10 });
                randomBridgeState.SolveRandomly();
                if (randomBridgeState.totalTime < bestTime)
                {
                    Console.WriteLine(string.Format("Better random solution found in pass {0}:", idx));
                    Console.WriteLine(string.Format("Time: {0} minutes", randomBridgeState.totalTime));
                    Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
                    bestTime = randomBridgeState.totalTime;
                    bestTimeResults = new List<string>();
                    bestTimeResults.Add(randomBridgeState.peopleMovement);
                }
                else if (randomBridgeState.totalTime == bestTime)
                {
                    if (!bestTimeResults.Contains(randomBridgeState.peopleMovement))
                    {
                        Console.WriteLine(string.Format("Sequence: {0}", randomBridgeState.peopleMovement));
                        bestTimeResults.Add(randomBridgeState.peopleMovement);
                    }
                }
            }
 
            Console.WriteLine("Press any key to exit the application");
            Console.ReadKey();
        }
    }
}