Шкатулка Тьюринга

Если вы когда-нибудь сталкивались с теорией информации, то вы, несомненно, знакомы с теоретической нотацией Машины Тьюринга. Но задумывались ли вы когда-нибудь, что вы будите делать, если получите в свое распоряжение настоящую машину Тьюринга – одну из этих больших металлических штуковин с кучей переключателей и рычагов и рулоном бесконечной ленты, которая выглядит точь-в-точь как рулон туалетной бумаги?...

Не очень веселый ответ: не так уж много интересных вещей, которые можно сделать с такой машиной. Но есть одна вещь, которую вы можете сделать с настоящей машиной и не можете сделать с теоретической: использовать её как музыкальную шкатулку.

Наша машина Тьюринга имеет ровно одну переменную состояния (целое число от 0 до 999) и бесконечную ленту, состоящую из ячеек с символами из заданного алфавита написанной на ней. Подвижная (read/write) головка установлена на некоторой ячейке ленты, и управляется она с помощью списка правил встроенных в машину. Каждое правило имеет следующий вид: S1 C1 S2 C2 M, что означает: если машина имеет состояние S1 и C1 записано в текущей ячейке, то изменить состояние на S2, записать C2 в текущую ячейку, и передвинуть головку в позицию M (на одну ячейку назад (влево), на одну ячейку вперед (вправо), или остаться на месте). Если ни одно из правил не найдено для данного состояния, машина останавливает свою работу.

Теперь поговорим о музыке. Головка машины издает скрипучий звук при каждом выполнении правила. Она издает звук da когда движется направо, di когда движется налево, и um когда остается на месте. Положим, что каждая ячейка ленты может содержать один из 16 символов, полученный объединением ровно двух слов: da, di, um и sh для тишины. Изначально, почти все ячейки ленты заполнены символом shsh. И совсем немного (не более чем 500) подряд идущих ячеек образуют небольшой музыкальный ряд, каждая ячейка которого задает пару звуков (одну из 9 комбинаций da, di или um, без тишины). Головка машины изначально поставлена в самую левую ячейку, содержащую звуки.

Теперь это ваша задача, используя машину Тьюринга сыграть мелодию, записанную на ленте (читая слева направо, начиная с начальной позиции головки, до первого значка тишины) как можно точнее, используя головку машины, что бы произвести необходимые звуки.

Выходные данные

Выход генерируемый вашей программой должен состоять из набора правил определяющих поведение машины Тьюринга разработанной для исполнения музыки. Каждое правило должно иметь следующую форму: S1 C1 S2 C2 M, где S1 и S2 целые числа из отрезка 0..999, C1 и C2 принадлежат 16 символам алфавита, а M определяет направление движения головки и обозначается значком звука, который она производит в момент движения (da, di или um).

Начисление очков

Ваша программа будет запущена несколько раз на разном наборе музыкальных записей. Количество полученных очков будет равно сумме положительных набранных очков за каждый из тестов.

За тест с n нотами (n/2 не тихих ячеек) ваша программа получит n-d очков, где d означает дистанцию Левенштейна между сыгранной и заданной музыкой (т.е. минимального количества операций вставки, удаления и замены нот необходимых для перевода сыгранной мелодии в заданную).

Пример

Рассмотрим следующий набор правил, которые выдала тестовая программа:

000 dada 000 dada da
000 umda 000 dada da
000 shsh 000 shsh da
000 didi 001 didi di
001 dada 002 didi di

Тогда результат тестирования может быть следующим:

Заданная музыка: da da|da da|da da|di di|um um
Сыгранная музыка: da da da di di
Кол-во очков: 5

Заданная музыка: um da|um da|um da|da um|di di
Сыгранная музыка: da da da
Кол-во очков: 3

Суммарное кол-во очков: 5 + 3 = 8

Дополнительная информация: Всего будет не более 100 тестов. Формат очков будет следующий: s.xxyy, где xx означает число тестов, на которых машина отыграла идеально, yy - число тестов, где машина получила положительно число очков.