package algo

import (
	"math/rand"
	"testing"
)

func TestDPKnownCase(t *testing.T) {
	arr := []int{30, 35, 15, 5, 10, 20, 25}
	want := 15125

	if got := DP(arr); got != want {
		t.Fatalf("DP(%v) = %d, want %d", arr, got, want)
	}
}

func TestGreedyRandomCompare(t *testing.T) {
	r := rand.New(rand.NewSource(1))

	for tc := 0; tc < 500; tc++ {
		matrixCount := r.Intn(5) + 3
		arr := make([]int, matrixCount+1)
		for i := range arr {
			arr[i] = r.Intn(9) + 2
		}

		greedy := Greedy(arr)
		dp := DP(arr)
		if greedy < dp {
			t.Fatalf("greedy beat dp unexpectedly: arr=%v greedy=%d dp=%d", arr, greedy, dp)
		}
	}
}

func TestGreedyIsNotAlwaysOptimal(t *testing.T) {
	r := rand.New(rand.NewSource(2))
	found := false

	for tc := 0; tc < 500; tc++ {
		matrixCount := r.Intn(5) + 3
		arr := make([]int, matrixCount+1)
		for i := range arr {
			arr[i] = r.Intn(9) + 2
		}

		greedy := Greedy(arr)
		dp := DP(arr)
		if dp < greedy {
			t.Logf("found counterexample: arr=%v greedy=%d dp=%d", arr, greedy, dp)
			found = true
		}

		if dp > greedy {
			t.Fatalf("why greedy < dp???")
		}
	}

	if !found {
		t.Fatal("expected to find at least one case where dp < greedy")
	}
}