Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 299
Good morning! Here's your coding interview problem for today.

This problem was asked by Samsung.

A group of houses is connected to the main water plant by means of a set of pipes. A house can either be connected by a set of pipes extending directly to the plant, or indirectly by a pipe to a nearby house which is otherwise connected.

For example, here is a possible configuration, where A, B, and C are houses, and arrows represent pipes:

`A <--> B <--> C <--> plant`
Each pipe has an associated cost, which the utility company would like to minimize. Given an undirected graph of pipe connections, return the lowest cost configuration of pipes such that each house has access to water.

In the following setup, for example, we can remove all but the pipes from plant to A, plant to B, and B to C, for a total cost of 16.
```
pipes = {
    'plant': {'A': 1, 'B': 5, 'C': 20},
    'A': {'C': 15},
    'B': {'C': 10},
    'C': {}
}
```

Pull request description:
Day299
Resolves #611.

Patch:
diff --git a/README.md b/README.md
index d56bb3d..aaf7a1a 100644
--- a/README.md
+++ b/README.md
@@ -306,3 +306,4 @@ problems from
 * [Day 296](https://github.com/vaskoz/dailycodingproblem-go/issues/605)
 * [Day 297](https://github.com/vaskoz/dailycodingproblem-go/issues/607)
 * [Day 298](https://github.com/vaskoz/dailycodingproblem-go/issues/609)
+* [Day 299](https://github.com/vaskoz/dailycodingproblem-go/issues/611)
diff --git a/day299/problem.go b/day299/problem.go
new file mode 100644
index 0000000..03fb2f6
--- /dev/null
+++ b/day299/problem.go
@@ -0,0 +1,8 @@
+package day299
+
+import "github.com/algds/kruskals"
+
+// LowestCostPipeConfiguration is a MST for the given pipes.
+func LowestCostPipeConfiguration(pipes []kruskals.WeightedEdge) []kruskals.WeightedEdge {
+	return kruskals.MinimumSpanningTree(pipes)
+}


Test patch:
diff --git a/day299/problem_test.go b/day299/problem_test.go
new file mode 100644
index 0000000..825c2d3
--- /dev/null
+++ b/day299/problem_test.go
@@ -0,0 +1,46 @@
+package day299
+
+import (
+	"reflect"
+	"testing"
+
+	"github.com/algds/kruskals"
+)
+
+// nolint
+var testcases = []struct {
+	pipes    []kruskals.WeightedEdge
+	expected []kruskals.WeightedEdge
+}{
+	{
+		[]kruskals.WeightedEdge{
+			kruskals.SimpleWeightedEdge{F: 0, T: 1, W: 1},
+			kruskals.SimpleWeightedEdge{F: 0, T: 2, W: 5},
+			kruskals.SimpleWeightedEdge{F: 0, T: 3, W: 20},
+			kruskals.SimpleWeightedEdge{F: 1, T: 3, W: 15},
+			kruskals.SimpleWeightedEdge{F: 2, T: 3, W: 10},
+		},
+		[]kruskals.WeightedEdge{
+			kruskals.SimpleWeightedEdge{F: 0, T: 1, W: 1},
+			kruskals.SimpleWeightedEdge{F: 0, T: 2, W: 5},
+			kruskals.SimpleWeightedEdge{F: 2, T: 3, W: 10},
+		},
+	},
+}
+
+func TestLowestCostPipeConfiguration(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LowestCostPipeConfiguration(tc.pipes); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkLowestCostPipeConfiguration(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LowestCostPipeConfiguration(tc.pipes)
+		}
+	}
+}