Palindrom mesafesi
Belirli bir dizgenin aynı uzunluktaki en yakın palindromuna olan mesafeyi bulun.
Bu görev için, karakterlere, merkeze olan mesafeleriyle orantılı olarak, dizenin merkezinden daha uzaktaki karakterlere daha fazla ağırlık vermeye (bunu daha fazla torka katkıda bulunduğunu düşünün) karar verdim.
Bir dizge için palindrom mesafesini tanımlayalım \$s\$ dizginin merkezinden eşit aralıklarla yerleştirilmiş karşılık gelen çiftlerin mutlak farkının tüm çarpımlarının toplamı ve merkeze uzaklıkları olarak.
\$D_p=\displaystyle\sum_{i=1}^{d}\left(d-i+1\right)|s_i-s_{l-i+1}|\$
nerede \$l\$uzunluğu \$s\$ve \$d = \left\lfloor\frac{l}{2}\right\rfloor\$
Ortadaki karakter toplama herhangi bir katkı sağlamadığından, \$d\$tek uzunluklu dizeler için \$l\$eşittir \$d\$uzunluktaki dizeler için \$l-1\$.
Görev
Verilen dizge \$s\$uzunluğu> 1 bul \$D_p(s)\$
Giriş
Aşağıdakilerden biri:
- dizi;
- karakter listesi;
- bir sayı listesi.
Çıktı
Bir tamsayı - giriş dizesinin palindrom mesafesi.
Test durumları
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
Kazanma kriterleri
Her dilde bayt cinsinden en kısa kod kazanır.
Kum havuzu
Yanıtlar
Haskell , 50 bayt
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
(0#)
Çevrimiçi deneyin!
Anne bak! Çarpma yok! (veya bölme)
Açıklama
Bu cevap ne olduğunu açıklamak yerine yapar sadece kafa karıştırıcı olacağını düşündüğümüz, ben bu cevaba nasıl geldiğini ben kısaltılmış açıklama verecektir düşünüyorum.
Öncelikle Haskell özyinelemeli bir dildir, bu yüzden bunu özyinelemeli bir şekilde ifade etmek istiyoruz. Bir listemiz varsa, bunu yapmak oldukça kolaydır
[ a , d... , c ]
Sonra orta bitin "palindrom mesafesini" dalıp ekliyoruz abs(a-c)*(div(length d)2). Başka bir şeyse, cevap sıfırdır.
Şimdi Haskell'de son öğeyi elde etmek biraz zor, ancak ilkini elde etmek son derece basit. Dolayısıyla, son öğeyi elde etmenin bir yolu, listeyi tersine çevirip ilkini elde etmektir. Ortayı elde etmek için bunu orijinal sıraya geri döndürmeliyiz.
İlk buluşumuz, bir dizgiyi ters çevirdiğinizde "palindrom mesafesinin" değişmediğini fark etmektir. Bu nedenle, ters sıra üzerinde hesaplama yapmak her halükarda doğru sonucu vereceğinden, orta parçayı orijinal sırasına geri döndürmemiz gerekmez.
f(a:b)|c:d<-reverse b= ...
Yani tüm kodumuzda:
f(a:b)|c:d<-reverse b=f d+abs(a-c)*div(length d)2
f _=0
Tamam ama lengthve divbiraz masraflı. Geriye kalan adım sayısı gerçekten aradığımız şeydir, peki ya bunu bize yardım etmek için kullanırsak.
f(a:b)|c:d<-reverse b,(k,n)=(k+abs(a-c)*n,n+1)
f _=(0,1)
g=fst.f
Bu yardımcı olmadı, ama burada bir şeyin peşindeyiz. Çarpma sadece tekrarlanan toplamadır, bu yüzden gerçekten istediğimiz şey abs(a-c)kalan her yineleme için bir kez eklemektir . Öyleyse neden eklemek istediğimiz sayıları takip etmiyoruz ve onları aşağıya doğru eklemeye devam etmiyoruz.
u#(a:b)|c:d<-reverse b=sum u+(abs(c-a):u)#d
u#_=sum u
g=([]#)
İşte burada u, şimdiye kadarki tüm mutlak farklılıkların listesi olan bu ekstra argümanımız var. Ve her yinelemede bunların toplamını bir sonraki yinelemenin sonucuna ekliyoruz. Bu şekilde, her bir fark merkezden olan adım sayısı kadar, özünde merkezden uzaklığı ile çarpılarak eklenir.
Elbette sadece utoplamını istediğimizden , aslında değerleri ayırmamıza gerek yok, bazı baytlardan tasarruf etmek için sadece devam eden toplamı takip edebiliriz.
u#(a:b)|c:d<-reverse b=u+(abs(c-a)+u)#d
u#_=u
g=(0#)
Ve bu bize son kodu verir.
05AB1E , 8 bayt
Girişin tam sayılar listesi olarak alınabileceğini bana hatırlattığı için Kevin Cruijssen'e -1 bayt teşekkürler .
Âα2äθā*O
Çevrimiçi deneyin!
Yorum yaptı:
# 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 bayt
Düzenleme: Giuseppe sayesinde %*%, elemanların çarpımını ayrı işlemler olarak toplamak yerine vektörlerin iç çarpımını hesaplamak için operatör kullanarak -3 bayt
abs((rev(x<-scan())-x)[(y=sum(x|1)/2):1])%*%1:y
Çevrimiçi deneyin!
Sayıların listesini kabul eder.
Golf oynamayan kod:
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 bayt
Kaydedilen 6 7 sayesinde bayt AZTECCO !!!
Kaydedilen 9 bir boğmaca 15 sayesinde bayt Dominic van Essen !!!
f(s,l)int*s;{l=l>1?l/2*abs(*s++-s[l-=2])+f(s,l):0;}
Çevrimiçi deneyin!
Benim Limanı Python 3 cevap .
JavaScript (ES6), 61 57 bayt
ASCII kodlarının bir listesini bekliyor.
f=a=>1/a?0:(a.length>>1)*Math.abs(a.shift()-a.pop())+f(a)
Çevrimiçi deneyin!
Nasıl?
Bu, her yinelemede listeden ilk ve son girişi kaldıran, farklarının mutlak değerini hesaplayan ve ağırlığı uygulayan oldukça basit, özyinelemeli bir uygulamadır \$\lfloor L/2 \rfloor\$, nerede \$L\$ öğeler kaldırılmadan önceki listenin uzunluğudur.
Durdurma kriteri 1 / aşu durumlarda doğrudur:
a[]bu durumda boştur1 / a == Infinity. Bu, giriş listesinin uzunluğu çift olduğunda olur.Veya
a[]listenin uzunluğu tuhafsa meydana gelen tek bir tamsayıdır. Özyinelemeyi başka bir hesaplama yapmadan güvenli bir şekilde durdurabiliriz çünkü tek bir karakter bir palindromdur ve bu noktada zaten nihai sonuca sahibiz.
Python 2 , 57 54 bayt
Tam sayılar listesi olarak girdi alan özyinelemeli bir işlev.
f=lambda l:l>[]and len(l)/2*abs(l[0]-l[-1])+f(l[1:-1])
Çevrimiçi deneyin!
Son kısım da abs(l[0]-l.pop())+f(l[1:])aynı uzunlukta olabilir.
Python 2 , 57 bayt
Özyinelemesiz biraz daha uzun bir yaklaşım.
lambda l:eval(len(l)/2*'+len(l)/2*abs(l.pop(0)-l.pop())')
Çevrimiçi deneyin!
Kömür , 22 bayt
ＩΣＥ∕θ²×⁻Ｌ∕θ²κ↔⁻℅ι℅§⮌θκ
Çevrimiçi deneyin! Bağlantı, kodun ayrıntılı sürümüne yöneliktir. Girdiyi dizge olarak alır (bir dizeyi yarıya indirmek, diziyi yarıya indirmekten daha iyidir). Açıklama:
θ 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
Alternatif yaklaşım, ayrıca 22 bayt:
ＩΣＥ⮌∕⮌θ²×⊕κ↔⁻℅ι℅§⮌∕θ²κ
Çevrimiçi deneyin! Bağlantı, kodun ayrıntılı sürümüne yöneliktir. Açıklama:
θ 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 Bayt
- Q-register A, başlatma koduna sahiptir.
*:ga
$$ j0uaz-1ub0uu0uw$$*
- Q-register M hepsini bir araya getiriyor. Sonuç, Q-register W'de kalır.
:gm$$ z/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>$$*
- “Neveroddoreven” ın \ $ D_p \ $ hesaplamasına bir örnek : tüm tamponu öldürün, kelimenizi ekleyin, A, B, U ve W kayıtlarını ilklendirin ve tamponun başlangıcına atlayın; sonra z / 2 kez yineleyin, W yazmacında biriktirin; son olarak W kaydının sayısal içeriğini göster.
hkiNeveroddoreven$mamm$$ *qw=$$
224
*
- Tam program ve uzunluğu.
*ht$$ j0uaz-1ub0uu0uwz/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>*z=$$
53
- Test durumları.
"aa" -> 0
"bab" -> 0
"abca" -> 1
"cbade" -> 6
"hello" -> 21
"code-golf" -> 45
"neveroddoreven" -> 0
"Neveroddoreven" -> 224
Bu, her bir test kelimesini boşaltılmış düzenleme arabelleğine ekleyen , ardından Q-yazmaçları A ve M makrolarını çağıran ve son olarak sayısal Q-yazmacı W'de toplanan \ $ D_p \ $ gösteren bir TECO oturumunu gösterir.
*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 bayt
{+/|⍵×⍳≢⍵}(⌈2÷⍨⍴)↓⊢-⌽
Çevrimiçi deneyin!
C (gcc) , 55 52 bayt
f(a,z)char*a;{z=z/2?z/2*abs(*a++-a[z-=2])+f(a,z):0;}
Çevrimiçi deneyin!
- @ Noodle9'dan çalmaktan ve yeniden düzenlemelerden biraz kurtardı
f (a, z) char * a; {z = - bir C-string işaretçisini ve uzunluğunu takip eden fonksiyon
ve eax yazmacı üzerinden geri dönüyor.
z / 2? - merkezde değilse:
f (a + 1, z-2)> işaretçi hareket ettirilmiş ve uzunluk azaltılmış olarak özyinelemeli olarak çağırın
+ abs (* aa [z-1]) * (z / 2)
- çiftlerin değerini ekleyin
: 0;}> yoksa r'yi 0'a başlat
Jöle , 7 bayt
ạṚŒHṪḋJ
Bir tamsayı veren tam sayıların bir listesini kabul eden monadik bir Bağlantı.
Çevrimiçi deneyin!
Nasıl?
ạṚŒ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)
Kabuk , 14 12 11 bayt
-2 Wheat Wizard sayesinde kod noktalarının bir listesi olarak girdi alabileceğinizi işaret ediyor
ve -1 sayesinde HP.Wiz, ≠'nin yalnızca eşitsizlik değil, mutlak fark olduğunu gösterir
ΣFoz*ŀ½Sz≠↔
Çevrimiçi deneyin!
Açıklama
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 Dili (Mathematica) , 53 bayt
f@_:0=0
f[a_,b___,c_]:=Abs[a-c]⌈Length@a?b/2⌉+f@b
Çevrimiçi deneyin!
Tam sayıların bir listesini alır.
Length@a?büzerinden bir bayt kaydeder Tr[1^{a,b}]/ Length[a.b]sayesinde PatternTestbireyin yüksek öncelik.
Python 3 , 59 bayt
f=lambda l:len(l)>1and len(l)//2*abs(l.pop(0)-l.pop())+f(l)
Çevrimiçi deneyin!
J , 24 bayt
+/@(#\.@]*|@-)&(,~inv)|.
Çevrimiçi deneyin!
Girdiyi tamsayılar listesi olarak alır.
J'de kısaca ifade etmesi beklenmedik bir şekilde zor olan ilginç sorunlardan bir diğeri birkaç yaklaşım denedim ve bu benim en iyi girişimim.
Nasıl
(...)|.Tüm ifade bir kancadır, yani orijinal girdi ve tersine çevrilen girdi|., sırasıyla sol ve sağ bağımsız değişkenler olarak parantez içindeki ifadeye aktarılacaktır.(...)&(,~inv)Oluşturma bağlacı&bu durumda her iki bağımsız değişkeni de belirtilen fiille dönüştürür,~inv.,~invBir listeyi kendi kendine ekleyerek ikiye katlayan fiilin tersidir,~. Bu işlemin tersi, listenin ilk yarısını almaktır ve bu, tek sayılar için "aşağı yuvarlama" olur, ki biz de burada istediğimiz şey budur.
#\.@]*|@-#\.@]Element-wise ile çarpın|@-|@-iki liste argümanını eleman bazında çıkarın ve mutlak değeri alın|. Bunlar "mesafeler" dir.#\.@]örneğin4 3 2 1listelerin uzunluğu 4 ise üretir . Bunu#\., doğru argümanın son ek uzunluklarını alarak yapar]. Sol argümanı burada da kullanabilirdik.
+/@Sonucu toplayın
Karşılaştırma için, J'ye dönüştürülen APL çözümü 25 bayttır:
>.@-:@#(1#.]*&|#\)@}.]-|.
Çevrimiçi deneyin!