Послідовність занадто мета

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- й елемент послідовності.

Перші 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 Якщо a (n) дорівнює 1, то n-й крок заповнить кожен залишок порожнім, припиняючи генерацію.
1 Leaky Nun 06/20/2017
@QBrute Я представив список перших 10 000 000, зв'язаних у питанні; просто сюжет їх.

6 Answers


Anders Kaseorg 06/20/2017.

Haskell , 80 67 байт

 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 Схоже, ви незнайомі з охороною картин. 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 байт

 f(n)NO 

Спробуйте онлайн!

Проходження

 f(n)NO 

через коротке замикання, а потім через закони Де Моргана та той факт, що 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-without-return, який працює з gcc , ми "повертаємо" останній елемент перших n термінів у послідовності, який, як виявляється, є n м терміном.


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

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

Спробуйте його в Інтернеті

Як це працює

Замість того, щоб обдурювати списки, це використовує звичайну рекурсивну формулу.

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 

Спробуйте онлайн!

Рекурсивне арифметичне рішення, яке вийшло в основному тим же способом, як і відповідь Піт на запитання Андера Казерога .

Цей код покритий бородавками - потворними частинами, які виглядають так, як їх можна було б відірватися від гольфу, але я не бачив, як це зробити.

Функція i%j дійсно хоче використати охорону, щоб перевірити, чи mod i(f j)>0 і оцінити один з відповідних двох виразів. Але обидва вирази використовують div i(f j) . Зв'язування того, що в охоронці не буде застосовуватися з обох сторін. Наскільки я знаю, охоронець не може бути "розподілений" над іншими охоронцями. let і where занадто довгі Таким чином, last код використовується для вибору одного з двох виразів, тоді як охоронець прив'язує змінну. Ух

В ідеалі ми будемо використовувати divMod оскільки використовуються як div і mod , але (d,m)<-divMod ... є довгим висловом. Замість того, щоб перевірити, чи мода, коли значення дільника перевищує початкове значення, ми перевіряємо, що мод не відрізняється від нуля.

0%j=2 справа не потрібна, якщо Haskell короткозамкнутий div 0 , який він не має. Файл .pred перетворює 1-індексований вхід на нульовий індекс, або в будь-якому місці буде -1 корекція.

4 comments
Ørjan Johansen 06/21/2017
Якщо ви ввімкнете індексування % 1, то вам потрібно 5 байт корекції - це просто зв'язок. However , ви можете вставити f в % безкоштовно, а потім f стає анонімним, тому ви в цілому зберігаєте два байти.
xnor 06/21/2017
@ ØrjanJohansen Що ви маєте на увазі тут за інлайн? Я не бачу, як змінити посилання на 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
Як ви бачите, inlining передбачає 1-reindexing, що видаляє .pred .

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 91 байт

Рекурсивна функція, яка зупиняється, як тільки результат є доступним.

 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)() . Хоча відповідний пост в meta на даний момент дає позитивну оцінку, цей синтаксис, очевидно, оскаржується.

 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
@Шаггі Спасибо! Додано як альтернативну версію.

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

Лямбда-вираз.

Створює цілий масив і постійно заповнює його, доки n-й значення не буде заповнено.

Попередньо оголошуючи змінні вгорі, щоб зменшити стільки декларацій, скільки можливо, оскільки кожна int витрачає 4 байти простору, а не додавання ,n що дорівнює 2.

У j -й ітерації обчислення кількість "заготовок", яку треба пропустити, дорівнює a[j] (або 2, якщо порожній). Звідси випливає, що якщо перший пробіл, який ми повинні заповнити, знаходиться в положенні k , k * a[j] дає нам "крок" ( s ).


HighResolutionMusic.com - Download Hi-Res Songs

1 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
3 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
4 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
7 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
8 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
9 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
10 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
11 Little Mix

Told You So flac

Little Mix. 2018. Writer: Eyelar;MNEK;Raye.
12 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
13 Cher Lloyd

None Of My Business flac

Cher Lloyd. 2018. Writer: ​iamBADDLUCK;Alexsej Vlasenko;Kate Morgan;Henrik Meinke;Jonas Kalisch;Jeremy Chacon.
14 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
15 Calum Scott

No Matter What flac

Calum Scott. 2018. Writer: Toby Gad;Calum Scott.
16 Ashley Tisdale

Voices In My Head flac

Ashley Tisdale. 2018. Writer: John Feldmann;Ashley Tisdale.
17 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
18 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
19 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
20 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.

Related questions

Hot questions

Language

Popular Tags