Suite de Conway

Version imprimable

30/03/2019, 12h10
FATENMRABET

Suite de Conway

salut:
j'ai l'énoncé suivant:
Enoncé
Voici le début d'une suite logique inventée par John Horton Conway (et donc appelée suite de Conway) :
1
11
21
1211
111221
312211
...
Chaque ligne à partir de la deuxième décrit la précédente...
La première ligne : 1,
on l'a décrit "Un 1" ce qui donne la deuxième : 11,
la troisième décrit la deuxième : "Deux 1" : 21
la quatrième décrit la troième : "Un 2 suivi de Un 1" : 1211
et ainsi de suite.
On vous demande d'écrire une fonction next_line(line) qui prend une liste d'entiers décrivant une ligne de cette suite et qui calcule et retourne la liste correspondant à la ligne suivante. Par exemple :
next_line([1,2,1,1])

Par convention, next_line([]) retourne la liste [1]

Salut,

C'est simplement un peu de logique.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
def next_line(numbers):
    count = 0
    val = numbers[0]
    res = ""
    for n in numbers:
        if n == val:
            count += 1
        else:
            res += "%s%s" %(count, val)
            count = ?
            val = ?
 
    res += "%s%s" %(count, val)
    return res
 
s = "1"
print(s)
for i in range(15):
    s = next_line(s)
    print(s)

pour ne pas te le donner tout mâché j'ai laissé deux points d'interrogation dans le code tu devrais trouver par quoi les remplacer.

pour les chaine de caractère c'est ça je pense : mais j'ai besoin de ça pour les listes

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def next_line(numbers):
    count = 0
    val = numbers[0]
    res = ""
    for n in numbers:
        if n == val:
            count += 1
        else:
            res += "%s%s" % (count, val)
            count = val
            val = n
 
            res += "%s%s" % (count, val)
            return res

salut,
voilà la proposition pour les chaine de caractère valide:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def next_line(numbers):
    count = 0
    val = numbers[0]
    res = ""
    for n in numbers:
        if n == val:
            count += 1
        else:
            res += "%s%s" %(count, val)
            count = 1
            val = n
 
    res += "%s%s" %(count, val)
    return res
 
s = "1"
print(s)
for i in range(15):
    s = next_line(s)
    print(s)

la solution proposé avec des listes mais avec erreur index outofrange index

salut,
pour les listes j'ai proposé ça:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def next_line(numbers): count = 0 val = numbers[0] res = [] for n in numbers: if n == val: count += 1 else: res.append(count) res.append(val) val = n count = 1 res.append(count) res.append(val) return res
les résultats sont valide pour:
ok Bon résultat pour next_line([1]) : [1, 1]
ok Bon résultat pour next_line([1, 1]) : [2, 1]
ok Bon résultat pour next_line([2, 1]) : [1, 2, 1, 1]
ok Bon résultat pour next_line([1, 2, 1, 1]) : [1, 1, 1, 2, 2, 1]
ok Bon résultat pour next_line([1, 1, 1, 2, 2, 1]) : [3, 1, 2, 2, 1, 1]
ok Bon résultat pour next_line([3, 1, 1, 4, 2, 3]) : [1, 3, 2, 1, 1, 4, 1, 2, 1, 3]
ok Bon résultat pour next_line([6, 6, 6, 6, 6, 6]) : [6, 6]
ok Bon résultat pour next_line([1, 3, 1, 1, 1, 3]) : [1, 1, 1, 3, 3, 1, 1, 3]
ok Bon résultat pour next_line([1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1]) : [6, 1, 7, 2, 3, 1]

mais il ya un seul erreur :
Votre programme a été interrompu par une exception: IndexError: list index out of range

30/03/2019, 16h05
FATENMRABET

salut,
alors l'erreur est dû à ce que je dois traiter ça :
Par convention, next_line([]) retourne la liste [1]
30/03/2019, 17h32
Sve@r

Bonjour

Citation:

Envoyé par FATENMRABET

ok Bon résultat pour next_line([3, 1, 1, 4, 2, 3])

Oui mais la suite de Conway ne peut pas avoir de valeur supérieure ou égale à 4.
C'est logique. Si la suite contient (par exemple) "4 1", ça veut dire que la ligne précédente contient "1 1 1 1" (quatre "1"). Mais cette ligne (qui décrit la ligne encore avant) signifie que encore un cran plus haut il y a un "1" suivi de un "1" autrement dit "1 1" . Mais cette ligne sera alors décrite par "2 1" et non "1 1 1 1". Donc jamais de 4.
De la même façon, il n'y aura jamais "3 3".

Citation:

Envoyé par FATENMRABET

mais il ya un seul erreur :
Votre programme a été interrompu par une exception: IndexError: list index out of range

Oui. C'est ici val = numbers[0]. Si "numbers" est vide, alors cet indice n'existe pas.

Citation:

Envoyé par FATENMRABET

Par convention, next_line([]) retourne la liste [1]

Ben cas particulier à tester au tout début de ta fonction.
Par ailleurs, tu peux supprimer tes deux dernières modifications de "res" (juste avant le return) si tu réécris l'itération ainsi: for n in tuple(numbers) + tuple((None,)). En rajoutant une valeur "neutre" l'itération se fait une fois de plus ce qui permet de finir de remplir "res". Que tu peux d'ailleurs remplir d'un coup de cette façon: res.extend((count, val)).

Citation:

Envoyé par FATENMRABET

pour les chaine de caractère c'est ça je pense : mais j'ai besoin de ça pour les listes

Plutôt que de faire deux fonctions, checke le paramètre entré. Si c'est une liste tu le convertis en chaine puis tu appliques l'algo des chaines (ou alors tu fais le contraire si c'est une chaine tu le convertis en liste et tu appliques l'algo pour les listes)...

salut,
pour cette énoncé il traite seulement le principe de "suite de Conway" sans des restriction sur les 3 , 4,...
donc la solution finale est:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def next_line(numbers):
    if numbers==[] :
        res=[1]
    else:
        count = 0
        res = []
        val = numbers[0]
        for n in numbers:
            if n == val:
                count += 1
 
            else:
                res.extend([count, val])
                val = n
                count = 1
        res.extend([count,val])
    return res

merci pour vos remarques

30/03/2019, 19h15
wiztricks

Citation:

Envoyé par FATENMRABET

pour cette énoncé il traite seulement le principe de "suite de Conway" sans des restriction sur les 3 , 4,...

Si les "restrictions" sont des conséquences de l'algo. çà veut dire que votre code doit être revu et corrigé.

- W
30/03/2019, 20h14
VinsS

Tu te casses la tête pour rien, ta deuxième solution (le post #4) est la bonne.

Que ce soit pour une chaîne "112112" ou une liste [1, 1, 2, 1, 1,2] le code fonctionne identiquement.

Citation:

Envoyé par FATENMRABET

donc la solution finale est:

Il n'y a jamais qu'une seule solution !!!
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def next_line(numbers): if not numbers: return [1,] res = [] (val, count) = (numbers[0], 0) for n in tuple(numbers) + tuple((None,)): if n == val: count += 1 continue # if res.extend((count, val)) (val, count) = (n, 1) # for return res # next_line()
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def next_line(numbers): if not numbers: return [1,] res = [] i=0 numbers.append(None) while True: for j in range(i, len(numbers)): if numbers[i] != numbers[j]: break res.extend((j-i, numbers[i])) if j == len(numbers)-1: break i=j # while return res # next_line()
Citation:

Envoyé par VinsS

Que ce soit pour une chaîne "112112" ou une liste [1, 1, 2, 1, 1,2] le code fonctionne identiquement.

Ben pas tout à fait (par rapport à ce qu'il avait fait avant). Car dans la fonction qui reçoit une chaine il retourne une chaine, et la fonction qui traite une liste retourne une liste. Alors voulu/pas voulu...
Ceci dit t'as raison. Il se casse la tête pour pas grand chose. A la limite, on remplace le return res par return "".join(res) if isinstance(numbers, str) else res et c'est réglé ;)

30/03/2019, 20h46
VinsS

Citation:

Envoyé par Sve@r

Ben pas tout à fait (par rapport à ce qu'il avait fait avant). Car dans la fonction qui reçoit une chaine il retourne une chaine, et la fonction qui traite une liste retourne une liste. Alors voulu/pas voulu...
Ceci dit t'as raison. Il se casse la tête pour pas grand chose. A la limite, on remplace le return res par return "".join(res) if isinstance(numbers, str) else res et c'est réglé ;)

Ben non, mon code fonctionne indifféremment avec les chaînes et les listes en affichant le résultat sous forme d'une chaîne.
Si l'on préfère ne traiter que les listes il faut déplacer la mise en forme au niveau du print, mais à ce moment là on a un code qui ne fonctionne que avec les listes et plus avec les chaînes.
Le mien fonctionne avec les deux.
30/03/2019, 21h11
Sve@r

Citation:

Envoyé par VinsS

Ben non, mon code fonctionne indifféremment avec les chaînes et les listes en affichant le résultat sous forme d'une chaîne.

Ouais, t'as raison, j'avais mal lu. je pensais que le PO voulait une fonction recevant une chaine et retournant une chaine, et une autre recevant une liste et retournant une liste.
Désolé :chin: