package main

import (
	"testing"
)

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func cutRod(p []int, n int) int {
	if n == 0 {
		return 0
	}
	q := -1
	for i := 1; i <= n; i++ {
		q = max(q, p[i]+cutRod(p, n-i))
	}
	return q
}

func memoizedCutRodAux(p []int, n int, r []int) int {
	if r[n] >= 0 {
		return r[n]
	}
	if n == 0 {
		return 0
	}
	q := -1
	for i := 1; i <= n; i++ {
		q = max(q, p[i]+memoizedCutRodAux(p, n-i, r))
	}
	r[n] = q
	return q
}

func memoizedCutRod(p []int, n int) int {
	r := []int{}
	for i := 0; i <= n; i++ {
		r = append(r, -1)
	}

	return memoizedCutRodAux(p, n, r)
}

func bottomUpCutRod(p []int, n int) int {
	if n == 0 {
		return 0
	}
	r := []int{0}
	for i := 1; i <= n; i++ {
		r = append(r, -1)
	}
	for j := 1; j <= n; j++ {
		q := -1
		for i := 1; i <= j; i++ {
			q = max(q, p[i]+r[j-i])
		}
		r[j] = q
	}

	return r[n]
}

func TestRodCutting(t *testing.T) {
	r := []int{0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30}
	p := []int{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}

	t.Run("with recursive approach", func(t *testing.T) {
		for n := 0; n < len(p); n++ {
			expected := r[n]
			actual := cutRod(p, n)

			if expected != actual {
				t.Errorf("%d: expected %d, actual %d", n, expected, actual)
			}
		}
	})

	t.Run("with top down dynamic programming approach", func(t *testing.T) {
		for n := 0; n < len(p); n++ {
			expected := r[n]
			actual := memoizedCutRod(p, n)

			if expected != actual {
				t.Errorf("%d: expected %d, actual %d", n, expected, actual)
			}
		}
	})

	t.Run("with bottom up dynamic programming approach", func(t *testing.T) {
		for n := 0; n < len(p); n++ {
			expected := r[n]
			actual := bottomUpCutRod(p, n)

			if expected != actual {
				t.Errorf("%d: expected %d, actual %d", n, expected, actual)
			}
		}
	})
}