Подтвердить что ты не робот

Каково ваше решение головоломки "Побег из 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();
}
}
4b9b3361

ОТВЕТЫ

Ответ 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