Как я могу использовать TDD для решения головоломки с неизвестным ответом? - PullRequest
Новая
       13

Как я могу использовать TDD для решения головоломки с неизвестным ответом?

9 голосов
/ 27 декабря 2010

Недавно я написал программу на Ruby, чтобы определить решения для «Scramble Squares» мозаичной головоломки:

image

Я использовал TDD для реализации большей части ее, что привело к тестам, которые выглядели так: 

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

Это хорошо работало для низкоуровневых «вспомогательных» методов: определение «сторон» плитки, определение того, можно ли правильно разместить плитку всетка и т. д.

Но я столкнулся с проблемой при кодировании фактического алгоритма для решения головоломки.Поскольку я не знал действительных возможных решений этой проблемы, Я не знал, как написать тест в первую очередь.

В итоге я написал довольно уродливый, непроверенный, алгоритм решенияit: 

  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

Итак, мой вопрос: как использовать TDD для написания метода, когда вы еще не знаете действительные выходные данные?

Если выЗаинтересованы, код на GitHub:

Ответы [ 3 ]

8 голосов
/ 27 декабря 2010

Это не прямой ответ, но это напоминает мне о сравнении между решателями судоку, написанными Питером Норвигом и Роном Джеффрисом.Подход Рона Джеффриса использовал классический TDD, но он так и не получил хорошего решения.Norvig, с другой стороны, смог очень элегантно решить его без TDD.

Фундаментальный вопрос: может ли алгоритм появиться с использованием TDD?

1 голос
/ 27 декабря 2010

С сайта головоломки :

Объект Scramble Squares® игра-головоломка, чтобы устроить девять красочно иллюстрированные квадратные кусочки в квадрат 12 "х 12", так что реалистичная графика на куски » края идеально совпадают, чтобы сформировать завершенный дизайн в каждом направлении.

Итак, первое, на что я обращаю внимание, это проверка того, соответствуют ли две плитки в определенном порядке друг другу. Это касается вашего вопроса о действительности. Без правильной работы этого метода невозможно оценить, была ли головоломка решена. Это похоже на хорошую отправную точку, хороший кусок размером с кусочек к полному решению. Конечно, это еще не алгоритм.

Как только match() заработает, куда мы пойдем отсюда? Что ж, очевидным решением является грубая сила: из набора всех возможных расположений плиток в сетке отклоните те, где любые две соседние плитки не совпадают. Это своего рода алгоритм, и он наверняка сработает (хотя во многих загадках смерть вселенной происходит раньше, чем решение).

Как насчет сбора набора всех пар плиток, которые совпадают по данному ребру (LTRB)? Не могли бы вы оттуда быстрее найти решение? Конечно, вы можете протестировать его (и протестировать) достаточно легко.

Тесты вряд ли дадут вам алгоритм, но они могут помочь вам подумать об алгоритмах, и, конечно, они могут упростить проверку вашего подхода.

0 голосов
/ 29 декабря 2010

не знаю, если это "отвечает" на вопрос либо

анализ "головоломки"

9 плиток
у каждой есть 4 стороны
каждая плитка имеет половину рисунка / рисунка

Подход BRUTE FORCE

чтобы решить эту проблему вам нужно сгенерировать 9! комбинации (9 плиток X 8 плиток X 7 плиток ...)

ограничено числом совпадающих сторон с текущими плитками, которые уже установлены

РАССМОТРЕЛ ПОДХОД

Q Сколько сторон разные? IE сколько совпадений?

, следовательно, 9 X 4 = 36 сторон / 2 (поскольку каждая сторона "должна" соответствовать как минимум 1 другой стороне)
в противном случае это нерешаемая головоломка
ПРИМЕЧАНИЕ: по крайней мере 12 должно соответствовать «правильно» для головоломки 3 X 3

маркируйте каждую подходящую сторону плитки, используя уникальную букву

затем создайте стол, содержащий каждую плитку
вам понадобится 4 записи в таблицу для каждой плитки
4 стороны (углы), следовательно, 4 комбинации
если вы сортируете таблицу рядом и INDEX в таблицу

сторона, tile_number
ABCD плитка_1
BCda tile_1
CDab tile_1
DAbc tile_1

использование таблицы должно ускорить процесс
так как вам нужно совпадать только с 1 или 2 сторонами
это ограничивает количество НЕ ПРОДУКТИВНОГО размещения плитки, которое она должна сделать

в зависимости от дизайна рисунка / рисунка
Есть 3 комбинации (ориентации), так как каждая плитка может быть размещена с использованием 3 ориентаций
- одинаковые (несколько копий одной плитки)
- отражение
- вращение

Боже, помоги нам, если они решат сделать жизнь очень трудной
поместив похожие рисунки / рисунки на другую сторону, которые также должны соответствовать
ИЛИ даже превращая плитки в кубики и сопоставляя 6 сторон !!!

Использование TDD,
вы бы написали тесты, а затем код для решения каждой небольшой части проблемы,
как описано выше, и напишите больше тестов и кода для решения всей проблемы

НЕТ, это не легко, вам нужно сидеть и писать тесты и код для практики

ПРИМЕЧАНИЕ: это вариант проблемы раскраски карты
http://en.wikipedia.org/wiki/Four_color_theorem

...