Python Project

Aegean Tour
You have a company that takes tourists on island tours on the Aegean Ocean (see Mykonos,
Santorini, Tinos etc.). Your customers are tour operators selling the tours to travelers.
The assignment
Write a computer program that prepares one island tour itinerary. The itinerary includes H + 1 islands
to visit and thus H hops between islands. It also includes the decision whether an island hop is airborne
or by sea for each hop between two consecutive islands. The means of transport to the first island and
from the last island onwards is not included in the itinerary.
Although airplanes and helicopters are faster than ships or boats, they're also more expensive to
operate and generate more emissions, so you and your customers aim to minimize airborne hops.
Satisfying your customers
You have prepared an initial sequence of islands to visit and sent this to your customers. (This initial
sequence is out of scope for this assignment.) Your customers respond with a list of preferred island
hops and the means of transport for those hops. Each customer is satisfied if the final itinerary includes
at least one island hop from their list with a matching means of transport. There is at most one airborne
hop on each customer's list. If a customer indicates that they only want an airborne hop between two
specific islands, they are not satisfied with traveling that leg by sea, and vice versa.
Specification
To formulate the above more precisely, prepare the final itinerary as follows:
1. There are exactly H island hops
2. Each hop between consecutive islands is either airborne or by sea
3. Each customer gets at least one hop with a matching means of transport (airborne or by sea)
from their preferred list
4. The final itinerary has the minimum number of airborne hops
5. It may be impossible to satisfy all your customers and your program must detect this
6. There are at most 250 customers



Program input
Your program must read input from a text file or stdin. The input has the following lines:
• First line: integer H, the number of island hops
• Second line: integer C, the number of customers
• Consecutive lines: one line per customer
o Each line has a list of pairs h t, where h is the number of the island hop, and t is the
specified means of transport for that hop: either airborne or by sea
o Each pair will occur at most once for a single customer
o Each customer wants to specify at least one hop
o Each customer wants airborne transport on at most one hop
o The h and the t are separated by a single space, the pairs are separated by a comma and
a space (,)

The input does not contain special characters or malicious tricks.
Program output
Your program must print to stdout. The output must be NO ITINERARY if the customers' requirements
cannot be met. Otherwise, the output must be the final itinerary: H pairs of number of hops h,
followed by t which is either airborne or by-sea. The syntax is similar to the input, that is, h and t have
a single space in-between, and the pairs are separated by a comma and a space (, ).
Examples
1.
Input 6
4
0 by-sea, 2 by-sea, 3 by-sea
0 by-sea, 5 airborne
0 airborne, 5 by-sea
2 airborne

Output 0 by-sea, 1 by-sea, 2 airborne, 3 by-sea, 4 by-sea, 5 by-sea


Transporting by sea for hop 0 satisfies the first two customers, by-sea for hop 5 satisfies the third
one, and one airborne leg is required, on hop 2, to satisfy the last customer.
2.
Input 2
3
0 by-sea
0 airborne
1 by-sea
Output NO ITINERARY

The first and the second customer only want to specify hop 0 but with opposite
requirements. You cannot satisfy both.