Skip to content

Instantly share code, notes, and snippets.

@messa

messa/kiwi_solution.py

Last active January 21, 2017 19:41
Show Gist options
  • Save messa/17756a6d0427b07e1d3629dfa88219fb to your computer and use it in GitHub Desktop.
Save messa/17756a6d0427b07e1d3629dfa88219fb to your computer and use it in GitHub Desktop.
Download ZIP
Raw
kiwi_solution.py
#!/usr/bin/env python3
from collections import defaultdict, namedtuple
from datetime import datetime, timedelta
import csv
import sys
def main():
flights = load_flights()
flights_by_src = defaultdict(list)
for f in flights:
flights_by_src[f.src_airport].append(f)
for fs in flights_by_src.values():
fs.sort(key=lambda f: f.src_dt)
q = [[f] for f in flights]
height = 1
while True:
height += 1
pr('Height: {}', height)
next_q = []
for itinerary in q:
last_flight = itinerary[-1]
# find what flights can we use to continue from last flight
available_flights = flights_by_src[last_flight.dst_airport]
possible_flights = filter_flights_by_time(available_flights, last_flight.dst_dt)
for possible_flight in possible_flights:
# check if segment would be repeating (A->B->A->B)
segment_would_be_repeating = any(
(it_flight.src_airport == possible_flight.src_airport and
it_flight.dst_airport == possible_flight.dst_airport)
for it_flight in itinerary)
if segment_would_be_repeating:
continue
# create new itinerary from this one + this flight
next_q.append(itinerary + [possible_flight])
if not next_q:
break
for itinerary in next_q:
print_itinerary(itinerary)
q = next_q
def print_itinerary(flights):
parts = []
for flight in flights:
if parts:
parts.append('::')
parts.extend([
flight.src_airport,
flight.src_dt,
flight.dst_airport,
flight.dst_dt,
flight.flight_number])
print(' '.join(str(p) for p in parts))
def filter_flights_by_time(flights, dt):
dt_lb = dt + timedelta(hours=1)
dt_ub = dt + timedelta(hours=4)
# we could use bisect module if it had key parameter like sort has...
lo = 0
hi = len(flights)
while lo < hi:
mid = (lo+hi) // 2
if flights[mid].src_dt < dt_lb:
lo = mid + 1
else:
hi = mid
possible_flights = []
while lo < len(flights) and flights[lo].src_dt <= dt_ub:
assert flights[lo].src_dt >= dt_lb
possible_flights.append(flights[lo])
lo += 1
return possible_flights
def pr(_s, *args, **kwargs):
if args or kwargs:
_s = _s.format(*args, **kwargs)
print(_s, file=sys.stderr)
Flight = namedtuple('Flight', 'src_airport src_dt dst_airport dst_dt flight_number')
def load_flights():
flights = []
reader = csv.DictReader(sys.stdin)
for row in reader:
flights.append(Flight(
src_airport=row['source'],
src_dt=parse_dt(row['departure']),
dst_airport=row['destination'],
dst_dt=parse_dt(row['arrival']),
flight_number=row['flight_number']))
return flights
def parse_dt(s):
return datetime.strptime(s, '%Y-%m-%dT%H:%M:%S')
if __name__ == '__main__':
main()
Raw
output.txt
Height: 2
USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967
USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:40:00 USM 2016-10-11 14:35:00 PV540
USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444
USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476 :: HKT 2016-10-11 22:05:00 USM 2016-10-11 23:00:00 PV551
USM 2016-10-11 19:45:00 HKT 2016-10-11 20:45:00 PV310 :: HKT 2016-10-11 22:05:00 USM 2016-10-11 23:00:00 PV551
USM 2016-10-11 10:30:00 HKT 2016-10-11 11:30:00 PV913 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967
USM 2016-10-11 10:30:00 HKT 2016-10-11 11:30:00 PV913 :: HKT 2016-10-11 13:40:00 USM 2016-10-11 14:35:00 PV540
USM 2016-10-11 10:30:00 HKT 2016-10-11 11:30:00 PV913 :: HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444
USM 2016-10-11 11:45:00 HKT 2016-10-11 12:45:00 PV260 :: HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444
USM 2016-10-11 11:45:00 HKT 2016-10-11 12:45:00 PV260 :: HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493
USM 2016-10-11 13:00:00 HKT 2016-10-11 14:00:00 PV719 :: HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493
HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493 :: USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476
HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493 :: USM 2016-10-11 19:45:00 HKT 2016-10-11 20:45:00 PV310
HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870 :: USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511
HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
HKT 2016-10-11 10:00:00 USM 2016-10-11 10:55:00 PV320 :: USM 2016-10-11 13:00:00 HKT 2016-10-11 14:00:00 PV719
HKT 2016-10-11 10:00:00 USM 2016-10-11 10:55:00 PV320 :: USM 2016-10-11 14:10:00 HKT 2016-10-11 15:10:00 PV909
HKT 2016-10-11 13:40:00 USM 2016-10-11 14:35:00 PV540 :: USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476
HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444 :: USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476
BWN 2016-10-11 14:35:00 DPS 2016-10-11 16:55:00 PV477 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
BWN 2016-10-11 16:15:00 DPS 2016-10-11 18:35:00 PV811 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
DPS 2016-10-11 05:40:00 BWN 2016-10-11 08:05:00 PV332 :: BWN 2016-10-11 10:35:00 DPS 2016-10-11 12:55:00 PV996
DPS 2016-10-11 13:50:00 BWN 2016-10-11 16:15:00 PV534 :: BWN 2016-10-11 18:45:00 DPS 2016-10-11 21:05:00 PV923
DPS 2016-10-11 13:50:00 BWN 2016-10-11 16:15:00 PV534 :: BWN 2016-10-11 19:00:00 DPS 2016-10-11 21:20:00 PV612
DPS 2016-10-11 00:30:00 HKT 2016-10-11 04:10:00 PV606 :: HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870
DPS 2016-10-11 09:20:00 HKT 2016-10-11 13:00:00 PV980 :: HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444
DPS 2016-10-11 09:20:00 HKT 2016-10-11 13:00:00 PV980 :: HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493
Height: 3
USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
USM 2016-10-11 10:30:00 HKT 2016-10-11 11:30:00 PV913 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870 :: USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967
DPS 2016-10-11 00:30:00 HKT 2016-10-11 04:10:00 PV606 :: HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870 :: USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511
DPS 2016-10-11 09:20:00 HKT 2016-10-11 13:00:00 PV980 :: HKT 2016-10-11 14:30:00 USM 2016-10-11 15:25:00 PV444 :: USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476
DPS 2016-10-11 09:20:00 HKT 2016-10-11 13:00:00 PV980 :: HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493 :: USM 2016-10-11 18:15:00 HKT 2016-10-11 19:15:00 PV476
DPS 2016-10-11 09:20:00 HKT 2016-10-11 13:00:00 PV980 :: HKT 2016-10-11 16:00:00 USM 2016-10-11 16:55:00 PV493 :: USM 2016-10-11 19:45:00 HKT 2016-10-11 20:45:00 PV310
Height: 4
HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870 :: USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967 :: DPS 2016-10-11 20:10:00 HKT 2016-10-11 23:50:00 PV731
DPS 2016-10-11 00:30:00 HKT 2016-10-11 04:10:00 PV606 :: HKT 2016-10-11 05:15:00 USM 2016-10-11 06:10:00 PV870 :: USM 2016-10-11 10:10:00 HKT 2016-10-11 11:10:00 PV511 :: HKT 2016-10-11 13:10:00 DPS 2016-10-11 16:50:00 PV967
Height: 5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment