using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BoardCutter
{
class Program
{
static List<double> Boards;
static List<double> LengthsNeeded;
static double CutWidth = double.NaN;
static double TotalBoardLength;
static int LengthsNeededLeft = 0;
static List<string> Instructions = new List<string>();
static List<string> Summary = new List<string>();
static bool TryCut()
{
if (LengthsNeededLeft == 0)
{
double BoardLengthRemaining = Boards.Where(b => !double.IsNaN(b)).Sum();
Summary.Add(String.Format("Boards Remaining:"));
for (int j = 0; j < Boards.Count; j++)
{
if (double.IsNaN(Boards[j])) continue;
Summary.Add(String.Format(" Board #{0}: {1}", j, Boards[j]));
}
Summary.Add(String.Format(
"Total Remaining {0} ({1:0.0}% efficiency)",
BoardLengthRemaining,
100 * (1 - (BoardLengthRemaining) / TotalBoardLength)));
return true;
}
for (int i = 0; i < LengthsNeeded.Count; i++)
{
double l = LengthsNeeded[i];
if (double.IsNaN(l)) continue;
for (int j = 0; j < Boards.Count; j++)
{
double b = Boards[j];
if (double.IsNaN(b)) continue;
double BoardRemaining = b - l - CutWidth;
if (BoardRemaining >= 0.0)
{
LengthsNeeded[i] = double.NaN;
LengthsNeededLeft--;
Boards[j] = double.NaN;
Boards.Add(BoardRemaining);
int NewBoardIndex = Boards.Count - 1;
if (TryCut())
{
Instructions.Add(
String.Format("Cut board #{3,2} of length {0,8} to size: {1,8} (leaving board #{4,2} of length {2,8})",
b, l, BoardRemaining, j + 1, NewBoardIndex+1));
return true;
}
Boards.RemoveAt(Boards.Count - 1);
LengthsNeeded[i] = l;
LengthsNeededLeft++;
Boards[j] = b;
}
}
}
//all boards are too short
return false;
}
static void Main(string[] args)
{
Boards = new List<double>(new double[]{48,48,48,48,48,48});
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});
CutWidth = 0.125;
TotalBoardLength = Boards.Sum();
LengthsNeeded.Sort();
LengthsNeeded.Reverse();
LengthsNeededLeft = LengthsNeeded.Count;
Console.WriteLine("Boards:");
foreach (double b in Boards) Console.WriteLine(" {0}", b);
Console.WriteLine("Total: {0}", Boards.Sum());
Console.WriteLine();
Console.WriteLine("Lengths Needed:");
foreach (double l in LengthsNeeded) Console.WriteLine(" {0}", l);
Console.WriteLine("Total: {0}", LengthsNeeded.Sum());
Console.WriteLine();
TryCut();
Instructions.Reverse();
for (int i = 0; i < Instructions.Count; i++)
Console.WriteLine("Cut {0,2}: {1}", i+1, Instructions[i]);
Console.WriteLine();
foreach (string s in Summary) Console.WriteLine(s);
Console.WriteLine();
Console.Read();
}
}
}
/*
* Example output:
Boards:
48
48
48
48
48
48
Total: 288
Lengths Needed:
36.75
36.5
36.5
26.25
26.125
22.5
21
20.5
14.5
9.25
9
6.5
4
Total: 269.375
Cut 1: Cut board # 1 of length 48 to size: 36.75 (leaving board # 7 of length 11.125)
Cut 2: Cut board # 2 of length 48 to size: 36.5 (leaving board # 8 of length 11.375)
Cut 3: Cut board # 3 of length 48 to size: 36.5 (leaving board # 9 of length 11.375)
Cut 4: Cut board # 4 of length 48 to size: 26.25 (leaving board #10 of length 21.625)
Cut 5: Cut board # 5 of length 48 to size: 26.125 (leaving board #11 of length 21.75)
Cut 6: Cut board # 6 of length 48 to size: 22.5 (leaving board #12 of length 25.375)
Cut 7: Cut board #10 of length 21.625 to size: 21 (leaving board #13 of length 0.5)
Cut 8: Cut board #11 of length 21.75 to size: 20.5 (leaving board #14 of length 1.125)
Cut 9: Cut board #12 of length 25.375 to size: 14.5 (leaving board #15 of length 10.75)
Cut 10: Cut board # 7 of length 11.125 to size: 9.25 (leaving board #16 of length 1.75)
Cut 11: Cut board # 8 of length 11.375 to size: 9 (leaving board #17 of length 2.25)
Cut 12: Cut board # 9 of length 11.375 to size: 6.5 (leaving board #18 of length 4.75)
Cut 13: Cut board #15 of length 10.75 to size: 4 (leaving board #19 of length 6.625)
Boards Remaining:
Board #12: 0.5
Board #13: 1.125
Board #15: 1.75
Board #16: 2.25
Board #17: 4.75
Board #18: 6.625
Total Remaining 17 (94.1% efficiency)
*/