Lining up people based on tuples inside list

user_12091336 0
Viewed 235

A group of students need to line up for the procession of an event. We only have the information about every pair of students who are next to each other. We use a list of tuples to represent this line-up information: Each element of the list is a tuple that contains the name of a student (call him/her A) and the name of the student behind A.

For example, ("Alice", "Bob") means Bob is behind Alice. The list [("Alice", "Bob"), ("Bob", "Chris")] means Bob is behind Alice and Chris behind Bob.

For the student who's at the very end of the line-up, we use an empty string to indicate that there's nobody behind this student. E.g., ("Darren", "") means there's nobody behind Darren, i.e., Darren is at the end of the line-up.

Given a list of tuples that contains the line-up information of every pair of students who are next to each other, implement a function that returns the students in a list based on their order in the line-up.

I could only manage to get the first and the last with the code below, but I can't get the whole group in.

def get_lineup(a_list):
    lst_of_names = []
    output_lst = []
    if len(a_list) == 0:
        return []
    for i in range(len(a_list)):
        for j in range(len(a_list[i])):

            lst_of_names.append(a_list[i][j])
    for k in range(len(lst_of_names)):
        if lst_of_names.count(lst_of_names[k]) == 1 and lst_of_names[k] != "":
            output_lst.append(lst_of_names[k])



    for i in range(len(a_list)):
        if a_list[i][1] == "":
            output_lst.append(a_list[i][0])
    return output_lst

Example 1:

get_lineup([("Chris", "Darren"), ("Alice", "Bob"), ("Darren", ""), ("Bob", "Chris")]) should return ["Alice", "Bob", "Chris", "Darren"].

Example 2:

Given the following code,

info = [("Mary", "Jason"), ("John", "Alan"), ("Jason", "George"), ("Alan", "Christie"), ("Christie", "Mary"), ("George", "")]
print(get_lineup(info))

we should see the following output:

['John', 'Alan', 'Christie', 'Mary', 'Jason', 'George']
python
4 Answers

The way I would tackle this is to work backwards from the known end point of "". We know that the last student is associated with this marker.

I use a dict to allow the code to step back through the tuples:

def get_lineup(info):
    rev_info = {pair[1]:pair[0] for pair in info}
    last = rev_info['']
    rev_order = []
    while True:
        rev_order.append(last)
        if last in rev_info:
            last = rev_info[last]
        else:
            return rev_order[::-1]

info = [("Mary", "Jason"), ("John", "Alan"), ("Jason", "George"), ("Alan", "Christie"), ("Christie", "Mary"), ("George", "")]
print(get_lineup(info))

Output:

['John', 'Alan', 'Christie', 'Mary', 'Jason', 'George']
quamrana_48340

Here's a possible solution, using recursion.

The function will start filling up a list from the last person in the queue, identified by the fact that the second element of the tuple is empty.

We'll go in reverse, looking at the second element each time, and checking if it matches the first element of one of our tuples. If there's a match, the first element is added.

We start again, until there's nothing left to add, calling .reverse() on the list (NB: reverse must be called first, as it's applied on the list object and returns None. THEN return the list).

def extract_names(info, curr):
    for n1, n2 in info:
        if n2 == curr[-1]:
            curr.append(n1)
            return extract_names(info, curr)
    curr.reverse()
    return curr

The call uses two arguments:

curr = [e[0] for e in info if e[1] == ""][0] # getting the last person (George), as it's an indicator we can use
extract_names(info, [curr])

Here are some prints of the execution, if this helps:

Inside the function again
CURR ['George']
Match found for George (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason']
Match found for Jason (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary']
Match found for Mary (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie']
Match found for Christie (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie', 'Alan']
Match found for Alan (second element of tuple/last element of curr)
Recursive call
Inside the function again
CURR ['George', 'Jason', 'Mary', 'Christie', 'Alan', 'John']
user_36085910

Here is my solution:

def get_lineup(pair_list):
    currnt_person = ""
    line = []
    while True:
        try:            
            currnt_person = [i[0] for i in pair_list if i[1] == currnt_person][0]
            line.insert(0, currnt_person)
        except IndexError:
            return line
user_78314550

This version is very similar to user quamrana's answer, in that it uses a dictionary to map the pairs. It's slightly neater, in that it avoids the if statement in the while loop, but at the cost of computing the dictionary's keys and values.

In the dictionary formed from the list of tuples, the student at the head of the procession is not in the dictionary's values, because they are not behind another student. Therefore, the identity of this student can be determined by subtracting the dictionary's values from its keys.

Once the head student has being identified, the next student is the value of dictionary[head], then that student the head until the value of head is the empty string.

def list_students(students):
    result = []
    dstudents = dict(students)
    head = (dstudents.keys() - dstudents.values()).pop()
    while head:
        result.append(head)
        head = dstudents[head]
    return result

If you are using Python 3.8, the function could employ the new assignment expressions syntax

def list_students(students):
    dstudents = dict(students)
    head = (dstudents.keys() - dstudents.values()).pop()
    result = [head]
    while head := dstudents[head]: 
        result.append(head)
    return result

but I don't think this significantly improves the function either in terms of reducing complexity or increasing readability.

user_53209060
Related