Advertisement
johnterickson

Board Cuttting Brute Force

Feb 17th, 2013
3,861
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 5.60 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace BoardCutter
  7. {
  8.     class Program
  9.     {
  10.         static List<double> Boards;
  11.         static List<double> LengthsNeeded;
  12.  
  13.         static double CutWidth = double.NaN;
  14.         static double TotalBoardLength;
  15.  
  16.         static int LengthsNeededLeft = 0;
  17.  
  18.         static List<string> Instructions = new List<string>();
  19.         static List<string> Summary = new List<string>();
  20.  
  21.         static bool TryCut()
  22.         {
  23.             if (LengthsNeededLeft == 0)
  24.             {
  25.                 double BoardLengthRemaining = Boards.Where(b => !double.IsNaN(b)).Sum();
  26.  
  27.                 Summary.Add(String.Format("Boards Remaining:"));
  28.  
  29.                 for (int j = 0; j < Boards.Count; j++)
  30.                 {
  31.                     if (double.IsNaN(Boards[j])) continue;
  32.                     Summary.Add(String.Format(" Board #{0}: {1}", j, Boards[j]));
  33.                 }
  34.  
  35.                 Summary.Add(String.Format(
  36.                     "Total Remaining {0} ({1:0.0}% efficiency)",
  37.                     BoardLengthRemaining,
  38.                     100 * (1 - (BoardLengthRemaining) / TotalBoardLength)));
  39.  
  40.                 return true;
  41.             }
  42.  
  43.  
  44.             for (int i = 0; i < LengthsNeeded.Count; i++)
  45.             {
  46.                 double l = LengthsNeeded[i];
  47.  
  48.                 if (double.IsNaN(l)) continue;
  49.  
  50.                 for (int j = 0; j < Boards.Count; j++)
  51.                 {
  52.                     double b = Boards[j];
  53.  
  54.                     if (double.IsNaN(b)) continue;
  55.  
  56.                     double BoardRemaining = b - l - CutWidth;
  57.  
  58.                     if (BoardRemaining >= 0.0)
  59.                     {
  60.                         LengthsNeeded[i] = double.NaN;
  61.                         LengthsNeededLeft--;
  62.  
  63.                         Boards[j] = double.NaN;
  64.  
  65.                         Boards.Add(BoardRemaining);
  66.  
  67.                         int NewBoardIndex = Boards.Count - 1;
  68.  
  69.                         if (TryCut())
  70.                         {
  71.                             Instructions.Add(
  72.                                 String.Format("Cut board #{3,2} of length {0,8} to size: {1,8} (leaving board #{4,2} of length {2,8})",
  73.                                     b, l, BoardRemaining, j + 1, NewBoardIndex+1));
  74.                             return true;
  75.                         }
  76.  
  77.                         Boards.RemoveAt(Boards.Count - 1);
  78.  
  79.                         LengthsNeeded[i] = l;
  80.                         LengthsNeededLeft++;
  81.  
  82.                         Boards[j] = b;
  83.                     }
  84.                 }  
  85.             }
  86.  
  87.             //all boards are too short
  88.  
  89.             return false;
  90.         }
  91.  
  92.  
  93.  
  94.         static void Main(string[] args)
  95.         {
  96.             Boards = new List<double>(new double[]{48,48,48,48,48,48});
  97.             LengthsNeeded = new List<double>(new double[] { 36.75, 36.5, 36.5, 26.25, 26.125, 22.5, 21, 20.5, 14.5, 9.25, 9, 6.5, 4});
  98.             CutWidth = 0.125;
  99.  
  100.             TotalBoardLength = Boards.Sum();
  101.             LengthsNeeded.Sort();
  102.             LengthsNeeded.Reverse();
  103.             LengthsNeededLeft = LengthsNeeded.Count;
  104.  
  105.             Console.WriteLine("Boards:");
  106.             foreach (double b in Boards) Console.WriteLine(" {0}", b);
  107.             Console.WriteLine("Total: {0}", Boards.Sum());
  108.             Console.WriteLine();
  109.  
  110.             Console.WriteLine("Lengths Needed:");
  111.             foreach (double l in LengthsNeeded) Console.WriteLine(" {0}", l);
  112.             Console.WriteLine("Total: {0}", LengthsNeeded.Sum());
  113.             Console.WriteLine();
  114.  
  115.             TryCut();
  116.  
  117.             Instructions.Reverse();
  118.  
  119.             for (int i = 0; i < Instructions.Count; i++)
  120.                 Console.WriteLine("Cut {0,2}: {1}", i+1, Instructions[i]);
  121.             Console.WriteLine();
  122.  
  123.             foreach (string s in Summary) Console.WriteLine(s);
  124.             Console.WriteLine();
  125.  
  126.             Console.Read();
  127.         }
  128.     }
  129. }
  130.  
  131. /*
  132.  
  133.  * Example output:
  134.  
  135. Boards:
  136.  48
  137.  48
  138.  48
  139.  48
  140.  48
  141.  48
  142. Total: 288
  143.  
  144. Lengths Needed:
  145.  36.75
  146.  36.5
  147.  36.5
  148.  26.25
  149.  26.125
  150.  22.5
  151.  21
  152.  20.5
  153.  14.5
  154.  9.25
  155.  9
  156.  6.5
  157.  4
  158. Total: 269.375
  159.  
  160. Cut  1: Cut board # 1 of length       48 to size:    36.75 (leaving board # 7 of length   11.125)
  161. Cut  2: Cut board # 2 of length       48 to size:     36.5 (leaving board # 8 of length   11.375)
  162. Cut  3: Cut board # 3 of length       48 to size:     36.5 (leaving board # 9 of length   11.375)
  163. Cut  4: Cut board # 4 of length       48 to size:    26.25 (leaving board #10 of length   21.625)
  164. Cut  5: Cut board # 5 of length       48 to size:   26.125 (leaving board #11 of length    21.75)
  165. Cut  6: Cut board # 6 of length       48 to size:     22.5 (leaving board #12 of length   25.375)
  166. Cut  7: Cut board #10 of length   21.625 to size:       21 (leaving board #13 of length      0.5)
  167. Cut  8: Cut board #11 of length    21.75 to size:     20.5 (leaving board #14 of length    1.125)
  168. Cut  9: Cut board #12 of length   25.375 to size:     14.5 (leaving board #15 of length    10.75)
  169. Cut 10: Cut board # 7 of length   11.125 to size:     9.25 (leaving board #16 of length     1.75)
  170. Cut 11: Cut board # 8 of length   11.375 to size:        9 (leaving board #17 of length     2.25)
  171. Cut 12: Cut board # 9 of length   11.375 to size:      6.5 (leaving board #18 of length     4.75)
  172. Cut 13: Cut board #15 of length    10.75 to size:        4 (leaving board #19 of length    6.625)
  173.  
  174. Boards Remaining:
  175.  Board #12: 0.5
  176.  Board #13: 1.125
  177.  Board #15: 1.75
  178.  Board #16: 2.25
  179.  Board #17: 4.75
  180.  Board #18: 6.625
  181. Total Remaining 17 (94.1% efficiency)
  182.  
  183. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement