Гольф Патерсонс Вормс

11

Черви Патерсона - это своего рода клеточный автомат, который существует на бесконечной треугольной сетке и на каждом шагу поворачивается в каком-то направлении и перемещается на одну единицу. Их определяющие свойства заключаются в том, что они никогда не могут пересечь одно и то же место дважды, и, когда они сталкиваются с одним и тем же окружением, они принимают одно и то же решение. Червь всегда «видит» со своей точки зрения, его хвост расположен в 3, а его голова расположена в центре этого шестиугольника:

Изображение из Википедии

Например, рассмотрим червя с правилами:

  1. Если 0, 1, 2, 4 и 5 не заполнены, двигайтесь в направлении 2
  2. Если 0, 1, 4 и 5 не заполнены, а 2 заполнено, двигайтесь в направлении 0
  3. Если 0, 1 и 5 не заполнены, а 2 и 4 заполнены, двигайтесь в направлении 0

Это приводит к следующему пути (из Википедии):

Червячная тропа

Если червь оказывается в ситуации, когда все окружение заполнено, он прекращается.

вход

Список номеров. Девятое число указывает, какое решение червь должен принять в n-й новой ситуации, с которой он сталкивается, когда ему необходимо принять решение. Обратите внимание, что если все окружения, кроме одного, заполнены, он должен двигаться в единственном пустом направлении. Это не считается «решением» и не потребляет число. Для генерирования примера червя, показанного выше, ввод будет [2, 0, 0]. На входе гарантированно создается червь, который завершает и не отслеживает свой путь, и вход никогда не будет слишком коротким.

Выход

Выведите список координат, указывающих, где находится голова червя, начиная с (1, 0). Мы будем рассматривать перемещение вверх и вправо как уменьшение только значения y, а перемещение вверх и влево - уменьшение значения x и уменьшение значения y. Например, выходной путь для примера ввода

(1, 0), (1, 1), (0, 0), (-1, -1), (0, -1), (0, 0), (0, 1), (-1, 0), (0, 0)

Контрольные примеры

Вы также можете использовать фрагмент javascript для запуска тестов.

[2,0,0]: (1,0),(1,1),(0,0),(-1,-1),(0,-1),(0,0),(0,1),(-1,0),(0,0)
[1,0,4,0,1,5]: (1,0),(2,1),(2,2),(1,2),(0,1),(0,0),(0,-1),(1,-1),(2,0),(2,1),(3,1),(4,2),(4,3),(3,3),(2,2),(1,1),(1,0),(2,0),(3,1),(3,0),(4,0),(5,1),(5,2),(4,2),(3,2),(2,1),(1,1),(0,0),(-1,0),(-2,-1),(-2,-2),(-1,-2),(0,-1),(1,0),(1,-1),(2,-1),(3,0),(4,1),(4,2),(5,3),(5,4),(4,4),(3,3),(3,4),(2,4),(1,3),(1,2),(1,1),(0,1),(-1,0),(-1,1),(-2,1),(-3,0),(-3,-1),(-2,-1),(-1,-1),(0,0)
[1,0,5,1]: (1,0),(2,1),(2,2),(1,2),(0,1),(0,0),(0,-1),(1,-1),(2,0),(2,1),(3,2),(3,3),(2,3),(1,2),(0,2),(-1,1),(-1,0),(0,0),(1,1),(1,2),(1,3),(0,3),(-1,2),(-1,1),(-2,0),(-2,-1),(-1,-1),(0,0)
[2,0,1,0]: (1,0),(1,1),(0,0),(-1,-1),(0,-1),(0,0),(-1,0),(-1,-1),(-1,-2),(0,-1),(1,0),(2,1),(1,1),(0,1),(0,0)

Следующая наскоро собранная (возможно, с ошибками) программа отобразит червей:

soktinpk
источник
2
Предлагаемый тестовый пример : p (Это [1,0,4,2,0,1,5].)
Арнаулд
Можем ли мы принять вход в обратном порядке?
Арно
1
@Arnauld уверен, что, кажется, хорошо
soktinpk

Ответы:

4

JavaScript (ES6),  261 250  249 байт

Принимает список ввода в обратном порядке. Возвращает список пар .[Икс,Y]

a=>(G=[[[x=1]]],v=[0,1,1,0,-1,-1],F=y=>[[x,y],...v.every((_,i)=>k^=g(o+i)[q%3]<<i,k=63,g=o=>(r=G[Y=y-o%2*v[q=(o+3)%6]]=G[Y]||[])[X=x-o%2*v[-~q%6]]=r[X]||[])?F(y+v[g(o+=F[k]|=1/F[k]?0:k&~-k?a.pop():31-Math.clz32(k))[q%3]=1,o%6],x+=v[-~o%6]):[]])(o=0)

Попробуйте онлайн!

По сути это порт демонстрационного фрагмента.

Arnauld
источник
4

К (нгн / к) , 115 байт

D,:-D:2\6 3;f:{d::0;m::2/=6;X::(!6),x;{m::?m,p:2/^(+':x)?(2*h:*|x)+/:D 6!d+!6;$[(~p)|^c:X m?p;x;x,,h+D 6!d+:c]}/,1 0}

(не считая части именования функций, f:)

Попробуйте онлайн!

D,:-D:2\6 3 генерирует шесть основных направлений (1 0;1 1;0 1;-1 0;-1 -1;0 -1)

d::0 текущее направление, используемое в качестве индекса мод 6 в D

m::2/=6генерирует начальную память червя 32 16 8 4 2 1. биты каждого числа кодируют окружение (0 = посещенный сегмент; 1 = не посещенный). изначально mсодержит только однозначное окружение - то, в котором доступен единственный выход.

X::(!6),xправила червя мы собираемся 0 1 2 3 4 5соответствовать первоначальной однозначной обстановке в m.

{... }/,1 0применять до сходимости функцию, { }начиная с 1-элементного списка, содержащего 1 0. список будет содержать пары координат, которые посетил червь.

D 6!d+!6шесть основных направлений, начиная с dи по часовой стрелке

h:*|x последний аргумент, то есть положение головы червя

(2*h:*|x)+/:D 6!d+!6умножьте координаты головы на 2 и добавьте кардинальные направления. это наш способ представления отрезков между точками.

+':x добавить пары соседних посещенных точек - это дает нам представление сегментов между ними

^(... )?... выяснить, какие из окружающих сегментов головы еще не посещены

p:2/ двоичное кодирование и присвоение p

m::?m,pДобавлять в mи сохранить отчетливый, т.е. Append , pчтобы mтолько тогда , когда pне происходит вm

$[... ;... ;... ]если-то-еще

c:X m?pнайти индекс pв mи использовать его в качестве индекса в X. результаты индексации за пределами допустимого диапазона 0N("null")

$[(~p)|^c:X m?p;x;... ]если p0 (нет пути выхода) или cесть 0N, то return, xчто приведет к сходимости и остановит цикл

x,,h+D 6!d+:cеще добавить новую голову xи повторить

СПП
источник