add recursive solution for rod cutting

1 files changed, 25 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting.rb b/exercises/15.1/rod_cutting.rb
new file mode 100644
index 0000000..ce9f058
--- /dev/null
+++ b/exercises/15.1/rod_cutting.rb
@@ -0,0 +1,25 @@
+require "minitest/autorun"
+
+def cut_rod(p, n)
+  return 0 if n == 0
+
+  q = -1
+  1.upto(n) do |i|
+    q = [q, p[i] + cut_rod(p, n - i)].max
+  end
+  q
+end
+
+class RodCuttingTest < Minitest::Test
+  def setup
+    @prices =      [ 0,  1,  5,  8,  9, 10, 17, 17, 20, 24, 30]
+    @max_revenue = [ 0,  1,  5,  8, 10, 13, 17, 18, 22, 25, 30]
+    @max_cuts =    [ 0,  1,  2,  3,  2,  2,  6,  1,  2,  3, 10]
+  end
+
+  def test_recursive_rod_cutting
+    0.upto(10) do |n|
+      assert_equal @max_revenue[n], cut_rod(@prices, n), "n: #{n}"
+    end
+  end
+end