Martin Ender hat vor kurzem 100.000 erreicht und sich einige ziemlich großartige Sprachen ausgedacht . Wir werden ein bisschen Spaß mit einem von ihnen haben, Hexagony (und ein bisschen Regex für Retina )

Als kurze Übersicht müssen Sie ein Programm schreiben, das ein Hexagony-Raster eingibt und feststellt, ob sich auf diesem Raster ein Pfad befindet, der mit einer Textzeichenfolge übereinstimmt

Generieren

Hexagony generiert Sechsecke aus einer Zeichenfolge mit den folgenden Schritten:

1. Berechne die minimale Sechseckgröße (nimm die Länge des Strings und runde auf die nächste Sechseckzahl auf )
2. Wickeln Sie den Text in ein Sechseck der obigen Größe
3. Füllen Sie die restlichen Stellen mit ..

Beispielsweise abcdefghijklmerfordert die Textzeichenfolge ein Sechseck mit der Seitenlänge 3 und wird daher zu:

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

Beachten Sie nun, dass es 6 mögliche Richtungen gibt, die Sie in einem Sechseck fahren können. Beispielsweise ist im obigen Sechseck eneben abfjid.

Verpackung

Außerdem werden in Hexagony Hexagone wie folgt umbrochen:

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

Wenn Sie sich das 2. und 4. Beispiel ansehen, bemerken Sie, wie aund kan den gleichen Stellen, obwohl Sie in verschiedene Richtungen wickeln. Aufgrund dieser Tatsache grenzen diese Spots nur an 5 andere Standorte .

Um dies klarer zu machen:

   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. Kanten werden auf den gegenüberliegenden Nachbarn ( b->Iund G->j) gewickelt .
2. Die oberen / unteren Ecken werden zur gegenüberliegenden mittleren Ecke und nach oben / unten ( d->K,pund H->a,v) gewickelt.
3. Die mittleren Ecken werden in die oberen und unteren Ecken gewickelt ( v->a,H)

Pfade

Ein Pfad , der eine Folge benachbarter Orte sein soll, ohne an denselben Ort zurückzukehren.

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

Im obigen Sechseck aefkgmist ein gültiger Pfad. Ist abfdjedoch kein gültiger Pfad ( fund dgrenzt nicht an) und abeaist nicht gültig (kehrt zum aSpeicherort zurück).

Wir können diese Pfade verwenden, um Text abzugleichen (wie Regex) . Ein alphanumerisches Zeichen entspricht sich selbst (und nur sich selbst), und ein .Zeichen entspricht einem beliebigen Zeichen. Zum Beispiel kann der Weg aej..lgmwürde übereinstimmen aej..lgm, aejAAlgm, aeja.lgm, oder aej^%gm.

Input-Output

Ihr Programm sollte zwei Zeichenfolgen (in beliebiger Reihenfolge) enthalten. Die erste Zeichenfolge ist nicht leer und besteht nur aus alphanumerischen Zeichen [a-zA-Z0-9]. Dies stellt das Sechseck dar, mit dem Sie arbeiten. Die zweite Zeichenfolge besteht aus druckbaren Zeichen.

Sie müssen einen Wahrheitswert zurückgeben, wenn sich im Sechseck ein Pfad befindet, der mit der angegebenen Zeichenfolge übereinstimmt, andernfalls ein falscher Wert.

Testfälle

Wahrheit:

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

Falsch:

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

Dies ist ein Code-Golf , also machen Sie Ihre Antworten so kurz wie möglich in Ihrer Lieblingssprache.

Retina , 744 Bytes

Sorry Leute, diesmal kein Hexagony ...

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

.+¶
$.'$*_¶$&
^_¶
¶
((^_|\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

Erwartet die Zielzeichenfolge in der ersten Zeile und das Sechseck in der zweiten Zeile der Eingabe. Druckt 0oder 1entsprechend.

Probieren Sie es online! (Die erste Zeile aktiviert eine Testsuite, bei der jede Zeile ein Testfall ist und ¦für die Trennung anstelle eines Zeilenvorschubs verwendet wird.)

Der richtige Weg, um diese Herausforderung zu lösen, ist natürlich mit einem Regex. ;) Und ohne die Tatsache, dass diese Herausforderung auch das Entfalten des Sechsecks beinhaltet , würde diese Antwort eigentlich nur aus einem einzigen ~ 600 Byte langen regulären Ausdruck bestehen.

Dies ist noch nicht ganz optimal, aber ich bin mit dem Ergebnis ziemlich zufrieden (meine erste Arbeitsversion nach dem Entfernen von benannten Gruppen und anderem für die Vernunft erforderlichen Material war ungefähr 1000 Bytes). Ich denke, ich könnte ungefähr 10 Bytes einsparen, indem ich die Reihenfolge der Zeichenfolge und des Sechsecks vertausche, aber es würde am Ende ein vollständiges Umschreiben des regulären Ausdrucks erfordern, was ich derzeit nicht für richtig halte. Es gibt auch eine 2-Byte-Einsparung, wenn die GBühne weggelassen wird , aber dies verlangsamt die Lösung erheblich. Ich werde mit dieser Änderung warten, bis ich sicher bin, dass ich so gut wie möglich Golf gespielt habe.

Erläuterung

Der Hauptteil dieser Lösung verwendet in großem Umfang Bilanzkreise , daher empfehle ich, sie zu lesen, wenn Sie verstehen möchten, wie dies im Detail funktioniert (ich werde Ihnen keine Vorwürfe machen, wenn Sie dies nicht tun ...).

Der erste Teil der Lösung (dh alles außer den letzten beiden Zeilen) ist eine modifizierte Version meiner Antwort auf das Entfalten des Hexagony-Quellcodes . Es konstruiert das Sechseck, während die Zielzeichenfolge unberührt bleibt (und es konstruiert tatsächlich das Sechseck vor der Zielzeichenfolge). Ich habe einige Änderungen am vorherigen Code vorgenommen, um Bytes zu sparen:

• Das Hintergrundzeichen steht ×anstelle eines Leerzeichens, damit es nicht zu Konflikten mit potenziellen Leerzeichen in der Eingabe kommt.
• Das No-Op / Wildcard-Zeichen ist _stattdessen ., sodass Rasterzellen zuverlässig als Wortzeichen identifiziert werden können.
• Ich füge keine Leerzeichen oder Einrückungen ein, nachdem das Sechseck zum ersten Mal konstruiert wurde. Das gibt mir ein schräges Sechseck, aber das ist tatsächlich viel bequemer zu bearbeiten und die Adjazenzregeln sind ziemlich einfach.

Hier ist ein Beispiel. Für den folgenden Testfall:

ja
abcdefghij

Wir bekommen:

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

Vergleichen Sie dies mit der üblichen Anordnung des Sechsecks:

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

Wir können sehen, dass die Nachbarn jetzt alle die üblichen 8 Moore-Nachbarn sind, mit Ausnahme der Nordwest- und Südostnachbarn. Wir müssen also die horizontale, vertikale und südwestliche / nordöstliche Nachbarschaft prüfen (und dann gibt es die Umhüllungskanten). Die Verwendung dieses kompakteren Layouts hat auch den Vorteil, dass wir diese ××am Ende verwenden können, um die Größe des Sechsecks im Handumdrehen zu bestimmen, wenn wir es benötigen.

Nachdem dieses Formular erstellt wurde, nehmen wir eine weitere Änderung an der gesamten Zeichenfolge vor:

T`d`À-É

Dadurch werden die Ziffern durch die erweiterten ASCII-Buchstaben ersetzt

ÀÁÂÃÄÅÆÇÈÉ

Da sie sowohl im Sechseck als auch in der Zielzeichenfolge ersetzt werden, hat dies keinen Einfluss darauf, ob die Zeichenfolge übereinstimmt oder nicht. Außerdem, da es sich um Buchstaben handelt \wund diese \bimmer noch als Sechseckzellen identifiziert werden. Der Vorteil dieser Ersetzung besteht darin, dass wir nun \Din der kommenden regulären Ausdrucksweise jedes Zeichen (insbesondere Zeilenvorschübe sowie Nicht-Zeilenvorschübe) abgleichen können. Wir können die sOption nicht verwenden, um dies zu erreichen, da wir .Zeichen ohne Zeilenvorschub an mehreren Stellen abgleichen müssen.

Jetzt das letzte Bit: Bestimmen, ob ein Pfad mit unserer angegebenen Zeichenfolge übereinstimmt. Dies geschieht mit einem einzigen monströsen Regex. Sie könnten sich fragen, warum?!?! Nun, das ist im Grunde genommen ein Backtracking-Problem: Sie beginnen irgendwo und versuchen einen Pfad, solange er mit der Zeichenfolge übereinstimmt, und wenn dies nicht der Fall ist, gehen Sie zurück und versuchen Sie es mit einem anderen Nachbarn als dem zuletzt funktionierenden Zeichen. Die eine SacheDas, was Sie bei der Arbeit mit Regex kostenlos bekommen, ist Backtracking. Das ist buchstäblich das einzige, was die Regex-Engine macht. Wenn wir also nur einen Weg finden, um einen gültigen Pfad zu beschreiben (der für diese Art von Problem schwierig genug ist, aber mit Bilanzgruppen definitiv möglich ist), dann wird die Regex-Engine diesen Pfad unter allen möglichen für uns herausfinden. Es wäre sicherlich möglich, die Suche manuell in mehreren Schritten durchzuführen ( und das habe ich in der Vergangenheit getan ), aber ich bezweifle, dass es in diesem speziellen Fall kürzer wäre.

Ein Problem bei der Implementierung mit einem regulären Ausdruck ist, dass wir den Cursor des regulären Ausdrucksmoduls während des Zurückverfolgens nicht willkürlich durch den String bewegen können (was wir benötigen würden, da der Pfad möglicherweise nach oben oder unten führt). Stattdessen verfolgen wir unseren eigenen "Cursor" in einer Erfassungsgruppe und aktualisieren diesen bei jedem Schritt (wir können mit einem Lookaround vorübergehend an die Position des Cursors springen). Auf diese Weise können wir auch alle früheren Positionen speichern, anhand derer wir überprüfen, ob wir die aktuelle Position noch nicht besucht haben.

Also lasst uns loslegen. Hier ist eine etwas vernünftigere Version des regulären Ausdrucks mit benannten Gruppen, Einrückung, weniger zufälliger Reihenfolge der Nachbarn und einigen Kommentaren:

\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

Ich hoffe, dass die allgemeine Idee hieraus ungefähr klar wird. Schauen wir uns als Beispiel für eine dieser Bewegungen entlang des Pfades das Bit an, das den Cursor nach Süden bewegt:

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

Denken Sie daran, dass Lookbehinds von rechts nach links (oder von unten nach oben) gelesen werden sollten, da dies die Reihenfolge ist, in der sie ausgeführt werden:

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

Beachten Sie, dass es nicht erforderlich ist, einen Anker vor den \k<pos>zu setzen, um sicherzustellen, dass dieser tatsächlich den Anfang der Zeichenfolge erreicht. <pos>Beginnt immer mit einer Menge ×, die nirgendwo anders zu finden ist, und fungiert daher bereits als impliziter Anker.

Ich möchte diesen Beitrag nicht mehr als nötig aufblähen, deshalb gehe ich nicht auf die anderen 11 Fälle im Detail ein, aber im Prinzip funktionieren sie alle ähnlich. Wir überprüfen <next>mit Hilfe von Bilanzkreisen, ob von der alten Cursorposition aus eine bestimmte (zulässige) Richtung gefunden werden kann, und speichern dann die Zeichenfolge bis zu dieser Übereinstimmung als neue Cursorposition in <pos>.

Python 3, 990 943 770 709 Bytes

Erste Antwort, yay!

BEARBEITEN: Erstellen einer Golf-Adjazenzliste. Ich verwende jetzt eine etwas andere Formel

EDIT 2: Unnötige Flusen entfernt, viel mehr golfen.

EDIT 3: Der Code für die Konvertierung von Index in Liste in Koordinaten wurde verkürzt, und es wurden noch ein paar Dinge erledigt.

Der Großteil der Bytes bezieht sich auf die Erstellung der Adjazenzliste (sie hat das größte Potenzial zum Golfen). Von da an ist es eine einfache Sache, die Lösung brachial zu erzwingen (was ich möglicherweise in weniger Bytes tun kann).

Golf gespielt:

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 / Erklärung:

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

So nah an der Retina! :( Yay, schlagen Sie 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 und kommentiert

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

Testfälle

Das folgende Snippet geht alle wahrheitsgemäßen und falschen Testfälle durch.

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