¿Cómo puedo usar TDD para resolver un puzzle con una respuesta desconocida?

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

  •  13-10-2019
  •  | 
  •  

Pregunta

Hace poco escribió un programa de Ruby para determinar soluciones a un "Scramble Squares" rompecabezas de baldosas :

Me TDD utiliza para poner en práctica la mayor parte de ella, lo que lleva a las pruebas que se parecía a esto: 

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

Esto funcionó bien para el de nivel inferior métodos "ayudantes":. Identificar los "lados" de una baldosa, la determinación de si una baldosa se puede colocar de forma válida en la red, etc

Pero me encontré con un problema cuando el algoritmo de codificación real para resolver el puzzle. Como yo no sé posibles soluciones válidas al problema, No sabía cómo escribir una prueba primero.

terminé escribiendo una muy fea, no probado, algoritmo para resolverlo: 

  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

Así que mi pregunta es:? ¿cómo se utiliza TDD escribir un método cuando no lo sabe ya las salidas válidas

Si está interesado, es el código en GitHub:

¿Fue útil?

Solución

Esto no es una respuesta directa, pero esto me recuerda a la comparación entre los solucionadores de Sudoku escrito por Peter Norvig y Ron Jeffries. enfoque Ron Jeffries utiliza TDD clásico, pero que en realidad nunca tuvo una buena solución. Norvig, por el contrario, era capaz de resolverlo con mucha elegancia y sin TDD.

La pregunta fundamental es: ¿puede surgir un algoritmo utilizando TDD

Otros consejos

Desde la página web rompecabezas :

El objeto de la Scramble Squares® juego de puzzle es el de organizar los nueve colorido ilustrado piezas cuadradas en un 12" x 12" cuadrado de manera que la gráficos realistas en las piezas se adaptan perfectamente a los bordes para formar una diseño completo en todas las direcciones.

Así que una de las primeras cosas que me gustaría buscar es una prueba de si dos azulejos, en una disposición particular, coinciden entre sí. Esto es lo que se refiere a la cuestión de la validez. Sin ese método funciona correctamente, no se puede evaluar si el enigma ha sido resuelto. Eso parece como un buen punto de partida, una buena pieza tamaño de un bocado a la solución completa. Todavía no es un algoritmo, por supuesto.

Una vez match() está trabajando, ¿hacia dónde vamos desde aquí? Pues bien, una solución obvia es la fuerza bruta: desde el conjunto de todas las disposiciones posibles de los azulejos dentro de la cuadrícula, rechazar aquellos en los que cualquiera de las dos baldosas adyacentes no coinciden. Eso es un algoritmo, de todo tipo, y es bastante seguro para el trabajo (aunque en muchos rompecabezas de la muerte térmica del universo se produce antes de una solución).

¿Qué hay de recoger el conjunto de todos los pares de fichas que coinciden largo de un borde dado (LTRB)? ¿Podría llegar desde allí a una solución, más rápido? Ciertamente, usted puede probarlo (y prueba de manejo de ella) con bastante facilidad.

Las pruebas son poco probable que give que un algoritmo, pero pueden ayudar a pensar acerca de los algoritmos, y por supuesto que pueden hacer más fácil la validación de su enfoque.

No sé si esta "respuestas" a la pregunta ya sea

análisis de la "puzzle"

9 azulejos
cada uno tiene 4 lados
cada baldosa tiene la mitad de un patrón / imagen

FUERZA BRUTA ENFOQUE

Para resolver este problema que necesita para generar 9! combinaciones (9 azulejos X 8 X azulejos 7 azulejos ...)

limitado por el número de búsqueda de lados a la teja de corriente (s) ya en el lugar

enfoque ponderado

Q ¿Cuántos lados son diferentes? Es decir, cuántos partidos hay?

por lo tanto, 9 x 4 = 36 lados / 2 (desde cada lado "debe" partido al menos 1 otro lado)
de lo contrario es un rompecabezas uncompleteable
NOTA: al menos 12 deben coincidir "correcta" para un 3 X 3 rompecabezas

etiquetar cada lateral a juego de una baldosa utilizando una letra única

A continuación, construir una tabla que contiene cada baldosa
necesitará 4 entradas en la tabla para cada baldosa
4 lados (esquinas) de ahí 4 combinaciones
Si ordena la mesa de a lado y índice en la tabla

lado, tile_number
ABcd tile_1
BCDA tile_1
CDAB tile_1
Dabc tile_1

utilizando la tabla debe acelerar las cosas
ya que sólo tendrá que coincidir con 1 o 2 caras como máximo
Esto limita la cantidad de baldosas productivas no colocar tiene que ver

dependiendo del diseño del patrón / imagen
hay 3 combinaciones (orientaciones) desde cada baldosa se puede colocar usando 3 orientaciones
- los mismos (múltiples copias de la misma baldosa)
- reflexión
- rotación

Dios nos ayuda si se deciden a hacer la vida muy difícil
poniendo similares patrones / imágenes en el otro lado que también es necesario para que coincida con
O incluso hacer las baldosas en cubos y resultados 6 lados !!!

El uso de TDD, España que iba a escribir pruebas y luego el código para resolver cada pequeña parte del problema,
como se indicó anteriormente y escribir más pruebas y código para resolver todo el problema

NO no es fácil, tiene que sentarse y pruebas de escritura y código para la práctica

Nota: esta es una variación del mapa colorear problema
http://en.wikipedia.org/wiki/Four_color_theorem

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top