icfpc 2010
Внезапно, решил поучастовать. Внезапно, оно кончилось. Поставленная задача - ненулевой результат - достигнута.
Первой ошибкой было то, что я почему-то решил, что начнётся оно в 21.00 по мск - как в прошлом году. Заглянув на оффсайт в это время, обломался - всё уже шло 5 часов как.
Прочитал задание и остался с мыслью, что всё это как-то неправильно. "Попытайтесь понять, что мы хотели сказать".
Суть была такова: есть машинки, описываемые непонятно как набором троичных цифр. Есть топливо, описываемое аналогично. Нужно делать топливо. только ручками его делать нельзя, нужно строить фабрики из троичных элементов (2 входа, 2 выхода, логика неизвестна)
Два часа дико тупил и не мог понять, как именно из гейтов собирается схема (не знаю, что на меня нашло, там всё было просто - входы до разделителя, выходы после. но два часа я таки протупил), и, соответственно, весьма обрадовался когда таки осознал как оно записывается. В это время появляется уже человек 10-сабмиттеров.
после этого первым делом написал генератор графвизовских графов по входной фабрике. Затем подумал, и нарисовал схему из одного элемента. Подсмотрел вход сервера (тот самый, что по Х::Х, да), написал брутфорсер матриц логического элемента. Люто, бешенно охренел, когда брутфорсер отработал за 10 секунд, выдав тысячи 4 набора-кандидата. Сгенерил схему из двух элементов, и добавил её в качестве ещё одной проверки в брутфорсе - выдало уже одного кандидата. Проверил по разным каналам значения в трех точках - со всеми сошлось.
Осознал эту логику как правильную. написал класс Gate. После этого написал интерпретатор фабрик, и отвалился спать.
На второй день свободного времени было мало, но написал генератор случайных схем из n элементов. Потом чертыхнулся и полез переписывать весь код. Поскольку времени было мало, этим день и ограничился. Уходя спать, включил генератор и начал отсеивать фабрики, чей выход совпадал с выходом фабрики образца (я, идиот. думал, что это и есть ключ). К утру, однако, полных совпадений не было.
Третий день начался с того, что я начал генерить разные трех- и четырехэлементные схемы. Одной из наиболее полезных с моей точки зрения оказалась четырехэлементная константа 2. после чего воспаленное сознание придумало следующую схему фабрики:
Входной поток просто сжигается в такой константе и в дальнейшем алгоритме не участвует.
Строится генератор единичек.
для каждой цифры входа строится агрегат (отбрутфорсенный для 0, 1 и 2), который обладает одним одним входом, одним мусорным входом (в который можно писать что угодно) и двумя выходами. на один из выходов копируется вход (сей поток называется триггер), на второй выход - всё время нули, кроме первого такта, на котором триггер стал единицей, на нём агрегат выдаёт нужную цифру. в первый агрегат подоётся константа единиц, а в связи с расположением агрегатов на каждый следующий триггер будет приходить с задержкой на 1. т.е. у второго агрегата вход триггера будет 011111 и т.д.
после этого выходы всех агрегатов суммируются (сумматор - два входа, 2 выхода, 5 гейтов, отбрутфорсен. на один выход подаётся сумма, на второй - мусор какой-то, который можно сжигать в мусорных входах агрегатов), а поскольку ненулевое значение на каждом шаге будет выдавать только один агрегат, у которого на итерации произошла смена триггера, то сумма всех агрегатов выдаст искомую цифру. профит.
Примерно в это же время осознал истинное значение ключа и засабмиттил первое топливо к пресловутой 219 машине. После этого решил, что программа-минимум решена и можно пойти спать.
С утречка пытался понять структуру топлива, но ничего не получилось. Т.е. написал генератор фабрик для топлива длины 20 со случайным содержанием и автосабмиттер для них. но ничего интересного не получилось, только разные ошибки. За сим и завершил выступление
0,118 i13
Первой ошибкой было то, что я почему-то решил, что начнётся оно в 21.00 по мск - как в прошлом году. Заглянув на оффсайт в это время, обломался - всё уже шло 5 часов как.
Прочитал задание и остался с мыслью, что всё это как-то неправильно. "Попытайтесь понять, что мы хотели сказать".
Суть была такова: есть машинки, описываемые непонятно как набором троичных цифр. Есть топливо, описываемое аналогично. Нужно делать топливо. только ручками его делать нельзя, нужно строить фабрики из троичных элементов (2 входа, 2 выхода, логика неизвестна)
Два часа дико тупил и не мог понять, как именно из гейтов собирается схема (не знаю, что на меня нашло, там всё было просто - входы до разделителя, выходы после. но два часа я таки протупил), и, соответственно, весьма обрадовался когда таки осознал как оно записывается. В это время появляется уже человек 10-сабмиттеров.
после этого первым делом написал генератор графвизовских графов по входной фабрике. Затем подумал, и нарисовал схему из одного элемента. Подсмотрел вход сервера (тот самый, что по Х::Х, да), написал брутфорсер матриц логического элемента. Люто, бешенно охренел, когда брутфорсер отработал за 10 секунд, выдав тысячи 4 набора-кандидата. Сгенерил схему из двух элементов, и добавил её в качестве ещё одной проверки в брутфорсе - выдало уже одного кандидата. Проверил по разным каналам значения в трех точках - со всеми сошлось.
Осознал эту логику как правильную. написал класс Gate. После этого написал интерпретатор фабрик, и отвалился спать.
На второй день свободного времени было мало, но написал генератор случайных схем из n элементов. Потом чертыхнулся и полез переписывать весь код. Поскольку времени было мало, этим день и ограничился. Уходя спать, включил генератор и начал отсеивать фабрики, чей выход совпадал с выходом фабрики образца (я, идиот. думал, что это и есть ключ). К утру, однако, полных совпадений не было.
Третий день начался с того, что я начал генерить разные трех- и четырехэлементные схемы. Одной из наиболее полезных с моей точки зрения оказалась четырехэлементная константа 2. после чего воспаленное сознание придумало следующую схему фабрики:
Входной поток просто сжигается в такой константе и в дальнейшем алгоритме не участвует.
Строится генератор единичек.
для каждой цифры входа строится агрегат (отбрутфорсенный для 0, 1 и 2), который обладает одним одним входом, одним мусорным входом (в который можно писать что угодно) и двумя выходами. на один из выходов копируется вход (сей поток называется триггер), на второй выход - всё время нули, кроме первого такта, на котором триггер стал единицей, на нём агрегат выдаёт нужную цифру. в первый агрегат подоётся константа единиц, а в связи с расположением агрегатов на каждый следующий триггер будет приходить с задержкой на 1. т.е. у второго агрегата вход триггера будет 011111 и т.д.
после этого выходы всех агрегатов суммируются (сумматор - два входа, 2 выхода, 5 гейтов, отбрутфорсен. на один выход подаётся сумма, на второй - мусор какой-то, который можно сжигать в мусорных входах агрегатов), а поскольку ненулевое значение на каждом шаге будет выдавать только один агрегат, у которого на итерации произошла смена триггера, то сумма всех агрегатов выдаст искомую цифру. профит.
Примерно в это же время осознал истинное значение ключа и засабмиттил первое топливо к пресловутой 219 машине. После этого решил, что программа-минимум решена и можно пойти спать.
С утречка пытался понять структуру топлива, но ничего не получилось. Т.е. написал генератор фабрик для топлива длины 20 со случайным содержанием и автосабмиттер для них. но ничего интересного не получилось, только разные ошибки. За сим и завершил выступление
0,118 i13