¿Cuál es su solución para el rompecabezas "Escape from Zurg" en C#?

Question

encontró este rompecabezas HERE ... Me hizo una solución de fuerza bruta y me gustaría saber cómo se woul resolverlo ...

Buzz, Woody, Rex y Hamm tienen que escapar de Zurg (a) Ellos simplemente tiene que cruzar un último puente antes de que estén libres. Sin embargo, el puente es frágil y puede contener como máximo dos de ellos al mismo tiempo. Además, para cruzar el puente, se necesita una linterna para , evitar trampas y piezas rotas. El problema es que nuestros amigos solo tienen una linterna con una batería que dura solo 60 minutos (esto no es un error tipográfico: sesenta). Los juguetes deben tiempos diferentes para cruzar el puente (en cualquier dirección):

TOY  TIME 
Buzz 5 minutes 
Woody 10 minutes 
Rex 20 minutes 
Hamm 25 minutes 

Como no puede haber sólo dos juguetes en el puente, al mismo tiempo, no pueden cruzar el puente todos a la vez. Como necesitan la linterna para cruzar el puente, cada vez que dos tienen cruzaron el puente, alguien tiene que regresar y llevar la linterna a los juguetes en del otro lado que todavía tienen que cruzar el puente. El problema ahora es: ¿En qué orden pueden los cuatro juguetes cruzar el puente a tiempo (que es, en 60 minutos) para ser guardado de Zurg?

//(a) These are characters from the animation movie “Toy Story 2”. 

aquí está mi solución:

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

Answer 1

solución recursiva utilizando 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; 
    } 
    } 
} 

Answer 2

que acaba de hacer a averiguar qué terriblemente fuera de forma que estoy con algoritmos de IA :(

Siempre volví con el tipo más rápido ... un poco de trampa, pero estoy demasiado cansado ahora para que funcione para todas las combinaciones ns. Aquí está mi solución usando 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(); 
    } 
} 

Answer 3

no tengo aplicación pero aquí cómo funciona la solución:
que siempre envía el par más rápido que tienes al otro lado y regresar el más rápido en el otro lado, pero nunca se envíe el mismo 2 veces (a menos que todos hayan sido enviados 2 veces y luego solo envíes el más rápido que haya corrido un máximo de 2 veces) marcándolo (aumentando su tiempo al infierno).
Esto se puede hacer con 2 Priority Queue s (O(n log) n tiempo de solución).

La solución para su caso:

 
    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 

Por ejemplo para el 6 de variación que va a hacer:

 
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 

Answer 4

Las dos únicas soluciones son:

* Buzz and Woody go right 
* Buzz goes left 
* Hamm and Rex go right 
* Woody goes left 
* Woody and Buzz go right 

y

* Buzz and Woody go right 
* Woody goes left 
* Hamm and Rex go right 
* Buzz goes left 
* Woody and Buzz go right 

Úselos para comprobar que su problema está dando los resultados correctos.