The River

Introduction au puzzle

En mathématiques, le concept de rivière est simple à comprendre. Il peut être défini récursivement par :

1. Prendre un nombre supérieur à 0
2. Additionner les chiffres qui le composent
3. Additionner le résultat avec le nombre de départ
4. Répéter les étapes 1., 2. et 3. avec le nombre obtenu

Soit, en prenant par exemple le nombre 1867 on obtient :

1. 1 8 6 7
2. 1 + 8 + 6 + 7 = 22
3. 1867 + 22 = 1889
4. 1. 1 8 8 9
   2. 1 + 8 + 8 + 9 = 26
   3. 1889 + 26 = 1915
   4. 1. 1 9 1 5
      2. 1 + 9 + 1 + 5 = 16
      3. 1915 + 16 = 1931
      4. . . .

Une rivière est donc une suite dont la croissance est infinie. Une rivière peut contenir deux types de nombres :

• Des point de confluence, ou des nombres ayant deux ou plus termes précédents, comme 519, qui a comme termes précédents 498 et 507.
• Des sources, ou des nombres présents dans une seule rivière (celle qu'ils débutent), comme 20 qui n'est présent que dans la rivière commençant par 20

Le problème en langage C à traiter est, dans un premier temps, de créer un programme qui puisse connaître le point de confluence de deux nombres donnés, et dans un deuxième temps, de déterminer si un nombre donné est une source.

Nous allons d'abord traiter le premier cas, puis utiliser les bases de l'algorithme utilisé pour résoudre le deuxième problème.

Premier problème

Les données auxquelles nous disposons sont donc :

• r1, le premier nombre
• r2, le deuxième nombre

r1 et r2 ne sont pas explicitement positionnés dans un ordre quelconque, r1 peut être supérieur OU inférieur à r2.

Les données à renvoyer sont donc :

• Le point de confluence commun à ces deux nombres

Résolution du premier puzzle

Résumé de la méthode

L'algorithme qui donne pour un nombre son terme suivant reprendra exactement celui évoqué en introduction.

La résolution de ce puzzle étant écrite en langage C, il n'est pas possible de facilement transformer un nombre en chaîne de caractères, puis d'extraire chacun des chiffres pour les additionner.

Nous allons trouver une autre solution sans chaîne de caractères, que nous verrons dans la prochain partie. La suite de l'algorithme consistera à choisir quand faire passer un nombre à son terme suivant dans la rivière.

Pour répondre à cette question, nous initialeriseront une boucle qui sera exécutée tant que les deux nombres r1 et r2 sont différents. Pour chaque itération de la boucle nous appliqueront l'algorithme de rivière au nombre qui est inférieur à l'autre.

Transposition en langage C

Nous commençons par créer un tableau qui contiendra les chiffres de r1 ou de r2. Il est de taille 10, car les nombres r1 et r2 sont inférieurs à 10⁹

Après l'entrée des valeurs de r1 et r2, la boucle suivante s'effectue tant que r1 est différent de r2 :

1. On prend le plus petit nombre entre r1 et r2.
2. On le stocke dans une variable temporaire
3. On effectue une boucle tant que cette variable est non-vide :
• Soit i l'indice de l'itération de la boucle
• Tant que la variable temporaire n'est pas divisible par 10ⁱ (i est initialisé à 1):
  On retire 10^i-1 à notre variable temporaire et on ajoute 1 à la i-1^èmecase du tableau
• On ajoute 1 à i
4. On ajoute chaque nombre du tableau au nombre de départ.

Code en C de la résolution

                    
                        int i = 1, test = 0;
                        long long number_r [10];
                    
                

Le programme commence par l'initialisation des variables. Le type long long permet de stocker des valeurs allant jusqu'à 2⁶³-1

                
                    while (r_1 != r_2)
                
            

C'est la boucle qui va s'exécuter tant que les variables r1 et r2 ont des valeurs différentes.

Nous allons traiter le cas générique du test r1>r2, puisque les deux cas ne diffèrent que par le nom de la variable traitée. Dans le code suivant la variable sera r.

                
                    test = r;
                    i = 1;
                
            

On initialise la variable temporaire à r. C'est cette variable sur laquelle on travaillera par la suite

i est initialisée à 1

                
                    while (test != 0) {
                    }
                
            

Cette boucle s'effectuera tant que la variable temporaire sera non-nulle.

                
                        number_r[i-1] = 0;
                        while ((test % (int)pow(10,i)) != 0) {
                            test -= (int)pow(10,i-1);
                            number_r[i-1] +=1;
                        }
                        i++;
                
            

La case i-1 est initialisée à 0, pour éviter de garder les valeurs précédemment ajoutées.

Tant que la variable temporaire n'est pas divisible par 10ⁱ, on enlève 10^i-1 à notre variable temporaire et on ajoute 1 à la case i de notre tableau. (Par exemple, pour une variable temporaire de valeur 426 et i = 1, tant que 426 n'est pas divisible par 10¹, on retire 1 et on ajoute 1 à la première case du tableau jusqu'à obtenir le nombre 420)

On finit par ajouter 1 à i.

                
                    for (int k = 0; k < 10; k++) {
                        r += number_r[k];
                    }
                
            

Enfin, on ajoute chaque nombre du tableau à notre variable de départ(sachant que les cases non remplies ont une valeur de 0 et n'influeront pas sur le résultat).

Comparaison avec un autre Codingamer

Le code donné par l'utilisateur Alain-Delpuch sur Codingame propose une solution différente de celle étudiée dans cette première partie.

Il commence par créer une fonction s, prenant en entrée un entier et retourne son terme suivant dans la rivière

                
                    int s(int n) {
                        return n ? n % 10 + s( n / 10 ) : 0 ;
                    }
                
            

La valeur retournée n'est pas évidente pour un lecteur non renseigné. Elle utilise l'opérateur '?', qui est l'opérateur conditionel. Si l'expression booléenne placée avant le '?' est vraie, alors le programme exécute l'instruction placée entre le '?' et le ':', sinon il exécute l'instruction placée après le ':'

Ici, si n est non-nul, la fonction retourne le reste de la division entière de n par 10 ajouté à l'image par la fonction s du quotient de la division entière de n par 10, faisant donc de s une fonction récursive

Si n est nul, la fonction renvoie 0.

                
                    main(r1, r2) {
                        if ( r1 == 1  ) scanf("%d %d", &r1, &r2);
                        if ( r1 == r2 ) printf("%d", r1);
                        if ( r1 > r2  ) main ( r1         , r2 + s(r2) );
                        if ( r1 < r2  ) main ( r1 + s(r1) , r2         ); 
                    }
                
            

Ici, la fonction principale est aussi rendue récursive, s'appelant elle-même.

• Si r1 est égal à 1, cela veut dire que nous sommes au début du programme, les instructions permettant d'entrer les valeurs r1 et r2 sont donc effectuées
• Si r1 est égal à r2, le résultat r1, point de confluence est renvoyé
• Si r1 est supérieur à r2, un appel à la fonction principale est réalisé, prenant en argument r1 et l'image de r2 par la fonction récursive s
• Si r1 est inférieur à r2, un appel à la fonction principale est réalisé, prenant en argument l'image de r1 par la fonction récursive s et r2

Le détail le plus attirant est sans-doute le fait que le code ne comporte que 13 lignes en comptant la directive de préprocesseur #include tout en restant efficace

La récursivité rend aussi ce code très élégant, y compris dans la fonction principale (le Codingamer ajoutera dans un commentaire que "le premier argument est fixé à 1 au début du programme, puisque les programmes Codingame sont appelés sans argument", ce qui explique le premier test effectué)

Deuxième problème

Nous allons maintenant résoudre le deuxième problème, qui consiste à savoir si un nombre donné est présent dans plusieures rivières ou non.

Les données auxquelles nous disposons sont donc :

• r1, le nombre à tester

Les données à renvoyer sont donc :

• La réponse "YES" ("OUI") ou "NO" ("NON") à la question de la présence du nombre dans une autre rivière.

Résolution du deuxième puzzle

Pour cette partie, nous allons prendre l'algorithme étudié dans la première partie.

Nous vérifieront, pour chaque entier entre r_1-1 et 1, si son terme suivant dans la rivière est égal à r_1, signifiant que ce n'est plus une source.

Le procédé est très similaire à celui du premier problème

En langage C, cela se traduit par :

1. Notre nombre à tester prend la valeur de r_1-1
2. Dans la boucle principale, tester le terme suivant dans la rivière de notre nombre à tester
3. S'il est égal à r_1, sortir de la boucle
4. Diminuer le nombre à tester de 1 (effectuer une recherche en décroissance est plus efficace que partir de 1 et augmenter à chaque itération)
5. Après la boucle, si r n'a pas été retrouvé dans une autre rivière, envoyer non, envoyer oui sinon

Au niveau du code on a (en plus du code précédent):

• int answer = 0, la variable booléenne de réponse (un test sera fait, renvoyant non si answer == 0, oui sinon)
• int t = r_1, le nombre à tester dans la boucle principale
• while (t > 1 && answer == 0), la boucle principale, qui s'exécute tant que le nombre à tester est supérieur à 1 et que r_1 n'a pas été trouvé dans une rivière

Enfin, avant d'envoyer la réponse, un simple test pour déterminer la réponse à envoyer :

                
                    if (answer == 0) {
                        printf("NO\n");
                    }
                    else {
                        printf("YES\n");
                    }
                
            

Bilan

Ce puzzle est un très bon moyen, en réfléchissant avec l'algorithme proposé d'apprendre ou de maîtriser le concept de tableaux en langage C, qui propose un moyen différent du Python de traiter des types conteneurs

La combinaison des deux puzzles permet de réfléchir "à long terme" en se forçant à créer du code s'insérant facilement dans un autre programme, réalisant une économie de temps plus ou moins efficace

La partie Comparaison avec un autre Codingamer m'a permi de faire des recherches et de mieux comprendre l'opérateur '?' qui est l'opérateur conditionnel