Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 346
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

You are given a huge list of airline ticket prices between different cities around the world on a given day. These are all direct flights. Each element in the list has the format (source_city, destination, price).

Consider a user who is willing to take up to `k` connections from their origin city `A` to their destination `B`. Find the cheapest fare possible for this journey and print the itinerary for that journey.

For example, our traveler wants to go from JFK to LAX with up to 3 connections, and our input flights are as follows:
```
[
    ('JFK', 'ATL', 150),
    ('ATL', 'SFO', 400),
    ('ORD', 'LAX', 200),
    ('LAX', 'DFW', 80),
    ('JFK', 'HKG', 800),
    ('ATL', 'ORD', 90),
    ('JFK', 'LAX', 500),
]
```
Due to some improbably low flight prices, the cheapest itinerary would be `JFK -> ATL -> ORD -> LAX`, costing `$440`.

Pull request:
Day346
Resolves #688.

Patch:
diff --git a/README.md b/README.md
index cce6a41..6701573 100644
--- a/README.md
+++ b/README.md
@@ -333,4 +333,5 @@ problems from
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
 * [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
 * [Day 342](https://github.com/vaskoz/dailycodingproblem-go/issues/682)
+* [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
diff --git a/day346/problem.go b/day346/problem.go
new file mode 100644
index 0000000..16be1dd
--- /dev/null
+++ b/day346/problem.go
@@ -0,0 +1,41 @@
+package day346
+
+// Flights represents all the flights and their prices.
+type Flights map[string]map[string]int
+
+// CheapestItinerary returns the cheapest itinerary that respects the
+// maxConnections limit.
+// Effectively, DFS for all possible answers that don't exceed the maximum
+// number of connections.
+// Runs in DFS performance. O(N+M)
+func CheapestItinerary(flights Flights, origin, destination string, maxConnections int) ([]string, int) {
+	visited := make(map[string]struct{})
+	return cheapestItinerary(flights, origin, destination, maxConnections, visited)
+}
+
+func cheapestItinerary(flights Flights, origin, destination string, connections int,
+	visited map[string]struct{}) ([]string, int) {
+	if connections < 0 {
+		return nil, 0
+	}
+	if origin == destination {
+		return []string{destination}, 0
+	}
+	cheapest := int(^uint(0) >> 1)
+	var itinerary []string
+	for next := range flights[origin] {
+		if _, seen := visited[next]; seen {
+			continue
+		}
+		visited[next] = struct{}{}
+		segments, price := cheapestItinerary(flights, next, destination, connections-1, visited)
+		if len(segments) != 0 {
+			if total := flights[origin][next] + price; total < cheapest {
+				cheapest = total
+				itinerary = append([]string{origin}, segments...)
+			}
+		}
+		delete(visited, next)
+	}
+	return itinerary, cheapest
+}


Test patch:
diff --git a/day346/problem_test.go b/day346/problem_test.go
new file mode 100644
index 0000000..8b667af
--- /dev/null
+++ b/day346/problem_test.go
@@ -0,0 +1,84 @@
+package day346
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	flights             Flights
+	origin, destination string
+	connections         int
+	itinerary           []string
+	cost                int
+}{
+	{
+		Flights{
+			"JFK": {
+				"ATL": 150,
+				"HKG": 800,
+				"LAX": 500,
+			},
+			"ATL": {
+				"SFO": 400,
+				"JFK": 1,
+				"ORD": 90,
+			},
+			"ORD": {
+				"LAX": 200,
+			},
+			"LAX": {
+				"DFW": 80,
+			},
+		},
+		"JFK",
+		"LAX",
+		3,
+		[]string{"JFK", "ATL", "ORD", "LAX"},
+		440,
+	},
+	{
+		Flights{
+			"JFK": {
+				"ATL": 150,
+				"HKG": 800,
+				"LAX": 500,
+			},
+			"ATL": {
+				"SFO": 400,
+				"ORD": 90,
+			},
+			"ORD": {
+				"LAX": 200,
+			},
+			"LAX": {
+				"DFW": 80,
+			},
+		},
+		"JFK",
+		"LAX",
+		1,
+		[]string{"JFK", "LAX"},
+		500,
+	},
+}
+
+func TestCheapestItinerary(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if itinerary, price := CheapestItinerary(tc.flights, tc.origin,
+			tc.destination, tc.connections); !reflect.DeepEqual(tc.itinerary, itinerary) ||
+			tc.cost != price {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.itinerary, tc.cost, itinerary, price)
+		}
+	}
+}
+
+func BenchmarkCheapestItinerary(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CheapestItinerary(tc.flights, tc.origin, tc.destination, tc.connections)
+		}
+	}
+}