Les nombres chanceux

Cherchons dans un intervalle tous les nombres contenant, 6 ou 8 mais pas les deux

L'auteur de ce sujet a trouvé une solution à son problème.
Staff
Auteur du sujet

Salut à tous,

Pour m'entraîner à Python, je me suis lancé dans un exercice de CodinGame appelé The Lucky Number. En voici l'énoncé.

A lucky number is a 10-based number, which has at least a "6" or an "8" in its digits. However, if it has "6" and "8" at the same time, then the number is NOT lucky. For example, "16", "38", "666" are lucky numbers, while "234" , "687" are not.

Now we want to know how many lucky numbers (without leading zeroes) are there between L and R, inclusive?

Seulement voilà, je suis bloqué depuis deux jours. J'ai tenté de convertir un nombre en chaîne de caractères pour trouver des occurrences de 6 ou 8, de récupérer chaque chiffre à coup de division par 10, rien n'y fait, c'est trop lent.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import sys
import math

# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.

l, r = [int(i) for i in input().split()]

# Write an action using print
# To debug: print("Debug messages...", file=sys.stderr)


def calculate_possibilities(max):
    """Calculate the numbers of lucky numbers from 0 to 10**(max - 1)"""
    possibilities = { 10: 2 }
    index = 2
    while index < max:
        possibilities[10**index] = 2*(9**(index - 1)) + 8 * possibilities[10**(index-1)]
        index = index + 1
    return possibilities
    
    
possibilities = calculate_possibilities(30)


def has_digit(number):
    string = str(number)
    return ('6' in string) ^ ('8' in string)
  
  
def count_occurences(min, max):
    count = 0
    while min < max:
        if has_digit(min):
            count = count + 1
        min = min + 1
    return count


def get_nearest_greater(number):
    temp = []
    for key in possibilities:
        if number <= key:
            temp.append(key)
    return min(temp)


count = 0

def contains_digits(n):
    while n >= 1:
        if (n % 10 == 6) ^ (n % 10 == 8):
            return True
        n = n // 10
    return False

luckies = [n for n in range(l, r) if contains_digits(n)]
count = len(luckies)
print(str(count))

Tout ce que j'ai réussi à trouver, c'est le total de nombres chanceux entre 0 et $1 + n 0$.

$$U_1 = 2 U_n = 2 \times 9^n + 8 \times U_n$$

Toute aide de votre part sera fortement appréciée. D'ailleurs, n'hésitez pas à critiquer le code sur la forme aussi, je suis un débutant Python donc tout est bon à prendre.

Merci d'avance,

informaticienzero

Édité par informaticienzero

J'ai fait tourner rapidement en n'utilisant que les fonctions has_digits() et count_occurences(), et tous les tests sont au vert sauf le dernier, qui prend en effet trop de temps.

Peut-être peux-tu couper les nombres, pour éviter beaucoup de calculs. Par exemple, pour les nombres à 20 chiffres, tu sais qu'aucun de ceux commencant par '68' ne sera chanceux.

Tu pourrais peut-être regarder d'abord les 6 premiers chiffres, ensuite les 12 premiers, et ainsi de suite (6 et 12 choisis de manière complètement arbitraire).

Staff

Là, tu regardes tous les nombres entre l et r et vérifies s'ils sont chanceux. Puisque les performances ne sont pas là et que la plupart des nombres ne sont pas chanceux, ne pourrais-tu pas construire tous les nombres chanceux entre l et r ? Voir seulement les compter ?

Si un nombre est une puissance de n, on peut placer un 6 ou un 8 à n emplacement différents. Chaque autre emplacement peut contenir 0 à 5, 7 ou 9 ou, soit 6, soit 8. Attention aux redites. Bon, il faut réfléchir un peu (j'aime pas la combinatoire), mais j'imagine que c'est une piste envisageable. :D

Le problème de les créer, c'est que l'opération de concaténation est lente en python, donc pas sur que tu gagnes du temps.

Hier, dans le parc, j'ai vu une petite vieille entourée de dinosaures aviens. Je donne pas cher de sa peau.

+0 -0

@Gabbro : Avec de la combinatoire, le nombre de nombres chanceux à $n$ chiffres serait

$$ 2 \binom{n}{1} \binom{n - 1}{9} = 2n\binom{n - 1}{9}. $$

Le problème est qu’ensuite, il faut réussir à retirer ceux qui ne sont pas dans l’intervalle demandé. Mais ça doit pouvoir se faire.

Édité par Karnaj

Je fais un carnage si ce car nage car je nage, moi, Karnaj ! - Tutoriels LaTeX - Contribuez à un tutoriel Ruby

+0 -0

Je trouve plutôt $2(9^n - 8^n)$

edit : décidément je fais que me tromper

edit bis : Du coup, ça fait un algo linéaire (en le nombre de chiffres).

Édité par blo yhg

+0 -0

@Karnaj : tu en comptes certains plusieurs fois il me semble. Plutôt quelque chose comme ca, non?

$$ 2 \sum_{i=1}^{n} \binom{n}{i} \binom{n - i}{8} $$

edit: Je ne vois pas d'où vient la réponse de ρττ, mais il est meilleur en maths que moi. Il reste les bornes à prendre en compte quand même.

Édité par Rockaround

@Rockaround : On sépare en si on veut des 8 ou des 6. Imaginons que l'on veuille des 6. On prend alors le nombre total de nombres possible ($9^n$, pas de 8) et on soustrait le nombre de nombres ne contenant pas de 6 ($8^n$, pas de 8 ni de 6). Pareil pour les 8 (ça fait la même formule, donc fois deux).

Pour compter le nombre de nombres chanceux inférieurs à une borne, on parcourt les chiffres de la borne, de gauche à droite. Pour chaque chiffre, on peut décider de le remplacer par un chiffre plus petit ou de le conserver. Si on le remplace par un chiffre plus petit, on utilise la formule $2(9^n - 8^n)$ pour couper-court si on décide de le remplacer un truc différent de 6 ou 8. Si on le remplace par un 8 ou un 6, on utilise $8^n$. Si on le "remplace" par lui-même, on continue simplement si ce n'est ni un 6 ni un 8. Sinon, on se souvient que c'est un 6 ou un 8 et on adapte en fonction.

Édité par blo yhg

+0 -0
Staff

Je crains que tu n'en surcomptes rototo. Si on teste pour n=2, j'en compte 32

  • 6 ou 8 suivi de 0 à 5 ou 7 ou 9 -> 2*8 possibilités ;
  • 1 à 5 ou 7 ou 9 suivi de 6 ou 8 -> 2*7 possibilités ;
  • 66, 88.

soit 32 possibilités. Ta formules en donnes 34.

Personnellement, je trouve une fonction récurrente, avec $\alpha_n$ le nombre de nombre chanceux à n chiffres,

$$\alpha_{n+1} = 2(9.10^{n-1}-\alpha_n)+9\alpha_n$$

et $\alpha_1 = 2$, en tenant compte de l'interdit du 0 en première place.

il y a $\alpha_n$ nombre chanceux et $9.10^{n-1}\alpha_n$ nombre non chanceux.

  • Un nombre non chanceux auquel on ajoute 6 ou 8 est chanceux -> $2(9.10^{n-1}-\alpha_n)$ ;
  • un nombre chanceux auquel on ajoute 0 à 5, 7 ou 9 est chanceux -> 8 $\alpha_n$ ;
  • un nombre chanceux avec des 6 auquel on ajoute un 6 est chanceux -> $\alpha_n$/2 ;
  • idem avec 8 -> $\alpha_n$/2.

D'où la formule proposée.

Édit : je ne suis pas certain que ce soit à ce genre de réponse que Informaticienzéro s'attendait. :-°

Édité par Gabbro

Hier, dans le parc, j'ai vu une petite vieille entourée de dinosaures aviens. Je donne pas cher de sa peau.

+0 -0

J'ai vérifié avec Haskell, on trouve bien 34 pour n=2. Tu as oublié 6 et 8.

Sinon, pour informaticienzero, je pense que tu devrais plus utiliser de boucle for. Tu recodes la fonction filter (enfin, je crois qu'elle est plus standard en Python maintenant, il faut aller chercher dans functool). Et j'aurais utilisé map au tout premier truc pour l'input.

+0 -0
Staff

J'ai vérifié avec Haskell, on trouve bien 34 pour n=2. Tu as oublié 6 et 8.

OK, on ne comptais pas la même chose. ^^ Faites comme si je n'avais rien dit.

Hier, dans le parc, j'ai vu une petite vieille entourée de dinosaures aviens. Je donne pas cher de sa peau.

+0 -0
Staff

Salut,

Si on prend les nombres $N$ chiffres (donc les nombres de $0$ à $10^N-1$), il y a $S_N=N\times 10^{N-1}$ nombres avec au moins un $6$ et $H_N=N\times 10^{N-1}$ nombres avec au moins un $8$, dont $B_N=\binom{N}{2}\times 2\times N\times 10^{N-2}$ avec au moins un $6$ et au moins un $8$ (on prends deux emplacements au pif, on a deux façons d'y caller le $8$ et le $6$, et il reste $N-2$ chiffres quelconques).

Je raconte n'importe quoi… :-°

Partant de là, le nombre de nombres chanceux à $N$ chiffres est de $K_N=S_N+H_N-B_N$. Il est alors très simple de prendre un nombre $R$ quelconque à $N+1$ chiffres et de compter le nombre de nombres chanceux inférieurs à ce dernier en "descendant" chiffre par chiffre. Je te laisse réfléchir là-dessus, il faut faire attention à ne pas oublier de compter les nombres chanceux en rab éventuels puisque $K_N$ est le nombre de nombres chanceux strictement inférieurs à $10^N$.

EDIT: cela va sans dire mais ça va mieux en le disant, il faut aussi faire attention pour $N<3$.

Édité par adri1

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0

@adri1 : C'est pas possible, $B_n$ grandit asymptotiquement plus vite que $S_n$ et $H_n$:P Il faut plutôt prendre $S_n = 10^n - 9^n$ (ou bien avec la formule d'inclusion-exclusion qui revient à développer $10^n - (10-1)^n$), pareil pour $H_n$, et pour $B_n$ prendre $10^n - 8^n$ avec la même idée. Ensuite il faut retirer deux fois $B_n$ à $S_n + H_n$, ce qui donne la même chose : $2(9^n - 8^n)$.

edit : ton expression pour $S_n$ va compter $k$ fois un nombre contenant $k$ fois le chiffre 6.

Édité par blo yhg

+0 -0
Staff
Auteur du sujet

Merci à tous les amis. J'ai bien fait de demander parce que ça dépasse vraiment mes capacités mathématiques. Qui eut cru en voyant un exercice aussi petit qu'il puisse être aussi complexe ?

Donc je pars sur la formule de adri1 alors ?

EDIT : je trouve que $K_1 = 2$, $K_2 = 36$ et $K_3 = 420$. Juste ?

EDIT 2 : non pas du tout. Je me suis fait avoir parce que les formules mathématiques ne sont pas barrées.

Du coup, je n'ai pas trop compris ce passage. Peut-être la fatigue.

Il est alors très simple de prendre un nombre $R$ quelconque à $N=1$ chiffres et de compter le nombre de nombres chanceux inférieurs à ce dernier en "descendant" chiffre par chiffre.

adri1

En fait, je vois bien comment compter le nombre de nombres chanceux inférieurs à $10^n$, mais je ne vois pas comment ça peut m'aider pour un intervalle du genre $\left[92871036442 ; 3363728910382456\right]$ par exemple.

Édité par informaticienzero

Staff

Il faut lire "à $N+1$ chiffres", j'ai corrigé dans mon post.

L'idée est qu'une fois que tu as une expression pour le nombre de nombres à $N$ chiffres avec un 6, avec un 8 et les deux, compter le nombre de nombres chanceux inférieurs à un nombre quelconque n'est pas compliqué.

Si je reprends les notations (mais pas les expressions qui sont du n'importe quoi :p ), et qu'on prend $R=4263$, le nombre de nombre chanceux inférieurs à ce nombre est de $4B_3+2B_2+6B_1+1+3$.

Édité par adri1

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0
Staff

J'avais trouvé le moyen de me planter encore une fois… Décidément, c'est pas mon jour. :p J'ai corrigé.

$6K_1$ nous donne le nombre de nombre chanceux entre $0$ et $59$. Le $+1$ est là pour compter le $4260$. Puis le $+3$ final est là pour compter les nombres chanceux restant jusqu'à $4263$.

Imagine maintenant que le $6$ soit remplacé par un $7$. Il faudra compter $4K_3+2K_2+6K_1+10^1-H_1$ nombres chanceux puisque les nombres $4260$ à $4269$ sont susceptibles d'être chanceux, à condition qu'ils ne contiennent pas de $8$.

Édité par adri1

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0
Staff
Auteur du sujet

Merci à toi pour les explications. Et si j'ai un $8$, alors ça devient $8K_1 + 1 + 3$ ? Et si c'est un $9$, ça devient $8K_1 + 10^1 - H_1$ aussi ?

EDIT : il doit y avoir un problème dans mes calculs, parce que de 0 à 4263, en comptant avec le programme je trouve 1819 nombres chanceux contre 808 avec la méthode que tu m'as donné. J'ai trouvé que $K_3 = 420$, $K_2 = 36$ et $K_1 = 2$.

Je suis tout perdu. :'(

EDIT 2 : ou alors $K_3$ c'est le nombre de nombres chanceux entre 0 et 1000 c'est ça ? Et du coup, là ça commence à s'éclaircir dans ma tête.

Mais par exemple, comment calculer si $R = 660$ ? Je sais par le code qu'il y a 258 nombres chanceux, mais je n'arrive pas à le retrouver avec la formule.

Édité par informaticienzero

Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte