Мартин Эндер недавно набрал 100K, и у него появилось несколько отличных языков . Мы собираемся повеселиться с одним из них, Hexagony (и немного регулярного выражения для Retina )

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

порождающий

Hexagony генерирует шестиугольники из строки текста, используя следующие шаги:

1. Рассчитать минимальный размер шестиугольника (взять длину строки и округлить до ближайшего шестнадцатеричного числа )
2. Заворачивание текста в шестиугольник указанного размера
3. Заполнение остальных мест ..

Например, строка текста abcdefghijklmтребует шестиугольник с длиной стороны 3 и поэтому становится:

   a b c
  d e f g
 h i j k l
  m . . .
   . . .

Теперь обратите внимание, что есть 6 возможных направлений, по которым вы можете путешествовать в шестиугольнике. Например, в указанном выше шестиугольнике, eрядом с abfjid.

Упаковка

Кроме того, в шестиугольниках шестиугольники оборачиваются:

   . . . .          . a . .          . . f .          . a . .   
  a b c d e        . . b . .        . . g . .        . b . . f  
 . . . . . .      g . . c . .      . . h . . a      . c . . g . 
. . . . . . .    . h . . d . .    . . u . . b .    . d . . h . .
 f g h i j k      . i . . e .      . j . . c .      e . . i . . 
  . . . . .        . j . . f        k . . d .        . . j . .  
   . . . .          . k . .          . . e .          . k . .   

Если вы посмотрите на 2-й и 4-й пример, обратите внимание, что aи kв одном и том же месте, несмотря на то, что вы оборачиваете в разные стороны. Из-за этого факта, эти пятна только смежны с 5 другими местоположениями .

Чтобы сделать это более понятным:

   a b c d
  e f g h i
 j k l m n o
p q r s t u v
 w x y z A B
  C D E F G
   H I J K

1. Края обертывают к своему противоположному соседу ( b->Iа G->j).
2. Верхний / нижний углы переносятся в противоположный центральный угол и вверх / вниз ( d->K,pи H->a,v).
3. Центральные углы переносятся на верхний и нижний углы ( v->a,H)

пути

Путь , чтобы быть последовательность соседних местах , не возвращаясь в том же месте.

   a b c
  d e f g
 h i f k l
  m . . .
   . . .

В приведенном выше шестиугольник, aefkgmэто правильный путь. Тем abfdне менее, это недопустимый путь ( fи dне являются смежными), и abeaне является действительным (возвращается в aместоположение).

Мы можем использовать эти пути для соответствия тексту (например, регулярное выражение) . Буквенно-цифровой символ соответствует самому себе (и только самому себе) и .соответствует любому символу. Например, путь aej..lgmбудет соответствовать aej..lgm, aejAAlgm, aeja.lgmили aej^%gm.

Ввод, вывод

Ваша программа должна принимать две строки (в любом порядке). Первая строка будет непустой и состоит только из буквенно-цифровых символов [a-zA-Z0-9]. Это будет шестиугольник, над которым вы работаете. Вторая строка будет состоять из печатных символов.

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

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

Truthy:

"a","a"
"ab","a"
"ab","b"
"ab","ba"
"ab","aba"
"ab","&"
"ab","#7.J!"
"ab","aaaaaa"
"ab","bgjneta"
"ab","cebtmaa"
"abcdefg","dfabcg"
"AbCDeFG","GCbAeFD"
"aaaabbb","aaababb"
"abcdefghijklmnopqrs","alq"
"abcdefghijklmnopqrs","aqnmiedh"
"abcdefghijklmnopqrs","adhcgkorbefjimnqlps"
"11122233344455","12341345123245"
"abcdefgh","h%a"
"abcdefghijklm","a)(@#.*b"
"abcdefghijklm","a)(@#.*i"
"abcdefghij","ja"
"abcdefghijklmno","kgfeia"
"abcdefghijklmno","mmmmmiea"
"abcdefghijklmno","mmmmmlae"
"abcdefghijklmno","ja"
"abcdefghijklmnopqrs","eijfbadhmnokgcsrql"

Falsy:

"a","b"
"a","%"
"a","."
"a","aa"
"a","a."
"ab","#7.J!*"
"ab","aaaaaaa"
"ab","aaaabaaa"
"ab","123456"
"abcdefg","bfgedac"
"abcdefg","gecafdb"
"abcdefg","GCbaeFD"
"aaaabbb","aaaaabb"
"abcdefghijklmnopqrs","aqrcgf"
"abcdefghijklmnopqrs","adhlcgknbeifjm"
"abcdefghijklmnopqrs","ja"
"abcdefghijklm","a)(@#.*&"
"abcdefghijklmno","a)(@bfeijk"
"abcdefghijklmno","kgfeic"
"abcdefghijklmno","mmmmmmiea"

Это код-гольф , поэтому делайте ваши ответы как можно короче на вашем любимом языке.

Сетчатка , 744 байта

Извините, ребята, на этот раз нет гексагонии ...

Число байтов предполагает кодировку ISO 8859-1.

.+¶
$.'$*_¶$&
^_¶
¶
((^_|\2_)*)_\1{5}_+
$2_
^_*
$.&$*×_$&$&$.&$*×
M!&m`(?<=(?=×*(_)+)\A.*)(?<-1>.)+(?(1)!)|^.*$
O$`(_)|.(?=.*$)
$1
G-2`
T`d`À-É
m`\A(\D*)(?(_)\D*¶.|(.)\D*¶\2)((.)(?<=(?<4>_)\D+)?((?<=(?<1>\1.)\4\D*)|(?<=(?<1>\D*)\4(?<=\1)\D*)|(?<=\1(.(.)*¶\D*))((?<=(?<1>\D*)\4(?>(?<-7>.)*)¶.*\6)|(?<=(?<1>\D*)(?=\4)(?>(?<-7>.)+)¶.*\6))|(?<=(×)*¶.*)((?<=(?<1>\1.(?>(?<-9>¶.*)*))^\4\D*)|(?<=(?<1>\D*)\4(?>(?<-9>¶.*)*)(?<=\1)^\D*)|(?<=(?<1>\1\b.*(?(9)!)(?<-9>¶.*)*)\4×*¶\D*)|(?<=(?<1>\D*\b)\4.*(?(9)!)(?<-9>¶.*)*(?<=\1.)\b\D*))|(?<=(?<1>\1.(?>(?<-11>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1(?>(?<-12>.)*)¶.*)\4(.)*¶\D*)|(?<=(?<1>\1.(?>(?<-13>.)*¶\D*))\4(\w)*\W+.+)|(?<=(?<1>.*)\4(?>(?<-14>.)*¶\D*)(?<=\1.)(\w)*\W+.+))(?<=\1(\D*).+)(?<!\1\15.*(?<-1>.)+))*\Z

Ожидается целевая строка в первой строке и шестиугольник во второй строке ввода. Отпечатки 0или 1соответственно.

Попробуйте онлайн! (Первая строка включает набор тестов, где каждая строка представляет собой тестовый пример, использующий ¦для разделения вместо перевода строки.)

Правильный способ решить эту проблему, конечно, с помощью регулярных выражений. ;) И если бы не тот факт, что этот вызов также включает в себя процедуру разворачивания шестиугольника , этот ответ на самом деле состоял бы из одного регулярного выражения длиной ~ 600 байт.

Это пока не совсем оптимально, но я вполне доволен результатом (моя первая рабочая версия, после удаления именованных групп и других вещей, необходимых для здравомыслия, составила около 1000 байт). Я думаю, что я мог бы сэкономить около 10 байтов, меняя порядок строки и шестиугольника, но это потребовало бы полного переписывания регулярного выражения в конце, чего я сейчас не чувствую. Существует также 2-байтовая экономия за счет пропуска Gсцены, но это значительно замедляет решение, поэтому я подожду с внесением этого изменения, пока не буду уверен, что играю в гольф так хорошо, как могу.

объяснение

Основная часть этого решения широко использует балансировочные группы , поэтому я рекомендую ознакомиться с ними, если вы хотите понять, как это работает в деталях (я не буду винить вас, если вы не ...).

Первая часть решения (т. Е. Все, кроме двух последних строк) является модифицированной версией моего ответа на Unfolding the Hexagony source code . Он создает шестиугольник, оставляя целевую строку нетронутой (и фактически создает шестиугольник перед целевой строкой). Я внес некоторые изменения в предыдущий код для сохранения байтов:

• Фоновый символ ×вместо пробела, чтобы он не конфликтовал с потенциальными пробелами на входе.
• _Вместо этого .используется подстановочный / подстановочный знак , поэтому ячейки сетки могут быть надежно идентифицированы как символы слова.
• Я не вставляю никаких пробелов или отступов после того, как шестиугольник сначала построен. Это дает мне наклонный шестиугольник, но на самом деле с ним гораздо удобнее работать, а правила смежности довольно просты.

Вот пример. Для следующего теста:

ja
abcdefghij

Мы получаем:

××abc
×defg
hij__
____×
___××
ja

Сравните это с обычным расположением шестиугольника:

  a b c
 d e f g
h i j _ _
 _ _ _ _
  _ _ _

Мы можем видеть, что соседи теперь все обычные соседи Мура, за исключением северо-западных и юго-восточных соседей. Таким образом, мы должны проверить горизонтальную, вертикальную и смежность с юго-западом / северо-востоком (ну, а затем есть края обтекания). Использование этой более компактной компоновки также дает бонус, который мы сможем использовать ××в конце, чтобы определить размер шестиугольника на лету, когда он нам понадобится.

После того, как эта форма была построена, мы вносим еще одно изменение во всю строку:

T`d`À-É

Это заменяет цифры расширенными буквами ASCII

ÀÁÂÃÄÅÆÇÈÉ

Поскольку они заменяются как в шестиугольнике, так и в целевой строке, это не повлияет на соответствие строки или нет. Кроме того, поскольку они являются буквами \wи \bдо сих пор идентифицируют их как ячейки шестиугольника. Преимущество этой замены состоит в том, что теперь мы можем использовать \Dв предстоящем регулярном выражении соответствие любому символу (в частности, символам перевода строки, а также символам перевода строки). Мы не можем использовать эту sопцию, чтобы выполнить это, потому что нам нужно .сопоставлять символы, не являющиеся переводом строки, в нескольких местах.

Теперь последний бит: определение, соответствует ли какой-либо путь нашей заданной строке. Это делается с помощью одного чудовищного регулярного выражения. Вы можете спросить себя, почему?!?! Что ж, по сути это проблема с возвратом: вы начинаете где-нибудь и пытаетесь найти путь, пока он совпадает со строкой, и если он не возвращается, вы пытаетесь найти соседа, отличного от последнего сработавшего символа. Одна вещьто, что вы получаете бесплатно при работе с регулярным выражением, является возвращением. Это буквально единственное, что делает движок регулярных выражений. Поэтому, если мы просто найдем способ описать действительный путь (который достаточно сложен для такого рода проблем, но определенно возможен с балансировкой групп), то механизм регулярных выражений будет разбираться в том, чтобы найти этот путь среди всех возможных для нас. Конечно, было бы возможно реализовать поиск вручную в несколько этапов ( и я делал это в прошлом ), но я сомневаюсь, что в данном конкретном случае это будет короче.

Одна из проблем, связанных с реализацией этого с помощью регулярного выражения, заключается в том, что мы не можем произвольно переплетать курсор движка регулярного выражения назад и вперед через строку во время обратного отслеживания (что нам понадобится, поскольку путь может идти вверх или вниз). Таким образом, вместо этого мы отслеживаем наш собственный «курсор» в группе захвата и обновляем его на каждом шаге (мы можем временно перейти к позиции курсора с помощью обходного пути). Это также позволяет нам сохранять все прошлые позиции, которые мы будем использовать для проверки того, что мы не посещали текущую позицию раньше.

Итак, давайте вернемся к этому. Вот немного более разумная версия регулярного выражения с именованными группами, отступами, менее случайным порядком соседей и некоторыми комментариями:

\A
# Store initial cursor position in <pos>
(?<pos>\D*)
(?(_)
  # If we start on a wildcard, just skip to the first character of the target.
  \D*¶.
|
  # Otherwise, make sure that the target starts with this character.
  (?<first>.)\D*¶\k<first>
)
(?:
  # Match 0 or more subsequent characters by moving the cursor along the path.
  # First, we store the character to be matched in <next>.
  (?<next>.)
  # Now we optionally push an underscore on top (if one exists in the string).
  # Depending on whether this done or not (both of which are attempted by
  # the engine's backtracking), either the exact character, or an underscore
  # will respond to the match. So when we now use the backreference \k<next>
  # further down, it will automatically handle wildcards correctly.
  (?<=(?<next>_)\D+)?
  # This alternation now simply covers all 6 possible neighbours as well as
  # all 6 possible wrapped edges.
  # Each option needs to go into a separate lookbehind, because otherwise
  # the engine would not backtrack through all possible neighbours once it
  # has found a valid one (lookarounds are atomic). 
  # In any case, if the new character is found in the given direction, <pos>
  # will have been updated with the new cursor position.
  (?:
    # Try moving east.
    (?<=(?<pos>\k<pos>.)\k<next>\D*)
  |
    # Try moving west.
    (?<=(?<pos>\D*)\k<next>(?<=\k<pos>)\D*)
  |
    # Store the horizontal position of the cursor in <x> and remember where
    # it is (because we'll need this for the next two options).
    (?<=\k<pos>(?<skip>.(?<x>.)*¶\D*))
    (?:
      # Try moving north.
      (?<=(?<pos>\D*)\k<next>(?>(?<-x>.)*)¶.*\k<skip>)
    |
      # Try moving north-east.
      (?<=(?<pos>\D*)(?=\k<next>)(?>(?<-x>.)+)¶.*\k<skip>)
    )
  |
    # Try moving south.
    (?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
  |
    # Try moving south-east.
    (?<=(?<pos>\k<pos>(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
  |
    # Store the number of '×' at the end in <w>, which is one less than the
    # the side-length of the hexagon. This happens to be the number of lines
    # we need to skip when wrapping around certain edges.
    (?<=(?<w>×)*¶.*)
    (?:
      # Try wrapping around the east edge.
      (?<=(?<pos>\k<pos>.(?>(?<-w>¶.*)*))^\k<next>\D*)
    |
      # Try wrapping around the west edge.
      (?<=(?<pos>\D*)\k<next>(?>(?<-w>¶.*)*)(?<=\k<pos>)^\D*)
    |
      # Try wrapping around the south-east edge.
      (?<=(?<pos>\k<pos>\b.*(?(w)!)(?<-w>¶.*)*)\k<next>×*¶\D*)
    |
      # Try wrapping around the north-west edge.
      (?<=(?<pos>\D*\b)\k<next>.*(?(w)!)(?<-w>¶.*)*(?<=\k<pos>.)\b\D*)
    )
  |
    # Try wrapping around the south edge.
    (?<=(?<pos>\k<pos>.(?>(?<-x>.)*¶\D*))\k<next>(?<x>\w)*\W+.+)
  |
    # Try wrapping around the north edge.
    (?<=(?<pos>.*)\k<next>(?>(?<-x>.)*¶\D*)(?<=\k<pos>.)(?<x>\w)*\W+.+)
  )
  # Copy the current cursor position into <current>.
  (?<=\k<pos>(?<current>\D*).+)
  # Make sure that no matter how many strings we pop from our stack of previous
  # cursor positions, none are equal to the current one (to ensure that we use
  # each cell at most once).
  (?<!\k<pos>\k<current>.*(?<-pos>.)+)
)*
# Finally make sure that we've reached the end of the string, so that we've
# successfully matched all characters in the target string.
\Z

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

(?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)

Помните, что lookbehinds следует читать справа налево (или снизу вверх), потому что это порядок, в котором они выполняются:

(?<=
  (?<pos>
    \k<pos>       # Check that this is the old cursor position.
    .             # Match the character directly on top of the new one.
    (?>(?<-x>.)*) # Match the same amount of characters as before.
    ¶.*           # Skip to the next line (the line, the old cursor is on).
  )               # We will store everything left of here as the new 
                  # cursor position.
  \k<next>        # ...up to a match of our current target character.
  (?<x>.)*        # Count how many characters there are...
  ¶\D*            # Skip to the end of some line (this will be the line below
                  # the current cursor, which the regex engine's backtracking
                  # will determine for us).
)

Обратите внимание, что нет необходимости ставить якорь перед, \k<pos>чтобы убедиться, что он действительно достигает начала строки. <pos>всегда начинается с количества, ×которое не может быть найдено где-либо еще, так что это уже действует как неявная привязка.

Я не хочу раздувать этот пост больше, чем необходимо, поэтому я не буду вдаваться в подробности остальных 11 случаев, но в принципе все они работают одинаково. Мы проверяем, что <next>можно найти в каком-то определенном (допустимом) направлении от старой позиции курсора с помощью уравновешивающих групп, а затем сохраняем строку до этого соответствия в качестве новой позиции курсора в <pos>.

Питон 3, 990 943 770 709 байт

Первый ответ, ууу!

РЕДАКТИРОВАТЬ: создание списка смежности в гольф. Я сейчас использую немного другую формулу

РЕДАКТИРОВАТЬ 2: Удалены ненужные пух, игра в гольф намного больше.

РЕДАКТИРОВАТЬ 3: Сократил код для преобразования из индекса в списке в координаты, добавил еще несколько вещей.

Большая часть байтов связана с составлением списка смежности (он обладает наибольшим потенциалом для игры в гольф). С этого момента это просто вопрос грубого решения (что я мог бы сделать за меньшее количество байтов).

Golfed:

from math import*
b=abs
c=max
e=range
f=len
A=input()
B=input()
C=ceil(sqrt((f(A)-.25)/3)+.5)
D=3*C*~-C+1
E=2*C-1
F=C-1
A+='.'*(D-f(A))
G=[set()for x in e(D)]
I=lambda H:sum(E+.5-b(t-F+.5)for t in e(int(H+F)))
for x in e(D):
 r=sum([[J-F]*(E-b(J-F))for J in e(E)],[])[x];q=x-I(r);s=-q-r;a=lambda q,r:G[x].add(int(q+I(r)));m=c(map(b,[q,r,s]))
 if m==F:
  if q in(m,-m):a(-q,-s)
  if r in(m,-m):a(-s,-r)
  if s in(m,-m):a(-r,-q)
 for K,L in zip([1,0,-1,-1,0,1],[0,1,1,0,-1,-1]):
  M,H=q+K,r+L
  if c(map(b,[M,H,-M-H]))<C:a(M,H)
def N(i,O,P):
 Q=O and O[0]==A[i]or'.'==A[i];R=0
 if(2>f(O))*Q:R=1
 elif Q:R=c([(x not in P)*N(x,O[1:],P+[i])for x in G[i]]+[0])
 return R
print(c([N(x,B,[])for x in e(D)])*(f(B)<=D))

Ungolfed W / объяснение:

from math import*

#Rundown of the formula:
# * Get data about the size of the hexagon
# * Create lookup tables for index <-> coordinate conversion
#   * q=0, r=0 is the center of the hexagon
#   * I chose to measure in a mix of cubic and axial coordinates,
#     as that allows for easy oob checks and easy retrevial  
# * Create the adjacency list using the lookup tables, while
#   checking for wrapping
# * Brute-force check if a path in the hexagon matches the
#   expression

# shorten functions used a lot
b=abs
c=max
e=range

# Get input

prog=input()
expr=input()

# sdln = Side length
# hxln = Closest hexagonal number
# nmrw = Number of rows in the hexagon
# usdl = one less than the side length. I use it a lot later

sdln=ceil(sqrt((len(prog)-.25)/3)+.5)
hxln=3*sdln*~-sdln+1
nmrw=2*sdln-1
usdl=sdln-1

# Pad prog with dots

prog+='.'*(hxln-len(prog))

# nmbf = Number of elements before in each row
# in2q = index to collum
# in2r = index to row

nmbf=[0]*nmrw
in2q=[0]*hxln
in2r=[0]*hxln

#  4    5
#   \  /
# 3 -- -- 0
#   /  \ 
#  2    1

# dirs contains the q,r and s values needed to move a point
# in the direction refrenced by the index

qdir=[1,0,-1,-1,0,1]
rdir=[0,1,1,0,-1,-1]

# generate nmbf using a summation formula I made

for r in e(nmrw-1):
    nmbf[r+1]=int(nmbf[r]+nmrw+.5-b(r-sdln+1.5))

# generate in2q and in2r using more formulas
# cntr = running counter

cntr=0
for r in e(nmrw):
    bgnq=c(-r,1-sdln)
    for q in e(nmrw-b(r-sdln+1)):
        in2q[cntr]=bgnq+q
        in2r[cntr]=r-usdl
        cntr+=1

# adjn = Adjacency sets

adjn=[set()for x in e(hxln)]

# Generate adjacency sets

for x in e(hxln):
    #Get the q,r,s coords
    q,r=in2q[x],in2r[x]
    s=-q-r
    # a = function to add q,r to the adjacency list
    a=lambda q,r:adjn[x].add(q+nmbf[r+usdl])
    # m = absolute value distance away from the center
    m=c(map(b,[q,r,s]))
    # if we are on the edge (includes corners)...
    if m==usdl:
        # add the only other point it wraps to
        if q in(m,-m):
            a(-q,-s)
        if r in(m,-m):
            a(-s,-r)
        if s in(m,-m):
            a(-r,-q)
    # for all the directions...
    for d in e(6):
        # tmp{q,r,s} = moving in direction d from q,r,s
        tmpq,tmpr=q+qdir[d],r+rdir[d]
        # if the point we moved to is in bounds...
        if c(map(b,[tmpq,tmpr,-tmpq-tmpr]))<sdln:
            # add it
            a(tmpq,tmpr)

# Recursive path checking function
def mtch(i,mtst,past):
    # dmch = Does the place we are on in the hexagon match
    #        the place we are in the expression?
    # out = the value to return
    dmch=mtst and mtst[0]==prog[i]or'.'==prog[i]
    out=0
    # if we are at the end, and it matches...
    if(2>len(mtst))*dmch:
        out=1
    # otherwise...
    elif dmch:
        # Recur in all directions that we haven't visited yet
        # replace '*' with 'and' to speed up the recursion
        out=c([(x not in past)*mtch(x,mtst[1:],past+[i])for x in adjn[i]]+[0])
    return out

# Start function at all the locations in the hexagon
# Automatically return false if the expression is longer
# than the entire hexagon
print(c([mtch(x,expr,[])for x in e(hxln)])*(len(expr)<=hxln))

Так близко к сетчатке! :( дааа, бей ретина!

Javascript (ES6), 511 500 496 байт

(H,N)=>{C=(x,y)=>(c[x]=c[x]||[])[y]=y;S=d=>(C(x,y=x+d),C(y,x),C(s-x,s-y),C(s-y,s-x));r=(x,p,v)=>{p<N.length?(v[x]=1,c[x].map(n=>!v[n]&&(H[n]==N[p]||H[n]=='.')&&r(n,p+1,v.slice()))):K=1};for(e=x=K=0;(s=3*e*++e)<(l=H.length)-1;);H+='.'.repeat(s+1-l);for(a=[],b=[],c=[[]],w=e;w<e*2;){a[w-e]=x;b[e*2-w-1]=s-x;for(p=w;p--;x++){w-e||S(s-e+1);w<e*2-1&&(S(w),S(w+1));p&&S(1)}a[w]=x-1;b[e*3-++w]=s-x+1}a.map((v,i)=>S(b[i]-(x=v)));[N[0],'.'].map(y=>{for(x=-1;(x=H.indexOf(y,x+1))>-1;r(x,1,[]));});return K}

Разоблаченный и прокомментированный

// Entry point
//   H = haystack (the string the hexagon is filled with)
//   N = needle (the substring we're looking for)
(H, N) => {
  // C(x, y) - Helper function to save a connection between two locations.
  //   x = source location
  //   y = target location
  C = (x, y) => (c[x] = c[x] || [])[y] = y;

  // S(d) - Helper function to save reciprocal connections between two locations
  //        and their symmetric counterparts.
  //   d = distance between source location (x) and target location
  S = d => (C(x, y = x + d), C(y, x), C(s - x, s - y), C(s - y, s - x));

  // r(x, p, v) - Recursive path search.
  //   x = current location in hexagon
  //   p = current position in needle
  //   v = array of visited locations
  r = (x, p, v) => {
    p < N.length ?
      (v[x] = 1, c[x].map(n => !v[n] && (H[n] == N[p] || H[n] == '.') &&
      r(n, p + 1, v.slice())))
    :
      K = 1
  };

  // Compute e = the minimum required edge width of the hexagon to store the haystack.
  // Also initialize:
  //   x = current location in hexagon
  //   l = length of haystack
  //   s = size of hexagon (number of locations - 1)
  //   K = fail/success flag
  for(e = x = K = 0; (s = 3 * e * ++e) < (l = H.length) - 1;);

  // Pad haystack with '.'
  H += '.'.repeat(s + 1 - l);

  // Build connections c[] between locations, using:
  //   x = current location
  //   w = width of current row
  //   p = position in current row
  // Also initialize:
  //   a[] = list of locations on top left and top right edges
  //   b[] = list of locations on bottom left and bottom right edges
  for(a = [], b = [], c = [[]], w = e; w < e * 2;) {
    a[w - e] = x;
    b[e * 2 - w - 1] = s - x;

    for(p = w; p--; x++) {
      // connection between top and bottom edges
      w - e || S(s - e + 1);
      // connections between current location and locations below it
      w < e * 2 - 1 && (S(w), S(w + 1));
      // connection between current location and next location
      p && S(1)
    }
    a[w] = x - 1;
    b[e * 3 - ++w] = s - x + 1
  }

  // Save connections between top left/right edges and bottom left/right edges.
  a.map((v, i) => S(b[i] - (x = v)));

  // Look for either the first character of the needle or a '.' in the haystack,
  // and use it as the starting point for the recursive search. All candidate
  // locations are tried out.
  [N[0], '.'].map(y => {
    for(x = -1; (x = H.indexOf(y, x + 1)) > -1; r(x, 1, []));
  });

  // Return fail/success flag.
  return K
}

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

Фрагмент, приведенный ниже, пройдет через все правдивые и ложные тесты.

let f =
(H,N)=>{C=(x,y)=>(c[x]=c[x]||[])[y]=y;S=d=>(C(x,y=x+d),C(y,x),C(s-x,s-y),C(s-y,s-x));r=(x,p,v)=>{p<N.length?(v[x]=1,c[x].map(n=>!v[n]&&(H[n]==N[p]||H[n]=='.')&&r(n,p+1,v.slice()))):K=1};for(e=x=K=0;(s=3*e*++e)<(l=H.length)-1;);H+='.'.repeat(s+1-l);for(a=[],b=[],c=[[]],w=e;w<e*2;){a[w-e]=x;b[e*2-w-1]=s-x;for(p=w;p--;x++){w-e||S(s-e+1);w<e*2-1&&(S(w),S(w+1));p&&S(1)}a[w]=x-1;b[e*3-++w]=s-x+1}a.map((v,i)=>S(b[i]-(x=v)));[N[0],'.'].map(y=>{for(x=-1;(x=H.indexOf(y,x+1))>-1;r(x,1,[]));});return K}

let truthy = [
  ["a","a"],
  ["ab","a"],
  ["ab","b"],
  ["ab","ba"],
  ["ab","aba"],
  ["ab","&"],
  ["ab","#7.J!"],
  ["ab","aaaaaa"],
  ["ab","bgjneta"],
  ["ab","cebtmaa"],
  ["abcdefg","dfabcg"],
  ["AbCDeFG","GCbAeFD"],
  ["aaaabbb","aaababb"],
  ["abcdefghijklmnopqrs","alq"],
  ["abcdefghijklmnopqrs","aqnmiedh"],
  ["abcdefghijklmnopqrs","adhcgkorbefjimnqlps"],
  ["11122233344455","12341345123245"],
  ["abcdefgh","h%a"],
  ["abcdefghijklm","a)(@#.*b"],
  ["abcdefghijklm","a)(@#.*i"],
  ["abcdefghij","ja"],
  ["abcdefghijklmno","kgfeia"],
  ["abcdefghijklmno","mmmmmiea"],
  ["abcdefghijklmno","mmmmmlae"],
  ["abcdefghijklmno","ja"],
  ["abcdefghijklmnopqrs","eijfbadhmnokgcsrql"]
];

let falsy = [
  ["a","b"],
  ["a","%"],
  ["a","."],
  ["a","aa"],
  ["a","a."],
  ["ab","#7.J!*"],
  ["ab","aaaaaaa"],
  ["ab","aaaabaaa"],
  ["ab","123456"],
  ["abcdefg","bfgedac"],
  ["abcdefg","gecafdb"],
  ["abcdefg","GCbaeFD"],
  ["aaaabbb","aaaaabb"],
  ["abcdefghijklmnopqrs","aqrcgf"],
  ["abcdefghijklmnopqrs","adhlcgknbeifjm"],
  ["abcdefghijklmnopqrs","ja"],
  ["abcdefghijklm","a)(@#.*&"],
  ["abcdefghijklmno","a)(@bfeijk"],
  ["abcdefghijklmno","kgfeic"],
  ["abcdefghijklmno","mmmmmmiea"]
];

console.log(
  'Testing truthy test cases:',
  truthy.every(v => f(v[0], v[1])) ? 'passed' : 'failed'
);
console.log(
  'Testing falsy test cases:',
  falsy.every(v => !f(v[0], v[1])) ? 'passed' : 'failed'
);