Crunchez vos adresses URL
|
Rejoignez notre discord
|
Hébergez vos photos
Affichage des résultats 1 à 13 sur 13
  1. #1
    Amis codeurs, amies codeuses, bonjour !

    Je crée ce topic car je suis un peu froissé, voire limite vexé, sur un exercice de code que je n'arrive pas à faire.
    Contexte: en recherche d'emploi, on m'a filler un test à faire avant un eventuel entretien. Bon je passe les detaisl et ce que je pense de ce genre de trucs, mais ça a quand même eu le merite de me montrer que j'etais un peu rouillé.
    Pour m'entrainer, j'ai fais une serie d'exo, ceux dispo sur https://www.testdome.com/d/java-interview-questions/4 . Et je bloque sur la question 11:

    11 Route Planner
    As a part of the route planner, the routeExists method is used as a quick filter if the destination is reachable, before using more computationally intensive procedures for finding the optimal route.

    The roads on the map are rasterized and produce a matrix of boolean values - true if the road is present or false if it is not. The roads in the matrix are connected only if the road is immediately left, right, below or above it.
    Finish the routeExists method so that it returns true if the destination is reachable or false if it is not.
    Les chemins c'est une matrice, true c'est une route, false c'est pas une route. Le but c'est d'ecrire une methode qui prend 2 points sur la matrice et qui nous dit si une route existe entre les deux.
    Et là c'est le drame. J'ai une solution, mais pas moyen d'avoir le score 100% xD . Ok, je conçois que ce que j'ai fait n'est pas forcément opti, mais je ne vois pas les cas qui sortiraient une stackoverflow
    J'ai cherché sur le net, j'ai pas trouvé de solutions meilleurs (il y a une reponse sur stackoverflow mais qui n'est franchement pas mieux)
    Bref, vous avez une idée ?

    Code:
    import java.util.*;
    
    public class RoutePlanner {
    
        public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn,
                                          boolean[][] mapMatrix) {
            
            //si destination pas une route -> false
    if (!mapMatrix[toRow][toColumn]) {
                return false;
    }
            //si depart pas une route -> false
    if (!mapMatrix[fromRow][fromColumn]) {
                return false;
    }
    
            //si on est à destination
    if (fromRow == toRow && fromColumn == toColumn) {
                return mapMatrix[toRow][toColumn];
    }
    
            //celulle à droite
    if (fromColumn +1 <= toColumn && mapMatrix[fromRow][fromColumn+1] && routeExists(fromRow, fromColumn+1, toRow, toColumn, mapMatrix)) {
                return true;
    }
            //cellule  en bas
    else if (fromRow+1 <= toRow && mapMatrix[fromRow+1][fromColumn] && routeExists(fromRow+1, fromColumn, toRow, toColumn, mapMatrix)) {
                return true ;
    }
            //cellule à gauche
    else if (fromColumn > 0 && mapMatrix[fromRow][fromColumn-1] && routeExists(fromRow, fromColumn-1, toRow, toColumn, mapMatrix)) {
                return true ;
    }
            //cellule en haut
    else if (fromRow > 0 && mapMatrix[fromRow-1][fromColumn] && routeExists(fromRow-1, fromColumn, toRow, toColumn, mapMatrix)) {
                return true;
    }
            return false;
    }
    
        public static void main(String[] args) {
            boolean[][] mapMatrix = {
                    {true,  false, false},
    {true,  true,  false},
    {false, true,  true}
            };
    
    System.out.println(routeExists(0, 0, 2, 2, mapMatrix));
    }
    }

  2. #2
    Tu tournes en rond jusqu'à remplir la pile.

    Teste un cas de ce genre, tu devrais reproduire ton bug (D = départ, A = arrivée, + = route).
    Code:
     A
    D+
    PS: le topic de la programmation est .
    Dernière modification par Cwningen ; 21/10/2020 à 23h02.

  3. #3
    Ha, j'avais pas vu qu'il y avais un topic, ok je poste là bas, merci.
    Sinon oui, j'ai vu à un moment un cas où je tourne en rond, mais je n'arrive plus à le reproduire oO

    On ferme !

  4. #4
    Effectivement ton algo parcours de manière aveugle les cases dans l'ordre des branches du IF, si le chemin à trouver ne suis pas aussi l'ordre des branches ça va boucler.

    L'exemple de Cwningen est bon, plus simplement tu peux faire un cul-de-sac vers la droite à partir du départ :
    1 tu vas entrer systématiquement dans la première branche ("existe une case à droite") jusqu'à être au fond du cul-de-sac
    2 une fois sur la dernière case, tu ne pourra entrer que dans la 3ème branche "existe une case à gauche" => appel sur l'avant-dernière case
    3 une fois revenu sur l'avant-dernière case... tu vas entrer dans la 1ère branche "existe une case à droite" et donc retour en 2

    Du coup suite d'appels infinie entre 2 et 3.

    En plus de tes test, il faut que tu gardes une trace des cases déjà parcourues pour interdire de partir dans la direction d'une case que tu aurais déjà visitée.
    Citation Envoyé par Sidus Preclarum Voir le message
    Ben du caramel pas sucré alors...
    "Avant, j'étais dyslexique, masi aujorudh'ui je vasi meiux."

  5. #5
    MAIS OUI ! Tracer les points que j'ai déjà visité pour eviter de revenir en arriere, j'y avais pensé en plus xD

    Du coup, en ayant fait à LaRache© sans opti* , ça donne ça ! je rajoute une liste de visited à chaque appel, et je verifie si la future position n'est pas déjà dedans avant de faire l'appel recursif.
    Code:
        public static boolean routeExistsRecur(int fromRow, int fromColumn, int toRow, int toColumn,
                                          boolean[][] mapMatrix, List<String> visited) {
    
            //si destination pas une route -> false
            if (!mapMatrix[toRow][toColumn]) {
                return false;
            }
            //si depart pas une route -> false
            if (!mapMatrix[fromRow][fromColumn]) {
                return false;
            }
    
            //si on est à destination
            if (fromRow == toRow && fromColumn == toColumn) {
                return mapMatrix[toRow][toColumn];
            }
    
    
            List<String> newVisited = new ArrayList<>(visited);
            newVisited.add(fromRow +"-" + fromColumn);
            //celulle à droite
            if (fromColumn +1 <= toColumn && mapMatrix[fromRow][fromColumn+1] && !visited.contains(fromRow +"-" + (fromColumn+1))
                    && routeExistsRecur(fromRow, fromColumn+1, toRow, toColumn, mapMatrix, newVisited)) {
                return true;
            }
            //cellule  en bas
            else if (fromRow+1 <= toRow && mapMatrix[fromRow+1][fromColumn] && !visited.contains((fromRow+1) +"-" + fromColumn)
                    && routeExistsRecur(fromRow+1, fromColumn, toRow, toColumn, mapMatrix, newVisited)) {
                return true ;
            }
            //cellule à gauche
            else if (fromColumn > 0 && mapMatrix[fromRow][fromColumn-1] && !visited.contains(fromRow +"-" + (fromColumn-1))
                    && routeExistsRecur(fromRow, fromColumn-1, toRow, toColumn, mapMatrix, newVisited)) {
                return true ;
            }
            //cellule en haut
            else if (fromRow > 0 && mapMatrix[fromRow-1][fromColumn] && !visited.contains((fromRow-1) +"-" + fromColumn)
                    && routeExistsRecur(fromRow-1, fromColumn, toRow, toColumn, mapMatrix, newVisited)) {
                return true;
            }
            return false;
        }
    
        public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn,
                                          boolean[][] mapMatrix) {
            return routeExistsRecur(fromRow, fromColumn, toRow, toColumn, mapMatrix, new ArrayList<>());
        }
    75% , il y a le test de performance sur grosse map qui foire, sans surprise. Bon y'a du mieux. Je vais poster l'exo sur le topic programm, je suis curieux de voir les réponses des gens.
    Le cas qui partez en overflow: partir de (1,0) et allez vers (0,2) en ayant mis (0,2) à true

    Code:
     
    {true,  false, true(A)},
     {(D)true,  true,  false},
     {false, true,  false}
    *Oui je sais, c'est ultra moche , et je me suis battu un con avec les égalités de tableaux vu que ma liste de visited au départ c'etait une List<int[]>, finalement je suis parti sur des String, parce que pourquoi s'emmerder ?
    Aprés avoir fait du groovy pendant 4 ans, ça pique de devoir re-manipuler des tableaux et des listes en java

  6. #6
    Citation Envoyé par jilbi Voir le message
    au départ c'etait une List<int[]>, finalement je suis parti sur des String, parce que pourquoi s'emmerder ?
    Tu fais très beaucoup saigner mon petit coeur de développeur HPC là.

    Effectivement ça devrait fonctionner correctement mais niveau perf c'est catastrophique.

    Par ordre croissant de tirage dans le pied

    1- Les strings c'est le mal. Il n'y a jamais de bonne raison de convertir un type numérique en string dans un algo (a moins de devoir obligatoirement manipuler un codage spécifique), ça prendra toujours plus de place et de temps à manipuler.

    2- Les listes c'est pourri, ton temps de recherche est proportionnel au nombre d'éléments de la liste. Or tu manipules des données ordonnées, il y a plein d'autre structures où les données sont triées dans lesquelles la recherche serait bien plus rapide.

    3- Le fait d'avoir une structure de donnée qui croît à chaque case parcourue va faire que les opérations sur cette structure seront de plus en plus coûteuse. Autrement dit, l'évaluation de chaque case sera plus longue que la précédente.

    Du coup l'idéal serait de s'en passer complètement, par exemple avec une solution tout simple qui coûte 0 en mémoire et ajoute juste un temps constant proche de peanuts....

    Spoiler Alert!
    Comme on ne veut plus parcourir les cases déjà explorées... il suffit de mettre leur valeur à 'false' dans la matrice.
    Citation Envoyé par Sidus Preclarum Voir le message
    Ben du caramel pas sucré alors...
    "Avant, j'étais dyslexique, masi aujorudh'ui je vasi meiux."

  7. #7
    Tout ça, c'est pas une implémentation simple de l'algo de pathfinding A* ?

  8. #8
    Citation Envoyé par LaVaBo Voir le message
    Tout ça, c'est pas une implémentation simple de l'algo de pathfinding A* ?
    C'est plus ou moins sa base mais il manque deux choses : ici on ne renvoie que l'existence d'un chemin mais pas le chemin en lui-même (il faudrait faire remonter la liste des directions empruntées en plus du true/false dans la pile des appels) et dans le A* on mets en place en plus une heuristique pour choisir quelle est la prochaine direction à explorer (heuristique de base par ex : quelle case voisine est la plus proche de l'arrivée à vol d'oiseau).
    Citation Envoyé par Sidus Preclarum Voir le message
    Ben du caramel pas sucré alors...
    "Avant, j'étais dyslexique, masi aujorudh'ui je vasi meiux."

  9. #9
    Citation Envoyé par Lazyjoe Voir le message
    Spoiler Alert!
    Comme on ne veut plus parcourir les cases déjà explorées... il suffit de mettre leur valeur à 'false' dans la matrice.
    j'y ai pensé, je vais re-essayer, mais pour moi il y a 2 inconvenients majeurs qui font que je ne l'ai pas fait:
    - on modifie un paramétre d'entré. On est pas chez les zozos qui font du C ou du C++ ici, merci.
    - appels recurcifs qui modifient une même ressources -> il faut faire des appels synchronized/volatil , bref on commence à se predre la tête avec les Threads

    Maintenant pour le lol oui, je tenterais cette piste demain.

  10. #10
    Citation Envoyé par jilbi Voir le message
    - on modifie un paramétre d'entré. On est pas chez les zozos qui font du C ou du C++ ici, merci.


    Si c'est ça qui te choque, tu fais une copie de travail de la matrice et c'est plié.

    Citation Envoyé par jilbi Voir le message
    - appels recurcifs qui modifient une même ressources -> il faut faire des appels synchronized/volatil , bref on commence à se predre la tête avec les Threads
    Drôle d'idée de vouloir lancer des threads sur une récursion tout simple comme ça. Et puis vaut mieux un seul thread efficace que plein de threads qui rament.
    Citation Envoyé par Sidus Preclarum Voir le message
    Ben du caramel pas sucré alors...
    "Avant, j'étais dyslexique, masi aujorudh'ui je vasi meiux."

  11. #11
    Citation Envoyé par Lazyjoe Voir le message
    https://i.pinimg.com/originals/5d/5f...5493f3e068.gif
    Si c'est ça qui te choque, tu fais une copie de travail de la matrice et c'est plié.

    C'etait totalement gratuit de ma part ( mais c'est vrai que ça me chiffonne )
    Pour les thread, c'est une idotie de ma part, j'étais persuadé qu'une methode recursive spawn un thread par appel, apres quelques recherche ce ne semble pas être le cas xD
    Rouillé je vous dis xD

  12. #12
    Plutôt que de garder tout le chemin parcouru en mémoire, peut-être faudrait-il ne mémoriser que les noeuds (les points où plusieurs directions sont possibles) parcourus afin de pouvoir revenir au noeud précédent si ton chemin débouche sur un cul-de-sac.
    Tu fais ça avec une liste pour pas être limité par des considérations d'espace mémoire.

    Et en bonus tu peux même retracer ton chemin avec ça.

  13. #13
    Bha, j'ai lâché l'affaire sur ce truc en vrai :D (aprés le but c'est pas de forcément trouver le meilleur chemin, plus de savoir s'il y en a un)
    Non, recemment, je me suis bien pris la tête sur ça: https://www.codingame.com/ide/puzzle/winamax-battle , principalement parce que j'ai mis du temps à comprendre que la "war", ça se fait avec le reste du deck, pas entre les 3 cartes que tu tires.
    Et aussi l'ordre d'ajout des "pots". Bref, vous allez dire que je suis con, mais je trouve que l'énoncé est loin d'être clair oO (bon, j'ai fini par trouver, il reste à optimiser par contre xD )

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •