Dialer ของอัศวิน
ลองนึกภาพคุณวางตัวหมากรุกอัศวินไว้บนแป้นกดโทรศัพท์ ตัวหมากรุกนี้เคลื่อนจากแป้นไปยังแป้นในรูปตัว "L" ตัวพิมพ์ใหญ่: สองขั้นตอนในแนวนอนตามด้วยหนึ่งขั้นในแนวตั้งหรือหนึ่งขั้นในแนวนอนจากนั้นสองขั้นในแนวตั้ง:
+-+
|1| 2 3
+-+
`-------v
| +-+
4 | 5 |6|
| +-+
|
|+-+
7 >|8| 9
+-+
0
สมมติว่าคุณกดปุ่มบนปุ่มกดโดยใช้เพียงอัศวินเท่านั้นที่ทำได้ ทุกครั้งที่อัศวินลงบนคีย์เราจะหมุนคีย์นั้นและทำการกระโดดอีกครั้ง ตำแหน่งเริ่มต้นนับเป็น hop 0
คุณสามารถหมุนหมายเลขที่แตกต่างกันใน N hops จากตำแหน่งเริ่มต้นที่เฉพาะเจาะจงได้กี่หมายเลข
ตัวอย่าง
คีย์เริ่มต้น : 6
จำนวนครั้งในการกระโดด : 2
ตัวเลขที่สามารถสร้างได้ :
6 0 6
6 0 4
6 1 6
6 1 8
6 7 2
6 7 6
ดังนั้นตัวเลขที่แตกต่างกันหกตัวสามารถสร้างได้จากคีย์ 6 และ 2 ฮ็อพ
ข้อ จำกัด
อินพุต:คุณจะได้รับตัวเลขสองตัวเป็นอินพุต คุณสามารถผสมอินพุตเหล่านั้นและใช้รูปแบบใดก็ได้ที่คุณต้องการ คีย์เริ่มต้นจะเป็นตัวเลขระหว่าง 0 ถึง 9 จำนวนฮ็อพจะเป็นจำนวนเต็มที่ไม่เป็นลบโดยไม่มีขีด จำกัด บน
เอาต์พุต:คุณจะแสดงผลตัวเลขเดียวในรูปแบบที่คุณต้องการ
กรณีทดสอบ
(key,hops) result
(6,0) 1
(6,1) 3
(6,2) 6
(6,10) 4608
(6,20) 18136064
(5,0) 1
(5,1) 0
การให้คะแนน
นี่คือโค้ดกอล์ฟ เพื่อส่งเสริมการมีส่วนร่วมในอนาคตจะไม่มีการยอมรับคำตอบ
บันทึก
สิ่งนี้ได้รับแรงบันดาลใจอย่างมากจากThe Knight's Dialerซึ่งเป็นบทสัมภาษณ์ของ Google ในอดีต แต่ระวังมันจะไม่เหมือนกันดังนั้นอย่าใช้เพียงแค่คำตอบของคุณกับรหัสที่คุณเห็นที่นั่น
คำตอบ
JavaScript (ES6), 62 61 60 ไบต์
พอร์ต Python ของฉันเปลี่ยนกลับเป็น JS :-p
f=(n,k,o=k%2)=>n--?k-5&&(2-o)*f(n,!k*3-~o)+(k&5&&f(n,o*4)):1
ลองออนไลน์!
ด้านล่างนี้เป็นเวอร์ชัน 62 ไบต์ดั้งเดิมของฉันซึ่งเข้าใจง่ายกว่า:
f=(n,k)=>n--?k&1?k-5&&f(n,2)+f(n,4):2*f(n,k?1:4)+(k&4&&f(n)):1
ลองออนไลน์!
อย่างไร?
มี 4 กลุ่มของคีย์ที่เชื่อมต่อกันจริงๆ คีย์ทั้งหมดภายในกลุ่มมีลักษณะการทำงานเหมือนกันทุกประการ
- มุม1, 3, 7, 9(สีเขียว) ลักษณะเฉพาะ: คีย์คี่ที่ไม่เท่ากับ\$5\$.
- ซ้าย / ข้างขวา4, 6(สีฟ้า) Characterization: แม้แต่คีย์ที่เรามี\$k \operatorname{and}4 = 4\$.
- ด้านบน / ด้านล่าง2, 8(สีเหลือง) ลักษณะ: ไม่ใช่ศูนย์แม้แต่คีย์ที่เรามี\$k \operatorname{and}4 = 0\$.
- 0คีย์ (สีแดง)
5ที่สำคัญคือการที่เงียบสงบและประมวลผลแยกต่างหาก
รูปด้านขวาคือกราฟกำกับแบบถ่วงน้ำหนักซึ่งแสดงให้เห็นว่ากลุ่มเป้าหมายใดสามารถเข้าถึงได้จากกลุ่มแหล่งที่มาที่ระบุและจำนวนคีย์ที่แตกต่างกันเป็นเป้าหมายที่ถูกต้องภายในกลุ่มเป้าหมาย
อัลกอริทึมนี้ทำการเรียกซ้ำหนึ่งครั้งต่อกลุ่มเป้าหมายจากกลุ่มปัจจุบันคูณแต่ละผลลัพธ์ด้วยน้ำหนักที่สอดคล้องกันและรวมทั้งหมด
เฉพาะการทำซ้ำครั้งแรกเท่านั้นที่คาดหวัง\$k\in[0..9]\$. สำหรับรายการถัดไปเราเพิ่งตั้งค่า\$k\$ไปยังคีย์นำหน้าของแต่ละกลุ่ม ( \$1\$, \$4\$, \$2\$และ\$0\$ ตามลำดับ).
JavaScript (ES6), 86 74 72 ไบต์
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1
ลองออนไลน์!
71 ไบต์
มากช้ากว่ามาก
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1)*f(k,n-1)+f(p,n,k):1
ลองออนไลน์!
การค้นหาฟังก์ชันแฮช
เรากำลังมองหาฟังก์ชัน\$h(p,k)\$บอกว่า\$p\$และ\$k\$เชื่อมต่อกันด้วยอัศวินกระโดด เนื่องจากฟังก์ชันนี้เป็นการสับเปลี่ยนและเนื่องจากผลลัพธ์จะเหมือนกันเสมอเมื่อ\$p=k\$XOR แบบบิตดูเหมือนผู้สมัครที่ดี
เราไม่สามารถทำโดยตรง\$p \operatorname{XOR} k\$เพราะตัวอย่างเช่น\$0 \operatorname{XOR} 4\$และ\$3 \operatorname{XOR} 7\$ทั้งคู่เท่ากับ\$4\$แม้ว่า\$(0,4)\$เชื่อมต่อและ\$(3,7)\$ ไม่ใช่
เราจำเป็นต้องได้รับเอนโทรปีมากขึ้นโดยใช้ตัวคูณ\$M\$เช่นนั้น\$(M\times p)\operatorname{XOR}\:(M\times k)\$ไม่มีการชนกัน ตัวคูณที่ถูกต้องสองสามตัวแรกคือ\$75\$, \$77\$, \$83\$, ... (เราสามารถใช้ตัวคูณที่แตกต่างกันสองตัวกับ\$p\$และ\$k\$แต่เราจะสูญเสียประโยชน์ของฟังก์ชันที่กำลังสับเปลี่ยน ดังนั้นจึงไม่น่าจะนำไปสู่การแสดงออกที่เล็กลง)
สำหรับตัวคูณที่ถูกต้องแต่ละตัวเราจะมองหาโซ่โมดูโลเพื่อลดขนาดของตารางการค้นหา
โดยเรียกใช้การค้นหาแบบดุร้ายด้วย\$M<10000\$และโมดูโลสองตัว\$1<m_0<m_1<100\$ตามด้วยโมดูโล\$32\$นิพจน์ต่อไปนี้เกิดขึ้น:
$$h(p,k)=((((p\times 2149)\operatorname{XOR}\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$
เรามี IFF ปฮอปที่ถูกต้อง\$h(p,k)\in\{1,4,5,8\}\$ซึ่งสามารถแสดงเป็นบิตมาสก์\$100110010_2=306_{10}\$.
ดังนั้นการใช้งาน JS:
306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1
โปรดทราบว่าโมดูโลสุดท้าย\$32\$ ถูกจัดเตรียมโดยปริยายโดยการเลื่อนขวา
แสดงความคิดเห็น
f = ( // f is a recursive function taking:
p, // p = current position
n, // n = number of remaining hops
k = 10 // k = key counter
) => //
n ? // if n is not equal to 0:
k-- && ( // decrement k; if it was not 0:
306 >> // right-shifted lookup bit-mask
(p * 2149 ^ k * 2149) // apply the XOR
% 71 % 35 // apply the modulo chain
& 1 && // if the least significant bit is set:
f(k, n - 1) // do a recursive call with p = k and n - 1
) + //
f(p, n, k) // add the result of a recursive call
// with the updated k
: // else:
1 // stop the recursion
// and increment the final result
เจลลี่ , 29 28 ไบต์
⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S
Dyadic Link ยอมรับจำนวนของการกระโดดทางด้านซ้ายและปุ่มทางด้านขวาซึ่งให้จำนวนพา ธ
ลองออนไลน์!
อย่างไร?
สร้างhopsตัวเลขทศนิยมที่มีความยาวทั้งหมดนำหน้าkeyไปยังแต่ละรายการและนับจำนวนเพื่อนบ้านที่ถูกต้องทั้งหมดโดยการค้นหาในรายการบีบอัด (หมายเหตุ: เมื่อใดที่hopsเป็นศูนย์ความจริงที่ว่าผลิตภัณฑ์ว่างเป็นหนึ่งหมายความว่าลิงก์จะให้ผลตอบแทน 1 ตามที่ต้องการ)
นี่คืออีก 28
⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S
อันนี้ใช้เลขคณิตขี้ขลาดในการตัดสินใจว่าการย้ายแต่ละครั้งนั้นถูกต้องหรือไม่โดยการเพิ่มสามตัวในแต่ละหลักสองหลักโดยใช้แฟกทอเรียลของพวกเขาคูณสิ่งเหล่านี้เข้าด้วยกันรับส่วนที่เหลือหลังจากหารด้วย\$22885\$รับส่วนที่เหลือหลังจากหารด้วย\$31\$และตรวจสอบว่าผลลัพธ์เป็นหนึ่งใน\$\{3,8,12,17\}\$.
Python 2 , 83 ไบต์
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)
ลองออนไลน์!
โซลูชันแบบวนซ้ำ ตรวจสอบคู่ของตัวเลขที่อัศวินเคลื่อนที่ออกไปโดยที่พวกมันเรียงต่อกันในสตริงฮาร์ดโค้ด604927618343816729406ซึ่งเขียนด้วยเลขฐานสิบหกที่สั้นกว่าหนึ่งไบต์ สตริงนี้เป็น palindrome เนื่องจากความสัมพันธ์ของ adjacency เป็นแบบสมมาตร แต่ฉันไม่เห็นวิธีที่สั้นกว่าในการใช้ประโยชน์จากสิ่งนั้นและลบความซ้ำซ้อน
83 ไบต์
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if 6030408>>(s*353^i*353)%62%29&1)
ลองออนไลน์!
85 ไบต์
def f(s,n):a=b=c=d=1;exec"a,b=b+c,2*a;c,d=b+d,2*c;"*n;print[d,a,b,a,c,n<1,c,a,b,a][s]
ลองออนไลน์!
ความคิดที่แตกต่างให้วิธีแก้ปัญหาที่รวดเร็วและทำซ้ำ เราใช้ประโยชน์จากกราฟการเลื่อนตำแหน่งอัศวินของปุ่มกดโทรศัพท์ที่สมมาตร:
3--8--1
| |
4--0--6
| |
9--2--7
โปรดทราบว่า 0 ไม่ทำลายความสมมาตรบน - ล่างของปุ่มกดเนื่องจากเชื่อมต่อกับ 4 และ 6 บนเส้นกึ่งกลางเท่านั้น ไม่ได้จับฉลากหมายเลข 5 มันไม่เชื่อมต่อกับอะไรเลย
เราใช้สมมาตรเพื่อยุบตำแหน่งลงไปสี่ประเภท:
a--b--a
| |
c--d--c
| |
a--b--a
a: 1379
b: 28
c: 46
d: 5
ตอนนี้เรามีช่วงการเปลี่ยนภาพ (บางส่วนปรากฏหลายครั้ง):
a -> b, c
b -> a, a
c -> a, a, d
d -> c, c
a,b,c,d=b+c,2*a,2*a+d,2*cสอดคล้องนี้เพื่อปรับปรุงการนับในขั้นตอนของแต่ละ สิ่งนี้สามารถเขียนให้สั้นลงa,b=b+c,2*a;c,d=b+d,2*cตามที่ ovs ระบุไว้ประหยัด 2 ไบต์
ดังนั้นเราย้ำnทำตามขั้นตอนในการผลิตค่าสอดคล้องของและตอนนี้เราจะต้องเลือกอย่างใดอย่างหนึ่งที่สอดคล้องกับจุดเริ่มต้นหลักa,b,c,d sเราจำเป็นต้องมีการทำแผนที่ของแต่ละหลัก0-9ไปยังรายการที่สอดคล้องกันa,b,c,dกับไป5 รหัสเพียงแค่ใช้ตัวเลือกอาร์เรย์โดยตรง:n<0[d,a,b,a,c,n<1,c,a,b,a][s]
อาจมีวิธีที่สั้นกว่าโดยใช้สมมาตรที่sและ10-sอยู่ในหมวดหมู่เดียวกันดังนั้นเราสามารถทำบางอย่างs*s%10เพื่อยุบสิ่งเหล่านี้หรือแม้กระทั่งs*s%10%8เพื่อให้ได้ลายนิ้วมือที่แตกต่างกันสำหรับแต่ละประเภท ด้วยการเพิ่มประสิทธิภาพวิธีนี้อาจเป็นผู้นำ
Python 2 , 68 ไบต์
บันทึก 1 ไบต์ขอบคุณ @Sisyphus
บันทึกอีก 5 ไบต์ขอบคุณ @xnor
นี่เป็นไปตามตรรกะที่ใช้ในเวอร์ชัน JS 62 ไบต์ของฉันพร้อมการใช้งานที่แตกต่างกันเพื่อให้ง่ายต่อการเล่นกอล์ฟใน Python ตั้งแต่นั้นมาฉันก็ย้ายกลับไปที่ JS แล้วเพราะมันก็สั้นลงเช่นกัน
f=lambda n,k:n<1or k-5and(2-k%2)*f(n-1,4-k%-9%2)+9%~k%2*f(n-1,k%2*2)
ลองออนไลน์!
ด้านล่างนี้เป็นข้อมูลสรุปของผลลัพธ์ที่แสดงโดยแต่ละนิพจน์โดยแยกตามกลุ่มสำคัญ:
expression | 1 3 7 9 | 2 8 | 4 6 | 0 | description
------------+---------+-----+-----+---+---------------------------------------
2-k%2 | 1 1 1 1 | 2 2 | 2 2 | 2 | weight for the 1st recursive call
4-k%-9%2 | 4 4 4 4 | 3 3 | 3 3 | 4 | target key for the 1st recursive call
9%~k%2 | 1 1 1 1 | 1 1 | 0 0 | 0 | weight for the 2nd recursive call
k%2*2 | 2 2 2 2 | 0 0 | - - | - | target key for the 2nd recursive call
Perl 5 , ( -p) 63 ไบต์
eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c
ลองออนไลน์!
ถ่าน 31 ไบต์
ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη
ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด รับจำนวนฮ็อปเป็นอินพุตแรก ช้าเกินไปสำหรับการกระโดดจำนวนมาก คำอธิบาย:
ＦＮ
ป้อนจำนวนฮ็อพและทำซ้ำหลาย ๆ ครั้ง
≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη
แมปทับอักขระทุกตัวในสตริงและแสดงรายการฮ็อปถัดไปที่เป็นไปได้ ตัวอย่าง: 6→การ170→การ682646→การ1701379170390170→การ ...
ＩＬη
นับจำนวนฮ็อพทั้งหมดที่พบ
รุ่น 44 ไบต์ที่เร็วขึ้น:
≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη
ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด คำอธิบาย: ทำงานโดยการคูณเมทริกซ์การเปลี่ยน hop ถัดไปซ้ำ ๆ
Python 3 , 88 ไบต์
f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634 9 7'[int(s)::10].strip(),[n-1]*3))
ลองออนไลน์!
-15 ไบต์ขอบคุณovs
-2 ไบต์ขอบคุณJonathan Allan
k4 , 60 ไบต์
{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}
ใช้พจนานุกรมเพื่อแมปคีย์ไปยังการเคลื่อนไหวที่ถูกต้องซึ่งเมื่อรวมกับ/ฟังก์ชันเป็นเครื่องที่มีสถานะ จำกัดเมล็ดพันธุ์ด้วยx( s) และรันสำหรับy( n) ซ้ำ ,//ทำให้ผลลัพธ์แบนเป็นอาร์เรย์หนึ่งมิติ
ทดสอบด้วย:
1 3 6 4608 18136064 1 0~{#,//y![!10;(4 6;6 8;7 9;4 8;0 3 9;();0 1 7;2 6;1 3;2 4)]/x}.'(6 0;6 1;6 2;6 10;6 20;5 0;5 1)
05AB1E , 24 22 ไบต์
F•žNjεEÿ¶^²è+%•5¡sèS}g
จำนวนฮ็อปเป็นอินพุตแรกและตัวเลขเริ่มต้นเป็นอินพุตที่สอง
ลองออนไลน์หรือตรวจสอบกรณีทดสอบทั้งหมด (ยกเว้นกรณีที่มี 20 ฮ็อพซึ่งหมดเวลา)
คำอธิบาย:
F # Loop the first (implicit) input amount of times:
•žNjεEÿ¶^²è+%• # Push compressed integer 46568579548530955107526513524
5¡ # Split it on 5: [46,68,79,48,309,"",107,26,13,24]
s # Swap to take the current list of digits,
# or the second (implicit) input in the first iteration
è # (0-based) index those into this list
S # Convert it to a flattened list of digits
# ("" becomes an empty list [])
}g # After the loop: pop the list of digits, and take its length
# (after which the result is output implicitly)
ดู 05AB1E นี้เคล็ดลับของฉัน (ส่วนวิธีการบีบอัดจำนวนเต็มขนาดใหญ่? )จะเข้าใจว่าทำไมเป็น•žNjεEÿ¶^²è+%•46568579548530955107526513524
ภาษา Wolfram 108 ไบต์
Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&
ลองออนไลน์!
คุณรู้ไหมอาจมีวิธีแก้ปัญหาที่สั้นกว่านี้ แต่ฉันชอบคณิตศาสตร์ของอันนี้ สิ่งนี้ได้รับเมทริกซ์ adjacencyสำหรับกราฟยกให้เป็นพลังของจำนวนการกระโดดและคูณด้วยเวกเตอร์ที่แสดงถึงคีย์ที่เริ่มจาก องค์ประกอบของเวกเตอร์ผลลัพธ์จะให้จำนวนพา ธ ไปยังแต่ละคีย์ดังนั้นผลรวมจึงให้จำนวนพา ธ ทั้งหมดของความยาวที่กำหนด
T-SQL, 197 ไบต์
ส่งคืนค่าว่างสำหรับไม่มีโซลูชัน
ซึ่งสามารถจัดการ 25 ฮ็อพใน 10 วินาที
WITH C as(SELECT 0i,1*translate(@n,'37986','11124')x,1q
UNION ALL
SELECT-~i,y,q*(2+1/~(y*~-a))FROM(values(1,4),(1,2),(4,0),(2,1),(4,1),(0,4))x(a,y),c
WHERE a=x AND i<@)
SELECT
sum(q)FROM C
WHERE i=@
ลองออนไลน์
Java 8, 137 129 91 89 ไบต์
int f(int n,int k){return--n<0?1:k%2>0?k==5?0:f(n,2)+f(n,4):2*f(n,k>0?1:4)+k/4%2*f(n,0);}
ท่าเรือ@Arnauldคำตอบ JavaScript 'sให้โดย@ OlivierGrégoire
-2 ไบต์ขอบคุณที่@ceilingcat
ลองออนไลน์
คำตอบเก่า137129ไบต์:
(s,h)->{for(;h-->0;){var t="";for(var c:s.getBytes())t+="46,68,79,48,309,,107,26,13,24".split(",")[c-48];s=t;}return s.length();}
ตัวเลขเริ่มต้นเป็นอินพุตสตริงจำนวนฮ็อพเป็นจำนวนเต็ม
ลองออนไลน์
คำอธิบาย:
(s,h)->{ // Method with String & integer parameter & integer return
for(;h-->0;){ // Loop the integer amount of times:
var t=""; // Temp-String, starting empty
for(var c:s.getBytes()) // Inner loop over the digit-codepoint of the String:
t+= // Append to the temp-String:
"46,68,79,48,309,,107,26,13,24".split(",")[c-48]);
// The keys the current digit can knight-jump to
s=t;} // After the inner loop, replace `s` with the temp-String
return s.length();} // Return the length of the String as result