Voici quelques morceaux de code qui vont seront utiles pour le hackathon.
1°/ Lire des lignes sur l'entrée standard et les découper
Dans tous les problèmes du hackathon, il faut lire des lignes sur l'entrée standard. Parfois, il faut analyser ces lignes, notamment en les découpant grâce à un caractère séparateur. Le code ci-dessous prend comme hypothèse :
- la première ligne à lire contient le nombre de lignes qui suivent
- chaque ligne suivante est constituée de trois entiers séparés par des espaces.
import java.io.*;
import java.util.*;
class PbReader {
public static void main(String[] args) {
Locale.setDefault(Locale.ENGLISH); // pour être ok avec le serveur qui juge votre solution
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = "";
line = br.readLine(); // lire la 1ère ligne
int nb = Integer.parseInt(line); // conversion en entier
for(int i=0;i<nb;i++) { // lire nb lignes suivantes
line = br.readLine();
String[] parts = line.split(" "); // découpage grâce aux espaces
int n1 = Integer.parseInt(parts[0]);
int n2 = Integer.parseInt(parts[0]);
int n3 = Integer.parseInt(parts[0]);
// faire qqchose avec n1, n2, n3
}
}
catch(IOException e) {}
}
}
2°/ générer toutes les combinaisons possibles de n éléments.
Dans certains problèmes, il faut parcourir toutes les combinaisons possibles d'un ensemble de caractères, entiers, ... Pour ce faire, le plus simple est de créer une méthode récursive qui utilise un algorithme simple à coder et qui chaque fois qu'on l'appelle génère une des combinaisons possibles. Pour certains problème, on peut traiter la combinaison directement et voir si elle répond aux données du problème. Dans d'autre cas, quand le nombre de combinaisons possibles n'est pas trop énorme (NB : pour n éléments, le nombre de combinaison est n!, donc par exemple n= 10 => n! = 3628800 !), on peut stocker toutes les combinaisons possibles dans une liste, pour ensuite explorer la liste.
Les algorithmes qui permettent de générer toutes les combinaisons sont nombreux et plus ou moins efficaces. Les plus efficaces sont ceux qui se permettent de modifier le tableau d'entrée à chaque appel de la fonction récursive. Parmi ceux-la, il y a le "heap recursive algorhtim" dont un exemple d'implémentation est donnée ci-dessous (cf. https://en.wikipedia.org/wiki/Heap%27s_algorithm#:~:text=Heap's%20algorithm%20generates%20all%20possible,2%20elements%20are%20not%20disturbed.)
La méthode récursive prend un tableau avec size entiers et met toutes les combinaisons possibles dans un liste de tableau d'entiers.
public void buildCombi(List<int[]> combi, int[] tab, int size) {
if (size == 1) {
combi.add(tab.clone());
}
else {
buildCombi(combi,tab,size-1);
for(int i=0;i<size-1;i++) {
if (size%2 == 1) { // swap elements 0 and size-1
int tmp = tab[0];
tab[0] = tab[size-1];
tab[size-1] = tmp;
}
else { // swap elements i and size-1
int tmp = tab[i];
tab[i] = tab[size-1];
tab[size-1] = tmp;
}
buildCombi(combi,tab,size-1);
}
}
}
Exemple d'utilisation :
int[] tab = { 1, 2, 7, 2, 9 };
List<int[]> combi = new ArrayList<>();
buildCombi(combi, tab, 5);
Vous pouvez facilement adapter ce code pour des tableaux d'autres types, ou bien en modifiant le test au début de buildCombi() pour traiter la combinaison courante immédiatement (ce qui rend la liste combi inutile)