ICFP Contest 2010: день второй
Отчет о первом дне в предыдущем посте.
Проснувшись утром часов в 11 за чашкой чая начал опять думать как же соединять эти гейты. Ничего не придумывалось. Где-то глубоко в мозгу возникали мысли про брутфорс, но я их отметал, понимая, что потом придется генерить достаточно длинные топлива, и всё равно придется придумывать генерилку топлива произвольной длины.
После, наверно, часа безуспешных попыток что-либо придумать, прикинул, что префикс длиной 17 тритов имеет 3^17 комбинаций (т.е. порядка 10^8).
В то же время из n гейтов можно составить 2n*(2n)! разных схем.
Т.е. из 5 гейтов можно составить 10*10! = 36288000 ~ 3*10^7
А из 6 гейтов аж 12*12! = 5748019200 ~ 5*10^9
Теория вероятностей давала надежду, что уж с помошью 6 гейтов префикс точно получится. На удивление быстро накропал брутфорсилку (да, почти всё писалось на голом C) и через 5 минут ее работы получил схему для префикса:
4L:
3L1L0#5R1R,
2L0R0#0R3R,
5R3R0#1L4R,
4R1R0#0L2R,
X2R0#5L3L,
4L0L0#X2L:
5L
Префикс был тут же скормлен серверу и... УРА! Я получил первые 0.003 очков и перестал чувствовать себя полным лузером :-)
Это всё было хорошо, но все равно надо было придумывать генерилку топлив. Видимо начавшие капать очки меня как-то вдохновили и наконец-то пришла долгожданная мысль как можно делать фабрики по заданному выходу. В голову пришло индуктивное решение. Сделать блок, который генерит нужную цифру, а затем повторяет свой вход. Обрадовавшись идее, которую я так долго ждал, я тут же бросился ее реализовывыть, а, как потом выяснилось, зря. Надо было еще совсем чуть-чуть подумать над ее оптимизацией.
Скормив брутфорсеру пары вход-выход вида:
01202101210201202
00120210121020120
01202101210201202
10120210121020120
01202101210201202
20120210121020120
я практически мгновенно получил нужные блоки. Вот они родимые:
0-and-repeat:
1L:
1L2R0#X2R,
X2L0#0L2L,
1R0R0#1R0R:
0L
1-and-repeat:
2L:
2R1R0#2R1R,
2L0R0#X0R,
X0L0#1L0L:
1L
2-and-repeat:
2R:
2R1R0#2L1L,
0R2L0#X0R,
0LX0#1R0L:
1L
Все они оказались размером всего по три гейта. Пошел писать генерилку фабрик по заданному выходу. По пути написания генерилки пришлось съездить в магазин за едой, ибо жена очень просила. :-)
Когда генерилка была готова, можно было начинать разбираться собственно с форматом топлива. В качестве тестового образца была выбрана машинка номер 2416 aka 122000010.
Начал засылать разные варианты топлив, получая разные ответы:
0000000000000
you have produced fuel
for 0 tanks
using 0 ingredients of air
-- ну понятно. ноль -- он и в Африке ноль.
1000000000000
for 1 tanks
using 0 ingredients of air
-- вот и единичка есть. хорошо.
2000000000000
parse error in fuel description
"input" (line 1, column 2):
unexpected token
expecting: '2'
-- тут что-то пока непонятное, но хочет вторую двойку. Дадим.
2200000000000
for 2 tanks
using 0 ingredients of air
-- ага 2 танка.
1100000000000
for 1 tanks
using 1 ingredients of air
dimension mismatch
-- ага две единицы. Значит скорее всего 1 кодируется просто как 1. И первым идет количество танков ака баков, вторым количество ингредиентов топлива.
дальше попробовал добавить еще единиц:
1110000000000
for 1 tanks
using 1 ingredients of air
check fuel for tank 0
c_{1,1} must be >= 1
-- хм. Добавим еще
1111000000000
for 1 tanks
using 1 ingredients of air
checking reaction chamber 0
first fuel component must increase
-- и еще...
1111100000000
you have produced fuel
for 1 tanks
using 1 ingredients of air
checking reaction chamber 0
Good! The car can use this fuel.
-- АГА!!!
Так, вобщем-то случайно, получилось еще одно топливо, которое подошло к достаточно большому количеству машин. На него кстати уходило (17+5)*3=66 гейтов.
Дальше за 10-15 минут получил табличку для первых чисел:
0: 0
1: 1
2: 220
3: 2210
4: 2211
5: 2212
6: 2222000
7: 2222001
8: 2222002
9: 2222010
10: 2222011
11: 2222012
12: 2222020
13: 2222021
14: 2222022 15: 222210000
16: 222210001
...
41: 222210222 42: 2222110000 ... 122: 2222112222 123: 22221200000 124: 22221200001 ... 365: 22221222222
366: 222222000000000
367: 222222000000001Получалось, что префикс вида (22)+[01][012]* в начале числа задает количество цифр и базу, потом идет N тритов с цифрами с добавкой к базе.
На этом второй день незаметно подошел к концу...
День третий
Проснувшись утром часов в 11 за чашкой чая начал опять думать как же соединять эти гейты. Ничего не придумывалось. Где-то глубоко в мозгу возникали мысли про брутфорс, но я их отметал, понимая, что потом придется генерить достаточно длинные топлива, и всё равно придется придумывать генерилку топлива произвольной длины.
После, наверно, часа безуспешных попыток что-либо придумать, прикинул, что префикс длиной 17 тритов имеет 3^17 комбинаций (т.е. порядка 10^8).
В то же время из n гейтов можно составить 2n*(2n)! разных схем.
Т.е. из 5 гейтов можно составить 10*10! = 36288000 ~ 3*10^7
А из 6 гейтов аж 12*12! = 5748019200 ~ 5*10^9
Теория вероятностей давала надежду, что уж с помошью 6 гейтов префикс точно получится. На удивление быстро накропал брутфорсилку (да, почти всё писалось на голом C) и через 5 минут ее работы получил схему для префикса:
4L:
3L1L0#5R1R,
2L0R0#0R3R,
5R3R0#1L4R,
4R1R0#0L2R,
X2R0#5L3L,
4L0L0#X2L:
5L
Префикс был тут же скормлен серверу и... УРА! Я получил первые 0.003 очков и перестал чувствовать себя полным лузером :-)
Это всё было хорошо, но все равно надо было придумывать генерилку топлив. Видимо начавшие капать очки меня как-то вдохновили и наконец-то пришла долгожданная мысль как можно делать фабрики по заданному выходу. В голову пришло индуктивное решение. Сделать блок, который генерит нужную цифру, а затем повторяет свой вход. Обрадовавшись идее, которую я так долго ждал, я тут же бросился ее реализовывыть, а, как потом выяснилось, зря. Надо было еще совсем чуть-чуть подумать над ее оптимизацией.
Скормив брутфорсеру пары вход-выход вида:
01202101210201202
00120210121020120
01202101210201202
10120210121020120
01202101210201202
20120210121020120
я практически мгновенно получил нужные блоки. Вот они родимые:
0-and-repeat:
1L:
1L2R0#X2R,
X2L0#0L2L,
1R0R0#1R0R:
0L
1-and-repeat:
2L:
2R1R0#2R1R,
2L0R0#X0R,
X0L0#1L0L:
1L
2-and-repeat:
2R:
2R1R0#2L1L,
0R2L0#X0R,
0LX0#1R0L:
1L
Все они оказались размером всего по три гейта. Пошел писать генерилку фабрик по заданному выходу. По пути написания генерилки пришлось съездить в магазин за едой, ибо жена очень просила. :-)
Когда генерилка была готова, можно было начинать разбираться собственно с форматом топлива. В качестве тестового образца была выбрана машинка номер 2416 aka 122000010.
Начал засылать разные варианты топлив, получая разные ответы:
0000000000000
you have produced fuel
for 0 tanks
using 0 ingredients of air
-- ну понятно. ноль -- он и в Африке ноль.
1000000000000
for 1 tanks
using 0 ingredients of air
-- вот и единичка есть. хорошо.
2000000000000
parse error in fuel description
"input" (line 1, column 2):
unexpected token
expecting: '2'
-- тут что-то пока непонятное, но хочет вторую двойку. Дадим.
2200000000000
for 2 tanks
using 0 ingredients of air
-- ага 2 танка.
1100000000000
for 1 tanks
using 1 ingredients of air
dimension mismatch
-- ага две единицы. Значит скорее всего 1 кодируется просто как 1. И первым идет количество танков ака баков, вторым количество ингредиентов топлива.
дальше попробовал добавить еще единиц:
1110000000000
for 1 tanks
using 1 ingredients of air
check fuel for tank 0
c_{1,1} must be >= 1
-- хм. Добавим еще
1111000000000
for 1 tanks
using 1 ingredients of air
checking reaction chamber 0
first fuel component must increase
-- и еще...
1111100000000
you have produced fuel
for 1 tanks
using 1 ingredients of air
checking reaction chamber 0
Good! The car can use this fuel.
-- АГА!!!
Так, вобщем-то случайно, получилось еще одно топливо, которое подошло к достаточно большому количеству машин. На него кстати уходило (17+5)*3=66 гейтов.
Дальше за 10-15 минут получил табличку для первых чисел:
0: 0
1: 1
2: 220
3: 2210
4: 2211
5: 2212
6: 2222000
7: 2222001
8: 2222002
9: 2222010
10: 2222011
11: 2222012
12: 2222020
13: 2222021
14: 2222022 15: 222210000
16: 222210001
...
41: 222210222 42: 2222110000 ... 122: 2222112222 123: 22221200000 124: 22221200001 ... 365: 22221222222
366: 222222000000000
367: 222222000000001Получалось, что префикс вида (22)+[01][012]* в начале числа задает количество цифр и базу, потом идет N тритов с цифрами с добавкой к базе.
На этом второй день незаметно подошел к концу...
День третий