Partage

Énigme : nombre de diodes allumées

Sujet résolu

3 juillet 2013 à 22:40:27

Salut tout le monde. Je débute dans la programmation et j'ai choisi Python comme premier langage.

J'ai vu une énigme sur un site, et j'ai essayé de la résoudre grâce un programme, voici l'énoncé :

Vous êtes face à une grande rangée de 12486 diodes bleues.
Au début, seule celle située complètement à gauche est allumée. Ensuite, toutes les secondes, l'opération suivante est réalisée:

Chaque diode change d'état si et seulement si celle située à sa gauche était allumée une seconde avant.
La diode située le plus à gauche reste allumée tout le temps. Le processus s'arrête lorsque la diode située à l'extrémité droite s'allume pour la première fois.
Combien de diodes sont alors allumées

Voici ce que j'ai pu faire :

a=0
diode=[]
diodeAvant=[]
b=1

while a<12486:
    diode.append(0)
    diodeAvant.append(0)
    a+=1
diode[0],diodeAvant[0]=1,1

while not diode[12485]:
    while b<12485:
        if diodeAvant[b-1]:
            if diode[b]:
                diode[b]=0
            elif not diode[b]:
                diode[b]=1
        b+=1
    diodeAvant=diode
    b=1

c=0
compt=0

while c<12486:
    if diode[c]:
        compt+=1
    c+=1

print(compt)

Une âme charitable pourrait me dire ce qui ne va pas ? : Merci d'avance !

-
Edité par nohar 5 juillet 2013 à 1:36:28

Smich74

3 juillet 2013 à 22:47:50

-
Edité par Smich74 3 juillet 2013 à 22:48:35

Si c'était facile, tout le monde le ferait.

nohar

3 juillet 2013 à 23:30:07

Ici :

    diodeAvant=diode

>>> liste1 = [1, 2, 3]
>>> liste2 = [4, 5, 6]
>>> liste1 = liste2
>>> liste1[1] = "plop"
>>> liste1
[4, 'plop', 6]
>>> liste2
[4, 'plop', 6]

Tes deux listes pointent vers le même objet. Au passage t'es pas obligé de maintenir 2 listes pour résoudre ce problème ; il suffit de mettre à jour tes diodes dans le bon ordre (enfin tu vas faire n^2 tours de boucle pour trouver ton résultat...).

-
Edité par nohar 5 juillet 2013 à 0:22:32

Zeste de Savoir, le site qui en a dans le citron !

stackOverflow

3 juillet 2013 à 23:38:19

La reponse c'est 64 ?

-
Edité par stackOverflow 3 juillet 2013 à 23:46:09

Hazzin

4 juillet 2013 à 12:54:16

nohar a écrit:

Ici :
    diodeAvant=diode 
>>> liste1 = [1, 2, 3] >>> liste2 = [4, 5, 6] >>> liste1 = liste2 >>> liste1[1] = "plop" >>> liste1 [4, 'plop', 6] >>> liste2 [4, 'plop', 6] 
Tes deux listes pointent vers le même objet. Au passage t'es pas obligé de maintenir 2 listes pour résoudre ce problème ; il suffit de mettre à jour tes diodes dans le bon ordre (enfin tu vas faire 2n tours de boucle pour trouver n/2+1...).

Salut. Merci pour ta réponse, mais je vois vraiment pas comment mettre à jour mes diodes.

Désolé je débute :/

stackOverflow a écrit:

La reponse c'est 64 ?
-
Edité par stackOverflow il y a environ 13 heures

Oui, mais je veux la méthode, et non la réponse.

Hazzin

4 juillet 2013 à 20:48:16

Bon j'ai changé un peu le code, maintenant ça donne ça :

diode=[]
diodeAvant=[]
diodeApres=[1]
b=1
     

diode=[0]*12486
diodeAvant=[0]*12486
diode[0],diodeAvant[0]=1,1
     
while not diode[12485]:
    diodeAvant=diode
    while b<12486:
        if diodeAvant[b-1]:
            if diode[b]:
                diodeApres.append(0)
            elif not diode[b]:
                diodeApres.append(1)
        else:
            diodeApres.append(0)
        b+=1   
    diodeAvant=diode
    diode=diodeApres
    diodeApres=[1]
    b=1
     

compt=0
     
for c in diode:
    if c:
        compt+=1
     
print(compt)

J'ai essayé avec des petits nombres, ça marche parfaitement, j'ai même vérifié sur papier, le résultat est le même. Avec le nombre qui m'intéresse, ça met trop de temps... Et la réponse est fausse ! Oo (Je trouve 6244, alors que sur le site qui propose l'énigme, c'est 64 la bonne solution)... Et là, je dois essayer avec 1001 et 2097153 xD Comment faire pour ce denier nombre ?

EDIT : C'est bon j'ai résolu le problème, y avait juste une petite erreur =)

Sur ce, je go trouver une astuce pour résoudre cette énigme avec 2 Millions de diodes :/

-
Edité par Hazzin 4 juillet 2013 à 21:53:44

azertymen

4 juillet 2013 à 22:03:37

Salut,

Tu gagnes du temps avec des numpy array :

import copy
import numpy as np

def list_solution(N):
    diode = [0] * N
    diodeAvant = [0] * N
    diode[0], diodeAvant[0] = 1, 1
    while not diode[-1]:
        for b in range(1,N):
            if diodeAvant[b-1]:
                diode[b] = not diode[b]
        diodeAvant = copy.copy(diode)
    return sum(diode)

def numpy_solution(N):
    diode = np.zeros(N,dtype=np.bool)
    diode[0] = True
    while not diode[-1]:
        indices = np.roll(diode, shift=1, axis=0)
        diode[indices] = -diode[indices]
        diode[0] = True
    return diode.sum()

if __name__ == '__main__':
    from time import clock
    N = 12486
    for func in (numpy_solution,list_solution):
        t0 = clock()
        res = func(N)
        t1 = clock()
        print("With {} : {} [executed in {:.3f} s]".format(func.__name__, res, t1-t0))

With numpy_solution : 64 [executed in 3.956 s]
With list_solution : 64 [executed in 16.705 s]

nohar

4 juillet 2013 à 23:01:00

@azertymen : Ta solution reste l'algorithme naïf en $O(n²)$ avec seulement une structure plus rapide. Pour 2 millions de diodes ça prendra quand même la vie.

Quelques remarques sur ce problème pour trouver un algo plus élégant et beaucoup plus rapide.

Si on affiche les 32 premières itérations de cet automate cellulaire, avec par exemple ce code :

diodes = [True] + [False] * 32

for _ in range(32):
    print(*map(lambda i: 1 if i else '_', diodes))
    for i in range(32, 0, -1):
        if diodes[i-1]:
            diodes[i] = not diodes[i]

On obtient ceci :

1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ 1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 1 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ _ _ _ _ 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ _ _ _ _ 1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 1 _ _ _ _ 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ 1 _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _
1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _
1 _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ 1 _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _
1 1 _ _ 1 1 _ _ _ _ _ _ _ _ _ _ 1 1 _ _ 1 1 _ _ _ _ _ _ _ _ _ _ _
1 _ 1 _ 1 _ 1 _ _ _ _ _ _ _ _ _ 1 _ 1 _ 1 _ 1 _ _ _ _ _ _ _ _ _ _
1 1 1 1 1 1 1 1 _ _ _ _ _ _ _ _ 1 1 1 1 1 1 1 1 _ _ _ _ _ _ _ _ _
1 _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _
1 1 _ _ _ _ _ _ 1 1 _ _ _ _ _ _ 1 1 _ _ _ _ _ _ 1 1 _ _ _ _ _ _ _
1 _ 1 _ _ _ _ _ 1 _ 1 _ _ _ _ _ 1 _ 1 _ _ _ _ _ 1 _ 1 _ _ _ _ _ _
1 1 1 1 _ _ _ _ 1 1 1 1 _ _ _ _ 1 1 1 1 _ _ _ _ 1 1 1 1 _ _ _ _ _
1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ 1 _ _ _ _
1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ 1 1 _ _ _
1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ _
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 _

Ceux qui ont l'œil et qui connaissent les fractales reconnaîtront un triangle de Sierpiński.

Un autre moyen d'obtenir ce motif est de partir du triangle de Pascal et de remplacer chaque nombre n par le reste de la division euclidienne de n par 2 (en gros, de remplacer tous les nombres impairs par 1 et virer tous les nombres pairs) :

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10 10 5  1
...

Pour rappel le triangle de Pascal se construit avec la formule du binôme :

$$C_n\^p = C_{n-1}\^{p-1} + C_{n-1}\^{p}$$

Donc, pour résumer, pour que la diode $p$ soit allumée à l'instant $n$ il faut que le coefficient $C_n\^p$ soit impair.

Quand on y réfléchit, c'est complètement lié. À l'instant $n$, l'état de la diode $p$ dépend de l'état des diodes $p$ et $p-1$ à l'instant $n-1$.

En gros, pour qu'une diode soit allumée, il faut qu'à l'instant d'avant :

elle soit éteinte et que la diode précédente soit allumée (pair + impair = impair)
elle soit allumée et que la diode précédente soit éteinte (impair + pair = impair)

Si les deux sont allumées (pair + pair) ou éteintes (impair + impair), alors la diode sera éteinte (pair).

Or les coefficients binomiaux peuvent aussi se calculer avec la formule :

$$ C_n\^p = \frac{n!}{p!\left(n - p\right)!} $$

Y'a donc moyen de compter le nombre de diodes allumées en seulement N/2 itérations s'il y a N diodes (avec N pair) en calculant $n!$ une seule fois, et le dénominateur de façon incrémentale.

Edit : Ceci n'est absolument pas une démonstration mathématique rigoureuse, mais c'est exactement le cheminement que j'ai suivi.

Edit2 : Et en fait il existe aussi un algorithme optimal en $O(log_2(n))$ pour résoudre ce problème. Je paye une pinte au premier qui le trouve.

-
Edité par nohar 5 juillet 2013 à 14:05:08

Zeste de Savoir, le site qui en a dans le citron !

nohar

5 juillet 2013 à 0:16:19

Bon, finalement je n'ai pas résisté et j'ai implémenté la solution en $O(log_2(N))$ :

from time import time

def diodes(n):
    c, p = 0, 1
    while n:
        p = 1
        while n >= p*2:
            p *= 2
        n, c = n-p, c+1
    return p * 2**(c-1)

for n in (1001, 12486,  2097153):
    begin = time()
    res = diodes(n)
    end = time()
    print('diodes(%d): %d (%f s)' % (n, res, end-begin))

diodes(1001): 64 (0.000011 s)
diodes(12486): 64 (0.000009 s)
diodes(2097153): 2 (0.000005 s)

À ce niveau là, on ne peut même plus dire que c'est "beaucoup plus rapide" : c'est juste instantané !

L'idée c'est simplement de prendre en compte la nature fractale du triangle de Sierpiński : si le nombre de diodes est une puissance de 2, alors elles seront toutes allumées lorsque la dernière s'allumera. Sinon, lorsque l'on atteint une puissance de 2, le motif recommence à l'itération suivante mais en étant dupliqué.

PS : Je me dois une pinte.

-
Edité par nohar 5 juillet 2013 à 18:13:21

Zeste de Savoir, le site qui en a dans le citron !

nohar

5 juillet 2013 à 18:08:55

Salut,

Je reviens à la charge parce qu'une solution encore plus rapide m'est tombée dessus dans le métro.

Pour la comprendre regardons déjà le principe de l'algorithme de mon précédent post :

tant que N est non nul
- on cherche la plus grande puissance de 2 inférieure ou égale à N
- on soustrait cette puissance de 2 à N
à la fin on double la dernière puissance de 2 le même nombre de fois que l'on a cherché d'autres puissances de 2 "inférieures ou égales à N"

Par exemple si on prend $N=12486$ :

$N = 12486, P = 8192$
$N = 4294, P = 4096$
$N = 198, P = 128$
$N = 70, P = 64$
$N = 6, P = 4$
$N = 2, P = 2$

On a donc $K=6$ itérations, le résultat est : $$P \times 2\^{K-1} = 2 \times 2\^5 = 2\^6 = 64$$

D'un autre côté, ça veut aussi dire que : $$N = 8192 + 4096 + 128 + 64 + 4 + 2 = 2\^{13} + 2\^{12} + 2\^{7} + 2\^{6} + 2\^{2} + 2\^{1} $$ Donc au passage en calculant les valeurs successives de P, on a décomposé N en une somme de puissances de 2, sauf que pour ça on a recalculé P à chaque itération... ce qui est un peu débile quand on sait qu'un entier, en mémoire, c'est représenté en binaire (donc précisément comme une somme de puissances de 2) : $$N = 12486 = 11000011000110_2 $$

Au final, on peut donc encore pas mal accélérer ce programme en itérant sur les bits de la représentation binaire de N : dès qu'on tombe sur le premier bit non nul, on garde la valeur équivalente dans un accumulateur, puis à chaque fois qu'on tombe sur un bit non nul par la suite, on double cet accumulateur. Ce qui donne en Python :

def diodes2(n):
    mask, result = 1, 0
    while mask <= n:
        if n & mask:
            result = result << 1 if result else mask
        mask <<= 1
    return result

Et avec un petit code de test :

for n in (1, 1001, 12486,  2097153, 1023, 203857693028, 103284375932347):
    begin = time()
    res = diodes(n)
    end = time()
    print('diodes (%d): %d (%d µs)' % (n, res, (end-begin) * 10**6))
    begin = time()
    res = diodes2(n)
    end = time()
    print('diodes2(%d): %d (%d µs)' % (n, res, (end-begin) * 10**6))
    print()

diodes (1): 1 (4 µs)
diodes2(1): 1 (3 µs)

diodes (1001): 64 (11 µs)
diodes2(1001): 64 (4 µs)

diodes (12486): 64 (10 µs)
diodes2(12486): 64 (5 µs)

diodes (2097153): 2 (5 µs)
diodes2(2097153): 2 (5 µs)

diodes (1023): 512 (10 µs)
diodes2(1023): 512 (5 µs)

diodes (203857693028): 8388608 (68 µs)
diodes2(203857693028): 8388608 (12 µs)

diodes (103284375932347): 268435456 (108 µs)
diodes2(103284375932347): 268435456 (14 µs)

Comme quoi...

-
Edité par nohar 5 juillet 2013 à 18:28:23

Zeste de Savoir, le site qui en a dans le citron !

Hazzin

5 juillet 2013 à 22:40:37

C'est incroyable Oo Comme je fais que débuter en Python et que je connais pas les notions de complexité d'algo toussa, je pense que je vais lire le cours sur l'Algo.

nohar

6 juillet 2013 à 13:51:21

Ça te sera forcément utile.

Un truc amusant à faire quand tu auras compris la notion de complexité, ça sera de calculer un ordre de grandeur du temps qu'aurait mis ta première fonction à obtenir le résultat pour mes deux derniers tests (ceux que la solution logarithmique résout en 12 et 14 microsecondes). En général ça donne le vertige la première fois.

Edit : Bien sûr en supposant que ton ordi dispose d'assez de RAM pour faire tenir tout ton tableau en mémoire...

-
Edité par nohar 7 juillet 2013 à 18:39:08

Zeste de Savoir, le site qui en a dans le citron !

Énigme : nombre de diodes allumées

Supprimer

Modérer

Signaler le message aux modérateurs