회문 거리
주어진 문자열이 같은 길이의 가장 가까운 회문까지의 거리를 찾으십시오.
이 작업을 위해 나는 스트링의 중심에서 더 멀리 떨어진 캐릭터에게 중심까지의 거리에 비례하여 더 많은 무게를 부여하기로 결정했습니다 (더 많은 토크에 기여한다고 생각하십시오).
문자열 \에 대한 회문 거리를 정의합시다.$s\$ 문자열의 중심에서 균등하게 간격을두고 해당 쌍의 절대 차이와 중심까지의 거리에 대한 모든 곱의 합계입니다.
\$D_p=\displaystyle\sum_{i=1}^{d}\left(d-i+1\right)|s_i-s_{l-i+1}|\$
여기서 \$l\$\ 의 길이입니다.$s\$및 \$d = \left\lfloor\frac{l}{2}\right\rfloor\$
중간 문자는 합계에 기여하지 않으므로 \$d\$길이가 홀수 인 문자열 \$l\$\와 같음$d\$길이가 \ 인 문자열의 경우$l-1\$.
직무
주어진 문자열 \$s\$길이> 1 find \$D_p(s)\$
입력
다음 중 하나 :
- 문자열;
- 캐릭터 목록;
- 숫자 목록.
산출
정수-입력 문자열의 회문 거리.
테스트 케이스
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
우승 기준
모든 언어에서 가장 짧은 코드 (바이트)가 우선합니다.
모래 상자
답변
Haskell , 50 바이트
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
(0#)
온라인으로 시도하십시오!
엄마 봐! 곱셈이 없습니다! (또는 부서)
설명
이 답변 이 무엇을하는지 설명하기보다 혼란 스러울 것이라고 생각 하기보다는이 답변에 어떻게 왔는지 요약 설명하겠습니다.
먼저 Haskell은 재귀 언어이므로이를 재귀 적으로 표현하고 싶습니다. 목록이 있으면 매우 쉽습니다.
[ a , d... , c ]
그런 다음 우리는 중간 비트의 "회문 거리"를 가지고 d와에 추가 abs(a-c)*(div(length d)2). 다른 것이라면 답은 0입니다.
이제 Haskell에서 마지막 요소를 얻는 것은 약간 어렵지만 첫 번째 요소를 얻는 것은 매우 간단합니다. 따라서 마지막 요소를 가져 오는 한 가지 방법은 목록을 반대로하고 첫 번째 요소를 가져 오는 것입니다. 중간을 얻으려면 원래 순서로 되돌려 야합니다.
우리의 첫 번째 돌파구는 스트링을 뒤집을 때 "회문 거리"가 변하지 않는다는 것을 깨닫는 것입니다. 따라서 역순으로 계산하면 어쨌든 올바른 결과를 얻을 수 있으므로 중간 부분을 원래 순서로 되돌릴 필요가 없습니다.
f(a:b)|c:d<-reverse b= ...
따라서 모든 코드는 다음과 같습니다.
f(a:b)|c:d<-reverse b=f d+abs(a-c)*div(length d)2
f _=0
그러나 확인 length및 div종류 비용의입니다. 남은 단계의 수는 실제로 우리가 찾고있는 것이므로 우리를 돕기 위해 사용했다면 어떨까요?
f(a:b)|c:d<-reverse b,(k,n)=(k+abs(a-c)*n,n+1)
f _=(0,1)
g=fst.f
그게 도움이되지 않았지만 우리는 여기서 뭔가를하고 있습니다. 곱셈은 반복되는 덧셈이기 때문에 우리가 정말로 원하는 것은 abs(a-c)남은 반복마다 한 번씩 더하는 것 입니다. 그래서 우리가 더하고 싶은 숫자를 추적하고 계속해서 계속해서 추가하는 것이 어떻습니까?
u#(a:b)|c:d<-reverse b=sum u+(abs(c-a):u)#d
u#_=sum u
g=([]#)
그래서 여기에 우리는 u지금까지의 모든 절대적인 차이의 목록 인 이 추가 주장 이 있습니다. 그리고 반복 할 때마다 다음 반복의 결과에 이들의 합계를 더합니다. 이렇게하면 각 차이가 중심으로부터의 걸음 수만큼 더해지며, 본질적으로 중심으로부터의 거리를 곱합니다.
물론 우리는 u그 합계 만을 요구 하기 때문에 실제로 값을 분리 할 필요가 없습니다. 단지 몇 바이트를 절약하기 위해 실행 합계를 추적 할 수 있습니다.
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
g=(0#)
그리고 이것은 우리에게 최종 코드를 제공합니다.
05AB1E , 8 바이트
-1 바이트 는 입력을 정수 목록으로 사용할 수 있음을 상기시켜 준 Kevin Cruijssen 에게 감사드립니다 .
Âα2äθā*O
온라인으로 시도하십시오!
댓글 :
# implicit input: a list of codepoints
 # push codepoints and codepoints reversed
α # take the (element-wise) absolute difference
2ä # split into 2 pieces
# the last one will be shorter for odd lengths
θ # take the last piece
ā # length-range: [1, ..., length] (doesn't pop the TOS)
* # multiply element-wise
O # take the sum
R , 50 47 바이트
편집 : %*%별도의 연산으로 요소의 곱을 합산하는 대신 연산자를 사용하여 벡터의 내적을 계산 함으로써 Giuseppe 덕분에 -3 바이트
abs((rev(x<-scan())-x)[(y=sum(x|1)/2):1])%*%1:y
온라인으로 시도하십시오!
번호 목록을 허용합니다.
골프를 치지 않은 코드 :
x=scan() # x is vector of numbers
y=sum(x|1)/2) # y is half the length of x
sum( # return the sum of...
abs( # the absolute values of...
(x-rev(x)) # the differences between each element of x
# and the same elements reversed...
[y:1] # at positions y..1
# (so only the first half, backwards)...
*1:y)) # multiplied by 1..y
C (gcc) , 74 \$\cdots\$ 52 51 바이트
저장 6 7 덕분에 바이트 AZTECCO ! Dominic van Essen 덕분에 9 를 15 바이트
절약했습니다 !!!
f(s,l)int*s;{l=l>1?l/2*abs(*s++-s[l-=2])+f(s,l):0;}
온라인으로 시도하십시오!
내 Python 3 답변의 포트 .
JavaScript (ES6), 61 57 바이트
ASCII 코드 목록이 필요합니다.
f=a=>1/a?0:(a.length>>1)*Math.abs(a.shift()-a.pop())+f(a)
온라인으로 시도하십시오!
어떻게?
이 제 1 및 각 반복에서 목록에서 마지막 항목을 제거하는 매우 간단 재귀 구현 그 차이의 절대 값을 계산하여 가중치를 적용이다 \$\lfloor L/2 \rfloor\$, 여기서 \$L\$ 항목이 제거되기 전 목록의 길이입니다.
중단 기준 1 / a은 다음 중 하나에 해당하는 경우 진실입니다.
a[]비어있는 경우1 / a == Infinity. 이것은 입력 목록의 길이가 짝수 일 때 발생합니다.또는
a[]목록의 길이가 홀수 인 경우 발생하는 단일 정수입니다. 단일 문자가 회문이고이 시점에서 이미 최종 결과가 있으므로 다른 계산없이 안전하게 재귀를 중지 할 수 있습니다.
Python 2 , 57 54 바이트
입력을 정수 목록으로받는 재귀 함수입니다.
f=lambda l:l>[]and len(l)/2*abs(l[0]-l[-1])+f(l[1:-1])
온라인으로 시도하십시오!
마지막 부분도 abs(l[0]-l.pop())+f(l[1:])같은 길이 일 수 있습니다 .
Python 2 , 57 바이트
재귀없는 약간 더 긴 접근 방식입니다.
lambda l:eval(len(l)/2*'+len(l)/2*abs(l.pop(0)-l.pop())')
온라인으로 시도하십시오!
목탄 , 22 바이트
ＩΣＥ∕θ²×⁻Ｌ∕θ²κ↔⁻℅ι℅§⮌θκ
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 입력을 문자열로받습니다 (문자열을 절반으로 줄이는 것이 배열을 절반으로 줄이는 것보다 골퍼입니다). 설명:
θ Input string
∕ ² First half
Ｅ Map over characters
κ Current index
⁻ Subtracted from
Ｌ∕θ² Length of half of string
× Multiplied by
↔⁻ Absolute difference of
℅ ℅ Ordinals of
ι Current character and
§ Character at
κ Current index in
⮌ Reversed
θ Input string
Σ Take the sum
Ｉ Cast to string
Implicitly print
대체 방법, 또한 22 바이트 :
ＩΣＥ⮌∕⮌θ²×⊕κ↔⁻℅ι℅§⮌∕θ²κ
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 설명:
θ Input string
⮌ Reversed
∕ ² "First" half
⮌ Reversed i.e. last "half"
Ｅ Map over characters
κ Current index
⊕ Incremented
× Multiplied by
↔⁻ Absolute difference of
℅ ℅ Ordinals of
ι Current character and
§ Character at
κ Current index in
⮌ Reversed
∕θ² First half of input string
Σ Take the sum
Ｉ Cast to string
Implicitly print
TECO , 53 바이트
- Q- 레지스터 A에는 초기화 코드가 있습니다.
*:ga
$$ j0uaz-1ub0uu0uw$$*
- Q- 레지스터 M은 모든 것을 더합니다. 결과는 Q 레지스터 W에 남아 있습니다.
:gm$$ z/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>$$*
- "Neveroddoreven" 의 \ $ D_p \ $ 계산 예제 : 전체 버퍼를 죽이고, 단어를 삽입하고, 레지스터 A, B, U, W를 초기화하고 버퍼의 시작 부분으로 점프합니다. 그런 다음 z / 2 번 반복하여 레지스터 W에 누적합니다. 마지막으로 레지스터 W의 숫자 내용을 표시합니다.
hkiNeveroddoreven$mamm$$ *qw=$$
224
*
- 완전한 프로그램과 그 길이.
*ht$$ j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>*z=$$
53
- 테스트 케이스.
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
빈 편집 버퍼에 각 테스트 단어를 삽입 한 다음 Q 레지스터 A와 M의 매크로를 호출하고 마지막으로 숫자 Q 레지스터 W에 누적 된 \ $ D_p \ $ 를 표시하는 TECO 세션을 보여줍니다 .
*hkiaa$mammqw=$$ 0 *hkibab$mammqw=$$ 0 *hkiabca$mammqw=$$ 1 *hkicbade$mammqw=$$ 6 *hkihello$mammqw=$$ 21 *hkicode-golf$mammqw=$$ 45 *hkineveroddoreven$mammqw=$$ 0 *hkiNeveroddoreven$mammqw=$$
224
APL (Dyalog Unicode) , 21 바이트
{+/|⍵×⍳≢⍵}(⌈2÷⍨⍴)↓⊢-⌽
온라인으로 시도하십시오!
C (gcc) , 55 52 바이트
f(a,z)char*a;{z=z/2?z/2*abs(*a++-a[z-=2])+f(a,z):0;}
온라인으로 시도하십시오!
- @ Noodle9 및 재 배열에서 약간의 훔치기를 저장했습니다.
f (a, z) char * a; {z =-C- 문자열 포인터와 그 길이를 고정하는 함수
트로프 eax 레지스터를 반환합니다.
z / 2? -중앙에 있지 않은 경우 :
f (a + 1, z-2)> 포인터를 이동하고 길이를 줄인 재귀 호출
+ abs (* aa [z-1]) * (z / 2)
-쌍의 가치 추가
: 0;}> else r을 0으로 초기화
젤리 , 7 바이트
ạṚŒHṪḋJ
정수를 생성하는 정수 목록을 허용하는 모나 딕 링크.
온라인으로 시도하십시오!
어떻게?
ạṚŒHṪḋJ - Link: list of integers, A e.g. (Abracadabra) [65,98,114,97,99,97,100,97,98,114,97]
Ṛ - reverse (A) [97,114,98,97,100,97,99,97,114,98,65]
ạ - absolute difference (vectorises) [32,16,16,0,1,0,1,0,16,16,32]
ŒH - split in two (1st part longest, if any) [[32,16,16,0,1,0],[1,0,16,16,32]]
Ṫ - tail [1,0,16,16,32]
J - range of length (of A) [1,2,3,4,5,6,7,8,9,10,11]
ḋ - dot-product 273 (= 1×1+0×2+16×3+16×4+32×5+0×6+...0×11)
Husk , 14 12 11 바이트
-2는 Wheat Wizard가 코드 포인트 목록으로 입력 할 수 있음을 지적한 덕분에
HP.Wiz 덕분에 ≠은 단순히 불평등이 아니라 절대적인 차이를 나타냅니다.
ΣFoz*ŀ½Sz≠↔
온라인으로 시도하십시오!
설명
Sz≠ Zip absolute difference the list from
↔ The reverse of the list
½ Split the list into two halves (with the longer being the first)
F Reduce by
o ŀ Converting the first half to range(1, length)
z* And zip multiplying with the second half
Σ Finally sum the absolute values
Wolfram 언어 (Mathematica) , 53 바이트
f@_:0=0
f[a_,b___,c_]:=Abs[a-c]⌈Length@a?b/2⌉+f@b
온라인으로 시도하십시오!
정수 목록을받습니다.
Length@a?b의 높은 우선 순위 덕분에 Tr[1^{a,b}]/ 보다 1 바이트를 절약 합니다.Length[a.b]PatternTest
Python 3 , 59 바이트
f=lambda l:len(l)>1and len(l)//2*abs(l.pop(0)-l.pop())+f(l)
온라인으로 시도하십시오!
J , 24 바이트
+/@(#\.@]*|@-)&(,~inv)|.
온라인으로 시도하십시오!
정수 목록으로 입력을받습니다.
J에서 간결하게 표현하기가 의외로 어려운 흥미로운 문제 중 하나입니다. 몇 가지 접근 방식을 시도했으며 이것이 최선의 시도입니다.
어떻게
(...)|.전체 구는 후크이며, 이는 원래 입력과 반전 된 입력|.이 괄호 안의 구에 각각 왼쪽 및 오른쪽 인수로 전달됨을 의미합니다.(...)&(,~inv)작성 접속사&는 지정된 동사 (이 경우)로 두 인수를 모두 변환합니다,~inv.,~inv자가 추가하여 목록을 두 배로 늘리는 동사의 역입니다,~. 이 연산의 반대는 목록의 전반부를 가져 오는 것이고, 우리가 여기서 원하는 것이 홀수 목록에 대해 "내림"하는 것입니다.
#\.@]*|@-#\.@]요소 별 곱하기|@-|@-두 개의 목록 인수를 요소별로 빼고 절대 값을 취합니다|. 이것이 "거리"입니다.#\.@]예를 들어4 3 2 1목록의 길이가 4 인 경우 생성합니다 .#\.오른쪽 인수 의 접미사 길이 를 사용하여이를 수행합니다]. 여기서도 왼쪽 인수를 사용할 수 있습니다.
+/@결과 합산
비교를 위해 J로 변환 된 APL 솔루션은 25 바이트입니다.
>.@-:@#(1#.]*&|#\)@}.]-|.
온라인으로 시도하십시오!