Come posso utilizzare TDD per risolvere un puzzle con una risposta sconosciuta?

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

  •  13-10-2019
  •  | 
  •  

Domanda

Di recente ho scritto un programma in Ruby per determinare le soluzioni ad un "piazze scramble" puzzle di mattonelle:

ho usato TDD per implementare la maggior parte di esso, portando a test che si presentava così: 

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

Questo ha funzionato bene per il livello inferiore metodi "helper":. Individuare i "fianchi" di una piastrella, determinare se una piastrella può essere validamente inserito nella griglia, etc

Ma mi sono imbattuto in un problema quando l'algoritmo di codifica reale per risolvere il puzzle. Dal momento che non sapevo valide soluzioni possibili al problema, non sapevo come scrivere un test prima.

ho finito per scrivere una bella brutta, non testato, algoritmo per risolverlo: 

  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

Quindi la mia domanda è: come si usa TDD scrivere un metodo quando non si conosce già le uscite validi

Se siete interessati, il codice è su GitHub:

È stato utile?

Soluzione

Questa non è una risposta diretta, ma questo mi ricorda il confronto tra i solutori di Sudoku scritto da Peter Norvig e Ron Jeffries. approccio Ron Jeffries' utilizzato TDD classico, ma non ha mai davvero ottenuto una buona soluzione. Norvig, d'altra parte, è stato in grado di risolverlo molto elegante, senza TDD.

La domanda fondamentale è: può un algoritmo emergere usando TDD

Altri suggerimenti

sito di puzzle :

L'oggetto del Scramble Squares® gioco di puzzle è quello di organizzare i nove colorfully illustrato pezzi quadrati in 12" x 12" quadrato in modo che la grafica realistica sui pezzi bordi abbinano perfettamente formando un progetto completato in ogni direzione.

Quindi, una delle prime cose che vorrei cercare è una prova di se due tessere, in una particolare sistemazione, corrisponde l'un l'altro. Questo è per quanto riguarda la tua domanda di validità. Senza questo metodo di lavoro in modo corretto, non è possibile valutare se il puzzle è stato risolto. Che sembra un bel punto di partenza, un bel pezzo morso dimensioni verso la soluzione completa. Non è un algoritmo ancora, naturalmente.

Una volta match() sta lavorando, dove andiamo da qui? Beh, una soluzione ovvia è la forza bruta: dal set di tutti i possibili disposizioni delle piastrelle all'interno della griglia, rifiutare quelle in cui ogni coppia di tessere adiacenti non corrispondono. Questo è un algoritmo, di sorta, ed è abbastanza certo al lavoro (anche se in molti enigmi della morte termica dell'universo si verifica prima una soluzione).

Come circa la raccolta l'insieme di tutte le coppie di tessere che incontro lungo un determinato bordo (LTRB)? Potrebbe arrivare da lì a una soluzione, più veloce? Certo, è possibile verificare (e test-drive di esso) abbastanza facilmente.

I test sono improbabili per Dare si un algoritmo, ma possono aiutare a pensare a algoritmi, e, naturalmente, possono fare la convalida approccio più semplice.

Non so se questo "risposte" alla domanda sia

analisi del "puzzle"

9 piastrelle
ognuno ha 4 lati
ogni tessera ha la metà un modello / immagine

forza bruta APPROCCIO

per risolvere questo problema è necessario generare 9! combinazioni (9 piastrelle X 8 piastrelle X 7 piastrelle ...)

limitata dal numero delle corrispondenti parti di piastrella corrente (s) già in atto

approccio considerato

Q Quanti lati sono diversi? IE quantità di partite ci sono?

dunque 9 x 4 = 36 lati / 2 (in quanto ogni lato "must" match almeno 1 altro lato)
altrimenti il ??suo un puzzle uncompleteable
NOTA: almeno 12 devono corrispondere "correttamente" per un 3 x 3 di puzzle

etichettare ciascun lato corrispondenza di una piastrella utilizzando una lettera unica

poi costruire un tavolo, tenendo ogni tessera
avrete bisogno di 4 voci nella tabella per ogni tessera
4 lati (angoli) quindi 4 combinazioni
se si ordina la tabella a fianco e indice nella tabella

lato, tile_number
Abcd tile_1
BCDA tile_1
CDAB tile_1
DABC tile_1

utilizzando la tabella dovrebbe accelerare le cose
dato che si dovrebbe solo bisogno di corrispondere 1 o 2 lati al massimo
Ciò limita la quantità di piastrelle non produttivi ponendolo ha a che fare

a seconda del design del modello / immagine
ci sono 3 combinazioni (orientamenti) poiché ogni piastrella può essere posizionato utilizzando 3 orientamenti
- gli stessi (più copie della stessa tessera)
- riflessione
- Rotazione

Dio ci aiuti, se decidono di rendere la vita molto difficile
mettendo simili modelli / immagini sul lato opposto che anche bisogno di abbinare
O anche fare le piastrelle a dadini e la congruenza 6 lati !!!

Utilizzando TDD,
si dovrebbe scrivere i test e quindi il codice per risolvere ogni piccola parte del problema,
come indicato sopra e scrivere altri test e il codice per risolvere l'intero problema

NO non è facile, è necessario sedersi e prove di scrittura e il codice per la pratica

Nota: Questa è una variante della mappa colorazione problema
http://en.wikipedia.org/wiki/Four_color_theorem

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top