?

Log in

No account? Create an account

Entries by category: общество

Избирательный участок

В нашем часовом поясе выборы уже начались. Оказалось, что участок открылся даже на нашем острове. Из любопытства съездили посмотреть.



немножко фотокCollapse )

Ехать на выборы тут надо через джунгли да через горы. Дорога между недавно открывшимся почетным консульством и моим домом:
Мы были еще подростками, недавно поступившими в универ, посмотрели Матрицу, 13-й Этаж и Экзистенцию, почитали Д.Т. Судзуки, геше Тинлея и других популярных авторов за буддизм, и много часов провели в ГЗ-шной столовке за обсуждениями всех этих тем о взаимоотношении ума и реальности... Сейчас наткнулся на 20-минутное выступление, где калифорнийский когнитивный учоный все те же телеги толкает (что в текстах Нагарджуны и Дхармакирти), одновременно капитанские и провокационные, но заходя внезапно со стороны эволюции и симуляционных экспериментов. Парочка анекдотов и метафор у него хорошо вышли..

https://www.ted.com/talks/donald_hoffman_do_we_see_reality_as_it_is

Hextris

В эти выходные прошло соревнование ICFPC - волшебная пора, когда все функциональные программисты мира (все 800!) могут оторваться от своей дневной работы на джаве, С++ или РНР и на три дня представить, что их любимый язык все-таки где-то применим.

В этом году надо было сделать свой решатель тетриса, но хексагонального, с занятной неевклидовой геометрией (движение фигуры по прямой не сохраняет взаимное расположение частей в их координатах относительно друг друга, движения и повороты работают по-разному в зависимости от места происходящего).
gif, 1.6 MBCollapse )
К этому сверху был прилеплен поиск и использование волшебных заклинаний ("ктулху фхтагн бешельме чернмернда") - каждый ход кодируется одним из нескольких возможных символов, если из этих символов в решении складывается какое-нибудь заклинание, за это дают дополнительные очки, и, видимо, много. Я как обычно участвовал без ансамбля, поэтому на заклинания совсем забил, занимался только тетрисом. За первый день сделал логику игры (загрузка данных, движения фигур, сжигание рядов, подсчет очков) с визуализацией и ручным управлением, можно было играть самому, а также прогнать пример от организаторов и убедиться, что все работает. Все получалось довольно гладко, разве что на поворот фигур потратил неожиданно много времени: гуглить готовые подходы не стал, хотя понимал, что наверняка известны какие-нибудь красивые подходы с трехмерными координатами. Стал придумывать сам, но формулу для преобразования координат при повороте не придумал, вместо этого сделал табличку (отображение разных координат при повороте), заполнявшуюся индуктивно: точка, вокруг которой идет поворот, не меняется, ее ближайшие 6 соседей меняются местами циклично, а дальше если для какой-то клетки знаешь, как при повороте двигается ее ближайший сосед, то ее движение состоит из такого же ровно сдвига (вместе с тем соседом) плюс поворот вокруг этого ближайшего соседа, такой поворот уже известно как делается.

На второй день стал придумывать стратегию для игры, и в течение второго и третьего дней ее постепенно реализовал (как-то не очень быстро каменный цветок выходил). Работало все следующим образом. Когда очередная фигура появляется на поле, понятно, что остановиться ей надо будет или где-то непосредственно рядом с уже имеющимися заполненными клетками, или рядом со стеной (краем уровня). Очки дают за сжигание полностью заполненных горизонтальных рядов, поэтому нас интересует соседство горизонтальное прежде всего. Поэтому в самом начале игры для каждой фигуры, для всех ее поворотов, были составлены списки точек, которыми она может касаться горизонтально. Когда фигура появляется на поле, надо пройтись по всем пустым горизонтальным соседям уже имеющихся на поле объектов и примерить к ним текущую фигуру по тем спискам потенциальных точек соприкосновения, т.е. перебирать все-все возможные ее положения не нужно, лишь те, где ожидаются касания. Для каждой такой потенциальной позиции приземления оценивается ее привлекательность: приведет ли ее занятие к полному заполнению каких-нибудь горизонтальных рядов (и их количество), если нет, то для каждого горизонтального ряда занимаемой позиции оценивается наибольшее количество получающихся заполненных подряд клеток (больше - лучше), плюс поправка на высоту: сжигать ряды лучше те, что выше, а вставать на пока еще незаполненные лучше пониже. Чуть позже был добавлен еще один фактор: сравнивалось количество "пузырей" (недостижимых сверху пустых клеток, т.к. фигуры могут двигаться лишь вбок и вниз, но не вверх) до и после занятия позиции, образование новых "пузырей" пенализируется, снижает оценку привлекательности позиции. Оценив все эти потенциальные позиции для приземления фигуры и отсортировав их по привлекательности, первая версия брала первую достижимую из них (для которой найдется путь от исходного положения фигуры). Это дало смешной результат: т.к. часто вращение фигуры на некоторые углы отображает ее в себя, позиции с такими углами поворота получают одинаковую оценку, и после сортировки по оценке первой часто попадалась позиция повернутая, в результате фигура перед ее занятием делала ненужные вращения, что по условиям задачи чревато обнулением очков. Поэтому вместо первой достижимой позиции из отсортированного списка брался набор позиций с одинаковыми оценками и из них выбирался вариант с кратчайшим путем, это отсекало ненужные вращения. Поиск пути был простым А* в трехмерном пространстве (x,y,угол), в процессе поиска строится множество достижимых позиций, в котором для каждой клетки сказано, как туда попали. Если для какой-то интересующей нас позиции путь не нашелся, то значит поиск пути перебрал все достижимые клетки карты, и при поиске путей для других позиций уже ничего еще раз строить не нужно: если позиция достижима, она уже в нашем множестве достижимых, и путь к ней уже известен, а если ее там нет, то путь не существует. В итоге все работало мгновенно, как-то еще оптимизировать или усложнять поиск не понадобилось. Памяти процесс ел меньше 3 МБ на маленьких задачах и около 20 МБ на больших.

В последний день к описанной схеме был еще добавлен look-ahead: последовательность фигур известна заранее, поэтому вместо принятия решений лишь по текущей фигуре был сделан рекурсивный перебор на пару шагов вперед. Вместо того, чтобы брать наиболее привлекательную достижимую позицию, составлятся список из 5 лучших достижимых (с разными оценками, чтобы отсечь те, что отличаются лишь поворотами), для каждой из них моделируем что получится при ее выборе, рекурсивно ищем решение для следующей фигуры, так на несколько фигур вглубь (в будущее), в этом дереве вариантов для листьев выбирается максимум, он возвращается наверх и складывается с оценкой узла-родителя, из его таких сложенных вариантов выбирается максимум и передается наверх.. В итоге для текущей фигуры выбирается такое положение, которое дает максимальную сумму оценок для этой и нескольких следующих фигур. Например, если текущей фигурой можно сжечь один ряд и следующей можно будет сжечь еще один, но если сейчас один не сжигать, то следующая сможет сжечь оба, то будет выбран именно последний вариант, ибо за сжигание двух рядов сразу дают больше очков, чем за два сжигания по одному ряду. С таким look-ahead'ом все стало ощутимо медленнее, но все равно большинство задач обсчитывалось меньше чем за минуту, и чтобы обновить все решения мне понадобилось менее получаса. Писал на D, исходники на битбакете, 1200 строк включая гуй.

Вот, получилось довольно интересно, на мой взгляд. Поскольку заклинаниями не занимался, очков набрал не очень много, в общем зачете из 300+ зарегистрированных команд на 103 месте (в этот раз назвался Dr. Zoidberg).

Tags:

рисуем монаду

Сегодня в нашем кружке "теоркат для самых маленьких" урок рисования. Будем рисовать монаду. (А то весной кое-кто писал "если монаду нельзя нарисовать, то её нет".)

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

Она должна быть ассоциативной, т.е. (a*b)*c = a*(b*c):

Тут мы используем нечто вроде фейнмановских диаграмм, где время на рисунке идет снизу-вверх. В самом низу - что было, в самом верху - что получилось, в середине всякие превращения.Read more...Collapse )