Pourquoi mes résultats sont décalés de +1 ?

Question

L'exercice "cats with hats" consiste à prendre 100 chats, faire le tour de chacun 100 x.
Chaque fois qu'on passe devant un chat sans chapeau on lui on pose un.
Et si il en a déjà un on le lui enlève.

On fait comme ça sur 1 chat sur 1 au 1er tour, 1 chat sur 2 au 2e tour, 1 chat sur 3 au 3e tour, ainsi de suite jusqu'au 100e tour (ou on ne fera donc que le dernier chat).

Ma logique globale semble être bonne car j'arrive (presque !) au résultat escompté, sauf que tout est décalé de +1 !

Pour l'exemple ici j'ai tout réduit à 10 au lieu de 100.

Résultat correct attendu :

1 hat
4 hat
9 hat

Mon résultat à moi :

2 hat
5 hat
10 hat

Mon script:

cats = {}

# put 100 cats key with "no hat" value in dict cats
for cat in range(1, 11):
    cats[cat] = "no hat"

step = 0

# we'll do 100 turn
for turn in range(1, 11):

    step += 1

    # give or remove hat for each cat
    for cat in range(1, 11, step):
        if cats[cat] == "no hat":
            cats[cat] = "hat"
        else:
            cats[cat] = "no hat"

print cats, "\n"

for cat in cats:
    if cats[cat] == "hat":
        print cat, cats[cat]
    else:
        pass

Je pense bien avoir pris en compte les exclusions de range et tout, mais je ne vois pas pourquoi mon résultat est décalé de +1 et j'ai beau utiliser le debugger je ne comprends toujours pas.

Answer 1

tes chats n'ont pas de chapeau initialement, tu fais 10 fois le tour (tel que décrit), dans ce cas :

• le premier chats s'est vu mettre un chapeau 5 fois (tours impaires) et s'est vu retiré son chapeau 5 fois (tours paires), donc il ne devrait pas avoir de chapeau... ce que tu trouve (et moi aussi).
• le second chat a un chapeau après le premier tour, et après on ne peut jamais le lui retirer car il n'est plus jamais testé...

bref, ta solution calculée semble bonne (j'ai la même), ta théorique semble mauvaise.
Je pense que la simulation théorique commence avec le chat numéro 0 (cf réponse de Kromak), et donc vous êtes d'accord...

pour info, mon code (qui trouve la même chose), Kromak a raison, un dico n'est pas l'idéal. De plus, il suffit d'un booléen (ou 0/1) pour savoir si un chat a un chapeau ou non, c'est plus simple qu'une chaîne de caractères...

import numpy as np
cats = np.zeros(10)  # aucun des 10 chat n'a de chapeau (tous à 0)
step = 0
for turn in range(10):
    step += 1
    for cat in range(0,10,step):
        cats[cat] = not cats[cat]  # on change l'état des chats concerné
    print("{: 3d} : {}".format(step, cats))

réponse type...

1 : [ 1.  1.  1.  1.  1.  1.  1.  1.  1.  1.]
2 : [ 0.  1.  0.  1.  0.  1.  0.  1.  0.  1.]
3 : [ 1.  1.  0.  0.  0.  1.  1.  1.  0.  0.]
4 : [ 0.  1.  0.  0.  1.  1.  1.  1.  1.  0.]
[...]
9 : [ 1.  1.  0.  0.  1.  0.  0.  0.  0.  1.]
10 : [ 0.  1.  0.  0.  1.  0.  0.  0.  0.  1.]

D'où tiens-tu ta réponse théorique (un programme test?)

Comments

Je viens de comprendre mon souci en te lisant :

le second chat a un chapeau après le premier tour, et après on ne peut
jamais le lui retirer car il n'est plus jamais testé...

Normalement, dès le second tour, on commence par lui (on teste 1 chat sur 2) et on lui enlève donc le chapeau, qui en effet, ne lui sera jamais remis par la suite.

J'aurais du designer mon script de manière à passer le premier chat, et donc faire :

for cat in range(step, 11, step):

Et là ça marche au poil !

En revanche j'ai bien noté vos remarques sur la préférence d'utiliser des listes plutôt que des dicos, je vais donc essayer des variantes comme ça.

Pour te répondre cet exo vient du cours "Real Python", les solutions sont [sur Github] je ne les ai utilisé que pour vérifier si j'arrivais bien au bon résultat (qui n'était pas donné dans le cours), je n'ai pas encore étudié les scripts-réponses, je comptais d'abord me casser la tête dessus avant.

1

---

tu fais effectivement l'hypothèse qu'on commence toujours par tester le premier chat, puis le chat (1+step), puis (1+2step), etc...
si le premier chat testé est le chat n° (step), ça peut changer les choses... :)

pour la solution, ce n'était pas une critique, juste pour vérifier sa fiabilité...
chercher à comprendre est tout à ton honneur, bien évidement!

l'utilisation des listes, et du codage binaire de la présence ou non de chapeau te fera un code un peu plus léger, mais surtout beaucoup plus rapide : ta liste sera itérée dans l'ordre (donc complexité total en n) alors que ton dico nécessite d'être parcouru à chaque fois pour accéder à chaque clé (complexité en n² probablement ramenée à une complexité en n)
(explication très grossière pour la complexité, mais c'est pour les ordres de grandeurs...)

---

C’est ça ton script de référence ?
Il n’est pas un peu faux ? Si tu prends un nombre pair de chats, le premier chat finit sans chapeau ; si tu prends un nombre impair, il finit avec un chapeau (premier point de la réponse de Lhassa). Avec leur algo, que tu prennes un nombre pair ou impair, le résultat est le même…
En plus, le:

if array_of_cats[cat] is True:

c’est un peu moche pour un exemple de cours… La pep8 quoi!

Don't compare boolean values to True or False using == .
Yes: if greeting:
No: if greeting == True:
Worse: if greeting is True:

Sinon, je propose le code suivant:

number_of_cats = 100
cats = [False] * number_of_cats

for turn in range(1, number_of_cats + 1):
    cats[::turn] = [not cat for cat in cats[::turn]]

cats_with_hat = [index for index, cat in enumerate(cats) if cat]

print(cats_with_hat)

Ça vous semble correct à vous ?

Answer 2

remplace tes range(1,11) par des range(0,10) et tu n'auras plus de décalage :)

Je rajouterais que ton décalage vient du fait que tu commences ta liste à 1, et non à 0, comme la plupart des listes.

Comments

Mais pourtant je ne travaille pas sur des index de liste...
que je commence à 0, 1 ou 50 ça aurait été pareil si mon range est bien de 10 non ?

---

ça dépend d'où vient ta solution et comment elle est construite. Je parierais que ça vient d'une liste classique, et une liste commence à zéro.

Si tu fais l'algo à la main sur une feuille, sans tenir compte des indices de tes chats dans la liste, tu te rendras compte que ton 2e chat a un chapeau. Donc son indice est 1, si ça vient d'une liste (vu que ça commence à 0). Alors que toi ton 2e chat a le numéro 2, d'où ton décalage.

Autre point, mais ça n'engage que moi, je ne pense pas qu'un dictionnaire soit l'outil le plus adapté à ton problème. Un dico n'est pas ordonné. Tu by-pass un peu ce problème en mettant un pseudo indice comme clé, mais ce n'est pas, à mon sens, la meilleure solution.

Et du coup, en utilisant une tableau [], tu n'aurais pas eu ce problème d'indice.