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)

*/