Shuffled Image.

Чем еще себя занять первого января, если не написанием 5 часового контеста? Андрей провел очень клевый контест (результаты), в котором я с удовольствием поучаствовал. Расскажу про одну из задач. Она формулировалась так.

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

Расшифруйте картинку и ответьте на вопрос: сколько иллюминаторов с одной стороны самолёта? Ответьте одним целым числом.

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

На этом моменте можно остановиться и подумать как бы вы решали эту задачу.

Квадратики были размера 16х16 пикселей, т.е. существует всего 256! различных шифров. 256! это очень много, но предположим, что мы смогли перебрать все варианты. Как определить, какой из них подходит? Можно предположить, что в исходной картинке соседние пиксели были примерно одинаковых цветов. Поэтому можно посчитать по всем парам соседних пикселей, на сколько они отличаются, а дальше выбрать перестановку с минимальной суммой.

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

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