Comment puis-je utiliser TDD pour résoudre un casse-tête avec une réponse inconnue?

StackOverflow https://stackoverflow.com/questions/4540265

  •  13-10-2019
  •  | 
  •  

Question

Récemment, j'écrit un programme Ruby pour déterminer des solutions à "Squares Scramble" puzzle tuile:

J'utilisé TDD pour mettre en œuvre la plus grande partie, ce qui conduit à des tests qui avaient l'air comme ceci: 

it "has top, bottom, left, right" do
  c = Cards.new
  card = c.cards[0]
  card.top.should == :CT
  card.bottom.should == :WB
  card.left.should == :MT
  card.right.should == :BT
end

Cela a bien fonctionné pour le niveau inférieur des méthodes « helper ». Identifier les « côtés » d'une tuile, la détermination si une tuile peut être valablement placé dans la grille, etc

Mais je suis tombé sur un problème lors du codage de l'algorithme réel pour résoudre le casse-tête. Comme je ne savais pas de solutions valables possibles au problème, Je ne savais pas comment écrire un premier test.

J'ai fini par écrire un assez laid, non testé, algorithme pour le résoudre: 

  def play_game
    working_states = []
    after_1 = step_1
    i = 0
    after_1.each do |state_1|
      step_2(state_1).each do |state_2|
        step_3(state_2).each do |state_3|
          step_4(state_3).each do |state_4|
            step_5(state_4).each do |state_5|
              step_6(state_5).each do |state_6|
                step_7(state_6).each do |state_7|
                  step_8(state_7).each do |state_8|
                    step_9(state_8).each do |state_9|
                      working_states << state_9[0]
                    end
                  end
                end
              end
            end
          end
        end
      end
    end

Alors ma question est: comment utilisez-vous TDD d'écrire une méthode lorsque vous ne connaissez pas déjà les sorties valides

Si vous êtes intéressé, le code est sur GitHub:

Était-ce utile?

La solution

Ce n'est pas une réponse directe, mais cela me rappelle la comparaison entre les solveurs Sudoku écrit par Peter Norvig et Ron Jeffries. L'approche de Ron Jeffries utilisé TDD classique, mais il n'a jamais vraiment eu une bonne solution. Norvig, d'autre part, a été en mesure de le résoudre avec beaucoup d'élégance sans TDD.

La question fondamentale est: un algorithme peut émerger en utilisant TDD

Autres conseils

Depuis le site Web de puzzle :

  

Le but de la Scramble Squares®   jeu de puzzle est d'organiser les neuf   coloré illustré morceaux carrés   dans un 12" x 12" de sorte que le carré   des graphismes réalistes sur les pièces   bords correspondent parfaitement pour former un   conception terminée dans toutes les directions.

Donc l'une des premières choses que je chercherais est un test pour savoir si deux tuiles, dans un arrangement particulier, un match autre. Ceci est en ce qui concerne votre question de la validité. Sans cette méthode fonctionne correctement, vous ne pouvez pas évaluer si le puzzle a été résolu. Cela semble être un point de départ agréable, un beau morceau bouchées vers la solution complète. Il est encore pas un algorithme, bien sûr.

Une fois que match() travaille, où allons-nous d'ici? Eh bien, une solution évidente est la force brute: de l'ensemble de tous les arrangements possibles des tuiles dans la grille, de rejeter ceux où les deux tuiles adjacentes ne correspondent pas. C'est un algorithme, en quelque sorte, et il est à peu près certain au travail (bien que dans de nombreux casse-têtes la mort thermique de l'univers se produit avant une solution).

Souhaitez-vous collecter l'ensemble de toutes les paires de tuiles qui correspondent le long d'un bord donné (LTRB)? Pourriez-vous obtenir de là à une solution, plus rapide? Certes, vous pouvez le tester (et test conduire) assez facilement.

Les tests ne sont pas susceptibles de donner un algorithme, mais ils peuvent vous aider à réfléchir à des algorithmes, et bien sûr, ils peuvent faire valider votre approche plus facile.

Je sais pas si cette "réponse" la question soit

analyse du "puzzle"

9 tuiles
chacun a 4 côtés
chaque tuile a une demi motif / image

APPROCHE BRUTE FORCE

pour résoudre ce problème vous devez générer 9! combinaisons (9 tuiles X 8 X 7 tuiles tuiles ...)

limité par le nombre de côtés correspondant à la tuile de courant (s) déjà en place

APPROCHE CONSIDÉRÉ

Q Combien de côtés sont différents? IE combien de matchs sont là?

donc 9 x 4 = 36 parties / 2 (puisque chaque côté "doit" rencontre au moins une autre partie)
sinon son casse-tête un uncompleteable
REMARQUE: au moins 12 doit correspondre à un 3 X 3 puzzle "correctement"

étiqueter chaque côté correspondant d'une tuile en utilisant une seule lettre

puis construire une table contenant chaque carreau
vous aurez besoin de 4 entrées dans la table pour chaque carreau
4 côtés (coins) donc 4 combinaisons
si vous triez la table côte à côte et INDEX dans la table

côté, tile_number
ABcd tile_1
BCDA tile_1
Cdab tile_1
Dabc tile_1

à l'aide de la table devrait accélérer les choses
puisque vous n'avez besoin de faire correspondre 1 ou 2 côtés au plus
ce qui limite la quantité de carreaux improductifs placer doit faire

en fonction de la conception du motif / image
il y a 3 combinaisons (orientations) puisque chaque tuile peut être placé en utilisant 3 orientations
 - les mêmes (plusieurs copies du même tuile)
 - réflexion
 - rotation

Dieu nous aide si elles décident de rendre la vie très difficile
en mettant motifs / images similaires de l'autre côté qui doivent aussi correspondre
Ou même faire les tuiles en cubes et correspondant à 6 côtés !!!

Utilisation TDD,
vous écrire des tests et du code pour résoudre chaque petite partie du problème,
comme indiqué ci-dessus et écrire plus de tests et le code pour résoudre le problème

NO ne est pas facile, vous devez vous asseoir et des tests d'écriture et le code à la pratique

NOTE: Ceci est une variante du problème de coloration carte
http://en.wikipedia.org/wiki/Four_color_theorem

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top