[Programmers] Catena di parole in inglese

https://programmers.co.kr/learn/courses/30/lessons/12981

Soluzione

Tra i vincoli del problema c’è il seguente:

words è un array contenente le parole usate nel gioco a catena, in ordine.

Da qui si capisce che estraendo gli elementi da words in ordine si può riprodurre il gioco.

Questo porta al seguente algoritmo:

1. Scorrere words in ordine, verificando se la catena continua.
2. Se la catena si interrompe, calcolare la risposta.

Dato che basta scorrere words in ordine per simulare il gioco, la risposta si ricava dall’indice $i$ e dal numero di giocatori $n$:

• Di quale giocatore è il turno:
  • $i \mod n$
  • Si aggiunge +1 perché si conta a partire da 1
• A quale giro si è:
  • $[ i \div n ]$
  • Si aggiunge +1 perché il primo giro conta come 1

Quoziente e resto si possono calcolare come sopra, oppure usando la funzione built-in divmod di Python:

1
q, r = divmod(a, b)

Codice

1
def solution(n, words):
2
    answer = [0,0]
3
    stack = [words[0]]
4
    for i in range(1, len(words)):
5
        # Se l'ultimo carattere della parola in cima allo stack coincide con il primo carattere della parola i-esima
6
        # e la parola i-esima non è già nello stack
7
        if stack[-1][-1] == words[i][0] \
8
            and words[i] not in stack:
9
            stack.append(words[i])
10
        # Se non si può aggiungere allo stack, aggiornare la risposta
11
        else:
12
            answer[0] = (i % n) + 1
13
            answer[1] = i // n + 1
14
            break
15
    return answer