Lucky numbers
Certain s’en souviennent peut-être, il y a presque deux ans (déjà si longtemps !), j’avais créé un topic à propos d’un exercice que je n’arrivais pas à résoudre sur CodinGame. Il m’en a fait baver mais j’en suis venu à bout hier. 
Commençons par le début. Je vais vous rappeler l’énoncé et vous indiquer que j’ai codé en Python, bien que le langage ne soit pas vraiment déterminant.
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?
L’énoncé parait assez simple n’est-ce pas ? Voici un exemple pour ceux qui n’ont pas saisi. Entre 12 et 34, il y a 4 nombres chanceux (que je vais abréger NC), qui sont 16, 18, 26 et 28. Entre 60 et 70, il y a en a 9. Tous en effet sont chanceux sauf 68 parce que justement, il contient et le 6, et le 8.
Mon idée première avait été de faire un algorithme naïf qui bouclait de L vers R en regardant, pour chaque nombre, s’il y a un 6 ou un 8 dedans. Pour se faire, je convertissais en string, ce qui est assez coûteux quand on a un milliard de nombres à traiter.
Je préfère prévenir, je n’ai pas de grandes connaissances mathématiques, donc les formules et autres explications ne seront sans doute pas les plus rigoureuses ni les plus exactes que tu lira.
Ensuite, j’ai remarqué, en déroulant des exemples à la main sur du papier, qu’on pouvait retrouver le nombre de NC entre $1$ et $10^n$ avec la formule suivante.
Qu’il est dur d’écrire du $LaTeX$ quand on a pas l’habitude.
Mais cette formule ne m’aidait guère quand il s’agissait de nombres comme 368442394117. Certains membres m’ont alors conseillé de descendre chiffre par chiffre. Mais je ne comprenais pas et j’ai laissé de côté pendant assez longtemps (c’était une période où je n’étais pas très actif sur CodinGame).
Puis avant-hier, je tente de m’y remettre mais mon code est sale, illisible, trop compliqué et ne passe pas tous les tests, malgré une amélioration du taux de réussite qui est passé de 33% à 66%. Je décide alors de tout reprendre et proprement cette fois, en passant par du papier pour me faire un algorithme clair et poser mes idées plutôt que de tout coder de tête et m’embrouiller encore une fois.
Là, je remarque une autre propriété mathématique. En effet, quand on analyse chiffre par chiffre, si le nombre contient déjà un 6 ou un 8 avant, alors le nombre de NC pour cette puissance de 10 est de $9^n$, avec $n$ un entier correspondant à la puissance de 10 actuelle.
Illustrons par un exemple avec le nombre 610. Nous avons un 6, donc potentiellement beaucoup de NB. Quand nous arrivons au 1, on constate que c’est $1 \times 10^1$. Donc le nombre de NC entre 600 et 610 et de $9^1$ soit 9. En effet, tous sont chanceux sauf 608.
Reprenons le même exemple mais multiplié par 10, ce qui donne 6100. Le 1 est le chiffre des centaines cette fois, soit $1 * 10^2$. Donc le total de NC entre 6000 et 6100 est de $9^2$ soit 81. Et ainsi de suite. J’en déduis donc l’algorithme suivant.
-
Dans le cas normal (pas encore vu de 6 ou de 8), pour un chiffre $x$ :
- Si $x \in [0;6]$, $NC = x \times U_{pow10}$.
- Si $x = 7$, $NC = 6 \times U_{pow10} + 9^n$.
- Si $x = 8$, $NC = 7 \times U_{pow10} + 9^n$.
- Si $x = 9$, $NC = 7 \times U_{pow10} + 2 \times 9^n$.
-
Dans le cas où j’ai déjà vu un 6 ou un 8:
- Si $x \in [0;6]$, $NC = x \times 9^n$.
- Si $x = 7$:
- Si le chiffre chanceux est 6, alors $NC = 7 \times 9^n$.
- Sinon, $NC = 6 \times 9^n$.
- Si $x = 8$:
- Si le chiffre chanceux est 6, alors plus d’autre NC possibles, on retourne le résultat.
- Sinon, $NC = 7 \times 9^n$.
- Si $x = 9$, $NC = 8 \times 9^n$.
Et pour être sûr de ne pas avoir de régression, j’ai recodé le projet en utilisant TDD, l’objectif étant d’étoffer la fonction de calcul au fur et à mesure, sans vouloir tout faire d’un coup. Le code résolvant l’exercice est disponible sur mon GitHub, de même que les tests unitaires. Le voici néanmoins ci-dessous.
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | from sys import stderr from time import process_time from typing import Dict, List def calculate_possibilities(max: int) -> Dict[int, int]: """Calculate the numbers of lucky numbers from 0 to 10**(max - 1)""" possibilities: Dict[int, int] = { 0: 0, 1: 2 } index: int = 2 while index < max: possibilities[index] = 2 * (9 ** (index - 1)) + 8 * possibilities[index - 1] index += 1 return possibilities def get_digits(number: int) -> List[int]: """ Gets the list of all digits of a number, from left to right. """ digits: List[int] = [] if number < 10: return [number] return [int(c) for c in str(number)] def count(number: int) -> int: """ Count the lucky numbers from 0 to number with a fast mathematic range. """ digits: List[int] = get_digits(number) pow_10: int = len(digits) - 1 possibilities: Dict[int, int] = calculate_possibilities(pow_10 + 1) lucky_numbers: int = 0 found_lucky_digit: bool = False lucky_digit: int = -1 for digit in digits: if not found_lucky_digit: # We're in the classic case. if digit == 7: lucky_numbers += 6 * possibilities[pow_10] + 9 ** pow_10 elif digit == 8: lucky_numbers += 7 * possibilities[pow_10] + 9 ** pow_10 elif digit == 9: lucky_numbers += 7 * possibilities[pow_10] + 2 * (9 ** pow_10) else: lucky_numbers += digit * possibilities[pow_10] else: # Things change now that we know we have a lucky digit before us. if digit == 6: lucky_numbers += 6 * (9 ** pow_10) if found_lucky_digit and lucky_digit != 6: # We'll find no more lucky numbers. return lucky_numbers elif digit == 7: if lucky_digit == 6: lucky_numbers += 7 * (9 ** pow_10) else: lucky_numbers += 6 * (9 ** pow_10) elif digit == 8: lucky_numbers += 7 * (9 ** pow_10) if found_lucky_digit and lucky_digit != 8: # We'll find no more lucky numbers. lucky_numbers += 9 ** pow_10 return lucky_numbers elif digit == 9: lucky_numbers += 8 * (9 ** pow_10) else: lucky_numbers += digit * (9 ** pow_10) pow_10 -= 1 if not found_lucky_digit and (digit == 6 or digit == 8): lucky_digit = digit found_lucky_digit = True return lucky_numbers |
Voilà, je tenais à partager un peu mon chemin et remercier encore une fois ceux qui m’ont mis sur le chemin. Ce fut long, mais je n’en suis que plus heureux d’avoir fait cette exercice. 
Je pense que ton algo est le bon, c’est juste qu’écrit comme ça, il y a beaucoup de disjonctions de cas et on voit pas très bien (en tout cas, moi je vois pas très bien) où sont les idées fondamentales du truc.