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
}
ν μ€νΈ μ¬λ‘
μλ μ€ λν«μ λͺ¨λ μ§μ€λκ³ νμ ν μ€νΈ μ¬λ‘λ₯Ό μλ΄ν©λλ€.
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'
);