What is your solution to the "Escape from Zurg" puzzle in C#?

Question

found this puzzle HERE... I made a brute force solution and I would like to know how you woul solve it...

Buzz, Woody, Rex, and Hamm have to escape from Zurg(a) They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):

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

Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge. The problem now is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?

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

here is my solution:

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

Recursive solution using 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

You just made me find out how terribly out of shape I am with AI algorithms :(

I always returned with the fastest guy... bit of a cheat but I'm too tired now to make it work for all combinations. Here's my solution using 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

I don't have implementation but here how the solution works:
You always send the fastest pair you got to the other side and return the fastest on the other side, but you never send the same one 2 times(unless everyone was sent 2 times and then you only send fastest that went max 2 times) by marking him(incresing his time by hell).
This can be done with 2 Priority Queues(O(n log) n solution time).

The solution for your case:

    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

For example for 6 variation you will do:

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