Les nombres chanceux

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

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

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

Mais pour détecter qu'ils commencent par "68", il faut les convertir en chaînes de caractères, ce qui est coûteux je pense.

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.

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.

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

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.

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

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

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.

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

Oups, je dois être fatigué moi.

Le nombre total de nombres possibles ne devrait-il pas être $8*9^{n-1}$ puisque le premicher chiffre ne peut pas être un 0 ?

La condition de ne pas avoir de "leading zero" ne change rien : chaque nombre a un unique identifiant, un tuple avec le même nombre de chiffres que la borne.

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,

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

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

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.

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.

@adri1 : C'est pas possible, $B_n$ grandit asymptotiquement plus vite que $S_n$ et $H_n$… 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.

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.

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.

Merci de ton retour. Est-ce que je peux abuser et demander un peu plus d'explication sur la décomposition de 4263 ? Pour 4 et 2 je comprends bien, mais pas le reste.

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.