Earlier, I wrote a blog post, SQL SERVER – The Two Doors, Two Guards Puzzle, and I received lots of appreciation for it. If you have not yet checked that blog post out, it is a fun post to read. Today we are going to see another such puzzle – The Flight Connection Puzzle.
Suppose you have a flight table with columns FlightID, Origin, Destination, and DepartureTime. Each entry in the table represents a direct flight from an origin city to a destination city. The challenge is to write a SQL query that, given an origin city and a destination city, finds all possible routes between the origin and the destination, with any number of connecting flights. Assume that a connecting flight must depart at least one hour after the previous flight arrives.
Setting Up the Scenario
Let’s first set the stage by creating our
Flights table and populating it with some data:
CREATE TABLE Flights ( FlightID INT PRIMARY KEY, Origin VARCHAR(255), Destination VARCHAR(255), DepartureTime DATETIME, ArrivalTime DATETIME ); INSERT INTO Flights VALUES (1, 'New York', 'Chicago', '2023-08-01 08:00:00', '2023-08-01 10:00:00'); INSERT INTO Flights VALUES (2, 'Chicago', 'Los Angeles', '2023-08-01 12:00:00', '2023-08-01 14:00:00'); INSERT INTO Flights VALUES (3, 'Los Angeles', 'San Francisco', '2023-08-01 16:00:00', '2023-08-01 18:00:00'); INSERT INTO Flights VALUES (4, 'New York', 'San Francisco', '2023-08-01 09:00:00', '2023-08-01 12:00:00'); INSERT INTO Flights VALUES (5, 'Chicago', 'San Francisco', '2023-08-01 15:00:00', '2023-08-01 17:00:00');
To solve this puzzle, we’ll use a feature of SQL Server called recursive Common Table Expressions (CTEs). Recursive CTEs are a powerful tool that can solve problems involving repeated or looped operations, such as traversing hierarchies or – in our case – finding all possible paths between two points.
Here’s the solution:
DECLARE @origin VARCHAR(255) = 'New York'; DECLARE @destination VARCHAR(255) = 'San Francisco'; WITH Route AS ( SELECT FlightID, Origin, Destination, DepartureTime, ArrivalTime, CAST(Origin + ' -> ' + Destination AS VARCHAR(MAX)) AS Path FROM Flights WHERE Origin = @origin UNION ALL SELECT f.FlightID, f.Origin, f.Destination, f.DepartureTime, f.ArrivalTime, CAST(r.Path + ' -> ' + f.Destination AS VARCHAR(MAX)) AS Path FROM Flights f JOIN Route r ON f.Origin = r.Destination AND f.DepartureTime > DATEADD(hour, 1, r.ArrivalTime) ) SELECT Path FROM Route WHERE Destination = @destination;
This query constructs all possible paths from the origin city to the destination city that meet the condition of having at least one hour between connecting flights.
That’s it for today’s puzzle. Remember, SQL Server is not just a tool for managing data. It’s also a powerful engine for solving complex problems. So keep practicing and pushing the boundaries of what you can do with SQL. You can always connect with me on YouTube.
Reference: Pinal Dave (https://blog.sqlauthority.com)