Struct_bugfix (#1)

* initial work finding bug

* moved solution output into struct

* added output formatting

* fixed issue with rolling average

* moved comment above main

2 files changed, 47 insertions, 51 deletions

diff --git a/src/Program/Program.cs b/src/Program/Program.cs
index 5dff2fc..70af96f 100644
--- a/src/Program/Program.cs
+++ b/src/Program/Program.cs
@@ -18,12 +18,19 @@ namespace Program
         public string Type;
         public int Value;
         public TimeSpan Runtime;
-        public override string ToString() => $"{Value} @ {Runtime.ToString("mm\\:ss\\.ff")}";
         public void AddAverage(Solution solution, int count)
         {
-            Runtime = (Runtime + solution.Runtime) / count;
-            Value = (Value + solution.Value) / count;
+            Runtime = (Runtime * (count - 1) + solution.Runtime) / count;
+            Value = (Value * (count - 1) + solution.Value) / count;
         }
+        public void Output(FileInfo outputFile = null)
+        {
+            if (outputFile != null)
+                File.AppendAllText(outputFile.FullName, this.ToString() + "\n");
+            Console.WriteLine($"{this.Type} Solution: {this.ToString()}");
+        }
+        public override string ToString()
+            => $"{Value} @ {Runtime.TotalMilliseconds}";
     }
 
     public struct Algorithm
@@ -35,7 +42,7 @@ namespace Program
     class Program
     {
         static readonly Algorithm Dynamic = new Algorithm { Type = "Optimal", Func = SolveSubsetSum.Dynamic };
-        static readonly Algorithm Greedy = new Algorithm { Type = "Approximate", Func = SolveSubsetSum.Greedy };
+        static readonly Algorithm Greedy = new Algorithm { Type = "Approx.", Func = SolveSubsetSum.Greedy };
         static Problem Defaults = new Problem
         {
             NumItems = 100,
@@ -44,30 +51,31 @@ namespace Program
             Capacity = 1000,
         };
 
+        /* 
+        run 10 times
+        keep track of high, low, and average values
+        keep track of the runtime of each algorithm
+            random number generator
+                generate 100 possible items
+                items should have random weights between 1 - 600
 
+            use dynamic algorithm to compute the optimal solution
+
+            use greedy algorithm to compute approximate solution
+        */
         static void Main(string[] args)
         {
+            Problem parameters = Defaults;
             FileInfo dynamicFile = new("dynamic.log");
             FileInfo greedyFile = new("greedy.log");
-            Problem parameters = Defaults;
             Solution averageDynamic = default(Solution);
             Solution averageGreedy = default(Solution);
 
             averageDynamic.Type = $"Average {Dynamic.Type}";
             averageGreedy.Type = $"Average {Greedy.Type}";
 
-            /* 
-            run 10 times
-            keep track of high, low, and average values
-            keep track of the runtime of each algorithm
-                random number generator
-                    generate 100 possible items
-                    items should have random weights between 1 - 600
-
-                use dynamic algorithm to compute the optimal solution
-
-                use greedy algorithm to compute approximate solution
-            */
+            File.WriteAllText(dynamicFile.FullName, "[Score @ Runtime]\n");
+            File.WriteAllText(greedyFile.FullName, "[Score @ Runtime]\n");
 
             for (int i = 0; i < 10; i++)
             {
@@ -78,14 +86,14 @@ namespace Program
                 averageDynamic.AddAverage(dynamic, i + 1);
                 averageGreedy.AddAverage(greedy, i + 1);
 
-                OutputSolution(dynamic, dynamicFile);
-                OutputSolution(greedy, greedyFile);
-
+                dynamic.Output(dynamicFile);
+                greedy.Output(greedyFile);
             }
 
-            OutputSolution(averageDynamic, dynamicFile);
-            OutputSolution(averageGreedy, greedyFile);
-
+            File.AppendAllText(dynamicFile.FullName, "[Average]\n");
+            File.AppendAllText(greedyFile.FullName, "[Average]\n");
+            averageDynamic.Output(dynamicFile);
+            averageGreedy.Output(greedyFile);
         }
 
         static int[] GenerateItems(Problem problem)
@@ -101,22 +109,10 @@ namespace Program
 
         static Solution GenerateSolution(Algorithm algorithm, int[] items, int capacity)
         {
-            Stopwatch stopWatch = new Stopwatch();
-            stopWatch.Restart();
-
+            Stopwatch runtime = Stopwatch.StartNew();
             var solution = algorithm.Func(items, capacity);
-            TimeSpan runtime = stopWatch.Elapsed;
-
-            stopWatch.Stop();
-            return new Solution { Type = algorithm.Type, Value = solution, Runtime = runtime };
-        }
-
-        static void OutputSolution(Solution solution, FileInfo outputFile = null)
-        {
-            Console.WriteLine($"{solution.Type} Solution: {solution}");
-
-            if (outputFile != null)
-                File.WriteAllText(outputFile.FullName, solution.ToString());
+            runtime.Stop();
+            return new Solution { Type = algorithm.Type, Value = solution, Runtime = runtime.Elapsed };
         }
     }
 }
diff --git a/src/SubsetSum/SolveSubsetSum.cs b/src/SubsetSum/SolveSubsetSum.cs
index 5541bf5..55de144 100644
--- a/src/SubsetSum/SolveSubsetSum.cs
+++ b/src/SubsetSum/SolveSubsetSum.cs
@@ -26,20 +26,20 @@ namespace SubsetSum
 
             //initialize "no items" row to all be weight 0
             for (int i = 0; i < maxWeight; i++)
-              matrix[0,i] = 0;
+                matrix[0, i] = 0;
 
-            for(int i = 1; i < n; i++)
+            for (int i = 1; i < n; i++)
             {
-              for(int w = 1; w < maxWeight; w++)
-              {
-                if(items[i] > w)
-                  matrix[i,w] = matrix[i-1,w];
-                else
-                  matrix[i,w] = Math.Max( matrix[i-1,w], (items[i] + matrix[i-1, w-items[i]]) );
-              }
+                for (int w = 1; w < maxWeight; w++)
+                {
+                    if (items[i] > w)
+                        matrix[i, w] = matrix[i - 1, w];
+                    else
+                        matrix[i, w] = Math.Max(matrix[i - 1, w], (items[i] + matrix[i - 1, w - items[i]]));
+                }
             }
 
-            return matrix[n,maxWeight];
+            return matrix[n - 1, maxWeight - 1];
         }
 
         /*
@@ -53,10 +53,10 @@ namespace SubsetSum
             int weightAdded = 0;
             int i = 0;
 
-            Array.Sort(items, (a,b) => b.CompareTo(a));
+            Array.Sort(items, (a, b) => b.CompareTo(a));
 
-            while(i < items.Length && weightAdded + items[i] <= maxWeight)
-              weightAdded += items[i++];
+            while (i < items.Length && weightAdded + items[i] <= maxWeight)
+                weightAdded += items[i++];
 
             return weightAdded;
         }