Codegolf — Получите Последовательность Шагов

  • Автор темы hedIncunc
  • Обновлено
  • 23, Oct 2024
  • #1

Испытание

Учитывая последовательность чисел, создайте функцию, которая возвращает шаги последовательности.

  • Предположим, что последовательность будет 
     Input: [5, 6, 7] => Output: [1]
  • Последовательность повторит свои шаги хотя бы один раз.
  • Последовательность будет содержать только натуральные числа
  • Ваша функция или программа должна возвращать максимально короткую последовательность шагов.

Пример:

Вход: Input: [2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47] => Output: [4,4,3,4]

Выход: Input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] => Output: [5,2]

Объяснение: Начальная последовательность идет от Input: [1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28] => Output: [3,4,1,1] . Then it repeats. The output then is [2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20] \ /\ /\ /\ / 3 1 1 1 Then it repeats...

Другой пример:

Вход: [3, 1, 1, 1]

Выход: [2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20]

[1 step, 1 step, 2 steps] => [1, 1, 2]

Тестовые случаи

1 => 2 (1 step), 2 => 3 (1 step), 3 => 5 (2 steps)

[1, 1, 2]

[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17]

N >= 3

Разъяснения

  • Входная длина - 1 делится на выходную длину
  • Предположим, что последовательность всегда будет возрастать.

Это , поэтому выигрывает самый короткий ответ в байтах.

#код-гольф #код-гольф #последовательность #массив

hedIncunc

hedIncunc

Пользователь
Рег
01 Mar, 2011
Тем
78
Постов
200
Баллов
610
  • 26, Oct 2024
  • #2

Желе, 9 7 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
āεI¥ô}ʒË}нн   Full program.
ā             Length range. Push [1 ... len(inp)].

ε   }        For each...

I¥ô         ... Chop the deltas into pieces of the corresponding size

ʒË}     Keep only those that have all their elements equal.

нн   And first retrieve the first element of the first one.

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

Как это работает

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 (*&d~/:c#'(!c:#d)#\:d)#d:1_-': / the solution

-': / deltas 

1_    / drop first

d:      / save as d

#        / take (#) from
(                    )         / do this together

#\:d          / take (#) each-left (\:) from d

(     )              / do this together

#d               / count length of d

c:                 / save as c

!                   / range 0..c-1

c#'                     / take c copies of each

d~/:                        / d equal (~) to each right (/:)

&                            / where true

*                             / first one
||answer||

JavaScript (ES6), 58 байт

Выводит строку, разделенную запятыми (с запятой в начале).

q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 5, 6, 7, 8, 11, 12, 13, 14, 17, 18, 19, 20 3 1 1 1 q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17 1 1 2 q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28 3 4 1 1 q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41 5 2 q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47 4 4 3 4 q)k)(*&d~/:c#'(!c:#d)#\:d)#d:1_-':5 6 7 ,1

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

Или 56 байт если мы будем использовать (*&d~/:c#'(!c:#d)#\:d)#d:1_-': as the separator and we assume that the sequence is always строго увеличивается.

Как?

Сначала мы преобразуем входной массив а[ ] к списку последовательных различий с:

FindRepeat@*Differences

Потому что п изначально установлено нечисловое значение (функция обратного вызова карта()), первая итерация дает НЭН.

Пример:

←ḟΛ=Um`CẊ≠⁰N

Затем мы приводим результат к строке:

s/\d+ (?=(\d+))/($1-$&).$"/ge;s/\d+$//;s/^(.+?)\1*$/$1/

Наконец, мы ищем кратчайший1 шаблон целых чисел, разделенных запятыми ( -p ) starting right after "NaN" and repeating till the end of the string:

.¥

1: использование нежадного ¥η.ΔÞ.¥-Ë

 
Opanasyuk.cergej

Opanasyuk.cergej

Пользователь
Рег
25 Nov, 2019
Тем
85
Постов
213
Баллов
648
  • 26, Oct 2024
  • #3

Брахилог, 11 байт

# take input implicitly ¥ # deltas, eg [4, 5, 7, 8, 10] -> [1, 2, 1, 2] © # save this to the global register η # prefixes, eg [1, 2, 1, 2] -> [[1], [1, 2], ...] .Δ # find the first one such that Þ # cycled infinitely, eg [1, 2] -> [1, 2, 1, 2, ...] Å? # starts with ® # the global register # and implicitly print the found element

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

Было бы 5 байт, если бы была встроенная функция для последовательных разностей.

Объяснение

¥©η.ΔÞ®Å? ||answer||

Пиф, 11 байт

{ # bare block lambda with implicit parameter $_ ~( # stringify (space separated) .rotor( 2 => -1 ) # from the input take 2 backup 1, repeat .map: { .[1] - .[0] } # subtract each pair to find the differences ) ~~ # smartmatch / # regex ^ # beginning of string ( .+? ) # match at least one character, but as few as possible {} # make sure $0 is set (probably a compiler bug) " $0"+ # match $0 one or more times (with a leading space) $ # end of string /; ~$0 # return the stringified $0 }

Попробуйте здесь

Объяснение

"1 1 2" ||answer||

Япт, 14 12 байт

{~(.rotor(2=>-1).map:{.[1]-.[0]})~~/^(.+?){}" $0"+$/;~$0}

Попробуйте это

Объяснение

:- pairwise differences :( all leftward rotations of array u keep only unique rotations mh output the first element from each unique rotation

Оригинал

░»F\☺»

Попробуйте это

 
Balkes

Balkes

Пользователь
Рег
06 Jun, 2006
Тем
72
Постов
190
Баллов
580
  • 26, Oct 2024
  • #4

Р, 49 46 байт

Полная программа:

let i=map(uncurry(-))$zip(tail x)(init x)in head$filter(\s->take(length i)(concat$repeat s)==i)(tail$inits i)

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

Р, 72 58 54 байт

Исходное представление функции со всеми тестовыми примерами в одном месте:

¥ # Calculate the deltas of the input-array # i.e. [1,2,3,5,6,7,9] → [1,1,2,1,1,2] D # Duplicate it η # Push all its prefixes # [1,1,2,1,1,2] → [[1],[1,1],[1,1,2],[1,1,2,1],[1,1,2,1,1],[1,1,2,1,1,2]] v # For-each over these prefixes Ð # Triplicate the (duplicated) deltas-list NƒÁ} # Rotate the deltas-list N+1 amount of times, # where N is the prefix index (== prefix_length-1) # i.e. [1,1,2] and [1,1,2,1,1,2] (rotate 3 times) → [1,1,2,1,1,2] Q # If the rotated deltas and initial deltas are equal # [1,1,2,1,1,2] and [1,1,2,1,1,2] → 1 D—# # Print the current prefix-list, and stop the for-each loop

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

Спасибо JayCe за предложение полного маршрута программы и -4 байта для функции, а также Джузеппе за дополнительные -3.

 
Dima2008

Dima2008

Пользователь
Рег
28 Mar, 2011
Тем
72
Постов
215
Баллов
595
  • 26, Oct 2024
  • #5

Дж, 22 19 байт

Сэкономлено 3 байта благодаря FrownyFrog!

Ð

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

[Попробуйте онлайн!][TIO-ji2uiwla]

Как?

D ||answer||

05AB1E, 8 байт

Сэкономлено 3 байта благодаря Кевин Круйссен.

®

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

05AB1E, 11 байт

©

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

Á

13 байт

Симпатичная альтернатива, ИМХО:

¥DηvÐNƒÁ}QD—#

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

1+ $.& ||answer||

Javascript, 49 56 байт

Редактировать Сэкономлено 7 байт, спасибо (угадайте кому?) Арно

Та же идея регулярного выражения, что и у Арно, но, как ни странно, такая другая реализация...

Возврат строки с шагами, разделенными запятыми (и ведущей запятой)

1+(.+?)\1*$ $1

Тест

(?<=(1+),)\1 ||answer||

МАТЛ, 14 13 12 байт

\d+ $*

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

Только что обнаружил, что у MATL есть циркуляционная функция!

Объяснение

\d+ $* (?<=(1+),)\1 1+(.+?)\1*$ $1 1+ $.& - Get the differences between successive terms, as an array

d[n:]==d[:-n] - duplicate that, then call the n («галерея») функция с d ('circulant') option. Creates a matrix with the given vector as first row, then successive rows are the same vector shifted circularly, until it wraps around.

d - Check for unique rows and get their row numbers (not sure if there's a shorter way of doing this). When sequence steps repeat, the circularly shifted row will be the same as the first row, and the subsequent rows will be repeats. So this gets the indices of the first run of sequence steps before they start repeating.

def f(a,n=1):d=[y-x for x,y in zip(a,a[1:])];return d[:-n]==d[n:]and d[:n]or f(a,n+1) - index using that into the original differences array, to get the answer.

Старше:

v←-2-/⎕ Prompt for input and take successive differences (⍳⍴v)⌽¨⊂v create a nested vector ans sequentially rotate by one to length of v +/¨(⊂v)= compare to original v and sum positions where there is match (⍴v)= identify where all elements match (↑(....) identify number of rotations giving a first complete match (↑(...)↑v take first number of elements from above from v as repeated sequence

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

(-1 байт благодаря Джузеппе)

Объяснение:

(↑((⍴v)=+/¨(⊂v)=(⍳⍴v)⌽¨⊂v)/⍳⍴v)↑v←-2-/⎕ ||answer||

Питон 2, 101 байт

a->{ // Method with integer-array parameter and String return-type var t=""; // Temp-String, starting empty for(int i=a.length;i-->1; // Loop backward over the input-array, skipping the first item t+=a[i]-a[i-1] // Calculate the difference between two adjacent items +" "); // And append this with a space to the temp-String return t.replaceAll("( ?.+?)\\1*$", // Find the shortest repeating substring "$1");}// And only keep one such substring

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

Сначала генерирует дельты д, затем находит первый префикс п из д что при повторении ⌊лен(L) / лен(п)⌋ раз дает л, где л это входной список.

 
Влад Хомков

Влад Хомков

Пользователь
Рег
23 Oct, 2020
Тем
80
Постов
190
Баллов
630
  • 26, Oct 2024
  • #6
Chaykovskiy

Chaykovskiy

Пользователь
Рег
09 Jun, 2008
Тем
63
Постов
209
Баллов
534
  • 26, Oct 2024
  • #7

Java 10, 104 100 байт

->a{[0,*a.each_cons(2).map{|x,y|y-x}]*?,=~/((,\d+)*?)\1*$/;$1}

регулярное выражение ->a{i=-2;a.map{|x|(i+=1)>=0?x-a[i]:0}*?,=~/((,\d+)*?)\1*$/;$1} for shortest repeating substring from @Нилкомментарий к @Арноответ на JavaScript (ES6).

Попробуйте онлайн.

Объяснение:

def f(l):d=[y-x for x,y in zip(l,l[1:])];g=len(l);print[d[:k]for k in range(1,g+1)if g/k*d[:k]==d][0] ||answer||

APL+WIN, 39 байт

Запрос на ввод.

d % Get the differences between successive terms, as an array ` % Start do-while loop tt % duplicate the difference array twice @ % push the current loop index value YS % circularly shift the difference array by that amount - % subtract the shifted diffs from the original diffs a % see if the subtraction resulted in any non-zeros % if it did, shifted differences were not equal to original differences, so continue loop }@ % if it didn't, then get loop index :) % get the differences upto the loop index, before they started repeating % implicit loop end

Попробуйте онлайн! С разрешения Диалог Классик

Объяснение:

d`tt@YS-a}@:) ||answer||

Питон 2, 86 85 байт

)

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

Постройте различия как FTF#Xu ; if 5 повторяется с размером единицы YL then t5YL ; иначе рекурсия.

 
Charlespog

Charlespog

Пользователь
Рег
10 May, 2014
Тем
65
Постов
178
Баллов
553
  • 26, Oct 2024
  • #8

Ретина 0.8.2, 42 байта

d

Попробуйте онлайн! Ссылка включает тестовые примеры. Вывод включает ведущую запятую. Объяснение:

dt5YLFTF#Xu)

Преобразовать в унарный.

var F= p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1] ;[[1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17] ,[1, 4, 8, 9, 10, 13, 17, 18, 19, 22, 26, 27, 28] ,[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] ,[2, 6, 10, 13, 17, 21, 25, 28, 32, 36, 40, 43, 47] ,[5, 6, 7]] .forEach(x=>console.log(x + ' -> ' + F(x)))

Вычислите прямые разницы, за исключением первого числа, которое остается позади.

p=>/N(.+?)\1+$/.exec(p.map(p=v=>[v-p,p=v][0]))[1]

Сопоставьте повторяющиеся различия.

¥©ηʒDg®ôÙ˜Q}н Full program. ¥ Push the deltas. © Copy them to the register. ηʒ } And filter the prefixes by... D Q ... Is the prefix itself equal to... g®ô ... The deltas, split into chunks of its length... Ù˜ ... Deduplicated and flattened? н Head.

Преобразовать в десятичное число.

 
Sallabas

Sallabas

Пользователь
Рег
15 Jul, 2015
Тем
69
Постов
192
Баллов
567
  • 26, Oct 2024
  • #9

05AB1E, 14 13 байты

¥©ηʒDg®ôÙ˜Q}н

Попробуйте онлайн или проверить все тестовые случаи.

Я знаю, что уже есть два более коротких ответа 05AB1E, опубликованные @Mr.Xcoder, но я хотел попробовать этот альтернативный подход, используя вращение и проверку равенства.
Возможно, удастся сжать его на несколько байтов, не теряя āεI¥ô}ʒË}нн .

-1 байт после подсказки @Эминья удалить регистры global_variable ( ¥.œʒË}нн and 2x - find the successive differences by subtracting }: the list with last element dropped }. from the list with the first element dropped |."{ rotate the list of differences /: 0..length-1 times (the input graded up) [:~. remove duplicating rows 0{"1 take the first element of each row ) и используйте дубликат ( 0{"1[:~./:|."{}.-}: ) and a Triplicate ( function(a,d=diff(a)){while(any((s=d[1:T])-d))T=T+1;s} ) вместо.

Объяснение:

d=diff(scan());while(any((s=d[1:T])-d))T=T+1;s ||answer||

Хаскель, 107 байт

äa @eUîX}a@¯XÄ

x — входной массив.

 
Grigoriy71

Grigoriy71

Пользователь
Рег
12 Aug, 2007
Тем
67
Постов
205
Баллов
560
  • 26, Oct 2024
  • #10

Стакс, 8 6 байты

:Implicit input of array U äa :Consecutive absolute differences \n :Reassign to U @ }aÄ :Return the first positive integer X that returns true UéX : Rotate U right X times e : Check equality with U ¯ :Slice U to that element

Запустите и отладьте его

Вот распакованная версия с аннотациями, показывающая, как это работает.

äa ¯@eUéX}aÄ

Запустите это

 
D_Argh

D_Argh

Пользователь
Рег
27 Sep, 2005
Тем
86
Постов
217
Баллов
687
  • 26, Oct 2024
  • #11

Перл 6, 57 байт

<J.+Qf.<IJT J.+Q Call the sequence of differences in the input J. f Find the first positive integer T... .<IJT ... where rotating J by T doesn't change it. <J Take that many elements of J.

Проверьте это

Вывод разделяется пробелами ( <J.+Qf.<IJT )

Расширено:

Example input: [6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] s₂ᶠ Find all substrings of length 2: [[6,11],[11,13],…,[34,39],[39,41]] -ᵐ Map subtraction: [-5,-2,-5,-2,-5,-2,-5,-2,-5,-2] ṅᵐ Map negate: [5,2,5,2,5,2,5,2,5,2] ~j₍ Anti-juxtapose the list of differences; the shortest repeated list is found first, with the biggest number of repetitions: [5,[5,2]] t Tail: [5,2] ||answer||

05AB1E, 9 байт

s₂ᶠ-ᵐṅᵐ~j₍t

Объяснение:

*?

Альтернативный 9-байтовый:

match(/N((,\d+)*?)\1*$/)

Тот же алгоритм, но вместо сравнения со списком дельт (который необходимо сохранить/восстановить) используется ,\d+ (undelta) then compares to the (implicit) input.

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

 
Bardachello

Bardachello

Пользователь
Рег
25 Nov, 2019
Тем
85
Постов
203
Баллов
668
  • 26, Oct 2024
  • #12

Перл 5 "NaN,5,2,5,2,5,2,5,2,5,2" , 55 bytes

[6, 11, 13, 18, 20, 25, 27, 32, 34, 39, 41] [ NaN, 5, 2, 5, 2, 5, 2, 5, 2, 5, 2 ]

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

Числа вводятся в виде списка, разделенного пробелами. Вывод имеет тот же формат.

 
Helpservisedl

Helpservisedl

Пользователь
Рег
28 Mar, 2020
Тем
73
Постов
200
Баллов
575
  • 26, Oct 2024
  • #15

К4, 30 байт

Решение:

a=>(a.map(p=x=>-(p-(p=x)))+'').match(/N((,\d+)*?)\1*$/)[1]

Примеры:

IsJEƇḢḢ Main link. Argument: A (array) I Increment; compute D, the array of A's forward differences. J Indices; yield [1, ..., len(A)]. s Split D into chunks of length k, for each k in [1, ..., len(A)]. EƇ Comb equal; keep only partitions of identical chunks. Ḣ Head; extract the first matching parititon. Ḣ Head; extract the first chunk.

Объяснение:

Кажется, это слишком много для того, что мы пытаемся решить. Получите дельты входных данных, а затем постройте последовательность и определите самую короткую, соответствующую ей.

IsJEƇḢḢ
 
JaK1L

JaK1L

Пользователь
Рег
03 Mar, 2014
Тем
67
Постов
216
Баллов
561
Похожие темы Дата
Why Rust? Trustworthy, Concurrent Systems Programming
OzCode for VisualStudio - All Here
Codegolf - Измените Гравитацию Текста, Как В Головоломке 2048 Года
Codegolf - Как Меня Зовут?
Codegolf — Рисование Диагональных Линий Текста
Codegolf — Кратчайшее Непревзойденное Регулярное Выражение
Codegolf — Кратчайший Способ Удалить Первый И Последний Элемент Списка И Распечатать Оба
Codegolf - Цитируя Большого Брата
Codegolf - Следующий Тур Рыцаря
Codegolf - Счетчик Лет Здесь
Похожие темы
Why Rust? Trustworthy, Concurrent Systems Programming
OzCode for VisualStudio - All Here
Codegolf - Измените Гравитацию Текста, Как В Головоломке 2048 Года
Codegolf - Как Меня Зовут?
Codegolf — Рисование Диагональных Линий Текста
Codegolf — Кратчайшее Непревзойденное Регулярное Выражение
Codegolf — Кратчайший Способ Удалить Первый И Последний Элемент Списка И Распечатать Оба
Codegolf - Цитируя Большого Брата
Codegolf - Следующий Тур Рыцаря
Codegolf - Счетчик Лет Здесь
I AM

I AM


Лучший автор
Тем
403,760
Комментарии
400,028
Опыт
2,418,908

Интересно