Message passing game algorithm in Python

August 14, 2023

I got the following Python assessment:

There are N people, numbered from 0 to N-1, playing a game. The K^th person is assigned the letter S[K]. At the beginning the 0^th person sends a message, consisting of a single letter S[0], to the A[0]^th person. When the K^th person receives the message, they append their letter S[K] to the message and forward it to A[K]. The game ends when the 0^th person receives the message. Find the final message.

You can assume that A contains every integer from 0 to N-1 exactly once.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.
Visit Medevel

Write a function:
class solution (public string solution(string 5, int[] A); }
that given a string S and an array of integers A, both of length N, returns a string denoting the final message received by the O^th person.

Examples:

Given S = "cdeo" and A = [3, 2, 0, 1], your function should return "code".

At the beginning, the 0^th person sends a message "c" to the 3^rd person. Next, the 3^rd person forwards the message "co" to the 1^st person. After that the 1st person forwards the message "cod" to the 2^nd person. After appending the letter ‘e’ to it, the 2^nd person forward it to the O^th person. The final message, received by O^th person, is ‘code’,

Given S = "cdeenetpi" and A = [5, 2, 0, 1, 6, 4, 8, 3, 7], your function should return "centipede".

Given S = "bytdag" and A = [4, 3, 0, 1, 2, 5], your function should return "bat".

Notice that not all letters from S have to be used.

Assume that:

N is an integer within the range [1..1,000);

string S is made only of lowercase letters (a-z);

A contains all integers within range [0..N-1);

S and A are both of length N

I have tried the Python code for this.

def solution(S, A):
    message = ""
    current_person = 0
    for i in range(len(S)):
        if current_person < len(S):
            message += S[current_person]
            current_person = A[current_person]

    while current_person != 0:
        if current_person < len(S):
            message += S[current_person]
            current_person = A[current_person]
    return message    

    
      
print(solution("cdeo", [3, 2, 0, 1]))
print(solution("cdeenetpi", [5, 2, 0, 1, 6, 4, 8, 3, 7]))
print(solution("bytdag", [4, 3, 0, 1, 2, 5]))

for solution("cdeo", [3, 2, 0, 1]) –> I got "code" as output as expected
for solution("cdeenetpi", [5, 2, 0, 1, 6, 4, 8, 3, 7]) –> I got "centipede" as output as expected.
but for solution("bytdag", [4, 3, 0, 1, 2, 5]) –> I am getting "batbat", but it should return only "bat". Any help on how to achieve this?

>Solution :

There shouldn’t be a need for two loops. Only keep the second one, but with one change: it shouldn’t start with the check whether current_person is zero, but do that check only after at least one iteration was executed.
I would exclude the if condition, since it is specified by the code challenge that these values are never out of range.

So:

def solution(S, A):
    message = ""
    current_person = 0
    while True:
        message += S[current_person]
        current_person = A[current_person]
        if current_person == 0:  # At least one iteration was performed
            return message