SQL SERVER – The Flight Connection Puzzle

SQL SERVER - The Flight Connection Puzzle airport-800x581 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.

SQL SERVER - The Flight Connection Puzzle flightdestination-800x179

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)

CTE, SQL Server
Previous Post
SQL SERVER – The Two Doors, Two Guards Puzzle
Next Post
SQL Puzzle – Retrieve the Unique Evens Under 10

Related Posts

5 Comments. Leave new

  • Carter Cordingley
    July 31, 2023 7:21 am

    The only rhing I would change is use datetimeoffset due to crossing timezones

    Reply
  • Should this be using “>=” instead of just “>”?
    AND f.DepartureTime > DATEADD(hour, 1, r.ArrivalTime)

    Reply
  • Paul Wichtendahl
    August 1, 2023 10:48 pm

    So I was playing with a puzzle trying to find the shortest distance one would have to travel to go to every capital in the contiguous 48 states. Would this also be a SQL based solution for that?

    Reply
    • That would be super interesting solution. However, this requires the distance between all the cities and may be we can find one such solution easily. Other thing is that we do not have details about how to roads are connected so it is difficult to come up with the real practical answer.

      Reply
  • Is recurcive CTE possible in sqlite?

    Reply

Leave a Reply