您对C#中"逃离Zurg"难题的解决方案是什么？

Question

在这里找到了这个谜题......我做了一个蛮力解决方案,我想知道你是如何解决它的...

巴兹,伍迪,雷克斯和哈姆必须逃离古尔格(a)他们只需要在自由之前越过最后一座桥.但是,这座桥很脆弱,最多可同时容纳两座桥.此外,为了穿过桥梁,需要手电筒以避免陷阱和破损的部件.问题是我们的朋友只有一个带一个电池的手电筒,持续时间只有60分钟(这不是一个错字:六十个).玩具需要不同的时间穿过桥梁(向任一方向):

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

由于桥上同时只有两个玩具,它们不能同时过桥.由于他们需要手电筒穿过桥梁,每当两个人越过桥梁时,有人必须返回并将手电筒带到另一侧仍然必须穿过桥梁的那些玩具上.现在的问题是:四个玩具能够以何种顺序及时(即60分钟)从Zurg中拯救出来？

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

Answer 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;
    }
  }
}