SQL SERVER – The Flight Connection Puzzle

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');

The Solution

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)