akkort: Конкурс

Ak Kort (

akkort) wrote,
@ 2005-12-16 10:53:00

Конкурс
По следам предыдущей беседы на тему оптимизации и решений интересных задачек. По заявкам читателей открываю конкурс на решение задач по программированию. С вашей стороны решение, с моей - приз.

Для начала дам простенькую задачку, у которой нет ни требований к памяти, ни к крутым алгоритмам. Просто умение думать плюс аккуратное программирование и внимательность к мелочам. И очень много мелкой оптимизации. Разворачивание циклов, табличные вычисления, #define и forceinline'ы в этой задаче рулят.

Итак, входной файл содержит N*N байтовых записей, где N-размер поля. Каждый байт входного файла содержит информацию об одной ячейке лабиринта: 4 младших бита показывают, где есть дорожки. Старшие биты нулевые. Соответствие бит по часовой стрелке начиная с 12 часов:

Каждая ячейка во входном файле повернута на случайный угол, кратный 90, таким образом, весь входной файл содержит некий лабиринт вида:

Задача: написать программу, которая поворачивает все ячейки так, чтобы получился связанный лабиринт и записывает его в аналогичном формате в выходной файл. Важное замечание: лабиринт должен быть полностью связанным, без петель и мертвых зон. Гарантируется, что входные данные позволяют построить не менее одного правильного лабиринта. Различные верные модификации лабиринта равноценны. Пример решения:

Язык и платформа любые, ограничений по использованию памяти и скорости работы нет. Правда, использование языка, отличного от С++ может привести к существенному замедлению алгоритма. Победителем считается тот, кто первым опубликует в комментариях к этому посту MD5 выходного файла и пришлет затем выходной файл мне на емайл akkort@hotmail.ru. Оценку правильности решения и соответствия ему контрольной суммы буду проводить после окончания приема результатов. Первенство будет определяться по дате комментария.

Входной файл лежит тут: problem.dat.

Для проверки MD5 входного файла = 9d59285d25b3b87f64896974887cf503

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

Для проверки правильности составления лабиринта можно использовать следующую программку (с исходником): checklab.rar

Приз победителю - бутылка армянского коньяка самовывозом из нашего офиса. На олимпиадах такие задачи решают 3 часа. У вас есть пять дней. Решения принимаются до среды 21 декабря, 16:00 уфимского времени (14:00 MSK). Если к тому времени победитель не определится, то коньяк я выпью сам. Пожалейте мою печень, решите задачку :)

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

Кстати было неплохо раскидать задание другим программерам, чтобы интереснее было.

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

(Post a new comment)

	timai 2005-12-16 06:16 am UTC (link)
	О, вот это Я понимаю! Приступаем =) (Reply to this)

	gogas 2005-12-16 06:21 am UTC (link)
	кхм, кхм... я все понимаю, но у тебя во френдах всего 28 человек и, дай бог, половина понимают о чем речь. Илы вопрос к этой половине? :) (Reply to this)(Thread)

	gogas 2005-12-16 06:22 am UTC (link)
	сорри, 59. не туда посмотрел. (Reply to this)(Parent)

	timai 2005-12-16 06:25 am UTC (link)
	Кому надо, тот найдет =) (Reply to this)(Parent)

	akkort 2005-12-16 07:04 am UTC (link)
	ну ничего страшного, мне не напряжно. в конце концов у френдов могут быть френды программеры, жеающие нахаляву получить бутылку коньяка :) (Reply to this)(Parent)(Thread)

	mik_matt 2005-12-16 09:04 am UTC (link)
	это, наверное, такой хитрый способ организации фриланса? недорого и никаких формальностей для работодателя, ведь так? (Reply to this)(Parent)(Thread)

	ерунда guestl 2005-12-16 09:07 am UTC (link)
	Пока это решение встроишь в готовый проект, времени и ресурсов уйдет столько, что дешевле будет купить программера. (Reply to this)(Parent)

akkort
2005-12-16 09:58 am UTC (link)

было бы нечестно с моей стороны давать задачу, которую я сам вчера вечером не решил.
было бы очень глупо искать фрилансеров на решение задачи, которую я решил сам.
нечестность и глупость к моим недостаткам не относятся :)

(Reply to this)(Parent)

gds
2005-12-16 08:29 am UTC (link)

простите, что вмешиваюсь. guestl дал ссылочку, мне показалось интересным. Однако есть вопросы.
Вы набираете на работу людей, специализирующихся на низкоуровневой оптимизации?
Вам важнее, чтобы человек умел писать код 1) правильно и быстро, или 2) почти-абсолютно-оптимально, но медленно?
Вместо "бутылки коньяка самовывозом за решение на VC" можно ли "что-нибудь другое как-нибудь почтой за решение на чем-нибудь другом"?

(Reply to this)(Thread)

akkort
2005-12-16 08:39 am UTC (link)

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

бутылка коньяка дается за любое решение на любом языке, но первым.
за решение на VC дается приглашение на работу.
могу изменить условие - бутылку коньяка можно получить в электронном виде по WebMoney. Скажем, рублей 700.

(Reply to this)(Parent)

	nicka_startcev 2005-12-16 08:41 am UTC (link)
	Более маленькие "тестовые" примеры с ответами есть? Коньяк почтой дойдет в целостности? (Reply to this)(Thread)

	akkort 2005-12-16 08:43 am UTC (link)
	более маленькие генерьте сами себе для отладки какие нужно. (Reply to this)(Parent)

	nicka_startcev 2005-12-16 08:44 am UTC (link)
	да, и еще один вопросик. Зачем одна из клеток на картинке помечена желтым? (Reply to this)(Parent)(Thread)

akkort
2005-12-16 08:47 am UTC (link)

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

(Reply to this)(Parent)

	gds 2005-12-16 11:31 am UTC (link)
	прошу сообщить, когда первый человек напишет решение. (чтобы не рвать попу зря) (Reply to this)(Thread)

akkort
2005-12-16 11:35 am UTC (link)

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

(Reply to this)(Parent)

	clarification request denspb 2005-12-16 12:49 pm UTC (link)
	Под связностью и проходимостью лабиринта понимается то, что все стенки лабиринта представляют собой суть дерево (связный граф без циклов?) (Reply to this)(Thread)

	Re: clarification request akkort 2005-12-16 01:19 pm UTC (link)
	да (Reply to this)(Parent)

denspb
2005-12-17 08:45 am UTC (link)

Порешал часик-другой.
Забавная задачка. Первые 90% берутся банальной эрудицией + 1й эвристикой (накиданная навскидку программа на BorlandPascal, работающая прямо из файла, не читая его в память, отработала минут за 15, переписанная потом на Java - секунд за 8), но вот дальше всё-таки требуется пара довольно сложных алгоритмы на графах. Они где-то ещё процентов 5 клеток, надеюсь, дадут. А вот дальше... Перебор с эвристиками + сложные графы опять же... тут-то самое болото и есть.

Так что насчёт 3х часов олипмиады не соглашусь, это всё-таки очень оптимистичная оценка.

(Reply to this)(Thread)

	akkort 2005-12-17 09:47 am UTC (link)
	хорошо, 5 часов :) (Reply to this)(Parent)(Thread)

denspb
2005-12-19 03:01 pm UTC (link)

Посидел ещё часа 4, поприменял всю аналитику, которую смог.
Программа на Java работает около 8 минут (из низ 7 минут - один кусок, который можно соптимизировать до минуты, но лень). После её работы не определены 8395 ячеек (около 5.25%) в 564 блоках.
Дальше, по всей видимости, только перебором.
Блоки по 4 (156 шт) и 6 клеток (102 шт) посчитаются быстро и с большой вероятностью дадут однозначную "коммутацию" уже опознаных блоков.
А вот дальше... там 8 блоков размером больше 40, один из которых имееет размер 86. Тут со временем будут проблемы....

(Reply to this)(Parent)(Thread)

	akkort 2005-12-19 03:14 pm UTC (link)
	от жавы я бОльшей скорости и не ждал. для сравнения - мой алгоритм просчитывает полное решения задания за 9 секунд. 10221022 - 10 минут. 20462046 - около часа. (Reply to this)(Parent)(Thread)

denspb
2005-12-20 09:45 am UTC (link)

Тут не в Java проблемы, а в том, что я для удобства отладки и визуализации очень сильно пожертвовал скоростью (например, каждый доступ к клетке делается через ассоциативный массив + ещё 3 вызова промежуточных методов). Да и оптимизацией я тоже не очень пока занимался — все циклы бегают по всему полю.

Кстати, с вашими цифрами забавная тенденция.
при первом увеличении задачи в (2.5)^2 = 6.25 раз время увеличивается в 67 раз, а при дальнейшем увеличении размера задачи в 4 раза, время увеличивается всего в 6 раз...

(Reply to this)(Parent)(Thread)

akkort
2005-12-20 03:35 pm UTC (link)

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

(Reply to this)(Parent)

	sergey_shandar 2005-12-17 10:28 am UTC (link)
	Это же pipe! Старая добрая игра :-) (Reply to this)(Thread)

akkort
2005-12-17 11:02 am UTC (link)

а у меня все задачки из старых добрых игр :)
только это не Pipe, где надо было ставить готовые фишки на скорость пока не затопило, а Vetka - старая досовая игруля, где такие деревья и надо было крутить-собирать.

(Reply to this)(Parent)(Thread)

sergey_shandar
2005-12-17 11:15 am UTC (link)

>только это не Pipe, где надо было ставить готовые фишки на скорость пока не затопило, а Vetka - старая досовая игруля, где такие деревья и надо было крутить-собирать.

Может и другое название, просто у меня эта игра (где именно нужно было поворачивать) была именно с таким названием (Pipe или Pipes). :-) Хорошая задачка.

(Reply to this)(Parent)

	shamany 2005-12-17 10:48 pm UTC (link)
	вот думаю - закинуть любой архив, а потом коллизию md5 подобрать, буду первым? http://voffka.com/archives/ps_Bobruisk.jpg p.s. ты в Москву не собираешься в ближайшее время - коньяка бы тяпнули? (я планирую съездить зимой) (Reply to this)(Thread)

	akkort 2005-12-18 08:34 am UTC (link)
	Коллизию-то подобрать можно. Только потом не окажется, что подобранная коллизия является правильным лабиринтом :) В Москву я собираюсь в начале апреля, зимой маловероятно. Давай ты к нам приезжай :) (Reply to this)(Parent)(Thread)

	shamany 2005-12-18 06:27 pm UTC (link)
	все равно через Москву ехать :) а в начале апреля я тоже буду в Москве, выровняемся по времени, обязательно встретимся! (Reply to this)(Parent)(Thread)

	akkort 2005-12-19 04:16 am UTC (link)
	я там с 7 по 9 апреля, на КРИ. днем весь день расписан. Или на выставке можно встретиться (вход платный), или вечером как-то время найти. (Reply to this)(Parent)(Thread)

	shamany 2005-12-19 10:20 am UTC (link)
	у меня 9-го ДР, врядли буду... или до или после :( p.s. хреново то, что от нас нету прямого самолета до Уфы, узнаю про поезда. (Reply to this)(Parent)

	antea 2005-12-20 10:09 am UTC (link)
	Выйди в аську пожалуйста (Reply to this)

	(Anonymous) 2005-12-20 02:29 pm UTC (link)
	[dimas] ee5834f28d034709a1e6fb15bbf1b0ab solution.dat (Reply to this)(Thread)

	alf_kadett 2005-12-20 02:33 pm UTC (link)
	если что - координаты Димаса у меня есть, обращайтесь. (Reply to this)(Parent)

	akkort 2005-12-20 03:17 pm UTC (link)
	решение и исходник на емайл не забудь прислать. (Reply to this)(Parent)(Thread)

(Anonymous)
2005-12-20 03:23 pm UTC (link)

Ну решение сейчас скину, а вот сорсы еще в чуство привести надо - там сейчас страх и ужас.

Плюс не уверен что без поллитры можно разобраться - я уже сам понял что сильно перемудрил :=)

btw, сейчас коллега подходил, альтернативное решение двинул - очень многообещающе. Если его не заломает его накодить, оно будет и быстрым и красивым, не то что мое.

(Reply to this)(Parent)(Thread)

	akkort 2005-12-20 03:30 pm UTC (link)
	главное, чтобы решение, выданное присланным сорцом совпадало с опубликованной контрольной суммой и можно было решить произвольный другой файл такого же размера (Reply to this)(Parent)(Thread)

(Anonymous)
2005-12-20 05:06 pm UTC (link)

Ну совпадет скорее всего, куда оно денется :=)

А вот на другом файле даже не знаю, заработает ли :=)
Не, я конечно никаких ручных "подправлений" и "хинтов" не делал, но всеже мне кажется что есть данные на которых все медным тазом накроется :=)

anyway, сорсы послал. У меня работают 7 секунд

(Reply to this)(Parent)(Thread)

	(Anonymous) 2005-12-20 05:12 pm UTC (link)
	Кстати, кто тут на Джаву бочки катил? 7 сек, повторяюсь! :=) (Reply to this)(Parent)(Thread)

	denspb 2005-12-22 09:56 am UTC (link)
	А можно на решение посмотреть? В плане собственного образования. Или идею основную описать? (Reply to this)(Parent)(Thread)

	(Anonymous) 2005-12-24 01:37 am UTC (link)
	http://hydra.dataart.com/dimas/maze/pipes.html ваще все описал и исходник там же (Reply to this)(Parent)

	timai 2005-12-21 04:57 am UTC (link)
	Эх, обломился таки коньяк. Ну да фиг с ним... (Reply to this)

	ivansorokin 2007-11-11 04:56 pm UTC (link)
	Картинки не открываются :-( (Reply to this)

	axiger 2007-12-18 11:23 am UTC (link)
	я опоздал? (Reply to this)(Thread)

	akkort 2007-12-18 11:27 am UTC (link)
	давно (Reply to this)(Parent)

Mini Sitemap:

Username:		Create an Account Forgot your login? Login w/ OpenID
Password:
	Remember Me
	English • Español • Deutsch • Русский…