ระยะ Palindrome
หาระยะทางของสตริงที่กำหนดกับพาลินโดรมที่ใกล้เคียงที่สุดที่มีความยาวเท่ากัน
สำหรับงานนี้ฉันตัดสินใจที่จะให้ตัวละครอยู่ห่างจากจุดศูนย์กลางของสตริงมากขึ้น (คิดว่ามันทำให้แรงบิดมากขึ้น) ตามสัดส่วนของระยะทางถึงจุดศูนย์กลาง
มากำหนดระยะทางพาลินโดรมสำหรับสตริง\$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 ค้นหา\$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 ]
จากนั้นเราจะใช้ "ระยะทาง palindrome" ของบิตกลางและเพิ่มd abs(a-c)*(div(length d)2)ถ้าเป็นอย่างอื่นคำตอบคือศูนย์
ตอนนี้การรับองค์ประกอบสุดท้ายเป็นเรื่องยากเล็กน้อยใน 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 ไบต์
แก้ไข: -3 ไบต์ขอบคุณ Giuseppe โดยใช้%*%ตัวดำเนินการเพื่อคำนวณผลคูณภายในของเวกเตอร์แทนที่จะรวมผลคูณขององค์ประกอบเป็นการดำเนินการแยกกัน
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 !!!
บันทึก9ไอกรน 15 ไบต์ขอบคุณDominic van Essen !!!
f(s,l)int*s;{l=l>1?l/2*abs(*s++-s[l-=2])+f(s,l):0;}
ลองออนไลน์!
ท่าเรือของฉันหลาม 3 คำตอบ
JavaScript (ES6), 61 57 ไบต์
คาดว่าจะมีรายการรหัส ASCII
f=a=>1/a?0:(a.length>>1)*Math.abs(a.shift()-a.pop())+f(a)
ลองออนไลน์!
อย่างไร?
นี่เป็นการใช้งานแบบวนซ้ำที่ค่อนข้างตรงไปตรงมาซึ่งจะลบรายการแรกและรายการสุดท้ายออกจากรายการในการวนซ้ำแต่ละครั้งคำนวณค่าสัมบูรณ์ของความแตกต่างและใช้น้ำหนัก\$\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-register A มีรหัสเริ่มต้น
*:ga
$$ j0uaz-1ub0uu0uw$$*
- Q-register M เพิ่มทุกอย่าง ผลลัพธ์ยังคงอยู่ใน Q-register W.
:gm$$ z/2<0ua0a-(qba)%a"L-qaua'qa%u%w$c-2%b>$$*
- ตัวอย่างการคำนวณ\ $ D_p \ $ของ "Neveroddoreven": ฆ่าบัฟเฟอร์ทั้งหมดแทรกคำของคุณเริ่มต้นการลงทะเบียน A, B, U และ W และข้ามไปที่จุดเริ่มต้นของบัฟเฟอร์ จากนั้นวนซ้ำ z / 2 ครั้งสะสมในรีจิสเตอร์ W; ในที่สุดก็แสดงเนื้อหาตัวเลขของ register 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
นี่แสดงเซสชัน TECO ของการแทรกคำทดสอบแต่ละคำลงในบัฟเฟอร์การแก้ไขที่ว่างเปล่าจากนั้นเรียกมาโครของ Q-register A และ M และสุดท้ายจะแสดง\ $ D_p \ $ที่สะสมใน Q-register ตัวเลข
*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)> เรียกซ้ำโดยย้ายตัวชี้และความยาวลดลง
+ เอบีเอส (* aa [z-1]) * (z / 2)
- เพิ่มมูลค่าของคู่
: 0;}> อื่น ๆ เริ่มต้น r ถึง 0
เยลลี่ 7 ไบต์
ạṚŒHṪḋJ
monadic Link ยอมรับรายการจำนวนเต็มซึ่งให้ผลเป็นจำนวนเต็ม
ลองออนไลน์!
อย่างไร?
ạṚŒ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)
แกลบ , 14 12 11 ไบต์
-2 ขอบคุณ Wheat Wizard ที่ชี้ให้เห็นว่าคุณสามารถป้อนข้อมูลเป็นรายการจุดรหัสได้
และ -1 ขอบคุณ 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}]/ 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. ฉันลองใช้สองสามวิธีและนี่เป็นความพยายามที่ดีที่สุดของฉัน
อย่างไร
(...)|.วลีทั้งหมดคือ hook ซึ่งหมายถึงอินพุตดั้งเดิมและอินพุตที่ย้อนกลับ|.จะถูกส่งผ่านเป็นอาร์กิวเมนต์ซ้ายและขวาตามลำดับไปยังวลีในวงเล็บ(...)&(,~inv)การรวมการเขียนจะ&แปลงอาร์กิวเมนต์ทั้งสองด้วยคำกริยาที่ระบุในกรณี,~invนี้,~inv,~เป็นสิ่งที่ตรงกันข้ามของคำกริยาที่คู่รายการโดยตนเองท้าย สิ่งที่ตรงกันข้ามของการดำเนินการนั้นคือการใช้ครึ่งแรกของรายการและจะเกิดขึ้นเพื่อ "ปัดเศษ" สำหรับรายการคี่ซึ่งเป็นสิ่งที่เราต้องการที่นี่
#\.@]*|@-คูณ#\.@]องค์ประกอบโดย|@-|@-|ลบทั้งสองมีปากเสียงรายการองค์ประกอบที่ชาญฉลาดและใช้ค่าสัมบูรณ์ นี่คือ "ระยะทาง"#\.@]ผลิตเช่น4 3 2 1ถ้ารายการมีความยาว 4 มันไม่นี้โดยการใช้ความยาวต่อท้ายของการโต้แย้งที่เหมาะสม#\.]เราสามารถใช้อาร์กิวเมนต์ด้านซ้ายได้เช่นกัน
+/@รวมผลลัพธ์
สำหรับการเปรียบเทียบโซลูชัน APL ที่แปลงเป็น J คือ 25 ไบต์:
>.@-:@#(1#.]*&|#\)@}.]-|.
ลองออนไลน์!