using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
namespace U2_Problem
{
class Program
{
static void Main()
{
var tries = 0;
var startTime = DateTime.Now;
SolverResult answer = null;
while (answer == null)
{
var crossResult = Task.Factory.StartNew<SolverResult>(new Solver().Solve).Result;
if (crossResult.Time <= 17)
answer = crossResult;
tries++;
}
Console.WriteLine("SOLVED!");
Console.WriteLine("Time taken: {0}", DateTime.Now - startTime);
Console.WriteLine("Iterations: {0}", tries);
Console.WriteLine("Winning time: {0}", answer.Time);
Console.WriteLine("Winning combo:{0}", Environment.NewLine);
foreach (var move in answer.CrossOrder)
Console.WriteLine(move);
}
}
public class SolverResult
{
public List<KeyValuePair<string, int>> CrossOrder { get; set; }
public int Time { get; set; }
}
class Solver
{
private readonly Dictionary<string, int> _peopleWaitingToCross;
private readonly Dictionary<string, int> _peopleCrossed;
readonly Random _random = new Random();
public Solver()
{
_peopleWaitingToCross = new Dictionary<string, int> {{"Zbornak", 1}, {"Magnolia", 2}, {"Pho", 5}, {"Semi-Pro", 10}};
_peopleCrossed = new Dictionary<string, int>();
}
public SolverResult Solve()
{
var crossOrder = new List<KeyValuePair<string, int>>();
var totalTime = 0;
while (_peopleWaitingToCross.Any())
{
// Take quickest people the first time to leave a fast person on either side of the bridge
// then continue to take the slowest two people to minimise cross time loss
// e.g. taking 5+10 together = 10 total whereas taking 1+5 then 1+10 = 15
var p1 = totalTime == 0 ? TakeFastestPerson(_peopleWaitingToCross) : TakeSlowestPerson(_peopleWaitingToCross);
var p2 = totalTime == 0 ? TakeFastestPerson(_peopleWaitingToCross) : TakeSlowestPerson(_peopleWaitingToCross);
// Cross them
AddToCrossed(p1);
AddToCrossed(p2);
totalTime += GetSingleCrossTime(p1, p2);
crossOrder.Add(new KeyValuePair<string, int>(string.Format("{0} + {1} Crosses", p1.Key, p2.Key), totalTime));
// If no one left we're done
if (_peopleWaitingToCross.Count == 0)
break;
// Cross fastest person back if people are left
var personToCrossBack = TakeFastestPerson(_peopleCrossed);
AddToWaiting(personToCrossBack);
totalTime += personToCrossBack.Value;
crossOrder.Add(new KeyValuePair<string, int>(string.Format("{0} Returns", personToCrossBack.Key), totalTime));
}
return new SolverResult { CrossOrder = crossOrder, Time = totalTime };
}
private static int GetSingleCrossTime(KeyValuePair<string, int> pesron1, KeyValuePair<string, int> person2)
{
return pesron1.Value > person2.Value ? pesron1.Value : person2.Value;
}
private KeyValuePair<string, int> TakeRandomPerson(IDictionary<string, int> source)
{
var person = source.ElementAt(_random.Next(source.Count));
source.Remove(person.Key);
return person;
}
private KeyValuePair<string, int> TakeFastestPerson(IDictionary<string, int> source)
{
var person = source.OrderBy(o => o.Value).First();
source.Remove(person.Key);
return person;
}
private KeyValuePair<string, int> TakeSlowestPerson(IDictionary<string, int> source)
{
var person = source.OrderByDescending(o => o.Value).First();
source.Remove(person.Key);
return person;
}
private void AddToWaiting(KeyValuePair<string, int> person)
{
_peopleWaitingToCross.Add(person.Key, person.Value);
}
private void AddToCrossed(KeyValuePair<string, int> person)
{
_peopleCrossed.Add(person.Key, person.Value);
}
}
}
![[FnG]magnolia](/styles/overclockers/avatars/9.png){kind=avatar}
.
.
. I never tend to have the patience with these things