Martin Ender baru-baru ini mencapai 100K, dan telah menghasilkan beberapa bahasa yang cukup mengagumkan . Kita akan bersenang-senang dengan salah satu dari mereka, Hexagony (dan sedikit regex untuk Retina )

Sebagai gambaran umum singkat, Anda perlu menulis sebuah program yang memasukkan kisi Hexagony dan menentukan apakah ada jalur di kisi itu yang cocok dengan string teks

Menghasilkan

Hexagony menghasilkan hexagon dari string teks menggunakan langkah-langkah berikut:

1. Hitung ukuran segi enam minimum (ambil panjang string dan bulatkan ke nomor hex terdekat )
2. Membungkus teks menjadi segi enam dengan ukuran di atas
3. Mengisi lokasi yang tersisa dengan ..

Misalnya, string teks abcdefghijklmmemerlukan segi enam sisi-panjang 3, dan karenanya menjadi:

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

Sekarang, perhatikan bahwa ada 6 kemungkinan arah yang bisa Anda tempuh dalam segi enam. Misalnya, dalam segi enam di atas, eberbatasan dengan abfjid.

Pembungkus

Selanjutnya, dalam Hexagony, hexagon membungkus:

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

Jika Anda melihat contoh ke-2 dan ke-4, perhatikan bagaimana adan kberada di tempat yang sama, meskipun Anda membungkus ke arah yang berbeda. Karena kenyataan ini, tempat-tempat ini hanya berdekatan dengan 5 lokasi lainnya .

Untuk memperjelas ini:

   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. Tepi membungkus tetangga yang berlawanan ( b->Idan G->j).
2. Sudut atas / bawah membungkus ke sudut tengah yang berlawanan dan atas / bawah ( d->K,pdan H->a,v).
3. Sudut tengah membungkus ke sudut atas dan bawah ( v->a,H)

Jalan

Sebuah jalan menjadi urutan lokasi yang berdekatan tanpa kembali ke lokasi yang sama.

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

Dalam segi enam di atas, aefkgmadalah jalur yang valid. Namun, abfdini bukan jalur yang valid ( fdan dtidak berdekatan), dan abeatidak valid (kembali ke alokasi).

Kita dapat menggunakan jalur ini untuk mencocokkan teks (seperti regex) . Karakter alfa-numerik cocok dengan dirinya sendiri (dan hanya dirinya sendiri), dan .cocok dengan karakter apa pun. Misalnya, jalan aej..lgmakan cocok aej..lgm, aejAAlgm, aeja.lgm, atau aej^%gm.

Input output

Program Anda harus mengambil dua string (dalam urutan apa pun). String pertama tidak akan kosong, dan hanya terdiri dari karakter alfanumerik [a-zA-Z0-9]. Ini akan mewakili segi enam tempat Anda beroperasi. String kedua akan terdiri dari karakter yang dapat dicetak.

Anda harus mengembalikan nilai kebenaran jika ada jalur di segi enam yang cocok dengan string teks yang diberikan, jika tidak nilai salah.

Uji kasus

Benar:

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

Ini adalah kode-golf , jadi buat jawaban Anda sesingkat mungkin dalam bahasa favorit Anda.

Retina , 744 byte

Maaf teman, tidak ada Hexagony saat ini ...

Hitungan byte mengasumsikan penyandian 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

Mengharapkan string target pada baris pertama dan segi enam pada baris kedua input. Cetakan 0atau 1sesuai.

Cobalah online! (Baris pertama memungkinkan suite uji, di mana setiap baris adalah kasus uji, menggunakan ¦untuk pemisahan dan bukan linefeed.)

Cara yang tepat untuk mengatasi tantangan ini adalah dengan regex tentunya. ;) Dan jika bukan karena fakta bahwa tantangan ini juga melibatkan prosedur membuka segi enam , jawaban ini sebenarnya hanya terdiri dari satu regex panjang ~ 600 byte.

Ini belum cukup optimal bermain golf, tapi saya cukup senang dengan hasilnya (versi kerja pertama saya, setelah menghapus grup bernama dan hal-hal lain yang diperlukan untuk kewarasan, sekitar 1000 byte). Saya pikir saya bisa menghemat sekitar 10 byte dengan menukar urutan string dan hexagon tetapi akan membutuhkan penulisan ulang lengkap regex pada akhirnya, yang saya tidak rasakan saat ini. Ada juga penghematan 2-byte dengan menghilangkan Gpanggung, tetapi itu sangat memperlambat solusinya, jadi saya akan menunggu dengan membuat perubahan itu sampai saya yakin saya telah bermain golf ini sebaik yang saya bisa.

Penjelasan

Bagian utama dari solusi ini membuat penggunaan ekstensif kelompok penyeimbang , jadi saya sarankan membaca mereka, jika Anda ingin memahami bagaimana ini bekerja secara rinci (saya tidak akan menyalahkan Anda jika Anda tidak ...).

Bagian pertama dari solusi (yaitu semuanya kecuali dua baris terakhir) adalah versi modifikasi dari jawaban saya untuk Unfolding the Hexagony source code . Itu membangun hexagon, sambil membiarkan string target tidak tersentuh (dan itu sebenarnya membangun hexagon sebelum string target). Saya telah membuat beberapa perubahan pada kode sebelumnya untuk menghemat byte:

• Karakter latar belakang ×bukannya spasi sehingga tidak bertentangan dengan ruang potensial dalam input.
• No-op / wildcard karakter _bukan ., sehingga sel-sel jaringan dapat diidentifikasi andal sebagai karakter kata.
• Saya tidak memasukkan spasi atau lekukan setelah segi enam pertama kali dibangun. Itu memberi saya segi enam miring, tapi itu sebenarnya jauh lebih nyaman untuk bekerja dengan dan aturan kedekatan cukup sederhana.

Berikut ini sebuah contoh. Untuk test case berikut:

ja
abcdefghij

Kita mendapatkan:

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

Bandingkan ini dengan tata letak hexagon yang biasa:

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

Kita bisa melihat bahwa para tetangga sekarang semua tetangga Moore-8 yang biasa, kecuali tetangga barat laut dan tenggara. Jadi kita perlu memeriksa adjacency horisontal, vertikal dan barat daya / timur laut (baik dan kemudian ada tepi pembungkus). Menggunakan tata letak yang lebih ringkas ini juga memiliki bonus bahwa kita akan dapat menggunakannya ××pada akhirnya untuk menentukan ukuran segi enam saat kita membutuhkannya.

Setelah formulir ini dibuat, kami membuat satu lagi perubahan pada seluruh string:

T`d`À-É

Ini menggantikan digit dengan huruf ASCII yang diperluas

ÀÁÂÃÄÅÆÇÈÉ

Karena mereka diganti baik di hexagon dan di string target, ini tidak akan mempengaruhi apakah string cocok atau tidak. Juga, karena mereka adalah huruf \wdan \bmasih mengidentifikasi mereka sebagai sel segi enam. Manfaat melakukan substitusi ini adalah bahwa kita sekarang dapat menggunakan \Ddalam regex yang akan datang untuk mencocokkan karakter apa pun (khususnya, umpan baris serta karakter non-umpan baris). Kami tidak dapat menggunakan sopsi untuk mencapai itu, karena kami harus .mencocokkan karakter non-linefeed di beberapa tempat.

Sekarang bit terakhir: menentukan apakah ada jalur yang cocok dengan string kami. Ini dilakukan dengan regex raksasa tunggal. Anda mungkin bertanya pada diri sendiri mengapa?!?! Nah, ini pada dasarnya masalah penelusuran mundur: Anda memulai suatu tempat dan mencoba jalur selama cocok dengan string, dan sekali tidak Anda mundur dan mencoba tetangga yang berbeda dari karakter terakhir yang bekerja. Satu halyang Anda dapatkan secara gratis saat bekerja dengan regex mundur. Itulah satu-satunya hal yang dilakukan mesin regex. Jadi jika kita hanya menemukan cara untuk menggambarkan jalur yang valid (yang cukup rumit untuk masalah seperti ini, tapi pasti mungkin dengan kelompok penyeimbang), maka mesin regex akan memilah menemukan jalan itu di antara semua yang mungkin bagi kita. Tentu akan mungkin untuk mengimplementasikan pencarian secara manual dengan beberapa tahap ( dan saya telah melakukannya di masa lalu ), tapi saya ragu itu akan lebih pendek dalam kasus khusus ini.

Salah satu masalah dengan menerapkan ini dengan regex adalah bahwa kita tidak dapat secara sewenang-wenang mengayunkan kursor mesin regex bolak-balik melalui string selama backtracking (yang kita perlukan karena jalur mungkin naik atau turun). Jadi alih-alih, kami melacak "kursor" kami sendiri dalam grup penangkap dan memutakhirkannya di setiap langkah (kami dapat pindah ke posisi kursor untuk sementara dengan pencarian). Ini juga memungkinkan kita untuk menyimpan semua posisi sebelumnya yang akan kita gunakan untuk memeriksa bahwa kita belum mengunjungi posisi saat ini sebelumnya.

Jadi mari kita mulai. Berikut ini adalah versi regex yang sedikit lebih waras, dengan grup yang diberi nama, indentasi, urutan tetangga yang kurang acak, dan beberapa komentar:

\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

Saya berharap bahwa ide umum kurang lebih jelas dari ini. Sebagai contoh bagaimana salah satu gerakan di sepanjang jalan itu bekerja, mari kita lihat bit yang menggerakkan kursor ke selatan:

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

Ingatlah bahwa lookbehinds harus dibaca dari kanan ke kiri (atau dari bawah ke atas), karena itulah urutan pelaksanaannya:

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

Perhatikan bahwa tidak perlu meletakkan jangkar di depan \k<pos>untuk memastikan bahwa ini benar-benar mencapai awal string. <pos>selalu dimulai dengan jumlah ×yang tidak dapat ditemukan di tempat lain, jadi ini sudah bertindak sebagai jangkar implisit.

Saya tidak ingin menggembungkan posting ini lebih dari yang diperlukan, jadi saya tidak akan membahas 11 kasus lainnya secara terperinci, tetapi pada prinsipnya semuanya bekerja sama. Kami memeriksa bahwa <next>dapat ditemukan dalam beberapa arah tertentu (dapat diterima) dari posisi kursor lama dengan bantuan kelompok penyeimbang, dan kemudian kami menyimpan string hingga cocok dengan posisi kursor baru di <pos>.

Python 3, 990 943 770 709 byte

Jawaban pertama, yay!

EDIT: Pembuatan daftar kedekatan golf. Saya sekarang menggunakan formula yang sedikit berbeda

EDIT 2: Menghilangkan bulu yang tidak perlu, lebih banyak bermain golf.

EDIT 3: Mempersingkat kode untuk konversi dari indeks dalam daftar ke koordinat, golf beberapa hal lagi.

Mayoritas byte terkait dengan membuat daftar adjacency (memiliki potensi paling besar untuk golf). Sejak saat itu, ini adalah masalah sederhana yang memaksa solusi (yang mungkin bisa saya lakukan dalam lebih sedikit byte).

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

Tanpa penjelasan bersama:

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

Begitu dekat dengan Retina! :( Yay, kalahkan Retina!

Javascript (ES6), 511 500 496 byte

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

Tidak diikat dan dikomentari

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

Uji kasus

Cuplikan di bawah ini akan menelusuri semua kasus uji yang benar dan salah.

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