В этом вызове вы будете считать «существ» в игре-плитке Palago.

Существо - это любая замкнутая форма, которая может быть сформирована из плиток Palago соответствующего цвета в шестиугольной сетке.

Игра Palago состоит из таких плиток:

Эти плитки могут вращаться на $120^\circ$ , $240^\circ$ или вообще не вращаться и размещаться в любом месте на шестиугольной сетке. Например, вот (красное) существо, которое требует 12 плиток.

Вызов

Цель этой задачи - написать программу, которая принимает целое число nв качестве входных данных и вычисляет количество существ (до вращения и отражения), которым требуются nплитки. Программа должна быть в состоянии обрабатывать до n=10на TIO . Это код-гольф , поэтому побеждает меньше байтов.

Пример данных

Значения должны соответствовать данным, найденным в разделе «Подсчет и оценка существ» на веб-сайте создателя . а именно

 n | output
---+-------
 1 | 0
 2 | 0
 3 | 1 
 4 | 0
 5 | 1
 6 | 1
 7 | 2
 8 | 2
 9 | 9
10 | 13
11 | 37
12 | 81

JavaScript (Node.js) , 480 417 байт

-63 байта благодаря @Arnauld. Вау.

n=>(E=(x,y,d,k,h)=>V[k=[x+=1-(d%=3),y+=~d%3+1,d]]?0:(V[k]=1,h=H.find(h=>h[0]==x&h[1]==y))?(d^(t=2-h[2])?E(x,y,t)||E(x,y,h[2]*2):E(x,y,t+2)):[x,y,0],I=c=>c.map(([x,y,t])=>[x-g(0),y-g(1),t],g=p=>Math.min(...c.map(h=>h[p]))).sort(),S=e=>(V={},e=E(0,0,0))?(--n&&H.pop(H.push(e),S(),S(e[2]=1),S(e[2]=2)),++n):n-1||E[I(c=H)]||[0,0,0,++N,0,0].map(r=>E[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1))(H=[[N=0,0,1]])&&N

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

Во-первых, респект Арно, чей ответ дал мне вдохновение копать глубже. Я изо всех сил старался быть оригинальным с моими алгоритмами, хотя я намеренно изменил часть своего кода, чтобы использовать те же переменные, что и Арно, чтобы было проще сравнивать код.

Поиск пустых гексов

Поиск существ - это:

• Инициализировать список тайлов с тайлом 1 на 0,0
• Рекурсивный:
  • Ищите пустой гекс, необходимый для завершения существа
  • Если найден пустой гекс
    • Добавьте каждый тип плитки 0,1,2 в пустой гекс и рекурсивно
  • Если пустой гекс не найден
    • Если существо правильного размера и его еще нет в зоопарке
      • Увеличивайте количество различных существ, найденных одним
      • Добавьте все повороты и отражения существа в зоопарк

Поиск пустых гексов открыл интересную симметрию. Арно обнаружил, что одно из шести направлений можно игнорировать, но на самом деле три из шести можно игнорировать!

Вот оригинальное направление Арнаулда и ключ тайла:

Представьте, что мы начинаем с плитки типа 1 с синей точки. Кажется, что мы должны вычеркнуть в d = 0 и d = 5. Однако, какой бы тайл не был размещен в d = 0, он обязательно будет иметь выход в d = 4, который посетит тот же гекс, что и выход из тайла A в d = 5. Это открытие Арно, и именно это заставило меня задуматься.

Заметить, что:

• Каждая плитка, у которой есть выход в d = 0, имеет выход в d = 5
• Каждая плитка, у которой есть выход в d = 2, имеет выход в d = 1

• Каждая плитка, у которой есть выход в d = 4, имеет выход в d = 3

• Каждая плитка, которую можно ввести с d = 0, имеет выход в d = 4

• Каждая плитка, которую можно ввести с d = 2, имеет выход с d = 0
• Каждая плитка, которую можно ввести из d = 4, имеет выход в d = 2

Это означает, что нам нужно учитывать только направления 0,2,4. Любые выходы в направлениях 1,3,5 могут быть проигнорированы, потому что гексы, достижимые в направлениях 1,3,5, могут быть достигнуты из соседнего гекса, используя направления 0,2 или 4.

Как это круто!?

Перемаркированные направления

Таким образом, я перемаркирую направления и тайлы вот так (отредактированное изображение Арно):

Теперь у нас есть следующие отношения между плитками, входами и выходами:

    |  t=0  |  t=1  |  t=2
----+-------+-------+-------
d=0 |  0,2  |  1,2  |    2
d=1 |  0,2  |    0  |  0,1
d=2 |    1  |  1,2  |  0,1

Итак, выходы: d + t == 2? (4-т)% 3: 2-т и 2 * т% 3

Гексагональные вращения и отражения

Для поворотов и отражений я решил использовать шестиугольные осевые координаты x, y вместо координат куба x, y, z.

-1,2   0,2   1,2   2,2
    0,1   1,1   2,1
 0,0   1,0   2,0   3,0

В этой системе вращение и отражение были проще, чем я ожидал:

120 Rotation:   x=-x-y   y=x   t=(t+1)%3
Reflection:     x=-x-y   y=y   t=(t*2)%3

Чтобы получить все комбинации, которые я выполнил: гнить, гнить, гнить, отражать, гнить, гнить

Код (оригинальный 480 байт)

f=n=>(
    // H:list of filled hexes [x,y,tile] during search for a complete creature
    // N:number of distinct creatures of size n
    // B:record of all orientations of all creatures already found
    H=[[0,0,1]],N=0,B={},

// E: find an empty hex required to complete creature starting in direction d from x,y
    E=(x,y,d,k,h)=>(
        x+=1-d,
        y+=1-(d+1)%3,
        // V: list of visited hexes during this search in E
        V[k=[x,y,d]] ? 
            0
        : (V[k]=1, h=H.find(h=>h[0]==x&&h[1]==y)) ? 
            // this hex is filled, so continue search in 1 or 2 directions
            (d==2-h[2] ? E(x,y,(4-h[2])%3) : (E(x,y,2-h[2]) || E(x,y,h[2]*2%3))) 
        : [x,y,0] // return the empty hex 
    ),

    // I: construct unique identifier for creature c by moving it so x>=0 and y>=0
    I=c=>(
        M=[0,1].map(p=>Math.min(...c.map(h=>h[p]))),
        c.map(([x,y,t])=>[x-M[0],y-M[1],t]).sort()
    ),

    // A: add complete creature c to B
    A=c=>{
        n==1&&!B[I(c)]&&(
            // creature is correct size and is not already in B
            N++,
            [0,0,0,1,0,0].map(
                // Add all rotations and reflections of creature into B
                // '0' marks a rotation, '1' marks a (vertical) reflection
                // rotation:   x=-x-y   y=x   t=(t+1)%3
                // reflection: x=-x-y   y=y   t=(t*2)%3
                r=>B[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1)          
        )
    },

    // S: recursively search for complete creatures starting with hexes H
    S=e=>{
        V={};
        (e=E(0,0,0)) ?
            // e is a required empty hex, so try filling it with tiles 0,1,2
            (--n && (H.push(e),S(),S(e[2]=1),S(e[2]=2),H.pop()), ++n)
        : A(H) // creature is complete, so add it to B
    },

    S(),
    N
)

Код (Арно, 417 байт)

Арно любезно предоставил 63-байтовое сохранение, в котором использовались трюки, на которые у меня ушло довольно много времени, чтобы обернуть голову. Поскольку в нем много интересных правок, я решил поместить его код ниже (я добавил свои комментарии), чтобы его можно было противопоставить моей версии.

f=n=>(
    // E:find an empty hex required to complete creature starting in direction d from x,y
    E=(x,y,d,k,h)=>
      V[k=[x+=1-(d%=3),y+=~d%3+1,d]] ?
        0
      :(V[k]=1,h=H.find(h=>h[0]==x&h[1]==y)) ?
        (d^(t=2-h[2]) ? E(x,y,t) || E(x,y,h[2]*2) : E(x,y,t+2))
      :[x,y,0],

    // I: construct unique identifier for creature c by moving it so x>=0 and y>=0
    I=c=>c.map(([x,y,t])=>[x-g(0),y-g(1),t],g=p=>Math.min(...c.map(h=>h[p]))).sort(),

    // S: recursively search for complete creatures starting with hexes H
    S=e=>
      (V={},e=E(0,0,0)) ?
        (--n&&H.pop(H.push(e),S(),S(e[2]=1),S(e[2]=2)),++n)
      :n-1
        ||E[I(c=H)] 
        // creature is the correct size and has not been seen before
        // so record all rotations and reflections of creature in E[]
        ||[0,0,0,++N,0,0].map(r=>E[I(c=c.map(([x,y,t])=>[-x-y,r?y:x,(r?t*2:t+1)%3]))]=1)
)
// This wonderfully confusing syntax initializes globals and calls S()
(H=[[N=0,0,1]]) && N

JavaScript (Node.js) ,  578 ... 433  431 байт

f=(n,T=[B=[N=0,0,0,1,1]])=>!n||T.some(([x,y,q,m])=>B.some((p,d)=>m>>d&1&&((p=x+~-s[d],q=y+~-s[d+2],t=T.find(([X,Y])=>X==p&Y==q))?(q=t[3])&(p=D[d*3+t[4]])^p?t[f(n,T,t[3]|=p),3]=q:0:[0,1,2].map(t=>f(n-1,[...T,[p,q,-p-q,D[d*3+t],t]])))),s="2100122",D=Buffer("160).(9!'8 &$<%"))|n>1||[0,1,2,1,2,0].some((_,d,A)=>B[k=T.map(a=>[(h=n=>Math.min(...T.map(R=a=>a[A[(d+n)%6]]))-R(a))(0),h(3),(x=(a[4]+d*2)%3,d>2)*x?3-x:x]).sort()])?N:B[k]=++N

$n=1$$n=13$

Как?

Направления и плитки

Мы используем следующие коды для компаса с 6 направлениями и плиток:

Мы предполагаем, что существо синее.

связи

Нам нужна таблица, чтобы знать, какие части существа должны быть связаны с другими плитками, когда мы входим в данную плитку в заданном направлении:

     |  T=0  |  T=1  |  T=2
-----+-------+-------+-------
 d=0 | 0,4,5 | 1,2,4 |   4
 d=1 | 0,3,5 | 1,2,3 |   3
 d=2 | 0,3,4 |   0   | 0,1,2
 d=3 | 3,4,5 |   5   | 1,2,5
 d=4 |   2   | 2,3,4 | 0,2,5
 d=5 |   1   | 1,3,4 | 0,1,5

Пример:

$1$$5$$1$$3$$4$

$5$

     |  T=0  |  T=1  |  T=2
-----+-------+-------+-------
 d=0 |  0,4  | 1,2,4 |   4
 d=1 |  0,3  | 1,2,3 |   3
 d=2 | 0,3,4 |   0   | 0,1,2
 d=3 |  3,4  |   -   |  1,2
 d=4 |   2   | 2,3,4 |  0,2

$+32$

     |  T=0  |  T=1  |  T=2              |  T=0  |  T=1  |  T=2
-----+-------+-------+-------       -----+-------+-------+-------
 d=0 |   17  |   22  |   16          d=0 |  "1"  |  "6"  |  "0"
 d=1 |    9  |   14  |    8          d=1 |  ")"  |  "."  |  "("
 d=2 |   25  |    1  |    7    -->   d=2 |  "9"  |  "!"  |  "'"
 d=3 |   24  |    0  |    6          d=3 |  "8"  |  " "  |  "&"
 d=4 |    4  |   28  |    5          d=4 |  "$"  |  "<"  |  "%"

После выравнивания это дает:

D = Buffer("160).(9!'8 &$<%")

Координаты

$x+y+z=0$

Кредиты: www.redblobgames.com

Это облегчит обработку поворотов и отражений на последнем шаге алгоритма.

Кодировка плитки

Плитки хранятся в списке без определенного порядка. Это означает, что нам не нужно беспокоиться о некотором динамическом распределении 2D, и мы можем легко перебирать существующие плитки. Недостатком является то, что с учетом конкретных координат нам нужна find()соответствующая плитка в списке.

$(x, y, z, m, t)$

• $(x, y, z)$
• $m$
• $t$$0$$1$$2$

Алгоритм

$1$$(0,0,0)$$0$

Следовательно, этот фрагмент закодирован как [0,0,0,1,1].

На каждой итерации мы ищем:

• Плитки с отсутствующими соединениями: в этом случае мы последовательно пытаемся завершить соединение с каждым типом плиток.

• Плитки, которые уже подключены, но для которых необходимо добавить новые подключения, поскольку они были достигнуты в другом направлении: в этом случае мы обновляем маску направления (с помощью побитового ИЛИ) и запускаем новую итерацию.

Если все соединения действительны, и мы достигли запрошенного числа плиток, нам все еще нужно проверить, является ли это новое существо или просто измененной версией существующего:

1. Мы применяем следующие преобразования:

   • $(x,y)$$(x,y)$$(y,z)$$(z,x)$

   • $(x,y)$$(y,x)$$(z,y)$$(x,z)$

2. $(0,0)$

3. Мы сортируем плитки по их координатам и типам. (Этот вид обрабатывается в лексикографическом порядке, что нормально.)

4. Наконец, мы приводим полученный список к ключевой строке, которую можно сравнить с другими ключами.

5. Мы прекращаем работу, как только сопоставляется известный ключ, или сохраняем новый ключ и увеличиваем конечный результат, если ни одно из преобразований не приводит к известному ключу.

комментарии

f = (n, T = [B = [N = 0, 0, 0, 1, 1]]) =>
  // abort if n = 0
  !n ||
  // for each tile in T
  T.some(([x, y, q, m]) =>
    // for d = 0 to d = 4
    B.some((p, d) =>
      // if this tile requires a connection in this direction
      m >> d & 1 && (
        // look for a connected tile t at the corresponding position (p, q)
        (
          p = x + ~-s[d],
          q = y + ~-s[d + 2],
          t = T.find(([X, Y]) => X == p & Y == q)
        ) ?
          // if t exists, make sure that its direction mask is up-to-date
          (q = t[3]) & (p = D[d * 3 + t[4]]) ^ p ?
            // if it's not, update it and force a new iteration
            t[f(n, T, t[3] |= p), 3] = q
          :
            0
        :
          // if t does not exist, try each type of tile at this position
          [0, 1, 2].map(t => f(n - 1, [...T, [p, q, -p - q, D[d * 3 + t], t]]))
      )
    ),
    // s is used to apply (dx, dy)
    s = "2100122",
    // D holds the direction masks for the connections
    D = Buffer("160).(9!'8 &$<%")
  ) |
  // stop here if the above some() was truthy or we have more tiles to add
  n > 1 ||
  // otherwise, apply the transformations
  [0, 1, 2, 1, 2, 0].some((_, d, A) =>
    B[
      // compute the key k
      k =
        // by generating the updated tuples [x, y, type] and sorting them
        T.map(a =>
          [
            // transform the 1st coordinate
            (h = n => Math.min(...T.map(R = a => a[A[(d + n) % 6]])) - R(a))(0),
            // transform the 2nd coordinate
            h(3),
            // update the type
            (x = (a[4] + d * 2) % 3, d > 2) * x ? 3 - x : x
          ]
        ).sort()
    ]
  ) ?
    // if the key was found, just return N
    N
  :
    // if this is a new creature, store its key and increment N
    B[k] = ++N