Строить / разбирать параллельно кучей ботов

[portnov]

При постройке слоя:

• определить сколько строк в этом слое (N)
• родить min(N, 40) ботов, выдать каждому по строке, поставить каждого в левый (правый) конец строки
• двигать ботов и красить параллельно. Если бот уже дошёл до конца своей строки, пусть ждёт.
• перейти к следующей пачке строк
• собрать ботов

Для сборки, видимо, понадобится pathfinding.

[ForNeVeR]

Мои наработки смержены в master. Запускал код я так:

$ stack build && stack exec -- icfpc2018-exe parallel .\problemsF\FA001_tgt.mdl FA001.nbt

Я решил реализовать такой алгоритм:

• подняться всеми ботами на нужный уровень
• форкнуться из начального бота и более-менее равномерно развести дочерних ботов по линиям на модели
  • протестировал на двух ботах, нужно отключить ограничение N = 2 в функции getPreferredTotalBotCount
  • при этом нужно распределять линии между ботами так, чтобы самые первые созданные боты получали линии, самые далёкие от начального бота. Это нужно для того, чтобы два бота никогда не заходили на одну и ту же линию. Кажется, для этого достаточно добавить reverse в функцию getAssignedLines — она управляет раздачей линий ботам.
  • в getAssignedLines сейчас линии распределяются не равномерно — я сделал, чтобы всем дочерним ботам просто отдавалась пачка последних линий. Это неправильно, надо сделать чтоб раздавались равномерно.
  • для перемещения построенных ботов я использовал функцию move — это неправильно, т.к. она вызывает step слишком много раз. Идея, как это исправить: в функциях childBotAdjustActions и rootBotAdjustAction можно заменить move на добавление одного сегмента пути. А на следующий вызов продолжить перемещение, и так по шагам доехать ботами куда нужно. Для этого всё готово, нужно только выпилить move и заменить на генерацию правильных команд (грубо говоря, там нужно подставлять первую команду из того списка, который скопом добавляет move).
• после этого боты должны параллельно построить слой. При этом, если бот добрался до конца линии, и на соседней с ним линии нет ни одного бота — он должен сам начинать её строить. Это важно, т.к. на одного бота может приходиться больше одной линии. Это и есть т.н. «змейка».
• когда все работы по слою завершены, нужно смержить лишних ботов (в случае, если следующий слой имеет меньше рабочих линий, чем текущий, и эти боты нам на следующем слое будут мешаться). Изначально по окончании работ каждый бот сидит на своей линии, так что они смогут по ней беспрепятственно перемещаться. Поэтому я придумал такую тактику:
  • разбиваем всех ботов на чётных и нечётных, N первых нечётных собираемся удалить
  • нечётные подходят к чётным (дожидаемся, пока все подойдут)
  • нечётные вмерживаются в чётных
  • если после этого ещё остались боты, которых нужно убрать, повторяем операцию, повторно разделяя выживших на чётных и нечётных
• в самом конце этим же способом объединяем вообще всех ботов за ln₂(N) итераций
• уезжаем по кромочке карты и выключаем бота

Тудушки для основных фаз алгоритма оставлены в файле ParallelAlgorithms.hs.

Нулевой бот в моём алгоритме считается особенным, т.к. именно из него все форкаются. Я не придумал, как бы поудачнее управлять сидами, чтобы ничего при этом не сломалось и боты не начали сталкиваться, передавая сиды друг другу. ⚠ Над этим надо подумать, потому что, похоже, без этого не будет нормально работать фаза, на которой мы делаем Fusion.

К сожалению, я не продумал, как мы в данном алгоритме будем контролировать гармоники. Можно эту ответственность переложить на того же первого бота. Если любой из ботов собирается создать ячейку, которая не будет заземлена — первый бот должен переключить гармонику.

[ForNeVeR]

Ну и там весь код сейчас обмазан unsafePerformIO — за это извиняюсь, но я не смог найти способа сделать через Debug.Trace нормально (вывод отладочных данных на одной строке с текстовой меткой): они у меня постоянно путались и перемежались из-за ленивых вычислений.