Martin Ender recientemente alcanzó los 100K, y ha creado algunos lenguajes asombrosos . Vamos a divertirnos un poco con uno de ellos, Hexagony (y un poco de expresión regular para Retina )

Como breve descripción general, debe escribir un programa que ingrese una cuadrícula de Hexagony y determine si hay una ruta en esa cuadrícula que coincida con una cadena de texto

Generando

Hexagony genera hexágonos a partir de una cadena de texto mediante los siguientes pasos:

1. Calcule el tamaño mínimo del hexágono (tome la longitud de la cuerda y redondee al número hexadecimal más cercano )
2. Envolviendo el texto en un hexágono del tamaño anterior
3. Llenar las ubicaciones restantes con ..

Por ejemplo, la cadena de texto abcdefghijklmrequiere un hexágono de longitud lateral 3 y, por lo tanto, se convierte en:

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

Ahora, observe que hay 6 direcciones posibles que puede viajar en un hexágono. Por ejemplo, en el hexágono anterior, eestá adyacente a abfjid.

Envase

Además, en Hexagony, los hexágonos envuelven:

   . . . .          . 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 . .   

Si observa el segundo y cuarto ejemplo, observe cómo ay kestán en los mismos lugares, a pesar del hecho de que está envolviendo en diferentes direcciones. Debido a este hecho, estos puntos son solo adyacentes a otros 5 lugares .

Para aclarar esto:

   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. Los bordes se envuelven a su vecino opuesto ( b->Iy G->j).
2. Las esquinas superior / inferior se envuelven en la esquina central opuesta y arriba / abajo ( d->K,py H->a,v).
3. Las esquinas centrales se envuelven en las esquinas superior e inferior ( v->a,H)

Caminos

Una ruta para ser una secuencia de ubicaciones adyacentes sin volver a la misma ubicación.

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

En el hexágono anterior, aefkgmes una ruta válida. Sin embargo, abfdno es una ruta válida ( fy dno es adyacente), y abeano es válida (vuelve a la aubicación).

Podemos usar estas rutas para hacer coincidir el texto (como regex) . Un carácter alfanumérico coincide con sí mismo (y solo con él mismo), y un .coincide con cualquier carácter. Por ejemplo, la ruta aej..lgmse correspondería aej..lgm, aejAAlgm, aeja.lgm, o aej^%gm.

De entrada y salida

Su programa debe tomar dos cadenas (en cualquier orden). La primera cadena no estará vacía y constará solo de caracteres alfanuméricos [a-zA-Z0-9]. Esto representará el hexágono en el que está operando. La segunda cadena consistirá en caracteres imprimibles.

Debe devolver un valor verdadero si hay una ruta en el hexágono que coincida con la cadena de texto dada, de lo contrario, un valor falso.

Casos de prueba

Verdad:

"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"

Este es un código de golf , así que haga sus respuestas lo más cortas posible en su idioma favorito.

Retina , 744 bytes

Lo siento amigos, no Hexagony esta vez ...

El recuento de bytes asume la codificación 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

Espera la cadena objetivo en la primera línea y el hexágono en la segunda línea de la entrada. Impresiones 0o en 1consecuencia.

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas, donde cada línea es un caso de prueba, que se utiliza ¦para la separación en lugar de un salto de línea).

La forma correcta de resolver este desafío es con una expresión regular, por supuesto. ;) Y si no fuera por el hecho de que este desafío también involucra el procedimiento de desarrollo del hexágono , esta respuesta en realidad consistiría en nada más que una simple expresión regular de ~ 600 bytes.

Esto todavía no está muy optimizado, pero estoy bastante contento con el resultado (mi primera versión de trabajo, después de eliminar los grupos con nombre y otras cosas necesarias para la cordura, era de alrededor de 1000 bytes). Creo que podría ahorrar unos 10 bytes intercambiando el orden de la cadena y el hexágono, pero requeriría una reescritura completa de la expresión regular al final, lo que no estoy sintiendo en este momento. También hay un ahorro de 2 bytes al omitir la Getapa, pero ralentiza la solución considerablemente, por lo que esperaré haciendo ese cambio hasta que esté seguro de haber jugado al golf tan bien como pueda.

Explicación

La parte principal de esta solución hace un uso extensivo de los grupos de equilibrio , por lo que le recomiendo leerlos, si desea entender cómo funciona esto en detalle (no lo culparé si no lo hace ...).

La primera parte de la solución (es decir, todo excepto las dos últimas líneas) es una versión modificada de mi respuesta a Desplegar el código fuente de Hexagony . Construye el hexágono, mientras deja intacta la cadena objetivo (y en realidad construye el hexágono antes de la cadena objetivo). He realizado algunos cambios en el código anterior para guardar bytes:

• El carácter de fondo es en ×lugar de un espacio para que no entre en conflicto con espacios potenciales en la entrada.
• El carácter no-op / comodín es _en cambio ., de modo que las celdas de la cuadrícula se pueden identificar de forma fiable como caracteres de texto.
• No inserto ningún espacio ni sangría después de que se construye el hexágono por primera vez. Eso me da un hexágono inclinado, pero en realidad es mucho más conveniente trabajar con él y las reglas de adyacencia son bastante simples.

Aquí hay un ejemplo. Para el siguiente caso de prueba:

ja
abcdefghij

Obtenemos:

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

Compare esto con el diseño habitual del hexágono:

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

Podemos ver que los vecinos ahora son todos los 8 vecinos habituales de Moore, excepto los vecinos del noroeste y sureste. Por lo tanto, debemos verificar la adyacencia horizontal, vertical y sur-oeste / noreste (bueno, y luego están los bordes de envoltura). El uso de este diseño más compacto también tiene la ventaja de que podremos usarlos ××al final para determinar el tamaño del hexágono sobre la marcha cuando lo necesitemos.

Después de construir este formulario, hacemos un cambio más en toda la cadena:

T`d`À-É

Esto reemplaza los dígitos con las letras ASCII extendidas

ÀÁÂÃÄÅÆÇÈÉ

Dado que se reemplazan tanto en el hexágono como en la cadena objetivo, esto no afectará si la cadena coincide o no. Además, dado que son letras \wy \baún las identifican como celdas hexagonales. El beneficio de hacer esta sustitución es que ahora podemos usar \Den la próxima expresión regular para que coincida con cualquier carácter (específicamente, saltos de línea, así como caracteres sin salto de línea). No podemos usar la sopción para lograr eso, porque necesitaremos .hacer coincidir los caracteres sin salto de línea en varios lugares.

Ahora el último bit: determinar si alguna ruta coincide con nuestra cadena dada. Esto se hace con una sola expresión monstruosa. Te preguntarás por qué?!?! Bueno, esto es fundamentalmente un problema de retroceso: comienzas en algún lugar e intentas un camino siempre que coincida con la cadena, y una vez que no lo haces, retrocedes e intentas con un vecino diferente del último personaje que funcionó. La única cosaque obtienes gratis cuando trabajas con regex es un retroceso. Eso es literalmente lo único que hace el motor regex. Entonces, si solo encontramos una manera de describir una ruta válida (que es lo suficientemente complicada para este tipo de problema, pero definitivamente posible con grupos de equilibrio), entonces el motor de expresiones regulares resolverá encontrar esa ruta entre todos los posibles para nosotros. Ciertamente sería posible implementar la búsqueda manualmente con múltiples etapas ( y lo he hecho en el pasado ), pero dudo que sea más corto en este caso particular.

Un problema con la implementación de esto con una expresión regular es que no podemos tejer arbitrariamente el cursor del motor de expresión regular hacia adelante y hacia atrás a través de la cadena durante el retroceso (que necesitaríamos ya que la ruta podría subir o bajar). Entonces, en cambio, hacemos un seguimiento de nuestro propio "cursor" en un grupo de captura y lo actualizamos en cada paso (podemos movernos temporalmente a la posición del cursor con una búsqueda). Esto también nos permite almacenar todas las posiciones pasadas que usaremos para verificar que no hayamos visitado la posición actual antes.

Vamos a por ello. Aquí hay una versión un poco más sensata de la expresión regular, con grupos con nombre, sangría, un orden menos aleatorio de vecinos y algunos comentarios:

\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

Espero que la idea general sea más o menos clara a partir de esto. Como ejemplo de cómo funciona uno de esos movimientos a lo largo del camino, veamos el bit que mueve el cursor hacia el sur:

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

Recuerde que las retrospectivas deben leerse de derecha a izquierda (o de abajo hacia arriba), porque ese es el orden en que se ejecutan:

(?<=
  (?<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).
)

Tenga en cuenta que no es necesario poner un ancla frente al \k<pos>para asegurarse de que esto realmente llegue al comienzo de la cadena. <pos>siempre comienza con una cantidad ×que no se puede encontrar en ningún otro lugar, por lo que esto ya actúa como un ancla implícita.

No quiero hinchar esta publicación más de lo necesario, por lo que no entraré en los otros 11 casos en detalle, pero en principio todos funcionan de manera similar. Verificamos que <next>se puede encontrar en alguna dirección específica (admisible) desde la posición del cursor anterior con la ayuda de grupos de equilibrio, y luego almacenamos la cadena hasta esa coincidencia como la nueva posición del cursor <pos>.

Python 3, 990 943 770 709 bytes

Primera respuesta, yay!

EDITAR: Lista de adyacencia de golf. Ahora uso una fórmula ligeramente diferente

EDIT 2: Se eliminó la pelusa innecesaria, se jugó mucho más.

EDITAR 3: acorté el código para la conversión del índice en la lista a las coordenadas, golfé algunas cosas más.

La mayoría de los bytes se relaciona con la creación de la lista de adyacencia (tiene el mayor potencial para jugar golf). A partir de entonces, es una simple cuestión de forzar a la solución (lo que podría hacer en menos bytes).

Golfizado:

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))

Sin golfista con explicación:

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))

¡Tan cerca de Retina! :( Yay, vencer a Retina!

Javascript (ES6), 511 500 496 bytes

(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}

Ungolfed y comentó

// 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
}

Casos de prueba

El fragmento a continuación recorrerá todos los casos de prueba de verdad y falsedad.

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'
);