[exercice] La suite de Conway

import time
def conway(nbr=25):
    n = "1"
    for i in range(nbr):
        n=n.replace('111','ca').replace('222','cb').replace('11','ba').replace('22','bb').replace('33','bc').replace('1','aa').replace('2','ab').replace('3','ac').replace('aaa','111').replace('bbb','222').replace('ccc','333').replace('aa','11').replace('bb','22').replace('cc','33').replace('a','1').replace('b','2').replace('c','3')
#cette mocheté a pour but de changer les "111" en "31" (et autres), en mettant des lettres ;
#les lettres seront ensuite regroupées pour donner des chiffres.

        yield n #c'est un générateur qui calculera les valeurs au fur et à mesure, c'est plus pratique à mon goût

suite = conway(50)

for i in suite:
    pass #pour éviter d'afficher les résultats ; ils seront néanmoins calculés

print(time.clock()) #prend 1,21 seconde en temps cpu chez moi, pour calculer les 50 premières occurences de la suite

def ligne_suivante(ligne):
    suivante = []
    chiffre_actuel = ligne[0]
    compteur = 0
    for chiffre in ligne:
        if chiffre == chiffre_actuel:
            compteur += 1
        else:
            suivante.append(str(compteur))
            suivante.append(chiffre_actuel)
            chiffre_actuel = chiffre
            compteur = 1
    suivante.append(str(compteur))
    suivante.append(chiffre_actuel)
    return "".join(suivante)


def conway(n):
    "Iterateur sur les n premiers termes de la suite"
    ligne = "1"
    for i in xrange(n):
        yield ligne
        ligne = ligne_suivante(ligne)
        
n=10
for i,z in enumerate(conway(n)):
    if i==n-1:
        print (z)

def A005150(n):
    p = "1"
    seq = [1]
    while (n > 1):
        q = ''
        idx = 0 # Index
        l = len(p) # Length
        while idx < l:
            start = idx
            idx = idx + 1
            while idx < l and p[idx] == p[start]:
                idx = idx + 1
            q = q + str(idx-start) + p[start]
        n, p = n - 1, q
        seq.append(int(p))
    return seq[-1]

print A005150(10)

def A005150(n):
    seq = [1] + [None] * (n - 1) # allocate entire array space
    def say(s):
        acc = '' # initialize accumulator
        while len(s) > 0:
            i = 0
            c = s[0] # char of first run
            while (i < len(s) and s[i] == c): # scan first digit run
                i += 1
            acc += str(i) + c # append description of first run
            if i == len(s):
                break # done
            else:
                s = s[i:] # trim leading run of digits
        return acc
    for i in xrange(1, n):
        seq[i] = int(say(str(seq[i-1])))
    return seq[-1] 

print A005150(45)

from time import clock
import sys

def conway(n):
    line = [1]
    for i in xrange(0,n-1):
        newline = []
        j = 0
        while j < len(line):
            k = 0
            while j+k < len(line) and line[j+k] == line[j]:
                    k += 1
            newline += [k] + [line[j]]
            j += k
        line = newline
    return str().join([str(x) for x in line])

start = clock()
line = conway(int(sys.argv[1]))
stop = clock()
print line
print >> sys.stderr, 'Execution time :', stop-start, 's'

from time import clock

def convert(a):
	c = a[0]
	cmp = 0
	res = ''
	for i in a:
		if i == c:
			cmp += 1
		else:
			res += str(cmp)
			res += c
			cmp = 1
			c = i
	res += str(cmp)
	res += c
	return res

def conway(n):
	res = ['1']
	for i in range(n):
		res.append(convert(res[i]))
	return res

debut = clock()
resultat = conway(50)
fin = clock()
print('Temps :',fin-debut)

#!/usr/bin/python
# -*- coding: utf-8 -*-

# SuiteConvey.py

"""
Ce programme génére la suite de Convey par itérations.
On commence le programme à l'itération n=1
"""

## A FAIRE : Créer une fonction qui compare le résultat à celui présent dans 1 fichier "étalon"

## Imports
import sys
from itertools import groupby

## Fonctions utilitaires
def iter_convey(boucle_iter1):
    """
    itération de la suite de Convey :
    Prend le paramétre d'entrée boucle_iter1 (itération n) et renvoie iter 2 l'itération n+1
    """
    if boucle_iter1 == '0': # Si n = 0:
        iter2 = '1' # Valeur pour n = 1
    else: # Si n > 0:
        iter1 = list(boucle_iter1) # On transforme boucle_iter1 en une liste de ses propres chiffres
        # On en tire chaque groupe de chiffres répétés grace à groupby
        # Puis On ajoute à iter2 : 1) le nombre de fois où le chiffre est répété et 2) le chiffre
        iter2 = ''.join([str(len(list(groupe))) + chiffre for chiffre, groupe in groupby(iter1)])
    return iter2 # Et on renvoie iter2

def test_option_entier(test_str, test_max , test_min = 0):
    """
    Teste si la valeur test_str (string) est bien un entier compris entre les limites test_min (par défaut 0) et test_max
    On retourne la valeur True si c'est le cas et False sinon
    """
    result = True
    try : # on vérifie que la valeur saisie est un entier
        if int(test_str) not in range(test_min, test_max + 1): # Si la saisie n'est pas comprise dans la liste proposée: MAJ du résultat
            result = False
    except : # si erreur, MAJ du résultat
        result = False
    return result


## Corps du programme

# Définition des variables
nmax = 0 # nombre d'itérations à effectuer à partir de la valeur 1 incluse. Si nmax = 0 alors le programme ne fera pas d'itération
n = 0 # compteur d'itérations effectuées (initialisé à 0)
main_iter1 = '0' # valeur de la suite à l'itération n (initialisé à '0' pour n = 0)
consencode = sys.stdout.encoding # Encodage des sorties texte basé sur la console
options = [u"Afficher la valeur de la suite pour l'itération n", u"Afficher toutes les valeurs pour les itérations de 1 à n",\
           u"Sauver toutes les valeurs pour les itérations de 1 à n", u"Charger un fichier de résultat", u"Quitter"]

# Demande des options de l'utilisateur
essais = 10 # nombre d'essais auxquels l'utilisateur a droit pour saisir les options
while essais > 0: # si il reste des essais possibles:
    essais = essais - 1 # MAJ essais restants
    print u'\nQue voulez-vous faire ?'.encode(consencode, 'replace')
    for index, option in enumerate(options):
        print (u'%s : %s' % (unicode(index + 1), option)).encode(consencode, 'replace')
    saisie = raw_input(u'Choix + [Entrée]: '.encode(consencode, 'replace'))
    if test_option_entier(test_str = saisie, test_max = len(options), test_min = 1) == False: #si saisie incorrecte :
        print u'Saisie incorrecte, rentrez un entier compris dans les valeurs proposées!'.encode(consencode, 'replace')
        continue
    else: # Si la saisie est correcte :
        saisie = int(saisie)
        if saisie == 5 : # Si dernière option (=quitter) : sortie de boucle et quitter
            print u'Sortie du programme'.encode(consencode, 'replace')
            break
        elif saisie < 4: # Sinon :
            # gestion du nombre d'itérations (pour les options 1, 2 et 3)
            essais = 10
            saisie1 = raw_input(u"\nChoix du nombre d'itérations (entre 1 et 100) + [Entrée]: ".encode(consencode, 'replace'))
            if test_option_entier(test_str = saisie1, test_max = 100, test_min = 1) == False: #si saisie incorrecte :
                print u'Saisie incorrecte, rentrez un entier compris dans les valeurs proposées!'.encode(consencode, 'replace')
                continue
            else: # Si la saisie est correcte :
                nmax = int(saisie1)
        # Confirmation chargement /  sauvegarde (pour les options 3 et 4)
        if saisie == 3:
            saisie1 = raw_input(u"\nLes résultats seront sauvegardés dans le fichier 'ConvResult.txt' dans le dossier du présent programme\nConfirmez (o) ou annulez (n'importe-quelle autre touche) :".encode(consencode, 'replace'))
            if saisie1 != 'o': #si annulation :
                continue
            else: # Si confirmation :
                break
        elif saisie == 4:
            saisie1 = raw_input(u"\nLe fichier 'ConvResult.txt' sera chargé dans le dossier du présent programme\nConfirmez (o) ou annulez (n'importe-quelle autre touche) :".encode(consencode, 'replace'))
            if saisie1 != 'o':
                continue
            else:
                break
        else:
            break
            
# Gestion de la sortie de boucle d'options
if essais == 0: # Si sortie et nombre d'essais dépassé :
    print u"\nNombre d'essais dépassé, sortie du programme".encode(consencode, 'replace')
elif saisie < 4: # Si sortie et itérations demandées (options 1 à 3):
    print (u"\nIterons %s fois:" % nmax).encode(consencode, 'replace')
    fichier_sauv = (open('ConvResult.txt', 'w') if saisie == 3 else None) # Ouverture du fichier si option 3
    try: # Essai d'itération + affichage et sauvegarde des résultats
        for n in range(nmax): # Boucle d'itérations
            main_iter1 = iter_convey(boucle_iter1 = main_iter1) # Itération à n+1
            if saisie == 2 or (saisie == 1 and n == nmax - 1): # Si l'option 2 ou fin de boucle et option 1: on affiche le résultat à n+1
                print "%s %s" % (n + 1, main_iter1)
            elif saisie == 3: # Si option 3 : sauvegarde du résultat n+1
                fichier_sauv.write("%s %s\n" % (n + 1, main_iter1))
        print u'Fin'.encode(consencode, 'replace') # Fin de boucle
    except:
        print u'Il y a eu une erreur pendant les itérations !'.encode(consencode, 'replace')
    finally:
        if saisie == 3 : fichier_sauv.close()
elif saisie == 4: # Si chargement fichier demandé :
    print (u"\nChargement du fichier ").encode(consencode, 'replace')
    try: # Essai de chargement et d'affichage des résultats:
        fichier_charg = open('ConvResult.txt', 'r')
        print (u"\nAffichage des résultats :").encode(consencode, 'replace')
        for result in fichier_charg : print result.rstrip("\n")
        print u'Fin'.encode(consencode, 'replace')
    except:
        print u"Erreur de chargement, le fichier n'existe pas dans le présent dossier ou est corrompu !".encode(consencode, 'replace')
    finally:
        fichier_charg.close()