Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 281
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

A wall consists of several rows of bricks of various integer lengths and uniform height. Your goal is to find a vertical line going from the top to the bottom of the wall that cuts through the fewest number of bricks. If the line goes through the edge between two bricks, this does not count as a cut.

For example, suppose the input is as follows, where values in each row represent the lengths of bricks in that row:
```
[[3, 5, 1, 1],
 [2, 3, 3, 2],
 [5, 5],
 [4, 4, 2],
 [1, 3, 3, 3],
 [1, 1, 6, 1, 1]]
```
The best we can we do here is to draw a line after the eighth brick, which will only require cutting through the bricks in the third and fifth row.

Given an input consisting of brick lengths for each row such as the one above, return the fewest number of bricks that must be cut to create a vertical line.

Pull request description:
Day281
Resolves #572.

Patch:
diff --git a/README.md b/README.md
index ea8ce27..68457b0 100644
--- a/README.md
+++ b/README.md
@@ -286,3 +286,4 @@ problems from
 * [Day 278](https://github.com/vaskoz/dailycodingproblem-go/issues/565)
 * [Day 279](https://github.com/vaskoz/dailycodingproblem-go/issues/566)
 * [Day 280](https://github.com/vaskoz/dailycodingproblem-go/issues/568)
+* [Day 281](https://github.com/vaskoz/dailycodingproblem-go/issues/572)
diff --git a/day281/problem.go b/day281/problem.go
new file mode 100644
index 0000000..0fd8ed9
--- /dev/null
+++ b/day281/problem.go
@@ -0,0 +1,22 @@
+package day281
+
+// FewestBricksCut return the fewest number of
+// bricks that must be cut to create a vertical line.
+func FewestBricksCut(bricks [][]int) int {
+	cumm := make(map[int]int)
+	for _, row := range bricks {
+		last := 0
+		for _, brick := range row {
+			last += brick
+			cumm[last]++
+		}
+		delete(cumm, last)
+	}
+	var most int
+	for _, count := range cumm {
+		if count > most {
+			most = count
+		}
+	}
+	return len(bricks) - most
+}


Test patch:
diff --git a/day281/problem_test.go b/day281/problem_test.go
new file mode 100644
index 0000000..b92786b
--- /dev/null
+++ b/day281/problem_test.go
@@ -0,0 +1,38 @@
+package day281
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	bricks [][]int
+	fewest int
+}{
+	{
+		[][]int{
+			{3, 5, 1, 1},
+			{2, 3, 3, 2},
+			{5, 5},
+			{4, 4, 2},
+			{1, 3, 3, 3},
+			{1, 1, 6, 1, 1},
+		},
+		2,
+	},
+}
+
+func TestFewestBricksCut(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := FewestBricksCut(tc.bricks); result != tc.fewest {
+			t.Errorf("Expected %v, got %v", tc.fewest, result)
+		}
+	}
+}
+
+func BenchmarkFewestBricksCut(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FewestBricksCut(tc.bricks)
+		}
+	}
+}