Martin Ender niedawno osiągnął 100 000 i wymyślił kilka niesamowitych języków . Będziemy się dobrze bawić z jednym z nich, Hexagony (i trochę wyrażenia regularnego dla Retina )

Krótko mówiąc, musisz napisać program, który wprowadza siatkę sześciokątną i określa, czy na tej siatce jest ścieżka, która pasuje do ciągu tekstu

Generowanie

Sześciokąt generuje sześciokąty z ciągu tekstowego, wykonując następujące kroki:

1. Oblicz minimalny rozmiar sześciokąta (weź długość łańcucha i zaokrąglij w górę do najbliższej liczby szesnastkowej )
2. Zawijanie tekstu w sześciokąt o powyższym rozmiarze
3. Wypełnianie pozostałych lokalizacji ..

Na przykład ciąg tekstu abcdefghijklmwymaga sześciokąta o długości 3 i dlatego staje się:

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

Teraz zauważ, że istnieje 6 możliwych kierunków, którymi możesz podróżować w sześciokącie. Na przykład w powyższym sześciokącie esąsiaduje z abfjid.

Zawijanie

Ponadto w Hexagony, sześciokąty zawijają:

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

Jeśli spojrzysz na drugi i czwarty przykład, zauważ, jak ai kjesteś w tych samych miejscach, mimo że owijasz się w różnych kierunkach. Z tego powodu miejsca te sąsiadują tylko z 5 innymi lokalizacjami .

Aby to wyjaśnić:

   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. Krawędzie owijają się na swoich przeciwnych sąsiadach ( b->Ii G->j).
2. Górne / dolne rogi zawijają się w przeciwległym środkowym rogu oraz w górę / w dół ( d->K,pi H->a,v).
3. Środkowe narożniki są zawijane zarówno do górnego, jak i dolnego rogu ( v->a,H)

Ścieżki

Ścieżka się sekwencję sąsiednich pozycjach, nie powraca do tej samej lokalizacji.

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

W powyższym sześciokącie aefkgmjest poprawna ścieżka. Nie abfdjest to jednak poprawna ścieżka ( fi dnie sąsiadują) i abeanie jest poprawna (wraca do alokalizacji).

Możemy użyć tych ścieżek do dopasowania tekstu (np. Regex) . Znak alfanumeryczny pasuje do siebie (i tylko do siebie), a .dopasowuje dowolny znak. Na przykład, ścieżka aej..lgmbędzie pasować aej..lgm, aejAAlgm, aeja.lgm, lub aej^%gm.

Wejście wyjście

Twój program powinien przyjąć dwa ciągi (w dowolnej kolejności). Pierwszy ciąg będzie niepusty i będzie się składał wyłącznie ze znaków alfanumerycznych [a-zA-Z0-9]. Będzie to reprezentowało sześciokąt, na którym operujesz. Drugi ciąg znaków będzie się składał ze znaków do wydrukowania.

Musisz zwrócić prawdziwą wartość, jeśli w sześciokącie znajduje się ścieżka pasująca do podanego ciągu tekstu, w przeciwnym razie wartość fałszowania.

Przypadki testowe

Prawda:

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

To jest gra w golfa , więc udziel odpowiedzi tak krótko, jak to możliwe, w swoim ulubionym języku.

Retina , 744 bajty

Przepraszam, tym razem brak heksagonii ...

Liczba bajtów zakłada kodowanie 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

Oczekuje ciągu docelowego w pierwszym wierszu i sześciokąta w drugim wierszu danych wejściowych. Drukuje 0lub 1odpowiednio.

Wypróbuj online! (Pierwszy wiersz włącza zestaw testowy, gdzie każdy wiersz jest przypadkiem testowym, używającym ¦do separacji zamiast podawania linii).

Właściwym sposobem rozwiązania tego problemu jest oczywiście wyrażenie regularne. ;) A gdyby nie to, że wyzwanie to obejmuje również procedurę rozwijania sześciokąta , odpowiedź ta składałaby się tylko z jednego ~ 600-bajtowego wyrażenia regularnego.

Nie jest to jeszcze optymalnie zoptymalizowane, ale jestem bardzo zadowolony z wyniku (moja pierwsza działająca wersja, po usunięciu nazwanych grup i innych rzeczy wymaganych dla zdrowia psychicznego, miała około 1000 bajtów). Myślę, że mógłbym zaoszczędzić około 10 bajtów, zamieniając kolejność łańcucha i sześciokąta, ale wymagałoby to całkowitego przepisania wyrażenia regularnego na końcu, czego nie czuję teraz. Istnieje również 2-bajtowa oszczędność poprzez pominięcie Gsceny, ale znacznie spowalnia to rozwiązanie, więc poczekam z wprowadzeniem tej zmiany, dopóki nie upewnię się, że grałem w nią najlepiej, jak potrafię.

Wyjaśnienie

Główna część tego rozwiązania w szerokim zakresie wykorzystuje grupy równoważące , więc polecam je przeczytać, jeśli chcesz zrozumieć, jak to działa w szczegółach (nie obwiniam cię, jeśli nie ...).

Pierwsza część rozwiązania (tj. Wszystko oprócz dwóch ostatnich wierszy) to zmodyfikowana wersja mojej odpowiedzi na Unfolding the Hexagony code source . Konstruuje sześciokąt, pozostawiając nietknięty ciąg docelowy (i faktycznie tworzy sześciokąt przed ciągiem docelowym). Wprowadziłem pewne zmiany w poprzednim kodzie, aby zapisać bajty:

• Znak tła jest ×zamiast spacji, aby nie powodował konfliktu z potencjalnymi spacjami na wejściu.
• _Zamiast tego występuje znak „brak operacji / symbol wieloznaczny” ., dzięki czemu komórki siatki mogą być niezawodnie identyfikowane jako znaki słowne.
• Po wstawieniu sześciokąta nie wstawiam żadnych spacji ani wcięć. Daje mi to nachylony sześciokąt, ale w rzeczywistości jest o wiele wygodniejszy w pracy, a zasady sąsiedztwa są dość proste.

Oto przykład. Dla następującego przypadku testowego:

ja
abcdefghij

Otrzymujemy:

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

Porównaj to ze zwykłym układem sześciokąta:

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

Widzimy, że sąsiedzi są teraz zwykłymi 8 sąsiadami Moore, z wyjątkiem północno-zachodnich i południowo-wschodnich sąsiadów. Musimy więc sprawdzić przyleganie poziome, pionowe i południowo-zachodnie / północno-wschodnie (dobrze, a potem są krawędzie owijania). Korzystanie z tego bardziej zwartego układu ma również tę zaletę, że będziemy mogli wykorzystać je ××na końcu, aby określić rozmiar sześciokąta w locie, gdy go potrzebujemy.

Po zbudowaniu tego formularza wprowadzamy jeszcze jedną zmianę do całego łańcucha:

T`d`À-É

Zastępuje to cyfry rozszerzonymi literami ASCII

ÀÁÂÃÄÅÆÇÈÉ

Ponieważ są one zastępowane zarówno w sześciokącie, jak i w ciągu docelowym, nie wpłynie to na to, czy ciąg zostanie dopasowany, czy nie. Ponadto, ponieważ są to litery \wi \bnadal identyfikują je jako komórki sześciokąta. Zaletą wykonania tej zamiany jest to, że możemy teraz użyć \Dw nadchodzącym wyrażeniu regularnym, aby dopasować dowolny znak (w szczególności znaki linefeed, a także znaki non-linefeed). Nie możemy skorzystać z sopcji, aby to osiągnąć, ponieważ .w wielu miejscach będziemy musieli dopasować znaki nieciągłe.

Teraz ostatni bit: ustalenie, czy jakakolwiek ścieżka pasuje do naszego podanego ciągu. Odbywa się to za pomocą jednego monstrualnego wyrażenia regularnego. Możesz zadać sobie pytanie, dlaczego?!?! Cóż, jest to zasadniczo problem z cofaniem się: zaczynasz gdzieś i próbujesz ścieżki, dopóki pasuje ona do łańcucha, a kiedy już nie, wycofujesz się i próbujesz innego sąsiada od ostatniej działającej postaci. Jednoktóre otrzymujesz za darmo podczas pracy z regexem jest cofanie się. To dosłownie jedyna rzecz, którą robi silnik regex. Jeśli więc znajdziemy sposób na opisanie prawidłowej ścieżki (co jest dość skomplikowane dla tego rodzaju problemu, ale z pewnością możliwe w przypadku grup równoważących), wówczas silnik wyrażenia regularnego wyszuka znalezienie tej ścieżki wśród wszystkich możliwych dla nas. Z pewnością byłoby możliwe ręczne zaimplementowanie wyszukiwania na wielu etapach ( a robiłem to w przeszłości ), ale wątpię, aby w tym konkretnym przypadku było ono krótsze.

Jednym z problemów związanych z implementacją tego z wyrażeniem regularnym jest to, że nie możemy arbitralnie przecinać kursora silnika wyrażenia regularnego w przód iw tył przez łańcuch podczas cofania (co byłoby nam potrzebne, ponieważ ścieżka może iść w górę lub w dół). Zamiast tego śledzimy własnego „kursora” w grupie przechwytywania i aktualizujemy go na każdym kroku (możemy tymczasowo przejść do pozycji kursora za pomocą obejrzenia). Dzięki temu możemy również przechowywać wszystkie poprzednie pozycje, których użyjemy, aby sprawdzić, czy nie odwiedziliśmy poprzedniej pozycji.

Przejdźmy więc do tego. Oto nieco rozsądniejsza wersja wyrażenia regularnego, z nazwanymi grupami, wcięciami, mniej losową kolejnością sąsiadów i kilkoma komentarzami:

\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

Mam nadzieję, że ogólna idea jest w przybliżeniu jasna z tego. Jako przykład działania jednego z tych ruchów wzdłuż ścieżki, spójrzmy na bit, który przesuwa kursor na południe:

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

Pamiętaj, że spojrzenia powinny być odczytywane od prawej do lewej (lub od dołu do góry), ponieważ w takiej kolejności są wykonywane:

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

Zauważ, że nie jest konieczne umieszczanie kotwicy przed, \k<pos>aby upewnić się, że faktycznie osiągnie początek łańcucha. <pos>zawsze zaczyna się od ilości ×, której nie można znaleźć nigdzie indziej, więc działa to już jako ukryta kotwica.

Nie chcę przesadzać z tym postem bardziej niż to konieczne, więc nie będę szczegółowo omawiał pozostałych 11 przypadków, ale w zasadzie wszystkie działają podobnie. Sprawdzamy, <next>czy można znaleźć w jakimś określonym (dopuszczalnym) kierunku od starej pozycji kursora za pomocą grup równoważących, a następnie przechowujemy ciąg znaków do tego dopasowania jako nową pozycję kursora w <pos>.

Python 3, 990 943 770 709 bajtów

Pierwsza odpowiedź, tak!

EDYCJA: Tworzenie listy sąsiadów golfowych. Teraz używam nieco innej formuły

EDYCJA 2: Usunąłem niepotrzebny puch, grałem w golfa o wiele więcej.

EDYCJA 3: Skrócono kod konwersji z indeksu na liście do współrzędnych, grałem w golfa jeszcze kilka rzeczy.

Większość bajtów dotyczy tworzenia listy sąsiadów (ma ona największy potencjał do gry w golfa). Odtąd jest to prosta sprawa brutalnego wymuszania rozwiązania (co może być w stanie zrobić w mniejszej liczbie bajtów).

Gra w golfa:

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 z wyjaśnieniem:

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

Tak blisko Retina! :( Tak, pokonaj Retinę!

JavaScript (ES6), 511 500 496 bajtów

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

Nie golfił i skomentował

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

Przypadki testowe

Poniższy fragment omówi wszystkie przypadki testowe zgodne z prawdą i fałszem.

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