פתרון תכנותי לבעיית חציית הגשר עם הפנס

[עמיר]

לאחר קריאת החידה מהדיון הזה:

http://hwzone.co.il/community/index.php?topic=248936

החלטתי לנסות לפתור את הבעיה באופן ממוחשב ויחסית כללי. לאחר כמה דקות של קידוד הגעתי לפתרון הזה:

d:\> answer.exe

Found 2 answers.

---

Configuration: 0 {5, 10, 20, 25, } {} 60 True

Configuration: 5 {20, 25, } {5, 10, } 50 False 0

Configuration: 15 {5, 20, 25, } {10, } 45 True 5

Configuration: 67 {5, } {10, 20, 25, } 20 False 15

Configuration: 201 {5, 10, } {20, 25, } 10 True 67

Configuration: 460 {} {5, 10, 20, 25, } 0 False 201

---

Configuration: 0 {5, 10, 20, 25, } {} 60 True

Configuration: 5 {20, 25, } {5, 10, } 50 False 0

Configuration: 16 {10, 20, 25, } {5, } 40 True 5

Configuration: 73 {10, } {5, 20, 25, } 15 False 16

Configuration: 220 {5, 10, } {20, 25, } 10 True 73

Configuration: 491 {} {5, 10, 20, 25, } 0 False 220

חשבתי שאם כבר כתבתי, נפרסם פה את הקוד (הוא לא הקוד הכי טוב שיש, הוא קודד יחסית מהר, סתם כדי לראות את התשובות), אפשר למשל לשפר אותו בקלות שיעבוד באופן מקבילי על כמה ליבות וכו'. כתבתי את הקוד ב C#:

using System;
using System.Collections.Generic;
using System.Text;

namespace Test
{
  //enteries must be sorted?
  class Configuration
  {
    int[] side_a;
    int[] side_b;
    int time;
    public Configuration father;
    int number;
    public bool side;
    public int[] pass;

    public static List<Configuration> options = new List<Configuration>();
    public static List<Configuration> possibilities = new List<Configuration>();
    static int num = 0;

    public Configuration(int[] side_a, int[] side_b, int time)
    {
      this.side_a = side_a;
      this.side_b = side_b;
      this.time = time;
      number = num++;
      father = null;
      side = true;
    }

    private Configuration(Configuration father, int[] side_a, int[] side_b, int time)
    {
      this.side_a = side_a;
      this.side_b = side_b;
      this.time = time;
      number = num++;
      this.father = father;
      side = father.side ? false : true;
    }

    public override string ToString()
    {
      string ret;
      ret = "Configuration: " + number + " {";
      foreach (int x in side_a)
        ret += x + ", ";
      ret += "} {";
      foreach (int x in side_b)
        ret += x + ", ";
      ret += "} " + time + " " + side;
      if (father != null)
        ret += " " + father.number;
      return ret;
    }

    public void step()
    {
      possibilities.Remove(this);

      if (side_a.Length == 0)
      {
        options.Add(this);
        return;
      }

      if (time <= 0)
        return;

      int[] from = side ? this.side_a : this.side_b;
      int[] to = side ? this.side_b : this.side_a;

      for (int i = 0; i < from.Length; i++)
      {
        if (time - from[i] >= 0)
        {
          List<int> a = new List<int>();
          for (int c = 0; c < from.Length; c++)
          {
            if (c == i)
              continue;
            a.Add(from[c]);
          }
          a.Sort();
          List<int> b = new List<int>();
          b.AddRange(to);
          b.Add(from[i]);
          pass = new int[] { from[i] };
          b.Sort();
          possibilities.Add(new Configuration(this, (side ? a : b).ToArray(), (side ? b : a).ToArray(), time - from[i]));
          a.Clear();
          b.Clear();
        }
      }
      for (int x = 0; x < from.Length; x++)
      {
        for (int y = x + 1; y < from.Length; y++)
        {
          if (time - Math.Max(from[x], from[y]) >= 0)
          {
            List<int> a = new List<int>();
            for (int c = 0; c < from.Length; c++)
            {
              if (c == x || c == y)
                continue;
              a.Add(from[c]);
            }
            a.Sort();
            List<int> b = new List<int>();
            b.AddRange(to);
            b.Add(from[x]);
            b.Add(from[y]);
            pass = new int[] { from[x], from[y] };
            b.Sort();
            possibilities.Add(new Configuration(this, (side ? a : b).ToArray(), (side ? b : a).ToArray(), time - Math.Max(from[x], from[y])));
            a.Clear();
            b.Clear();
          }
        }
      }
    }
  }

  class Program
  {

    static void Main(string[] args)
    {
      Configuration a = new Configuration(new int[] { 5, 10, 20, 25 , 50}, new int[] { }, 110);
      a.step();
      while (Configuration.possibilities.Count != 0)
      {
        Configuration.possibilities[0].step();
      }
      Console.Out.WriteLine("Found {0} answers.", Configuration.options.Count);
      foreach (Configuration conf in Configuration.options)
      {
        List<string> way = new List<string>();
        Configuration up = conf;
        while (up != null)
        {
          way.Add(up.ToString());
          up = up.father;
        }
        way.Reverse();
        Console.WriteLine("---");
        foreach (string str in way)
          Console.WriteLine(str);
      }
    }
  }
}

אם אתם רוצים למשל לפתור בעיה עם נתונים אחרים, פשוט תשנו ב main את השורה:

Configuration a = new Configuration(new int[] { 5, 10, 20, 25 , 50}, new int[] { }, 110);

כאשר המערך הראשון זה הצד שממנו מתחילים (כל מספר שם זה בן אדם שלוקח לו X זמן לעבוד), ה מערך השני זה אנשים בצד השני של הגשר, ו 110 דקות זה המגבלת זמן שיש. (כרגע הקוד מטפל במעבר של עד 2 אנשים בכל פעם).

תהנו.