Подписчик прислал мне интересную задачку с stratascratch.com, и я не могла устоять, чтобы не решить её.
Нужно найти самый дешёвый путь между городами, учитывая варианты с пересадками (до двух).
📌 Дано:
Есть таблица da_flights, в которой:
✈️ origin – пункт отправления
✈️ destination – пункт назначения
✈️ cost – стоимость перелёта
Чтобы найти маршруты с пересадками, нам нужно соединить таблицу саму с собой (self-join).
🛠 Решение
1️⃣ Прямые рейсы (без пересадок) — просто берём origin, destination, cost.
2️⃣ Рейсы с одной пересадкой — соединяем таблицу саму с собой (JOIN), где f1.destination = f2.origin. Это значит, что первый рейс прилетает в город, из которого отправляется второй.
3️⃣ Рейсы с двумя пересадками — соединяем таблицу трижды (JOIN), добавляя ещё один уровень соединения (f2.destination = f3.origin).
4️⃣ Объединение всех маршрутов:
Используем UNION для объединения всех трех типов маршрутов (прямые, с одной и двумя пересадками).
5️⃣ Группируем GROUP BY origin, destination и выбираем минимальную цену MIN(total_cost). Жаль нельзя по таким ценам реально на морюшко улететь 🌊 🌊 🌊
6️⃣ Сортируем результат по городу отправления и городу назначения.
Создадим табличку с данными:
Ну и сам основной запрос:
Большое решение, но если по частям разобрать, то разобраться проще. Для этого вот вам ноутбук с этим скриптом. экспериментируйте!
Ну и всем отдыха на море в этом году!🏖 🏖🐠🌊
Нужно найти самый дешёвый путь между городами, учитывая варианты с пересадками (до двух).
📌 Дано:
Есть таблица da_flights, в которой:
✈️ origin – пункт отправления
✈️ destination – пункт назначения
✈️ cost – стоимость перелёта
Чтобы найти маршруты с пересадками, нам нужно соединить таблицу саму с собой (self-join).
🛠 Решение
Используем UNION для объединения всех трех типов маршрутов (прямые, с одной и двумя пересадками).
Создадим табличку с данными:
import pandas as pd
from pandasql import sqldf
data = {
'id': [1, 2, 3, 4, 5, 6],
'origin': ['SFO', 'SFO', 'SFO', 'DFW', 'DFW', 'JFK'],
'destination': ['JFK', 'DFW', 'MCO', 'MCO', 'JFK', 'LHR'],
'cost': [500, 200, 400, 100, 200, 1000]
}
da_flights = pd.DataFrame(data)
Ну и сам основной запрос:
query = """
SELECT
origin,
destination,
MIN(total_cost) AS min_price
FROM (
-- Прямые рейсы
SELECT origin, destination, cost AS total_cost
FROM da_flights
UNION
-- Рейсы с одной пересадкой
SELECT f1.origin, f2.destination, f1.cost + f2.cost AS total_cost
FROM da_flights f1
JOIN da_flights f2 ON f1.destination = f2.origin
UNION
-- Рейсы с двумя пересадками
SELECT f1.origin, f3.destination, f1.cost + f2.cost + f3.cost AS total_cost
FROM da_flights f1
JOIN da_flights f2 ON f1.destination = f2.origin
JOIN da_flights f3 ON f2.destination = f3.origin
) AS all_flights
GROUP BY origin, destination
ORDER BY origin, destination
"""
result = sqldf(query)
print(result)
Большое решение, но если по частям разобрать, то разобраться проще. Для этого вот вам ноутбук с этим скриптом. экспериментируйте!
Ну и всем отдыха на море в этом году!
