Martin Ender a récemment atteint 100 000 livres et a mis au point des langages assez impressionnants . Nous allons nous amuser un peu avec l'un d'eux, Hexagony (et un peu de regex pour Retina )

En résumé, vous devez écrire un programme qui entre une grille Hexagony et détermine s’il existe un chemin correspondant à une chaîne de texte.

Générateur

Hexagony génère des hexagones à partir d'une chaîne de texte en procédant comme suit:

1. Calculez la taille minimum d'un hexagone (prenez la longueur de la chaîne et arrondissez au nombre hexadécimal le plus proche )
2. Envelopper le texte dans un hexagone de la taille ci-dessus
3. Remplir les emplacements restants avec ..

Par exemple, la chaîne de texte abcdefghijklmnécessite un hexagone de côté 3 et devient donc:

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

Maintenant, notez qu'il y a 6 directions possibles que vous pouvez voyager dans un hexagone. Par exemple, dans l'hexagone ci-dessus, eest adjacent à abfjid.

Emballage

De plus, en hexagone, les hexagones enveloppent:

   . . . .          . 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 vous regardez les 2ème et 4ème exemples, remarquez comment aet si vous kêtes au même endroit, malgré le fait que vous vous dirigiez dans des directions différentes. De ce fait, ces spots ne sont adjacents qu'à 5 autres endroits .

Pour rendre cela plus clair:

   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. Les bords se terminent à leur voisin opposé ( b->Iet G->j).
2. Les coins supérieur / inférieur se déplacent vers le coin central opposé et vers le haut / bas ( d->K,pet H->a,v).
3. Coins centraux enveloppant les coins supérieur et inférieur ( v->a,H)

Les chemins

Un chemin doit être une séquence d'emplacements adjacents sans revenir au même emplacement.

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

Dans l'hexagone ci-dessus, aefkgmest un chemin valide. Cependant, le abfdchemin n'est pas valide ( fet dne sont pas adjacents) et abean'est pas valide (retourne à l' aemplacement).

Nous pouvons utiliser ces chemins pour faire correspondre le texte (comme regex) . Un caractère alphanumérique correspond à lui-même (et uniquement à lui-même), et a .correspond à tout caractère. Par exemple, le chemin aej..lgmcorrespondrait aej..lgm, aejAAlgm, aeja.lgmou aej^%gm.

Entrée sortie

Votre programme doit prendre deux chaînes (dans n'importe quel ordre). La première chaîne ne sera pas vide et ne comportera que des caractères alphanumériques [a-zA-Z0-9]. Cela représentera l'hexagone sur lequel vous opérez. La deuxième chaîne sera composée de caractères imprimables.

Vous devez renvoyer une valeur de vérité si et seulement si l'hexagone contient un chemin qui correspond à la chaîne de texte donnée, sinon une valeur de falsy.

Cas de test

Vérité

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

Fausseté:

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

Ceci est un code-golf , alors répondez aussi brièvement que possible dans votre langue préférée.

Retina , 744 octets

Désolé les gars, pas d'Hexagonie cette fois ...

Le nombre d'octets suppose un codage 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

Attend la chaîne cible sur la première ligne et l'hexagone sur la deuxième ligne de l'entrée. Imprime 0ou en 1conséquence.

Essayez-le en ligne! (La première ligne active une suite de tests, où chaque ligne est un scénario de test et utilise ¦pour la séparation au lieu d'un saut de ligne.)

La bonne façon de résoudre ce défi est bien sûr avec une expression régulière. ;) Et si ce n’était pas le cas, ce défi impliquait également la procédure de déploiement de l’hexagone , cette réponse ne serait en réalité constituée que d’une simple expression rationnelle longue de 600 octets.

Le jeu n’est pas encore optimal, mais je suis assez satisfait du résultat (ma première version opérationnelle, après avoir supprimé les groupes nommés et d’autres éléments nécessaires à la santé mentale, était d’environ 1000 octets). Je pense que je pourrais économiser environ 10 octets en inversant l'ordre de la chaîne et de l'hexagone, mais cela nécessiterait une réécriture complète de la regex à la fin, ce que je ne me sens pas à la hauteur. En omettant l' Gétape, on économise également 2 octets , mais cela ralentit considérablement la solution. J'attendrai donc de faire ce changement jusqu'à ce que je sois sûr d'avoir joué au golf autant que je peux.

Explication

La partie principale de cette solution utilise énormément les groupes d'équilibrage . Je vous recommande donc de les lire si vous voulez comprendre comment cela fonctionne en détail (je ne vous blâmerai pas si vous ne le faites pas ...).

La première partie de la solution (c'est-à-dire tout sauf les deux dernières lignes) est une version modifiée de ma réponse à Unfolding le code source Hexagony . Il construit l'hexagone, tout en laissant la chaîne cible intacte (et construit en fait l'hexagone avant la chaîne cible). J'ai apporté quelques modifications au code précédent pour économiser des octets:

• Le caractère d'arrière-plan ×remplace un espace afin d'éviter tout conflit avec des espaces potentiels dans l'entrée.
• Le caractère no-op / wildcard est à la _place ., de sorte que les cellules de la grille peuvent être identifiées de manière fiable en tant que caractères de mot.
• Je n'insère pas d'espaces ni d'indentation après la construction initiale de l'hexagone. Cela me donne un hexagone incliné, mais c'est en fait beaucoup plus pratique et les règles de contiguïté sont assez simples.

Voici un exemple. Pour le cas de test suivant:

ja
abcdefghij

On a:

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

Comparez cela avec la disposition habituelle de l'hexagone:

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

Nous pouvons voir que les voisins sont maintenant tous les voisins habituels de 8 Moore, à l'exception des voisins du nord-ouest et du sud-est. Nous devons donc vérifier la contiguïté horizontale, verticale et sud-ouest / nord-est (bon et puis il y a les bords enveloppants). L'utilisation de cette présentation plus compacte offre également l'avantage supplémentaire de pouvoir utiliser celles-ci ××à la fin pour déterminer la taille de l'hexagone à la volée lorsque nous en avons besoin.

Une fois ce formulaire construit, nous apportons un changement supplémentaire à la chaîne entière:

T`d`À-É

Ceci remplace les chiffres par les lettres ASCII étendues

ÀÁÂÃÄÅÆÇÈÉ

Comme ils sont remplacés à la fois dans l'hexagone et dans la chaîne cible, cela n'aura aucune incidence sur le fait que la chaîne soit identique ou non. En outre, puisque ce sont des lettres \wet les \bidentifient toujours comme des cellules hexagonales. L'avantage de cette substitution est que nous pouvons maintenant utiliser \Ddans la prochaine expression rationnelle pour associer n'importe quel caractère (en particulier les sauts de ligne ainsi que les caractères autres que les sauts de ligne). Nous ne pouvons pas utiliser l' soption pour accomplir cela, car nous devrons .faire correspondre des caractères sans saut de ligne à plusieurs endroits.

Maintenant le dernier bit: déterminer si un chemin correspond à notre chaîne donnée. Cela se fait avec une seule regex monstrueuse. Vous pourriez vous demander pourquoi?!?! Eh bien, c’est fondamentalement un problème de retour en arrière: vous commencez quelque part et essayez un chemin tant qu’il correspond à la chaîne, et une fois que cela ne vous retourne pas, vous essayez un voisin différent du dernier caractère qui a fonctionné. La seule choseque vous obtenez gratuitement lorsque vous travaillez avec regex est un retour en arrière. C'est littéralement la seule chose que fait le moteur regex. Donc, si nous trouvons simplement un moyen de décrire un chemin valide (ce qui est assez compliqué pour ce genre de problème, mais tout à fait possible avec des groupes d'équilibrage), le moteur des expressions rationnelles trouvera ce chemin parmi tous ceux qui sont possibles pour nous. Il serait certainement possible de mettre en œuvre la recherche manuellement avec plusieurs étapes ( et je l'ai déjà fait par le passé ), mais je doute que cela soit plus court dans ce cas particulier.

Un problème avec l'implémentation de cela avec une expression rationnelle est que nous ne pouvons pas tisser de manière arbitraire le curseur du moteur des expressions rationnelles dans la chaîne pendant le retour en arrière (ce dont nous aurions besoin, car le chemin pourrait monter ou descendre). Donc, au lieu de cela, nous gardons trace de notre propre "curseur" dans un groupe de capture et le mettons à jour à chaque étape (nous pouvons nous déplacer temporairement à la position du curseur avec un lookaround). Cela nous permet également de stocker toutes les positions passées que nous utiliserons pour vérifier que nous n'avons pas visité la position actuelle auparavant.

Alors allons-y. Voici une version légèrement plus saine de la regex, avec des groupes nommés, une indentation, un ordre moins aléatoire des voisins et quelques commentaires:

\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

J'espère que l'idée générale en ressort clairement. À titre d'exemple du fonctionnement de l'un de ces mouvements le long du chemin, examinons le bit qui déplace le curseur vers le sud:

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

Rappelez-vous que les regards noirs doivent être lus de droite à gauche (ou de bas en haut), car c'est l'ordre dans lequel ils sont exécutés:

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

Notez qu'il n'est pas nécessaire de mettre une ancre devant le \k<pos>pour s'assurer que cela atteint réellement le début de la chaîne. <pos>commence toujours par une quantité de ce ×qui ne peut être trouvé nulle part ailleurs, donc cela agit déjà comme une ancre implicite.

Je ne veux pas trop encaisser ce message, je ne vais donc pas entrer dans les 11 autres cas en détail, mais en principe, ils fonctionnent tous de la même manière. Nous vérifions qu’il <next>peut être trouvé dans une direction spécifique (admissible) à partir de l’ancienne position du curseur à l’aide de groupes d’équilibrage, puis nous stockons la chaîne jusqu’à cette correspondance en tant que nouvelle position du curseur <pos>.

Python 3, 990 943 770 709 octets

Première réponse, yay!

EDIT: Faire une liste de contiguïté au golf. J'utilise maintenant une formule légèrement différente

EDIT 2: Suppression des peluches inutiles, beaucoup plus joué au golf.

EDIT 3: raccourci le code pour la conversion de l’index dans la liste en coordonnées, a joué au golf encore quelques choses.

La majorité des octets est liée à la création de la liste de contiguïté (celle-ci a le plus de potentiel pour être jouée au golf). À partir de là, il s’agit simplement de forcer brutalement la solution (ce que je pourrais peut-être faire en moins d’octets).

Golfé:

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 / explication:

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

Si près de la rétine! :( Ouais, bat Retina!

Javascript (ES6), 511 500 496 octets

(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 et commenté

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

Cas de test

L'extrait ci-dessous passera en revue tous les cas de vérification de la vérité et de la fausseté.

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