Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Flight Itinerary
The flight itinerary problem is as follows:

Given an unordered list of flights taken by someone, each represented as (origin, destination) pairs, and a starting airport, compute the person's itinerary. If no such itinerary exists, return null. All flights must be used in the itinerary.

For example, given the following list of flights:

HNL ➔ AKL
YUL ➔ ORD
ORD ➔ SFO
SFO ➔ HNL
and starting airport YUL, you should return YUL ➔ ORD ➔ SFO ➔ HNL ➔ AKL. (This also happens to be the actual itinerary for the trip I'm about to take.)

Pull request description:
Flights
Resolves #45.

Patch:
diff --git a/README.md b/README.md
index 02cd0b7..c296b22 100644
--- a/README.md
+++ b/README.md
@@ -31,3 +31,4 @@ problems from
 * [Day 18](https://github.com/vaskoz/dailycodingproblem-go/issues/39)
 * [Day 19](https://github.com/vaskoz/dailycodingproblem-go/issues/41)
 * [Day 19 N-Queens](https://github.com/vaskoz/dailycodingproblem-go/issues/43)
+* [Day 19 Flight Itinerary](https://github.com/vaskoz/dailycodingproblem-go/issues/45)
diff --git a/flights/problem.go b/flights/problem.go
new file mode 100644
index 0000000..1d347fe
--- /dev/null
+++ b/flights/problem.go
@@ -0,0 +1,28 @@
+package flights
+
+// Airport represents the airport code.
+type Airport string
+
+// Flight from a departure airport to an arrival airport.
+type Flight struct {
+	depart, arrive Airport
+}
+
+// Itinerary takes a list of flights and returns the itinerary.
+// Returns nil if there is no possible itinerary that uses all flights.
+func Itinerary(segments []Flight, route []Airport) []Airport {
+	if len(segments) == 0 {
+		return route
+	}
+	last := route[len(route)-1]
+	for i, segment := range segments {
+		segmentsWoCurrent := append([]Flight{}, segments[:i]...)
+		segmentsWoCurrent = append(segmentsWoCurrent, segments[i+1:]...)
+		route = append(route, segment.arrive)
+		if segment.depart == last {
+			return Itinerary(segmentsWoCurrent, route)
+		}
+		route = route[:len(route)-1]
+	}
+	return nil
+}


Test patch:
diff --git a/flights/problem_test.go b/flights/problem_test.go
new file mode 100644
index 0000000..d690891
--- /dev/null
+++ b/flights/problem_test.go
@@ -0,0 +1,36 @@
+package flights
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	segments []Flight
+	start    []Airport
+	expected []Airport
+}{
+	{[]Flight{{"HNL", "AKL"}, {"YUL", "ORD"}, {"ORD", "SFO"}, {"SFO", "HNL"}},
+		[]Airport{"YUL"},
+		[]Airport{"YUL", "ORD", "SFO", "HNL", "AKL"}},
+	{[]Flight{{"HNL", "AKL"}, {"YUL", "ORD"}, {"ORD", "SFO"}, {"SFO", "HNL"}, {"ORD", "LAX"}},
+		[]Airport{"YUL"},
+		nil},
+}
+
+func TestItinerary(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := Itinerary(tc.segments, tc.start); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkItinerary(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			Itinerary(tc.segments, tc.start)
+		}
+	}
+}