Suite de Conway

**FATENMRABET** · 30/03/2019, 13h10

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]

**VinsS** · 30/03/2019, 15h15

Salut,

C'est simplement un peu de logique.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**FATENMRABET** · 30/03/2019, 16h08

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**FATENMRABET** · 30/03/2019, 16h54

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

**FATENMRABET** · 30/03/2019, 16h57

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**FATENMRABET** · 30/03/2019, 17h05

salut,
alors l'erreur est dû à ce que je dois traiter ça :
Par convention, next_line([]) retourne la liste [1]

**Sve@r** · 30/03/2019, 18h32

Bonjour

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".

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.

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)).

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)...

**FATENMRABET** · 30/03/2019, 19h23

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**wiztricks** · 30/03/2019, 20h15

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

**VinsS** · 30/03/2019, 21h14

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.

**Sve@r** · 30/03/2019, 21h29

Envoyé par FATENMRABET

donc la solution finale est:

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

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

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 python :

Sélectionner tout - Visualiser dans une fenêtre à part

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()

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é

**VinsS** · 30/03/2019, 21h46

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.

**Sve@r** · 30/03/2019, 22h11

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é

Suite de Conway

Python

Discussions similaires

Partager

Partager