Re: 21ème jour

J'ai lutté sur celui-ci... presque 9h.

Pour la partie 1, j'ai tenté trouver un ordre dans les mouvements qui était toujours valide via un sort.
Finalement, je m'étais rabattu sur une fonction qui donnait tous les mouvements possibles.

Pour la partie 2, mon code de la partie 1 explosait même pour un chiffre à profondeur de 4.
Je me suis donc douté qu’il fallait faire un min. J’ai rapidement résolut ce problème avec un cache pour la programmation dynamique.
Par erreur, je pensai que çà exploserai en temps. Si je considérai tous les mouvements d’une case à l’autre.
Donc, j’ai tenté de chercher une distribution qui marchait dans tous les cas. J’ai réussi à trouver une combinaison qui valider pour la profondeur 2 et 3 pour les 2 jeux de test (j’ai obtenu la validation à 3 avec mon code de la partie 1) mais bien sûr, çà ne fonctionnait pas en profondeur 25. Il y a un cas non optimum qui doit apparaitre.
J’ai finalement tenté d’envisager tous les chemins possibles et j’ai été surpris de voir que cela marchait.
Comme quoi, quand on part sur une mauvaise piste, on bloque dessus.

 private static long processDoors(List<String> doors) {
 long sum = 0;
 for(String door : doors) {
 long messageLength = 0;
 String previous = "A";
 for(char c : door.toCharArray()) { 
 messageLength += recurse(0, handleNumPad.get(previous + c));
 previous = String.valueOf(c);
 }
 System.out.println(door + ":" + messageLength);
 sum += messageLength * Long.valueOf(door.substring(0, door.length()-1));
 }
 return sum;
 }
 private static long recurse(int i, List<String> paths) {
 long sum = 0;
 Seek seek = new Seek(i, paths);
 Long cached = cacheResult.fromCache(seek);
 if(cached != null) {
 return cached;
 }
 if(i <= LIMIT) {
 long minPath = Long.MAX_VALUE;
 for(String path: paths) {
 char previous = 'A';
 long currentPath = 0;
 for(char c: path.toCharArray()) { 
 currentPath += recurse(i + 1, handleArrowPad.get("" + previous + c)); 
 previous = c;
 }
 if(currentPath < minPath) {
 minPath= currentPath;
 }
 }
 sum+= minPath;
 } else {
 sum = 1;
 }
 cacheResult.setInCache(seek, Long.valueOf(sum));
 return sum;
 }