ICFP Contest 2010: день третий
День первый
День второй
Проснувшись утром, глянул на таблицу результатов. У меня было что-то около 3 очков. Негусто, учитывая что наверху у народа были уже сотни. Количество засабмиченных народом машинок тоже было каким-то немаленьким. Понял, что надо писать автосабмитилку.
Глянул на сорцы странички сабмита топлива. Страничка похоже была полностью динамической и генерилась тремя обфускейчеными джаваскриптами. Разбираться с ними не было никакого желания. Была мысль глянуть на посылаемые HTTP запросы через прокси, но я что-то тоже поленился. Пошел в гугл искать что-то типа wget-а с автопарсингом скриптов. Этого не нашел, зато нашел классный плагин к FF под названием iMacros. Эта штека умела отдавать текст странички в обычном текстовом виде и парой команд сабмитить формы. То что надо!
Быстренько накатал скрипт на перле, который генерил макрос, сабмитящий топливо 11111 ко всем машинкам. Генерируемый макрос выглядел как-то так:
VERSION BUILD=6650406 RECORDER=FX
TAB T=1
URL GOTO=http://icfpcontest.org/icfp10/instance/256934/solve/form?x=8&y=8
TAG POS=1 TYPE=TEXTAREA FORM=ACTION:/icfp10/instance/256934/solve ATTR=ID:_contents_id CONTENT=2L:
2R1R0#2R1R,...136L138L0#139L138L:
139L
TAG POS=1 TYPE=INPUT:SUBMIT FORM=ID:solution ATTR=ID:proceed
SAVEAS TYPE=TXT FOLDER=c:\!icfp\machines FILE=machine.256934
URL GOTO=http://icfpcontest.org/icfp10/instance/256980/solve/form?x=8&y=8
TAG POS=1 TYPE=TEXTAREA FORM=ACTION:/icfp10/instance/256980/solve ATTR=ID:_contents_id CONTENT=2L:
2R1R0#2R1R,
...115L117L0#118L117L:
118L
TAG POS=1 TYPE=INPUT:SUBMIT FORM=ID:solution ATTR=ID:proceed
SAVEAS TYPE=TXT FOLDER=c:\!icfp\machines FILE=machine.256980
...
Запустил его работать... Тем временем начал разбираться с форматом машинок. Глянул на две похожие машинки "122000010" и "12210000010". Как-то сразу понял, что первое число '1' - это, вероятно, количество камер (chambers). Дальше должно идти описание одной камеры. Следующее число '2' (код 220) у первой машинки и '3' (код 2210) у второй. Количество оставшихся цифр у первой машинки 5 (...00010) и 6 (...000010) у второй отличаются как раз на 1. Очевидно, что формат такой: количество элементов, далее идут сами элементы и некий суффикс "010" одинаковый для обеих машинок. Немного поигрался с этим суффиксом и выяснил что "10" это тоже список из 1 элемента.
Получалось, что два списка - это описания секций камеры и некое число 0 между ними. Дальше пошел разбираться с форматом элементов этих списков. Поменял последний 0 на 1, получил сообщение "unexpected end of input". Добавил еще 0 сообщение ушло. Получалось, что элементы - это тоже списки. Короче говоря, через полчасика разобрался, что элементы - это номера баков, связанных с соответствующей секцией, и кодируются они так:
0 бак: 0
1 бак: 10
2 бак: 11
3 бак: 12
4 бак: 22000
5 бак: 22001
В принципе больше 6 баков не бывает, но ради интереса поигрался дальше и понял, что числа тут кодируются так: количество цифр и сами цифры. Т.е. 220:01 значит 2 цифры, и цифры эти 01. Эти 01 надо добавить к базе. Проверил, что 22022 и 2210001 -- это действительно 12 и 14. Вот такая вот кодировка. Как потом оказалось, она же используется для кодирования чисел в топливе, так что числа больше 5 мне все-таки пригодились.
Не совсем правда понятно, зачем понадобилось делать еще одну кодировку для чисел. Наверно просто для запутывания. Хорошо, что они не догадались для нижнего пайпа сделать еще одну кодировку :-)
Пошел писать парсилку машины и ее печать в удобочитаемом формате. В результате для 12200010 выдавалось что-то типа:
Car: 122000010
chambers N=1 {
chamber #0 {
upper_pipe(2): 0 0
main=1
lower_pipe(1): 0
}
}
Теперь можно было подумать, какое подойдет топиво к такой машине. Как было понятно из задания, на вход системы поступает вектор неких чисел (air). Проходя по пайпу вектор умножается на матрицы характеризующие топливо в i-том баке. на выходе должно соблюдаться условие out_high(i) >= out_low(i), а для главной камеры (main chamber) кроме того должно быть out_high(1) > out_low(1).
Да уж. Похоже предстояло решать систему матричных неравенств :-)
Времени до конца воскресенья оставалось немного. Я понимал, что все что будет сделано завтра очков уже почти не принесет. Надо делать всё по максимуму сегодня. Решил начать со скалярного случая.
Пусть нам дана например такая машина:
upper pipe: 0 1 1 2 2
lower pipe: 0 0 1 2
цифры -- это, соответсвенно номера баков секций в верхнем и ниэнем пайпах. Нужно найти коэффициенты топлив во всех трех баках, так чтобы c0*c1*c1*c2*c2*x > c0*c0*c1*c2*x
Достаточно очевидно, что нужно найти бак, который используется больше в верхнем пайпе и дать ему любой коэффициент больше 1, а всем другим пайпам назначить коэффициенты 1. Т.е. топливо [1, 2, 1] должно подойти к такой машине, т.к. 1*2*2*1*1 >1*1*2*1.
А ведь еще бывают машины с несколькими камерами. Нужно чтобы для них тоже выполнялось такое неравенство. Думать дальше было некогда и я написал простую перебиралку коэффициентов от 1 до 10 для 1-6 баков -- всего то миллион комбинаций. Поставил еще ограничение, что если какой-то бак в верхнем пайпе встречается не чаше, чем в нижнем, то его коэффициент всегда 1.
Надо еще было разобрать формат топлива, но на это не ушло много времени. Оказалось, что формат тривиален. Количество баков, за ним описания для каждого бака: количество строк, столбцов и сами значения коэффициентов. У меня всегда были 1 строка и 1 столбец, так что топливо, например, для [1, 2, 1] выглядело так: 2210111011111110.
Т.е. 2210 (три бака) 1 1 (первый бак размер 1х1) 10 (коэффициент 1) 11 (второй бак 1х1) 11 (коэффициент 2) 11 (третий бак 1х1) 10 (коэффициент 1).
Написав соответствующую генерилку топлива, поставил сабмититься топлива для опубликованных на тот момент машин. Всё, больше сил держаться уже не было -- пошел спать. Продолжение