Martin Ender는 최근 100K를 기록했으며 꽤 멋진 언어를 생각해 냈습니다 . 우리는 그들 중 하나 인 Hexagony (그리고 Retina에 대한 약간의 정규 표현식 ) 와 약간의 재미를 가질 것입니다.
간단한 개요로, Hexagony 그리드 를 입력하고 해당 그리드에 텍스트 문자열과 일치하는 경로가 있는지 판별 하는 프로그램을 작성해야 합니다.
생성
Hexagony는 다음 단계를 사용하여 텍스트 문자열에서 육각형을 생성합니다.
- 최소 육각형 크기를 계산하십시오 (끈의 길이를 취하고 가장 가까운 16 진수로 반올림하십시오 )
- 위의 크기의 육각형으로 텍스트 감싸기
- 로 나머지 위치를 채 웁니다
.
.
예를 들어, 텍스트 문자열은 abcdefghijklm
측면 길이 3의 육각형이 필요하므로 다음과 같이됩니다.
a b c
d e f g
h i j k l
m . . .
. . .
이제 6 각형으로 여행 할 수있는 6 가지 방향이 있습니다. 예를 들어, 위 육각형에서은에 e
인접합니다 abfjid
.
외장
또한 Hexagony에서는 육각형이 다음과 같이 랩핑됩니다.
. . . . . 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 . .
두 번째와 네 번째 예를 보면 다른 방향으로 포장되어 있음에도 불구하고 같은 지점에있는 방법 a
과 k
위치를 확인하십시오. 이 사실로 인해이 지점들은 5 곳의 다른 위치에만 인접 해 있습니다 .
이것을 더 명확하게하려면 :
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
- 가장자리는 반대쪽 이웃 (
b->I
및G->j
) 으로 줄 바꿈됩니다 . - 위 / 아래 모서리는 반대쪽 가운데 모서리와 위 / 아래 (
d->K,p
및H->a,v
) 로 둘러싸 입니다. - 가운데 모서리는 위쪽 및 아래쪽 모서리 모두로 줄 바꿈 (
v->a,H
)
경로
동일한 위치로 돌아 가지 않고 인접한 위치의 시퀀스가 되는 경로 입니다.
a b c
d e f g
h i f k l
m . . .
. . .
위의 육각형에서 aefkgm
유효한 경로입니다. 그러나, abfd
유효한 경로가 아닌 ( f
와 d
인접하지 않은), 및 abea
유효한 (받는 리턴없는 a
위치).
이러한 경로를 사용하여 텍스트와 일치시킬 수 있습니다 (예 : 정규식) . 영숫자 문자는 자신과 .
일치하며 모든 문자와 일치합니다. 예를 들어, 경로가 aej..lgm
일치합니다 aej..lgm
, aejAAlgm
, aeja.lgm
, 또는 aej^%gm
.
입출력
프로그램은 어떤 순서로든 두 개의 문자열을 가져야합니다. 첫 번째 문자열은 비어 있지 않으며 영숫자로만 구성됩니다 [a-zA-Z0-9]
. 작동중인 육각형을 나타냅니다. 두 번째 문자열은 인쇄 가능한 문자로 구성됩니다.
주어진 텍스트 문자열과 일치하는 육각형 경로가 있으면 거짓 값을 반환해야합니다. 그렇지 않으면 거짓 값입니다.
테스트 사례
진실한 :
"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"
거짓 :
"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"
이것은 코드 골프 이므로 선호하는 언어로 가능한 한 빨리 답변하십시오.
답변
레티 나 744 바이트
죄송합니다. 이번에는 Hexagony가 없습니다 …
바이트 수는 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
입력의 첫 번째 행에서 대상 문자열을, 두 번째 행에서 육각형을 예상합니다. 인쇄 0
하거나 1
그에 따라.
온라인으로 사용해보십시오! 첫 번째 줄은 ¦
줄 바꿈 대신 구분 을 위해 사용하는 각 테스트 줄인 테스트 스위트를 활성화합니다 .
이 문제를 해결하는 올바른 방법은 물론 정규식을 사용하는 것입니다. 😉 그리고이 도전이 육각형 의 전개 절차와 관련이 없다는 사실이 아니라면 이 대답은 실제로 ~ 600 바이트 길이의 정규 표현식으로 구성됩니다.
이것은 아직 최적의 골프는 아니지만 결과에 매우 만족합니다 (이름이 지정된 그룹과 위생을 위해 필요한 다른 것들을 제거한 후의 첫 번째 작업 버전은 약 1000 바이트였습니다). 문자열과 육각형의 순서를 바꿈으로써 약 10 바이트를 절약 할 수 있다고 생각하지만 끝에 정규식을 완전히 다시 작성해야합니다. 지금 기분이 좋지 않습니다. G
스테이지 를 생략하여 2 바이트를 절약 할 수도 있지만 솔루션 속도를 상당히 느리게 할 수 있으므로 골프를 할 수있을뿐만 아니라 골프를 칠 때까지 변경을 기다릴 것입니다.
설명
이 솔루션의 주요 부분은 밸런싱 그룹을 광범위하게 사용하기 때문에 이것이 어떻게 작동하는지 이해하고 싶다면 읽어보십시오. (그렇지 않으면 당신을 비난하지 않을 것입니다.)
솔루션의 첫 번째 부분 (즉, 마지막 두 줄을 제외한 모든 것)은 Hexagony 소스 코드 확장에 대한 내 대답의 수정 된 버전입니다 . 대상 문자열을 그대로 유지하면서 육각형을 구성하고 실제로 대상 문자열 앞에 육각형을 구성합니다. 바이트를 절약하기 위해 이전 코드를 약간 변경했습니다.
- 배경 문자는
×
공백 대신 입력의 잠재적 공백과 충돌하지 않습니다. - no-op / wildcard 문자는
_
대신.
그리드 셀을 단어 문자로 확실하게 식별 할 수 있도록합니다. - 육각형이 처음 구성된 후에 공백이나 들여 쓰기를 삽입하지 않습니다. 그것은 경사 육각형을 제공하지만 실제로 작업하기가 훨씬 편리하며 인접 규칙은 매우 간단합니다.
다음은 예입니다. 다음 테스트 사례의 경우 :
ja
abcdefghij
우리는 얻는다 :
××abc
×defg
hij__
____×
___××
ja
이것을 일반적인 육각형 레이아웃과 비교하십시오.
a b c
d e f g
h i j _ _
_ _ _ _
_ _ _
우리는 이웃이 이제 북서쪽과 남동쪽 이웃을 제외하고 일반적인 8 개의 무어 이웃 모두임을 알 수 있습니다. 따라서 수평, 수직 및 남서 / 북동 인접성을 확인해야합니다 (잘 감싸는 가장자리가 있습니다). 이보다 작은 레이아웃을 사용 ××
하면 필요할 때 즉시 육각형의 크기를 결정하기 위해 끝에 있는 레이아웃을 사용할 수 있다는 보너스 가 있습니다.
이 폼이 구성되면 전체 문자열을 한 번 더 변경합니다.
T`d`À-É
이것은 숫자를 확장 ASCII 문자로 대체합니다
ÀÁÂÃÄÅÆÇÈÉ
그것들은 육각형과 대상 문자열 모두에서 교체되기 때문에 문자열의 일치 여부에 영향을 미치지 않습니다. 또한, 그들은 문자부터입니다 \w
그리고 \b
여전히 육각형 세포로를 식별합니다. 이 대체 작업의 이점은 이제 \D
다음 정규식에서 모든 문자 (특히 줄 바꿈 및 비줄 바꿈 문자) 를 일치시키기 위해 사용할 수 있다는 것 입니다. 여러 위치에서 줄 바꿈되지 않은 문자를 일치 s
시켜야 .
하기 때문에이 옵션을 사용할 수 없습니다 .
이제 마지막 비트 : 경로가 주어진 문자열과 일치하는지 여부를 결정합니다. 이것은 단일 괴물 정규식으로 수행됩니다. 왜 그런지 물어봐도 될까요?!?! 글쎄, 이것은 근본적으로 역 추적 문제입니다. 어딘가에서 시작하여 문자열과 일치하는 한 경로를 시도하고 일단 경로를 추적하지 않으면 마지막으로 작동 한 마지막 문자와 다른 이웃을 시도하십시오. 한 가지정규식으로 작업 할 때 무료로 얻는 것은 역 추적입니다. 그것은 문자 그대로 정규식 엔진이하는 유일한 일입니다. 따라서 유효한 경로를 설명하는 방법을 찾으면 (이러한 종류의 문제에는 충분히 까다 롭지 만 그룹 밸런싱으로 가능할 수 있습니다) 정규식 엔진은 가능한 모든 경로 중에서 해당 경로를 찾는 것을 분류합니다. 여러 단계를 사용하여 수동으로 검색을 구현하는 것이 가능할 것입니다 ( 과거에는 그렇게 했음 ).이 특별한 경우에는 더 짧을 것입니다.
정규식으로 이것을 구현할 때의 한 가지 문제는 역 추적 중에 경로를 통해 정규식 엔진의 커서를 임의로 앞뒤로 움직일 수 없다는 것입니다 (경로가 올라가거나 내려갈 수 있기 때문에 필요합니다). 대신 캡처 그룹에서 자체 “커서”를 추적하고 모든 단계에서 업데이트합니다 (일시적으로 커서 위치로 일시적으로 이동할 수 있음). 또한 이전에 현재 위치를 방문하지 않았는지 확인하는 데 사용할 모든 과거 위치를 저장할 수 있습니다.
이제 시작하겠습니다. 다음은 이름이 지정된 그룹, 들여 쓰기, 이웃의 무작위 순서가 적고 일부 주석이있는 약간 더 정식 버전의 정규 표현식입니다.
\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
나는 일반적인 아이디어가 이것으로부터 대략 명확하기를 바랍니다. 경로를 따라 움직이는 동작 중 하나의 작동 방식에 대한 예를 들어 커서를 남쪽으로 움직이는 비트를 살펴 보겠습니다.
(?<=(?<pos>\k<pos>.(?>(?<-x>.)*)¶.*)\k<next>(?<x>.)*¶\D*)
lookbehinds는 오른쪽에서 왼쪽으로 (또는 위에서 아래로) 읽어야합니다. 순서는 다음과 같습니다.
(?<=
(?<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).
)
\k<pos>
실제로 문자열의 시작 부분에 도달하도록 앵커를 앞에 배치 할 필요는 없습니다 . <pos>
항상 ×
다른 곳에서는 찾을 수없는 양으로 시작 하므로 이미 암시 적 앵커 역할을합니다.
이 게시물을 필요 이상으로 늘리고 싶지 않으므로 다른 11 가지 사례에 대해서는 자세히 설명하지 않지만 원칙적으로 모두 비슷하게 작동합니다. <next>
밸런싱 그룹을 사용하여 이전 커서 위치에서 특정 (허용 가능한) 방향으로 찾을 수 있는지 확인한 다음 일치하는 문자열을에서 새 커서 위치로 저장 <pos>
합니다.
답변
파이썬 3, 990 943 770 709 바이트
첫 번째 대답입니다.
편집 : 골프 인접 목록 만들기. 나는 이제 약간 다른 공식을 사용합니다
편집 2 : 불필요한 보풀을 제거하고 훨씬 더 골프를 쳤다.
편집 3 : 목록의 색인에서 좌표로 변환하기위한 코드가 단축되어 몇 가지 사항이 추가되었습니다.
바이트의 대부분은 인접 목록을 만드는 것과 관련이 있습니다 (골프 가능성이 가장 높습니다). 그때부터는 솔루션을 강제로 처리하는 간단한 문제입니다 (더 적은 바이트로 수행 할 수 있음).
골프 :
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 / 설명 :
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))
레티 나에 너무 가까이! 🙁 예, 레티 나를 이겼다!
답변
자바 스크립트 (ES6), 511 500 496 바이트
(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}
언 골프 및 댓글
// 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
}
테스트 사례
아래 스 니펫은 모든 진실되고 허위 테스트 사례를 안내합니다.