Mes exercices d'algorithmique sur codingame (cliquez moi)
import java.util.*;
import java.util.stream.Collectors;
class Solution {
static int calcSomme(long r){
int somme = 0;
while(r != 0){
somme += r%10;
r /= 10;
}
return somme;
}
private static List generateSequence(int river) {
List nbs = new ArrayList<>();
int i=0;
nbs.add(river);
while(i < 3000){
river = river + calcSomme(river);
nbs.add(river);
i++;
}
return nbs;
}
private static Set findCommonElements(List first, List second) {
return first.stream().filter(second::contains).collect(Collectors.toSet());
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
long r1 = in.nextLong();
long r2 = in.nextLong();
List nbs = generateSequence((int)r1);
List nbs2 = generateSequence((int)r2);
// Collections.sort(nbs);
// Collections.sort(nbs2);
System.err.println(nbs);
System.err.println(nbs2);
Set common = findCommonElements(nbs, nbs2);
System.out.println(Collections.min(common));
}
}
L'objectif de cet exercice algorithmique est de trouver le point de rencontre entre deux rivieres digitales. Une riviere digitale est une sequence de nombres dont chaque nombre est suivi du meme nombre plus la somme de ses chiffres.
Par exemple, prenons le nombre (ou riviere) 471 , on a 4 + 7 + 1 = 12 et 471 + 12 = 483 , puis 4 + 8 + 3 = 15 donc on a 498 etc...Les rivieres 471 et 480 se rencontrent à 519. Comment j'ai résolu cet exercice?
La première étape consiste à sommer chacun des chiffres d'un nombre.J'ai donc créé une méthode calcSomme(r).Comment fonctionne cette méthode?
J'ai utilisé % qui donne le reste de la division entiere afin de recuperer chacun des chiffres d'un nombre,Par exemple
471 % 10 donne 1 , je met 1 dans somme donc somme vaut 1 (zero initialement), puis je dis r = r/10 donc r vaut 47 Puis 47%10 donne 7 , donc somme = 1 + 7 puis on recommence et on a somme = 8 + 4 , on a bien 12 comme somme des chiffres de 471...
Ma seconde etape est de generer des liste d'entiers ou rivieres digitales.Je génère deux liste d'entiers correspondant à mes deux rivieres digitales grace à ma methode "generateSequence" que j'appelle deux fois. Cette methode generateSequence genere une suite mathématique de 3000 elements.On verra que cela pose un petit probleme. Puis en 3eme etape je recupere les elements communs à ces deux listes grace à la methode findCommonElements.Methode qui me renvoit une liste fusionnee à partir de ces deux listes.Enfin je retourne le minimum de cette liste fusionnee, ce minimum sera le point de rencontre que l'on cherche.
Cette solution a passé tous les tests unitaires sauf le dernier qui est composé des 2 entrees : 15485863 et 13000000. Ce qui montre que ma solution n'est pas assez performante pour les tres grands nombres (de l'ordre de plusieurs millions dans ce cas).
Explication détaillée de la méthode findCommonElements:
Cette méthode qui prend deux liste d'éléments quelconques en paramètres retourne une liste d'éléments communs aux deux listes et uniques (Set).
first.stream() transforme une liste en stream afin de pouvoir effectuer de la programmation fonctionnelle puis stream().filter filtre les elements de ce stream selon un predicat c'est à dire que pour chaque élement de la liste2 pour laquelle le predicat est vrai alors on filtre la liste1.Puis avec ce stream filtré on recrée un Set d'éléments (ou liste d'elements uniques) avec les instructions "collect(Collectors.toSet()"