Aller au contenu

E10 - Ga Bu Zo Meu⚓︎

Le problème

Ga Bu Zo Meu

Proposition 1⚓︎

🐍 Script Python
def toutes_phrases(phrase: str, longueur: int, nb_mots: int):
    """
    Affiche toutes les posibilités d'assemblage des mots de la longueur nb_mots

    >>> toutes_phrases('', 1, 2)
    Bu Bu
    Bu Ga
    Bu Meu
    Bu Zo
    Ga Bu
    Ga Ga
    Ga Meu
    Ga Zo
    Meu Bu
    Meu Ga
    Meu Meu
    Meu Zo
    Zo Bu
    Zo Ga
    Zo Meu
    Zo Zo
    """
    mots = ["Bu ", "Ga ", "Meu ", "Zo "]
    if longueur <= nb_mots:
        for mot in mots:
            nv_phrase = phrase + mot
            if len(nv_phrase.split()) == nb_mots:
                print(phrase + mot.rstrip())
            toutes_phrases(phrase + mot, longueur + 1, nb_mots)     

import doctest
doctest.testmod()

nombre_de_mot_dans_phrase = int(input())
assert nombre_de_mot_dans_phrase <= 10, "Nb entre 1 et 10 inclus requis"
toutes_phrases('',1, nombre_de_mot_dans_phrase)

  • Joli, tu as trouvé une version récursive en utilisant une phrase préfixe. BRAVO. Regarde la solution, pour une version plus propre.

  • En général, on fait diminuer longueur de 1 à chaque tour, indiquant la profondeur qu'il reste à atteindre. À zéro, on fait le cas de base. Le dernier test devient if nb_mots == 0: print(...)

  • Tu aurais pu utiliser la liste des préfixes avec une variable globale.

Corrigé du professeur⚓︎

Version itérative 1⚓︎

Les phrases correspondent aux nombres écrits en base 4, dans l'ordre.

Première version où on construit le nombre 000...000 en base 4, puis on ajoute un à chaque tour de boucle... Jusqu'à obtenir 333...333.

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/gabuzomeu
"""

MOTS = ["Bu", "Ga", "Meu", "Zo"]

def ga_bu_zo_meu(nb_mots: int) -> None:
    """Affiche, dans l'ordre alphabétique toutes les phrases de `nb_mots` mots,
    avec uniquement des `MOTS` Shadocks : "Ga", "Bu", "Zo", "Meu".

    >>> ga_bu_zo_meu(2)
    Bu Bu
    Bu Ga
    Bu Meu
    Bu Zo
    Ga Bu
    Ga Ga
    Ga Meu
    Ga Zo
    Meu Bu
    Meu Ga
    Meu Meu
    Meu Zo
    Zo Bu
    Zo Ga
    Zo Meu
    Zo Zo

    """
    chiffres = [0 for _ in range(nb_mots)]
    chiffres[-1] = -1
    for n in range(4 ** nb_mots):
        i = nb_mots - 1
        chiffres[i] += 1
        while chiffres[i] == 4:
            chiffres[i] = 0
            i -= 1
            chiffres[i] += 1
        print(" ".join(MOTS[chiffre] for chiffre in chiffres))

# Tests
import doctest
doctest.testmod()

# Entrée
nb_mots = int(input())
assert 1 <= nb_mots <= 10, f"Erreur de contrainte {nb_mots=}"

# Sortie
ga_bu_zo_meu(nb_mots)

Version itérative 2⚓︎

On prend tous les nombres, et avec leur écriture binaire, on récupère deux bits par deux bits, l'écriture en base 4.

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/gabuzomeu
"""

MOTS = ["Bu", "Ga", "Meu", "Zo"]

def ga_bu_zo_meu(nb_mots: int) -> None:
    """Affiche, dans l'ordre alphabétique toutes les phrases de `nb_mots` mots,
    avec uniquement des `MOTS` Shadocks : "Ga", "Bu", "Zo", "Meu".

    >>> ga_bu_zo_meu(2)
    Bu Bu
    Bu Ga
    Bu Meu
    Bu Zo
    Ga Bu
    Ga Ga
    Ga Meu
    Ga Zo
    Meu Bu
    Meu Ga
    Meu Meu
    Meu Zo
    Zo Bu
    Zo Ga
    Zo Meu
    Zo Zo

    """
    for i in range(4 ** nb_mots):
        n = i
        n_base_4 = []
        for _ in range(nb_mots):
            n_base_4.append(n & 0b11)  # les deux derniers bits de n
            n >>= 2
        print(" ".join(MOTS[chiffre] for chiffre in n_base_4[::-1]))

# Tests
import doctest
doctest.testmod()

# Entrée
nb_mots = int(input())
assert 1 <= nb_mots <= 10, f"Erreur de contrainte {nb_mots=}"

# Sortie
ga_bu_zo_meu(nb_mots)

Version récursive⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/gabuzomeu
"""

MOTS = ["Bu", "Ga", "Meu", "Zo"]

prefixes = []

def ga_bu_zo_meu(nb_mots: int) -> None:
    """Affiche, dans l'ordre alphabétique toutes les phrases de `nb_mots` mots,
    avec uniquement des `MOTS` Shadocks : "Ga", "Bu", "Zo", "Meu".

    >>> ga_bu_zo_meu(2)
    Bu Bu
    Bu Ga
    Bu Meu
    Bu Zo
    Ga Bu
    Ga Ga
    Ga Meu
    Ga Zo
    Meu Bu
    Meu Ga
    Meu Meu
    Meu Zo
    Zo Bu
    Zo Ga
    Zo Meu
    Zo Zo

    """
    if nb_mots == 0:
        print(" ".join(prefixes))
    else:
        for mot in MOTS:
            prefixes.append(mot)
            ga_bu_zo_meu(nb_mots - 1)
            prefixes.pop()

# Tests
import doctest
doctest.testmod()

# Entrée
nb_mots = int(input())
assert 1 <= nb_mots <= 10, f"Erreur de contrainte {nb_mots=}"

# Sortie
ga_bu_zo_meu(nb_mots)