ลำดับเป็นเมตาดาต้าเกินไป

Leaky Nun 09/11/2017. 6 answers, 2.053 views
code-golf sequence

เราเริ่มต้นด้วยลำดับที่ว่าง 1 รายการ:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,... 

ในขั้นตอนที่ n เรากรอกทุกช่องว่าง (n) ด้วยจำนวนเต็มมากกว่า 1 เริ่มต้นจากช่องว่างแรกที่เหลืออยู่โดยที่ a (n) เป็น ลำดับที่ n ในลำดับ

หลังจากขั้นตอนแรก:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,... 

โปรดทราบว่า a (1) ต้องเป็น 2 เนื่องจากจำนวนเต็มแรกมากกว่า 1 คือ 2

ในขั้นตอนที่สองเรากรอกทุกช่องว่าง (2) จะเห็นได้ชัดว่า (2) ต้องเป็น 2

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,... 

ในขั้นตอนที่สามเรากรอกทุกช่องว่าง (3) จากลำดับ, a (3) = 3

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,... 

ในขั้นตอนที่สี่เรากรอกทุกช่องว่าง (4) จากลำดับ, a (4) = 2

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,... 

ในที่สุด:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,... 

งาน

ให้ n ส่งค่า n th element ของ sequence

สามารถหาข้อตกลง 10,000,000 คำแรกได้ ที่นี่

นี่คือ คำตอบที่สั้นที่สุดในไบต์จะชนะ ใช้ ช่องโหว่มาตรฐาน

5 Comments
Leaky Nun 06/20/2017
@LuisMendo ขอบคุณฉันได้เพิ่มมัน
Dead Possum 06/20/2017
อยากรู้ไหมว่าอะไรผิดพลาดที่คุณได้รับการยกเว้นจากลำดับ?
Leaky Nun 06/20/2017
@DeadPossum ดีถ้าคุณกรอกข้อมูลลงในช่องว่างทั้งหมดคุณจะทำในขั้นตอนเดียว
2 Leaky Nun 06/20/2017
@DeadPossum ถ้า n (n) มีค่าเป็น 1 ขั้นตอน n-th จะเติมข้อมูลทุกๆอันที่ยังเหลืออยู่เพื่อยกเลิกการสร้าง
1 Leaky Nun 06/20/2017
@ QBrute ฉันให้รายชื่อ 10,000,000 คนแรกที่เชื่อมโยงกันในคำถามนี้ เพียงแค่วางแผนพวกเขา

6 Answers


Anders Kaseorg 06/20/2017.

Haskell , 80 67 bytes

 g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m 

ทดลองใช้แบบออนไลน์!

Haskell เป็นภาษาที่สมบูรณ์แบบสำหรับการกำหนดรายการอนันต์ในแง่ของตัวเอง

5 comments
1 Julian Wolf 06/20/2017
ระบุว่าลิงก์ TIO ทำงานตามที่คาดไว้ฉันเดาว่าคำถามของฉันน่าจะเป็น: คุณช่วยเพิ่มคำอธิบายวิธีการทำงานได้หรือไม่?
2 Anders Kaseorg 06/20/2017
@JulianWolf ดูเหมือนคุณไม่คุ้นเคยกับรูปแบบ guards pattern1 | let pattern2 = expr2 = expr1 pattern1 | let pattern2 = expr2 = expr1 หมายถึงสิ่งเดียวกับ pattern1 = let pattern2 = expr2 in expr1 (ด้วยเหตุผลเดียวกันกับที่ [expr1 | let pattern2 = expr2] หมายถึงสิ่งเดียวกันกับ [let pattern2 = expr2 in expr1] )
1 Ørjan Johansen 06/20/2017
ฉันต้องจำไว้ let ยามรูปแบบ (โดยเฉพาะอย่างยิ่งที่พวกเขาสามารถทำหน้าที่)! นอกจากนี้ m=2:2:2`drop`g m เป็นไบต์ที่สั้นกว่า
1 Ørjan Johansen 06/20/2017
(!!)$0:m เป็นไบต์ที่สั้นกว่าสองไบต์
1 Ørjan Johansen 06/20/2017
จริงๆแล้วคุณสามารถลด 2:2: ทั้งหมดด้วยความเกียจคร้านเล็กน้อย: g ~(a:b)|... และ m=g m

Doorknob 06/20/2017.

C, 123 bytes

 f(n)NO 

ทดลองใช้แบบออนไลน์!

เกมส์

 f(n)NO 

โดยการลัดวงจรแล้วตามกฎหมาย De Morgan และความจริงที่ว่า 0 เป็นเท็จใน C:

 if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
} 

นี้เป็นหลักระบุว่า "ถ้าพื้นที่ว่างเปล่านี้เพิ่ม k และถ้า k ก่อนหน้านี้หลายขนาดขั้นตอนเรียกใช้คำสั่งต่อไปนี้" ดังนั้นเราจึงเรียกใช้คำชี้แจงเกี่ยวกับองค์ประกอบทุก step size ซึ่งตรงกับลำดับที่อธิบายไว้ คำสั่งนั้นง่าย; ทั้งหมดมันไม่เป็นสร้าง 2 , 3 , 4 , ....

 n=p[n-1];} 

เราใช้ "return" เป็นองค์ประกอบสุดท้ายของคำศัพท์ n คำแรกในซีเควนซ์ซึ่งเป็นคำที่ n


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1 

ลองใช้แบบออนไลน์

มันทำงานอย่างไร

แทนการหลอกลวงรอบกับรายการนี้ใช้สูตร recursive ธรรมดา

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input()))) 

xnor 06/20/2017.

Haskell 67 ไบต์

 0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j 

ทดลองใช้แบบออนไลน์!

วิธีแก้ปัญหาเลขคณิตแบบวนซ้ำที่เปิดออกโดยทั่วไปเป็นวิธีเดียวกันกับ คำตอบ Pyth ของ Anders Kaseorg

รหัสนี้ครอบคลุมในหูด - ชิ้นส่วนที่น่าเกลียดที่ดูเหมือนว่าพวกเขาอาจจะเล่นกอล์ฟ แต่ฉันไม่ได้เห็นอย่างไร

ฟังก์ชัน i%j ต้องการใช้ยามเพื่อตรวจสอบว่า mod i(f j)>0 และประเมินหนึ่งในสองนิพจน์ที่ตรงกัน แต่สำนวนทั้งสองใช้ div i(f j) การผูกมัดว่าในยามจะไม่นำมาใช้กับทั้งสองฝ่าย เท่าที่ฉันรู้ยามไม่สามารถทำ "กระจาย" เหนือยามอื่น ๆ ได้ let และ where ยาวเกินไป ดังนั้นรหัสใช้ last เพื่อเลือกหนึ่งในสองนิพจน์ในขณะที่ยามผูกตัวแปร ฮึ.

เราต้องการใช้ divMod เนื่องจากทั้ง div และ mod ถูกใช้ แต่ (d,m)<-divMod ... เป็นนิพจน์ที่ยาวนาน เราตรวจสอบแทน hackily ของ mod เป็น nonzero โดยดูว่าค่า div divisor ค่าต่ำกว่าค่าเดิม

0%j=2 กรณีจะไม่จำเป็นถ้า Haskell ลัดวงจร div 0 ซึ่งไม่ได้ .pred แปลงข้อมูลที่จัดทำดัชนีไว้ 1 รายการให้เป็นดัชนีศูนย์หรืออื่น ๆ ก็จะมีการแก้ไข -1 ใดก็ได้

4 comments
Ørjan Johansen 06/21/2017
ถ้าคุณเปิด % 1-index แล้วคุณต้องแก้ไขห้าไบต์ - ซึ่งเพิ่งผูกมัด However คุณสามารถแทรกบรรทัด f เป็น % โดยไม่เสียค่าใช้จ่ายและ f จะกลายเป็นนิรนามเพื่อให้คุณประหยัดทั้งสองไบต์โดยรวม
xnor 06/21/2017
@ ØrjanJohansenสิ่งที่คุณหมายถึงที่นี่โดย inline? ฉันไม่เห็นวิธีการเปลี่ยนการอ้างอิงถึง f โดยไม่สูญเสียไบต์
Ørjan Johansen 06/21/2017
divMod น่าจะเป็นหนึ่งไบต์ที่ถูกกว่าเพราะจะช่วยให้สามารถแบ่งแยกด้วย !!(0^m) จนถึงตอนนี้ฉันมี: 1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);‌​(%1)
Ørjan Johansen 06/21/2017
ตามที่คุณเห็นการ .pred นี้คาดว่าจะมีการจัดเรียงข้อมูลใหม่ 1 ครั้งซึ่งจะลบ .pred . .pred

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 93 ไบต์

ฟังก์ชันแบบทวนซ้ำที่จะหยุดทำงานทันทีที่มีผลการค้นหา

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

เวอร์ชันสำรอง 90 ไบต์

Suggested by Shaggy for -1 byte

ต้องเรียกชื่อนี้ด้วย f(n)() แม้ว่า โพสต์ที่เกี่ยวข้องในเมตา จะให้คะแนนบวกไวยากรณ์นี้ดูเหมือนจะเป็นข้อพิพาท

 n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

การสาธิต

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
} 

2 comments
Shaggy 06/20/2017
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k‌​?c:++v:(i=1,v=2),i=0‌​,k=a[p]||2)) ควรทำงานเป็น 92 ไบต์ โทรออกด้วย f(n)()
Arnauld 06/20/2017
@Shaggy ขอบคุณ! เพิ่มเป็นเวอร์ชันสำรอง

Xanderhall 06/20/2017.

Java 8, 124 ไบต์

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];} 

การแสดงออกแลมบ์ดา

สร้างอาร์เรย์จำนวนเต็มและเติมข้อมูลอย่างต่อเนื่องจนกว่าจะมีการเติมค่า nth

ก่อนประกาศตัวแปรที่ด้านบนเพื่อลดการประกาศให้มากที่สุดเท่าที่จะเป็นไปได้แต่ละค่าใช้จ่าย 4 ไบต์ของพื้นที่ในทางตรงกันข้ามกับการเพิ่ม ,n ซึ่งเป็น 2

ในการคำนวณซ้ำของ j ', จำนวน' ช่องว่าง 'ต้องข้ามเป็นเท่ากับ a[j] (หรือ 2 ถ้าว่าง) มันทำงานได้ว่าถ้าพื้นที่ว่างเปล่าแรกที่เราต้องกรอกคือตำแหน่ง k , k * a[j] ทำให้เรา 'ขั้นตอน' ( s )

Related questions

Hot questions

Language

Popular Tags