Каково ваше решение головоломки "Побег из Zurg" в С#?
нашел эту головоломку ЗДЕСЬ... Я сделал решение грубой силы, и я хотел бы знать, как вы его решаете...
Buzz, Woody, Rex и Hamm должны бежать из Zurg (a) Они просто должны пересечь
один последний мост, прежде чем они свободны. Однако мост является хрупким и может удерживать максимум
два из них одновременно. Кроме того, чтобы пересечь мост, необходим фонарик для
избегать ловушек и сломанных деталей. Проблема в том, что у наших друзей есть только один фонарик
с одной батареей, которая длится всего 60 минут (это не опечатка: шестьдесят). Игрушки нужны
разное время пересечения моста (в любом направлении):
TOY TIME
Buzz 5 minutes
Woody 10 minutes
Rex 20 minutes
Hamm 25 minutes
Так как на мосту одновременно может быть только две игрушки, они не могут пересечь
мост все сразу. Поскольку им нужен фонарик, чтобы пересечь мост,
пересек мост, кто-то должен вернуться и принести фонарик к этим игрушкам на
другой стороне, которая все еще должна пересечь мост.
Теперь проблема заключается в следующем: в каком порядке четыре игрушки могут пересечь мост во времени (что
через 60 минут), чтобы спастись от Цурга?
//(a) These are characters from the animation movie "Toy Story 2".
вот мое решение:
public Form1()
{
InitializeComponent();
List<toy> toys = new List<toy>(){
new toy { name = "buzz", time = 5 } ,
new toy { name = "woody", time = 10 } ,
new toy { name = "rex", time = 20 } ,
new toy { name = "ham", time = 25 } ,
};
var posibles = Combinaciones(toys, 4).ToList(); //all permutations
List<Tuple<string, int>> solutions = new List<Tuple<string, int>>();
foreach (var pointA in posibles)
{
string order = "";
int flashlight = 60;
List<toy> pointB = new List<toy>();
do
{
var fastestInA = pointA.Take(2).ToList();
flashlight -= fastestInA.Max(t => t.time);
order += "go " + String.Join(",", fastestInA.Select(t => t.name)) + "\n";
fastestInA.ForEach(t => pointA.Remove(t));
pointB.AddRange(fastestInA);
if (pointB.Count < 4)
{
var fastestInB = pointB.Take(1).ToList();
flashlight -= fastestInB.Max(t => t.time);
order += "return " + String.Join(",", fastestInB.Select(t => t.name).ToArray()) + "\n";
fastestInB.ForEach(t => pointB.Remove(t));
pointA.AddRange(fastestInB);
}
} while (pointB.Count != 4);
solutions.Add(new Tuple<string, int>(order, flashlight));
}
var optimal = solutions.Where(s => s.Item2 == solutions.Max(t => t.Item2)).ToList();
optimal.ForEach(s => Console.Write("Order:\n" + s.Item1 + "TimeLeft:" + s.Item2 + "\n\n"));
}
public class toy
{
public int time { get; set; }
public string name { get; set; }
}
// this is to do permutations
public static List<List<toy>> Combinaciones(List<toy> list, int take)
{
List<List<toy>> combs = new List<List<toy>>();
foreach (var item in list)
{
var newlist = list.Where(i => !i.Equals(item)).ToList();
var returnlist = take <= 1 ? new List<List<toy>> { new List<toy>() } : Combinaciones(newlist, take - 1);
foreach (var l in returnlist)
{
l.Add(item);
}
combs.AddRange(returnlist);
}
return combs.ToList();
}
}
Ответы
Ответ 1
Рекурсивное решение с использованием LINQ:
using System;
using System.Collections.Generic;
using System.Linq;
namespace Zurg
{
class Program
{
static readonly Toy[] toys = new Toy[]{
new Toy("Buzz", 5),
new Toy("Woody", 10),
new Toy("Rex", 20),
new Toy("Ham", 25),
};
static readonly int totalTorch = 60;
static void Main()
{
Console.WriteLine(Go(new State(toys, new Toy[0], totalTorch, "")).Message);
}
static State Go(State original)
{
var final = (from first in original.Start
from second in original.Start
where first != second
let pair = new Toy[]
{
first,
second
}
let flashlight = original.Flashlight - pair.Max(t => t.Time)
select Return(new State(
original.Start.Except(pair),
original.Finish.Concat(pair),
flashlight,
original.Message + string.Format(
"Go {0}. {1} min remaining.\n",
string.Join(", ", pair.Select(t => t.Name)),
flashlight)))
).Aggregate((oldmax, cur) => cur.Flashlight > oldmax.Flashlight ? cur : oldmax);
return final;
}
static State Return(State original)
{
if (!original.Start.Any())
return original;
var final = (from toy in original.Finish
let flashlight = original.Flashlight - toy.Time
let toyColl = new Toy[] { toy }
select Go(new State(
original.Start.Concat(toyColl),
original.Finish.Except(toyColl),
flashlight,
original.Message + string.Format(
"Return {0}. {1} min remaining.\n",
toy.Name,
flashlight)))
).Aggregate((oldmax, cur) => cur.Flashlight > oldmax.Flashlight ? cur : oldmax);
return final;
}
}
public class Toy
{
public string Name { get; set; }
public int Time { get; set; }
public Toy(string name, int time)
{
Name = name;
Time = time;
}
}
public class State
{
public Toy[] Start { get; private set; }
public Toy[] Finish { get; private set; }
public int Flashlight { get; private set; }
public string Message { get; private set; }
public State(IEnumerable<Toy> start, IEnumerable<Toy> finish, int flashlight, string message)
{
Start = start.ToArray();
Finish = finish.ToArray();
Flashlight = flashlight;
Message = message;
}
}
}
Ответ 2
Единственные два решения:
* Buzz and Woody go right
* Buzz goes left
* Hamm and Rex go right
* Woody goes left
* Woody and Buzz go right
и
* Buzz and Woody go right
* Woody goes left
* Hamm and Rex go right
* Buzz goes left
* Woody and Buzz go right
Используйте их, чтобы проверить, что ваша проблема дает правильные результаты.
Ответ 3
Вы только что заставили меня узнать, насколько я ужасно не в форме с алгоритмами AI: (
Я всегда возвращался с самым быстрым парнем... немного обмана, но я слишком устал, чтобы заставить его работать на все комбинации. Здесь мое решение с использованием BFS.
class Program
{
private class Toy
{
public string Name { get; set; }
public int Time { get; set; }
}
private class Node : IEquatable<Node>
{
public Node()
{
Start = new List<Toy>();
End = new List<Toy>();
}
public Node Clone()
{
return new Node
{
Start = new List<Toy>(Start),
End = new List<Toy>(End),
Time = Time,
Previous = this
};
}
public int Time { get; set; }
public List<Toy> Start { get; set; }
public List<Toy> End { get; set; }
public Node Previous { get; set; }
public Toy Go1 { get; set; }
public Toy Go2 { get; set; }
public Toy Return { get; set; }
public bool Equals(Node other)
{
return Start.TrueForAll(t => other.Start.Contains(t)) &&
End.TrueForAll(t => other.End.Contains(t)) &&
Time == other.Time;
}
}
private static void GenerateNodes(Node node, Queue<Node> open, List<Node> closed)
{
foreach(var toy1 in node.Start)
{
foreach(var toy2 in node.Start.Where(t => t != toy1))
{
var newNode = node.Clone();
newNode.Start.Remove(toy1);
newNode.Start.Remove(toy2);
newNode.End.Add(toy1);
newNode.End.Add(toy2);
newNode.Go1 = toy1;
newNode.Go2 = toy2;
newNode.Time += Math.Max(toy1.Time, toy2.Time);
if(newNode.Time <= 60 && !closed.Contains(newNode) && !open.Contains(newNode))
{
open.Enqueue(newNode);
}
}
}
}
static void Main(string[] args)
{
var open = new Queue<Node>();
var closed = new List<Node>();
var initial = new Node
{
Start = new List<Toy>
{
new Toy {Name = "Buzz", Time = 5},
new Toy {Name = "Woody", Time = 10},
new Toy {Name = "Rex", Time = 20},
new Toy {Name = "Ham", Time = 25}
}
};
open.Enqueue(initial);
var resultNodes = new List<Node>();
while(open.Count != 0)
{
var current = open.Dequeue();
closed.Add(current);
if(current.End.Count == 4)
{
resultNodes.Add(current);
continue;
}
if(current.End.Count != 0)
{
var fastest = current.End.OrderBy(t => t.Time).First();
current.End.Remove(fastest);
current.Start.Add(fastest);
current.Time += fastest.Time;
current.Return = fastest;
}
GenerateNodes(current, open, closed);
}
foreach(var result in resultNodes)
{
var path = new List<Node>();
var node = result;
while(true)
{
if(node.Previous == null) break;
path.Insert(0, node);
node = node.Previous;
}
path.ForEach(n => Console.WriteLine("Went: {0} {1}, Came back: {2}, Time: {3}", n.Go1.Name, n.Go2.Name, n.Return != null ? n.Return.Name : "nobody", n.Time));
Console.WriteLine(Environment.NewLine);
}
Console.ReadLine();
}
}
Ответ 4
У меня нет реализации, но вот как работает решение:
Вы всегда отправляете самую быструю пару, которую вы получили с другой стороны, и возвращаете самую быструю с другой стороны, но вы никогда не отправляете ее один раз 2 раза (если все не были отправлены 2 раза, а затем вы отправляете только самые быстрые, которые прошли максимум 2 раза), отмечая его (призывая его время ад).
Это можно сделать с помощью 2 Priority Queue s (O(n log) n время решения).
Решение для вашего случая:
P-Q 1 P-Q 2
Buzz
Woody
Rex
Hamm
Buzz + Woody go = 10 min
P-Q 1 P-Q 2
Rex Buzz
Hamm Woody
Buzz goes back = 5 min
P-Q 1 P-Q 2
Hamm Woody
Rex
* Buzz
Hamm + Rex go = 25 min
P-Q 1 P-Q 2
* Buzz Woody
Hamm
Rex
Woody comes back = 10 min
P-Q 1 P-Q 2
* Buzz Hamm
* Woody Rex
Woddy + Buzz go = 10 min
---------------------------
Total: 60 mins
Например, для 6 вариантов вы будете делать:
1 - fastest
2 - after fastest
3 - you got it
4
5
6 - slowest
1 + 2 go
1 goes back
3 + 4 go
2 goes back
5 + 6 go
3 goes back
1 + 2 go
1 goes back
1 + 3 go
