Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 19
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.

Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.

Pull request description:
Day19
Resolves #41 

Patch:
diff --git a/README.md b/README.md
index f828aa3..3e89e6d 100644
--- a/README.md
+++ b/README.md
@@ -29,3 +29,4 @@ problems from
 * [Day 16](https://github.com/vaskoz/dailycodingproblem-go/issues/35)
 * [Day 17](https://github.com/vaskoz/dailycodingproblem-go/issues/37)
 * [Day 18](https://github.com/vaskoz/dailycodingproblem-go/issues/39)
+* [Day 19](https://github.com/vaskoz/dailycodingproblem-go/issues/41)
diff --git a/day19/problem.go b/day19/problem.go
new file mode 100644
index 0000000..950d0d3
--- /dev/null
+++ b/day19/problem.go
@@ -0,0 +1,34 @@
+package day19
+
+import "math"
+
+// PaintingCosts represents the cost to paint in each of these colors.
+type PaintingCosts []int
+
+// Houses represents a list of houses that can be painting a different color for a price.
+type Houses []PaintingCosts
+
+// MinPaintingCost uses dynamic programming to calculate the cheapest way to paint houses
+// so that no adjacent houses have the same color.
+func MinPaintingCost(houses Houses) int {
+	for i := 1; i < len(houses); i++ {
+		for j := range houses[i] {
+			houses[i][j] += minimum(houses[i-1], j)
+		}
+	}
+	return minimum(houses[len(houses)-1], -1)
+}
+
+// minimum returns the minimum of all the values excluding the value at index 'exclude'.
+func minimum(costs PaintingCosts, exclude int) int {
+	var minimum int64 = math.MaxInt64
+	for i, cost := range costs {
+		if i == exclude {
+			continue
+		}
+		if cost64 := int64(cost); cost64 < minimum {
+			minimum = cost64
+		}
+	}
+	return int(minimum)
+}


Test patch:
diff --git a/day19/problem_test.go b/day19/problem_test.go
new file mode 100644
index 0000000..93fd15e
--- /dev/null
+++ b/day19/problem_test.go
@@ -0,0 +1,26 @@
+package day19
+
+import "testing"
+
+var testcases = []struct {
+	houses   Houses
+	expected int
+}{
+	{Houses{PaintingCosts{2, 4, 5}, PaintingCosts{3, 6, 9}}, 7},
+}
+
+func TestMinPaintingCost(t *testing.T) {
+	for _, tc := range testcases {
+		if result := MinPaintingCost(tc.houses); result != tc.expected {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMinPaintingCost(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinPaintingCost(tc.houses)
+		}
+	}
+}