Was ist Ihre Lösung für das Puzzle "Escape from Zurg" in C#?

Question

dieses Rätsel gefunden HERE ... Ich habe eine Brute-Force-Lösung gemacht und ich würde gerne wissen, wie Sie es lösen woul ...

Buzz, Woody, Rex und Hamm aus Zurg entkommen müssen (a) Sie Überqueren Sie einfach eine letzte Brücke, bevor sie frei sind. Die Brücke ist jedoch zerbrechlich und kann höchstens zwei von ihnen zur gleichen Zeit halten. Darüber hinaus, um die Brücke zu überqueren, wird eine Taschenlampe benötigt, um Fallen und gebrochene Teile zu vermeiden. Das Problem ist, dass unsere Freunde nur eine Taschenlampe haben mit einer Batterie, die nur 60 Minuten dauert (das ist kein Tippfehler: sechzig). Das Spielzeug braucht verschiedene Zeiten die Brücke zu überqueren (in beiden Richtungen):

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

Da es nur zwei Spielzeug auf der Brücke zur gleichen Zeit sein kann, können sie die Brücke auf einmal nicht überqueren. Da sie die Taschenlampe brauchen, um die Brücke zu überqueren, müssen zwei, wenn zwei die Brücke überquert haben, zurückgehen und die Taschenlampe zu den Spielzeugen auf der anderen Seite bringen, die noch die Brücke überqueren müssen. Das Problem ist jetzt: In welcher Reihenfolge können die vier Spielzeuge die Brücke rechtzeitig überqueren (dass ist, in 60 Minuten) von Zurg gerettet werden?

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

hier ist meine Lösung:

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

rekursive Lösung mithilfe von 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

Du mich gerade gemacht herauszufinden, wie schrecklich aus der Form I mit AI Algorithmen sind :(

Ich kam immer mit dem schnellsten Kerl zurück ... ein bisschen wie ein Betrüger, aber ich bin jetzt zu müde, um es für alle Kombinationen funktionieren zu lassen ns. Hier ist meine Lösung mit 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

Ich habe Implementierung nicht, aber hier, wie die Lösung funktioniert:
Sie immer das schnellste Paar schicken Sie auf die anderen Seite bekommen und wieder die schnellsten auf der anderen Seite, aber Sie nie die gleichen schicken 2 Mal (es sei denn, jeder wurde 2 Mal gesendet und dann schickst du nur den schnellsten, der maximal 2 Mal ging), indem du ihn markierst (seine Zeit verdreifacht durch die Hölle).
Dies kann mit 2 Priority Queue s (O(n log) n Lösungszeit) erfolgen.

Die Lösung für Ihren Fall:

 
    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 

Zum Beispiel für 6 Variation Sie tun:

 
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

Die einzigen beiden Lösungen sind:

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

und

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

Verwenden Sie diese, um zu überprüfen, ob Ihr Problem die richtigen Ergebnisse liefert.