Google Kickstart 2014 Round D Sort a scrambled itinerary – Do I need to bring the input in a ready-to-use array format?

Problem:

Once upon a day, Mary bought a one-way ticket from somewhere to somewhere with some flight transfers.

For example: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.

Obviously, transfer flights at a city twice or more doesn’t make any sense. So Mary will not do that.

Unfortunately, after she received the tickets, she messed up the tickets and she forgot the order of the ticket.

Help Mary rearrange the tickets to make the tickets in correct order.

Input:

The first line contains the number of test cases T, after which T cases follow.

For each case, it starts with an integer N. There are N flight tickets follow.

Each of the next 2 lines contains the source and destination of a flight ticket.

Output:

For each test case, output one line containing "Case #x: itinerary", where x is the test case number (starting from 1) and the itinerary is a sorted list of flight tickets that represent the actual itinerary.

Each flight segment in the itinerary should be outputted as pair of source-destination airport codes.

Sample Input:             Sample Output:

2                         Case #1: SFO-DFW
1                         Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

My question:

I am a beginner in the field of competitive programming. My question is how to interpret the given input in this case. How did Googlers program this input? When I write a function with a Python array as its argument, will this argument be in a ready-to-use array format or will I need to deal with the above mentioned T and N numbers in the input and then arrange airport strings in an array format to make it ready to be passed in the function’s argument?

I have looked up at the following Google Kickstart’s official Python solution to this problem and was confused how they simply pass the ticket_list argument in the function. Don’t they need to clear the input from the numbers T and N and then arrange the airport strings into an array, as I have explained above?

Also, I could not understand how could the methods first and second simply appear if no Class has been initialized? But I think this should be another question…

def print_itinerary(ticket_list):
    arrival_map = {}
    destination_map = {}
    for ticket in ticket_list:
        arrival_map[ticket.second] += 1
        destination_map[ticket.first] += 1
    current = FindStart(arrival_map)
    while current in destination_map:
        next = destination_map[current]
        print current + "-" + next
        current = next 

Answer

You need to implement it yourself to read data from standard input and write results to standard output.

Sample code for reading from standard input and writing to standard output can be found in the coding section of the FAQ on the KickStart Web site.

If you write the solution to this problem in python, you can get T and N as follows.

T = int(input())
for t in range(1, T + 1):
    N = int(input())
    ...

Then if you want to get the source and destination of the flight ticket as a list, you can use the same input method to get them in the list.

ticket_list = [[input(), input()] for _ in range(N)]
# [['MIA', 'ORD'], ['DFW', 'JFK'], ['SFO', 'DFW'], ['JFK', 'MIA']]

If you want to use first and second, try a namedtuple.

Pair = namedtuple('Pair', ['first', 'second'])
ticket_list = [Pair(input(), input()) for _ in range(N)]