Problème Codingame des rivières

Table des matières

• River I
  1. 1. Présentation du problème
  2. 2. Résolution
  3. 3.Code
     1. 3.1. Fonction number_sum
     2. 3.2. fonction main
• River II
  1. 1. Présentation du problème
  2. 2. Résolution
  3. 3. Code
     1. 3. 1. Fonction number_sum
     2. 3. 2. Fonction main

River I

1. Présentation du problème

Le problème est simple. Il s’agit de savoir quand les deux Rivières digitales¹ vont se croiser.

2. Résolution

r_1 et r_2 désignent les 2 rivières de départ.

On cherche donc à trouver la valeur de croisement. Pour celà, on prend la plus petite valeur des 2 rivières et on lui ajoute la somme de ses chiffres jusqu’à ce que les 2 rivières soit égales.

3. Code

#include <stdio.h>

long long number_sum(long long number){
    long sum = 0;
    do {
        sum += number % 10;
        number /= 10;
    } while (number != 0);
    return sum;
}

int main()
{
    long long r_1;
    scanf("%lld", &r_1);
    long long r_2;
    scanf("%lld", &r_2);
    while( r_1 != r_2 ) {
        if (r_1 < r_2){
            r_1 += number_sum(r_1);
        } else{
            r_2 += number_sum(r_2);
        }
    }

    printf("%lld\n", r_1);

    return 0;
}

3.1. Fonction number_sum

On calcule la somme des chiffres de number. Pour celà, tant que number ne vaut pas 0, on ajoute à somme le modulo en base 10 de number et on affecte à number le quotient de sa division entière par 10.

3.2. fonction main

On commence par récupérer les deux entiers r_1 et r_2.
Tant que les entiers ne sont pas égaux, on cherche :

• le plus petit des 2 entiers
  
• on lui ajoute number_sum() de lui-même.

4. Solution d’Alain-Delpuch

Code

#include <stdio.h>
// --------------------------------------------
int s(int n) {
    return n ? n % 10 + s( n / 10 ) : 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         ); 
}

Explications

Ce qui saute évidemment aux yeux c’est la beauté de la simplicité des solutions courtes et claires.

Fonction s

Cette fonction renvoie la somme des chiffres du nombre n donné.
On repère ici 2 astuces particulièrement intelligentes:

• Tout d’abord l’utilisation de l’opérateur ternaire qui revient à :

if (n){
    return n%10 + s(n/10); 
} else {
    return 0;
}

• La deuxième astuce réside dans l’inclusion du cas de base. En effet, s est une fonction récursive. il faut donc un cas de base pour être sûre que la fonction s’arrête un jour. Alain-Delpuch utilise ici le fait que toute valeur de n soit considérée comme true en algèbre booléenne. sont cas de base est donc lorsque n vaut 0. Or, lorsque n vaut 0, la condition deveint fausse et l’on sort de la fonction.

Fonction main

Encore une fois, l’efficacité est saisissante ! Une nouvelle fois, main est une fonction récursive. Le cas de base de cette fonction est lorsque les deux rivières sont égales. Sinon, on rappelle la fonction main en changeant la de la plus petite rivière.

River II

Ici le problème est un peu différent car il s’agit de déterminer si il exister une Rivière n différentes de K tel que rivière n passe par K.

1. Présentation du problème

Cette fois-ci, on cherche à savoir si pour une rivière donnée, il existe plus d’une rivière qui la rencontre.

2. Résolution

On parcours, chaque rivière de 1 à r_1 en marquant chaque valeur déjà rencontrée afin de n’y passer qu’une seule fois jusqu’à trouver ou non une rivière r_2 qui croise r_1.

3. Code

#include <stdio.h>

long long number_sum(long long number){
    long sum = 0;
    do {
        sum += number % 10;
        number /= 10;
    } while (number != 0);
    return sum;
}

int main()
{
    long long r_1, r_2;
    long long i;
    scanf("%d", &r_1);
    int visited_rivers[r_1];

    for (i = 1; i <= r_1; i++){
      visited_rivers[i] = i;
    }

    for (i = 1; i<r_1; i++){
        r_2 = i;
        while (visited_rivers[r_2] && r_2 <= r_1){
            visited_rivers[r_2] = 0;
            if (r_2 == r_1){
                puts("YES");
                return 0;
            }
            r_2 += number_sum(r_2);
        }
    }
    printf("NO\n");

    return 0;
}

3. 1. Fonction number_sum

La fonction number_sum est la même que la précédente

3. 2. Fonction main

Dans le détails; on initialise un tableau visited_rivers associant pour chaque i allant de 1 à r_1 pour marquer les rivières déjà visitées. Ensuite, on créé une rivière r_2 pour chaque valeur allant de 1 à r_1 :

• Tant que r_2 n’a pas été visité et que r_2 est inférieur ou égale à r_1
  • On marque r_2 (on met visited_rivers[r_2])
    
  • On affich "YES" et arrête le program si r_1 fini par valoir r_2
    
  • On ajoute à r_2 number_sum(r_2) tant que r_2 est inférieur à r_1

Si l’on arrive a la fin du program, on fini par afficher "NON".

4. Solution d’Alain-Delpuch

Code

#include <stdio.h>
// --------------------------------------------
int
sum(int n) {
    return n ? n%10+sum(n/10) : 0 ;
}
// --------------------------------------------
#define N 100000
int sieve[N];

void
sieveCompute(void) {
    for (int i = 1 ; i < N ; i++) {
        for (int j = i ; sieve[j] == 0 && j < N ; j += sum(j)) {
            sieve[j] = i;
        }
    }
}
// --------------------------------------------
int main() {
    int r1;
    scanf("%d", &r1);
    sieveCompute();
    printf( sieve[r1] == r1  ? "NO": "YES");
}

Explications

Apprentissage

Je suis admiratif devant les solutions d’Alain-Delpuch qui font pour moi preuve d’une grande intelligence dans leur dévelopement. Il sait tirer pleinement partie de toutes les spécificités du C. J’aimerai pouvoir être capable de rédiger du code aussi propre.