CodinGame November: Нотная грамота от Доктора Кто

В субботу (23.11.2013) прошел очередной конкурс от CodinGame. А так как в этот же день исполнилось ровно 50 лет со дня первого выпуска сериала «Доктор Кто», все задания на конкурсе были связаны с этой тематикой. В своей заметке я разберу одно из заданий, опишу вариант решения и укажу его недостатки.

О конкурсе

Я принимаю участие в конкурсе CodinGame второй раз. В прошлый раз это был конкурс от oDesk. Там я занял 65-е место, хотя задачи были, субъективно, легче. В этот раз формат конкурса не изменился: две задачи, пятнадцать языков на выбор, четыре часа и более тысячи участников. Код можно набирать прямо во встроенном редакторе, заботливо подготовленные тесты прогонять тоже там.

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

Задание коротко

Распознать последовательность нот с черно-белой картинки, представленной в формате блоков черных и белых пикселей.

Задание подробно

На картинке изображен нотный стан из пяти линеек. Ноты могут располагаться на линейке, между линейками или на дополнительной линейке. Головка ноты может быть пустой или заполненной, что означает разную длину звука (пустая — половинная нота, заполненная — четвертная). Ноты, расположенные в нижней половине нотоносца, записаны штилем вверх, в верхней части — штилем вниз. Штиль ноты «B» может быть направлен как вверх, так и вниз.

Данные поступают с STDIN, ответ нужно выдать в STDOUT. На вход скрипта приходит две строки: первая — ширина и высота картинки через пробел, вторая — закодированная картинка. Изображение передается используя кодирование длин серий (Run-Length Encoding). Последовательность пикселей одного цвета кодируется одной буквой (B для черных пикселей, W для белых), после которой через пробел идет число, обозначающее количество пикселей этого цвета. Например: W 5 B 20 W 16 означает 5 белых пикселей, после которых идет 20 черных пикселей и еще 16 белых пикселей. Изображение кодируется сверху вниз, слева направо. Один блок может продолжаться на следующей строке. На выход нужно выдать строку с указанием нот (и их длительности) через пробел. По заданию, между нотами в верхней и нижней половинах нотоносца нет различия. Значение имеет только длина, которая передается буквами H (для половинной ноты) или Q (для четвертной).

Параметры изображения:

100 < Ширина < 5000
70 < Высота < 300
Минимальная ширина нотных линеек и штилей 1 пиксель
Минимальное расстояние между двумя нотами 1 пиксель
Расстояние между двумя линейками не меньше 8 пикселей и как минимум в 4 раза больше ширины линейки

Пример

Вход:

120 176
W 4090 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 1020 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 26 B 10 W 82 B 2 W 25 B 12 W 81 B 2 W 23 B 4 W 8 B 4 W 79 B 2 W 23 B 2 W 12 B 2 W 79 B 2 W 22 B 2 W 14 B 2 W 78 B 2 W 21 B 3 W 14 B 3 W 77 B 2 W 21 B 2 W 16 B 2 W 77 B 2 W 20 B 3 W 16 B 3 W 36 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 60 B 2 W 20 B 2 W 18 B 2 W 76 B 2 W 20 B 3 W 16 B 3 W 76 B 2 W 20 B 3 W 16 B 2 W 77 B 2 W 20 B 4 W 14 B 3 W 77 B 2 W 20 B 4 W 14 B 2 W 78 B 2 W 20 B 2 W 1 B 2 W 12 B 2 W 79 B 2 W 20 B 2 W 1 B 4 W 8 B 4 W 79 B 2 W 20 B 2 W 3 B 12 W 81 B 2 W 20 B 2 W 4 B 10 W 82 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 46 B 10 W 4 B 2 W 20 B 2 W 81 B 12 W 3 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 78 B 20 W 20 B 2 W 77 B 21 W 20 B 2 W 77 B 21 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 77 B 20 W 21 B 2 W 77 B 20 W 21 B 2 W 78 B 18 W 22 B 2 W 79 B 16 W 23 B 2 W 79 B 16 W 23 B 2 W 81 B 12 W 25 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 2420 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 5050

Выход:

AQ DH

Список всех тестов, которые должен пройти скрипт, можно посмотреть тут.

Решение

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

Решение

1) Разбираем входные данные и формируем массив столбцов картинки

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

3) Проходим по массиву нот и распознаем каждую ноту

4) Берем средний столбец ноты

5) Проверяем все интервалы между нотными линейками (обозначены фиолетовым)



6) Возможные варианты для каждого интервала:
— интервал не содержит черных пикселей (пуст) — нота не найдена, переходим к следующему
— первый пиксель черный и интервал не содержит белых пикселей — найдена четвертная нота между линейками
— первый пиксель черный и интервал содержит белые пиксели — найдена половинная нота между линейками
— интервал содержит белые-черные-белые пиксели — найдена половинная нота на следующей линейке
— иначе — найдена четвертная нота на следующей линейке

Недостатки решения

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

Предположения:
1) первый не пустой столбец это разделитель, а не начало ноты;
2) ширина линеек и расстояние между ними не меняется на всей картинке;
3) нота занимает все место между двумя линейками.

Итоги

Решение этой задачи заняло у меня 2 часа 40 минут. Задача решена в полном объеме, все тесты пройдены. По результатам конкурса я занял 23-е место.