De volgorde is te meta

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

We beginnen met een lege 1-geïndexeerde reeks:

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

In de eerste stap vullen we alle a (n) lege waarden in met de gehele getallen groter dan 1, beginnend bij de eerste lege lege cel, waarbij een (n) de ne - invoer in de reeks is.

Na de eerste stap:

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

Merk op dat a (1) 2 moet zijn omdat het eerste gehele getal groter dan 1 2 is.

In de tweede stap vullen we elke a (2) spaties in. Het zal duidelijk zijn dat a (2) 2 moet zijn.

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

In de derde stap vullen we elke a (3) spaties in. Uit de reeks, a (3) = 3.

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

In de vierde stap vullen we elke a (4) spaties in. Uit de reeks, 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,_,... 

uiteindelijk:

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

Taak

Geef n het n- de element van de reeks terug, gegeven n.

De eerste 10.000.000 termen van de reeks zijn hier te vinden.

Dit is . Het kortste antwoord in bytes wint. Standaard mazen zijn van toepassing.

5 Comments
Leaky Nun 06/20/2017
@LuisMendo Bedankt, ik heb het toegevoegd.
Dead Possum 06/20/2017
Benieuwd, wat voor fout heeft mr. Eén van de sequenties uitgesloten?
Leaky Nun 06/20/2017
@DeadPossum Nou, als je elke lege invult, ben je klaar in een stap.
2 Leaky Nun 06/20/2017
@DeadPossum Als a (n) 1 is, vult de n-de stap alle resterende blanco in, waardoor de generatie wordt beëindigd.
1 Leaky Nun 06/20/2017
@QBrute I leverde een lijst met de eerste 10.000.000 die in de vraag zijn gekoppeld; zet ze gewoon in kaart.

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 

Probeer het online!

Haskell is de perfecte taal voor het definiëren van een oneindige lijst in termen van zichzelf.

5 comments
1 Julian Wolf 06/20/2017
Aangezien de TIO-link werkt zoals verwacht, denk ik dat mijn vraag in plaats daarvan zou moeten zijn: zou u een uitleg kunnen toevoegen over hoe dit werkt?
2 Anders Kaseorg 06/20/2017
@ JulianWolf Het klinkt alsof je onbekend bent met verharde patroonwachten. pattern1 | let pattern2 = expr2 = expr1 pattern1 | let pattern2 = expr2 = expr1 betekent hetzelfde als pattern1 = let pattern2 = expr2 in expr1 (om dezelfde reden dat [expr1 | let pattern2 = expr2] hetzelfde betekent als [let pattern2 = expr2 in expr1] ).
1 Ørjan Johansen 06/20/2017
Ik moet onthouden patroonwachters let (vooral dat ze functies kunnen uitvoeren)! Ook is m=2:2:2`drop`g m een byte korter.
1 Ørjan Johansen 06/20/2017
(!!)$0:m is twee bytes korter.
1 Ørjan Johansen 06/20/2017
Eigenlijk kun je de 2:2: dingen helemaal met wat meer luiheid laten vallen: g ~(a:b)|... en m=g m .

Doorknob 06/20/2017.

C, 123 bytes

 f(n)NO 

Probeer het online!

walkthrough

 f(n)NO 

door kortsluiting, en dan door de wetten van De Morgan en het feit dat 0 in C vals is:

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

Dit stelt in feite: "als deze ruimte leeg is, verhoog dan k . En als k eerder een veelvoud was van de stapgrootte, voer dan de volgende verklaring uit." Daarom voeren we de instructie uit op alle step size elementen, precies zoals de volgorde wordt beschreven. De verklaring zelf is eenvoudig; alles wat het doet is het genereren van 2 , 3 , 4 , ....

 n=p[n-1];} 

Met de tricky-return-without-a-return die werkt met gcc , "keren we" terug naar het laatste element van de eerste n termen in de reeks, wat toevallig de n ste term is.


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

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

Probeer het online

Hoe het werkt

In plaats van rond te lummelen met lijsten, gebruikt dit een eenvoudige recursieve formule.

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 bytes

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

Probeer het online!

Een recursieve rekenkundige oplossing die in principe dezelfde methode bleek te zijn als het Pyth-antwoord van Anders Kaseorg .

Deze code is bedekt met wratten - lelijke delen die eruitzien alsof ze kunnen worden weggegolfd, maar ik zag niet hoe.

De functie i%j wil echt een bewaker gebruiken om te controleren of mod i(f j)>0 en een van de overeenkomende twee expressies te evalueren. Maar beide uitdrukkingen gebruiken div i(f j) . Bindend dat in een bewaker het niet op beide zijden van toepassing zal zijn. Voor zover ik weet, kan er geen bewaker worden gemaakt om te 'verdelen' over andere bewakers. let en where zijn te lang. Dus, de code gebruikt als last een van de twee uitdrukkingen, terwijl de bewaker de variabele bindt. Ugh.

Idealiter zouden we divMod omdat zowel de div als de mod worden gebruikt, maar (d,m)<-divMod ... is een lange uitdrukking. We controleren in plaats daarvan de mod niet-nul door te kijken of de div waarde keer de deler tekortschiet van de oorspronkelijke waarde.

Het 0%j=2 geval zou niet nodig zijn als Haskell div 0 kortgesloten had, wat niet het geval is. De .pred converteert de 1-geïndexeerde invoer naar nul geïndexeerd, anders zouden er overal -1 correcties zijn.

4 comments
Ørjan Johansen 06/21/2017
Als u % 1-geïndexeerd draait, heeft u vijf bytes-correcties nodig - die alleen maar binden. U kunt dan kosteloos f in % in % in % f en dan wordt f anoniem zodat u in totaal twee bytes bespaart.
xnor 06/21/2017
@ ØrjanJohansen Wat bedoel je hier met inline? Ik zie niet hoe de verwijzingen naar f te veranderen zonder bytes te verliezen.
Ørjan Johansen 06/21/2017
divMod lijkt één byte goedkoper te zijn, omdat het vertakking mogelijk maakt met !!(0^m) . Tot nu toe heb ik: 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
Zoals je ziet, veronderstelt de inlining de 1-reindexering, die de .pred verwijdert.

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 91 bytes

Een recursieve functie die stopt zodra het resultaat beschikbaar is.

 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)) 

Alternatieve versie, 90 bytes

Suggested by Shaggy for -1 byte

Deze moet worden aangeroepen met f(n)() . Hoewel de corresponderende post in meta momenteel een positieve score geeft, is deze syntax kennelijk betwist.

 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)) 

demonstratie

 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)) zou moeten werken voor 92 bytes. Noem het met f(n)() .
Arnauld 06/20/2017
@Shaggy Bedankt! Toegevoegd als een alternatieve versie.

Xanderhall 06/20/2017.

Java 8, 124 bytes

(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];} 

Lambda-expressie.

Creëert een integer array en vult deze voortdurend in totdat de n-de waarde wordt ingevuld.

Vooraf declareren van variabelen bovenaan om zoveel mogelijk declaraties te verminderen aangezien elke int 4 bytes van de ruimte kost in plaats van optellen ,n dat is 2.

In de eerste reeks berekeningen is het aantal spaties dat men moet overslaan gelijk aan a[j] (of 2, indien leeg). Het komt er op neer dat als de eerste lege ruimte die we moeten invullen op positie k , k * a[j] ons de 'stap' ( s ) geeft.

Related questions

Hot questions

Language

Popular Tags