Lucky numbers

Finir un exercice, quelle joie, quel bonheur !

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. :pirate:

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.

$$ \begin{aligned} U_0 &= 0 \\ U_1 &= 2 \\ U_{n+1} &= 9^n \times 2 + 8 \times U_n \end{aligned} $$

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



6 commentaires

Bravo !

Ça m’a fait marrer comme énoncé alors j’ai vite écrit une solution naïve de 20 lignes à ce problème et réutilisé ta suite de tests.

La chose qui m’a surprise si on utilise cette suite de tests c’est que tu comptes le nombre de lucky numbers entre 0 et n, n exclu. ;)

+0 -0

Oui c’est vrai, je n’ai pas pensé à le préciser. Du coup ça m’a joué une surprise quand j’ai envoyé mon code en validation, puisque le test le plus simple ne passait pas.

J’avais alors ajouté artificiellement un +1 au résultat, ça faisait planter les autres mais celui-là passait. J’en ai déduis qu’effectivement, n était exclus. Ce que j’ai corrigé très simplement, comme tu peux le voir. :)

À vrai dire j’ai pas trop compris comment t’as trouvé toutes tes formules, ça a pas dû être facile à débuguer de cette manière. ^^ 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.

Une autre manière de penser l’algo, qui est en fait c’est assez proche d’une catégorie de problèmes qui se révolent avec de la programmation dynamique sur les chiffres (« digits dp », il doit y avoir quelques exemples de ça sur les sites de competitive programming) : si disons on veut compter les nombres chanceux entre 0 et 7894379 (je travaille toujours en [inclu; exclu)) :

  • On compte les nombres chanceux entre 0 et 7000000.
  • On compte les nombres chanceux entre 0 et 7800000.
  • On compte les nombres chanceux entre 0 et 7890000.
  • etc.

Un peu comme tu fais on garde deux booléens pour dire si on a déjà un 6 ou un 8 à gauche de la position actuelle. Si on a vu les deux, on peut sortir de la boucle. Si on en a vu aucun des deux, il suffit de compter les nombres de $k$ chiffres qui contiennent un 6 (donc $k$ fois $10^{k-1}$), + ceux qui contiennent un 8 (identique), - ceux qui contiennent un 6 et un 8 (2 parmi $k$ fois $10^{k-2}$). Bon là j’arnaque un peu parce qu’il faut adapter légèrement les formules pour prendre en compte la valeur de s[i] ; en particulier, il faut juste rajouter 2 if du type if s[i] > 6 et if s[i] > 8 au début pour savoir si on peut mettre un 6 ou un 8 à la position courante. Mais je pense qu’au total ça doit tenir en 15 lignes (et avec beaucoup moins de if que dans ton code).

Deux questions sur le code par ailleurs :

  • Pour les "tests unitaires", pourquoi ne pas tester contre un algo naïf plutôt que d’écrire toutes les valeurs en dur ?
  • Ces quoi ces trucs de typage ? ^^

Pour répondre à tes questions :

  • Parce que l’algorithme naïf commence à être lent si on dépasse le million. Par exemple, entre 0 et 50 millions, il me fallait déjà une dizaine de secondes sur un PC de bonne qualité. J’ai obtenu toutes les valeurs que tu vois avec un algorithme naïf, mais au prix d’une attente plus ou moins longue.
  • C’est une nouveauté de Python 3.5 ou 3.6, je ne sais plus. C’est facultatif, l’interpréteur s’en fout, mais c’est utilié par Mypy et c’est plus clair pour relire. :)

Parce que l’algorithme naïf commence à être lent si on dépasse le million. Par exemple, entre 0 et 50 millions, il me fallait déjà une dizaine de secondes sur un PC de bonne qualité. J’ai obtenu toutes les valeurs que tu vois avec un algorithme naïf, mais au prix d’une attente plus ou moins longue.

Justement, le but de ce genre de tests, c’est de vérifier la correction, pas les performances, non ? Autrement dit, tu vas comparer uniquement la sortie sur des entrées de taille raisonnable (m’enfin ça reste quand même franchement testable quasiment instantanément jusqu’à $10^5$) Parce que sinon tu peux imaginer que ta vision des "tests unitaires" ne marcherait plus en général le jour où tu trouverais un algo qui ferait vraiment gagner un gros ordre de grandeur.

Bon en soi c’est pas une mauvaise idée de tester en plus sur des valeurs générées à la main (ou sur un bourrin qui a tourné plus longtemps), c’est juste qu’abandonner l’idée de tester sur un grand nombre de valeurs (disons générées aléatoirement) simplement pour cette raison, c’est dommage.

C’est une nouveauté de Python 3.5 ou 3.6, je ne sais plus. C’est facultatif, l’interpréteur s’en fout, mais c’est utilié par Mypy et c’est plus clair pour relire. :)

informaticienzero

Ah ok ! Je me demande ce qu’en penseraient les férus de typage de ce site (vu comme ça, on dirait surtout "on va revenir 30 ans en arrière en rajoutant des annotations de types juste pour le plaisir"). ^^

Je me demande ce qu’en penseraient les férus de typage de ce site (vu comme ça, on dirait surtout "on va revenir 30 ans en arrière en rajoutant des annotations de types juste pour le plaisir").

Je pense que les férus de typage te diraient que le typage a une utilité et n’est pas juste pour le plaisir. ;)

Les avantages que je vois au typage statique, d’expérience, c’est que ça me rend plus productif dans tous les aspects du développement et plus particulièrement quand je dois travailler sur ou avec des parties que je connais moins dans une codebase. Ça supprime partiellement le besoin de jouer aux devinettes.

Les autres avantages sont la correction et donc la confiance que j’ai dans ce que je fais, j’ai moins besoin de passer de temps à débugger 3 semaines plus tard un cas rare où un truc peut être null alors que j’avais pensé que ça puisse être le cas, par exemple. Parce que le type checker m’a dit "attention, t’as pas prévu le cas où tu reçois null ! Regarde, là tu passes un objet avec tel type jamais null à cette fonction qui peut retourner null et après tu continues comme si ton objet pouvait pas être null !" Et le refactoring : je peux modifier une signature de fonction et le type checker me dira partout où ce changement casse un truc, comme ça je risque pas d’oublier d’aller modifier partout où la fonction est utilisée.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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