Forum Programmation.autre Google Code Jam 2014 - Démineur

Posté par  . Licence CC By‑SA.
Étiquettes : aucune
0
13
avr.
2014

Bonjour,

Qui a participé au Code Jam ? Je cherche surtout quelqu’un qui aurait résolu le problème du démineur. Mon programme a l’air de fonctionner, mais sa sortie pour le jeu de tests Large n’est pas acceptée, et je ne trouve pas pourquoi. Je suppose que son résultat à un ou plusieurs cas est faux, mais une inspection visuelle des 134 (!) solutions ne me dit pas laquelle poserait problème.

  • # un truc facile mais long

    Posté par  . Évalué à 2. Dernière modification le 13/04/14 à 19:27.

    faire jouer la partie en ralentissant volontairement les boucles pour avoir le temps de d'afficher la grille entre les deux clics
    et en connaissant la position des mines par avance.

    tu peux alor verifier ton algo de resolution et voir s'il fait des erreurs.

    • [^] # Re: un truc facile mais long

      Posté par  . Évalué à 1.

      L’exercice ne consiste pas à résoudre des grilles, mais à en produire. Et les solutions produites sont assez évidentes visuellement, du genre :

      **************************************************
      *****.............................................
      *****.c...........................................
      *****.............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      ****..............................................
      

      donc suivre leur résolution pas à pas, en plus d’être très long, ne servirait pas à grand-chose.

      • [^] # Re: un truc facile mais long

        Posté par  . Évalué à 2.

        pourtant ton enoncé dit bien

        Il s’agissait de construire des grilles de démineur avec lesquelles le joueur peut gagner en un seul clic

        la validation se fait donc en testant la grille générée

        pour cela tu parcours la grille, case apres case tu cliques, si ca decouvre la totalité de la grille, c'est une "bonne grille"
        sinon tu reinitialises la grille, et tu passes à la grille suivante.
        si tu as parcouru la grille et que tu n'as trouvé aucune case qui decouvre toute la grille, alors ca ne se valide pas.

        • [^] # Re: un truc facile mais long

          Posté par  . Évalué à 1.

          Non, la grille produite doit comporter une case marquée c sur laquelle on clique pour gagner, donc il n’y a pas lieu de la chercher.

          Si quelqu’un d’autre a résolu ce problème (surtout si la sortie de son programme est acceptée par le validateur), ça pourrait déjà me mettre sur la voie.

  • # question bête

    Posté par  . Évalué à 2.

    tu réponds la case a cliquer au 1er 0 ou à la première case bordé par un 0 ?

    Il ne faut pas décorner les boeufs avant d'avoir semé le vent

    • [^] # Re: question bête

      Posté par  . Évalué à 1.

      La case à cliquer, marquée par c, est la première case qui n'est voisine d'aucune mine (ce que tu appelles « le premier 0 » si j'ai bien compris), sauf dans un cas : s'il n'y a qu'une case non minée, c est cette case. Le cas de zéro case non minée n'est pas autorisé par l'énoncé.

      • [^] # Re: question bête

        Posté par  . Évalué à 2.

        sauf que la première case à cliquer n'est pas celle qui n'est voisine d'aucune mine, mais celle qui est voisine d'un 0, le 0 découvrant automatiquement le reste.

        Il ne faut pas décorner les boeufs avant d'avoir semé le vent

        • [^] # Re: question bête

          Posté par  . Évalué à 1.

          Toute case qui n’est voisine d’aucune mine (càd n’importe quelle case 0) est nécessairement un choix correct de case à cliquer (sauf s’il n’y a qu’une case non minée, auquel cas c’est elle qui est choisie comme case à cliquer), car dans toute grille résoluble en un clic, il existe obligatoirement un chemin de zéros entre deux zéros distincts et toute case > 0 est forcément voisine d’un zéro.

          • [^] # Re: question bête

            Posté par  . Évalué à 2.

            C'est juste que sur une grille

            ########
            ########
            ##c.....
            ##.d....
            ##......
            ##......

            la je clique sur c ( qui vaut 5) et ça découvre toute la grille, d est aussi un choix correcte, mais de mon point de vue n'est pas la première case à cliquer (note bien j'ai pas lu l’énoncé )

            Il ne faut pas décorner les boeufs avant d'avoir semé le vent

            • [^] # Re: question bête

              Posté par  . Évalué à 2.

              trop tard pour l'edit

              j'ajouterai que ne sélectionner que les 0 bloque les résolutions de grille du genre

              ###########
              #.........#
              #.........#
              #.........#
              #.........#
              #...#.....#
              ###..c..###
              #.....#...#
              #.........#
              #.........#
              #.........#
              #.........#
              ###########

              Il ne faut pas décorner les boeufs avant d'avoir semé le vent

              • [^] # Re: question bête

                Posté par  . Évalué à 1.

                Cette grille n’est pas correcte au sens de l’énoncé. Ce n’est que si on clique sur un 0 que ses voisins sont découverts. C’est d’ailleurs cohérent : quand on clique sur une case 2, comme ci-dessus, il n’y a aucune raison pour découvrir ses voisines, il faut continuer de jouer pour trouver où sont les deux mines.

                • [^] # Re: question bête

                  Posté par  . Évalué à 2.

                  Ha oui c'est vrai autant pour moi, ça fait longtemps que je n'ai pas fait un démineur …

                  Il ne faut pas décorner les boeufs avant d'avoir semé le vent

  • # Impossible

    Posté par  . Évalué à 2.

    Pour les cas "impossibles" quelles étaient les configurations ?

  • # ayè, ça marche

    Posté par  . Évalué à 1.

    Je ne sais pas ce qui s'est passé. J'ai retéléchargé le jeu d'entrées, envoyé la sortie correspondante, et… elle est acceptée. Merci à ceux qui ont répondu.

    Je ne sais pas s’il y aura un retour là-dessus d’un membre de l’organisation ou d’un autre concurrent. Sinon, ça restera un mystère.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.