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

Задание

Рассмотрим арифметическую последовательность: список натуральных чисел, в которых разница между любыми двумя последовательными элементами одинакова.

2 5 8 11 14 17

Теперь предположим, что одно или несколько целых чисел удалены из последовательности при условии соблюдения следующих ограничений:

• Удаленные целые числа будут последовательными членами последовательности.
• Первое и последнее целые числа в последовательности не будут удалены.
• По крайней мере три целых числа останутся в последовательности.

Для вышеуказанной последовательности возможные удаления включают в себя:

2 5 8 14 17  (removed 11)
2 5 17       (removed 8 11 14)
2 14 17      (removed 5 8 11)

Ваша задача: учитывая одну из этих частичных последовательностей, восстановить исходную полную последовательность.

Детали

Вы можете предположить, что ввод действителен (имеет решение) и отсутствует хотя бы один термин. Все числа в последовательности будут положительными (> 0) целыми числами. Последовательность может иметь положительную или отрицательную разницу между терминами (т.е. она может увеличиваться или уменьшаться). Это не будет постоянная последовательность (например 5 5 5).

Ваше решение может быть полной программой или функцией . Любой из методов ввода и вывода по умолчанию является приемлемым.

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

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

Контрольные примеры

In: 2 5 8 14 17
Out: 2 5 8 11 14 17
In: 2 5 17
Out: 2 5 8 11 14 17
In: 2 14 17
Out: 2 5 8 11 14 17
In: 21 9 6 3
Out: 21 18 15 12 9 6 3
In: 10 9 5
Out: 10 9 8 7 6 5
In: 1 10 91 100
Out: 1 10 19 28 37 46 55 64 73 82 91 100

Это код-гольф ; самый короткий ответ на каждом языке выигрывает.

Haskell , 63 байта

f(a:b:c)|s<-[a,b..last c],all(`elem`s)c=s
f a=r$f$r a
r=reverse

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

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

РЕДАКТИРОВАТЬ: спасибо @xnor за указание на ошибку и предоставление решения!

05AB1E , 9 8 байт

Ÿs¥¿Äô€н

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

объяснение

• Построить диапазон [первый, ..., последний] с разницей +/- 1
• Рассчитать дельты ввода
• Получить абсолютное значение gcd дельт
• Разделите весь диапазон на куски такого размера
• Получить первый элемент каждого куска

Сохранено 1 байт с использованием gcd of deltasвместо min delta, вдохновленный user202729

Brachylog v2, 9 байт

⊆.s₂ᵇ-ᵐ=∧

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

Это функция представления. Интерпретатор Brachylog может быть сделан для оценки функции, как если бы она была полной программой, передавая ее Zв качестве аргумента командной строки; в этом случае ввод указывается в формате, например, [1, 2, 4]и вывод возвращается в аналогичном формате, например Z = [1, 2, 3, 4]. (Конечно, для отправки функции ввод и вывод не в любом формате; это просто списки.)

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

объяснение

Программа состоит из трех основных частей.

⊆находит суперпоследовательность ввода (то есть последовательность, которая имеет вход в качестве подпоследовательности). Когда существует более одного возможного вывода из программы Brachylog, выбранный вывод является первым выводом в порядке разрыва связей, и порядок разрыва связей определяется первой командой в программе, которая имеет мнение по этому поводу; в этом случае ⊆указывает порядок, который предпочитает короткие выходы по сравнению с длинными. Таким образом, вывод, который мы получим, будет самой короткой последовательностью ввода, которая подчиняется ограничениям в остальной части программы.

.… ∧Используется для вывода значения, которое он видит в качестве входных данных (т. Е. В данном случае является суперпоследовательность), но также утверждает, что для него выполняется определенное условие Другими словами, мы выводим самую короткую суперпоследовательность, которая подчиняется определенному условию (и игнорируем любые промежуточные результаты, используемые для проверки, соответствует ли оно условию).

Наконец, мы имеем s₂ᵇ-ᵐ =, то есть «все дельты последовательности равны», условие, которое мы применяем к выводу. (Возвращаемое значение из этого является списком дельт, а не самой суперпоследовательностью, поэтому нам нужно .… ∧чтобы гарантировать, что правильная вещь выводится.)

Brachylog сдерживается тем, что не имеет встроенных функций, которые могут обрабатывать вычисления дельт, применяет операцию к перекрывающимся парам из списка и т.п. Вместо этого мы должны сказать, что мы имеем в виду в явном виде: s₂ᵇнаходит все ( ᵇ) подстроки ( s) длины 2 ( ₂) (использование ᵇнеобходимо для сохранения связи между неизвестными в подстроках и в суперпоследовательности; чем чаще используется, тем ᶠбольше ссылка). Затем -ᵐвычитает каждую из этих пар, чтобы получить дельту. Раздражает необходимость записывать пять байтов s₂ᵇ-ᵐдля чего-то, для чего есть встроенные возможности большинства современных языков игры в гольф, но я думаю, именно так иногда и поступает Codegolf.

Python 2, 104 97 89 83 71 67 60 байт

Спасибо Часу Брауну за сохранение 4 байта.
Спасибо ovs за сохранение 7 байтов.

Введите список по аргументам.

lambda a,b,*c:range(a,c[-1],min(b-a,c[0]-b,key=abs))+[c[-1]]

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

Объяснение:

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

Pyth , 11 байт

%hS.+SQ}hQe

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

Спасибо Стивену Х. за сохранение байта!

Pyth , 12 байт

%.aiF.+Q}hQe

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

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

% .aiF. + Q} hQe ~ Полная программа.

     . + Q ~ Получить дельты.
   iF ~ Уменьшить с помощью GCD.
 .a ~ Абсолютное значение.
% ~ Модульный. Получить каждый n-й элемент ...
        } ~ Включающий числовой диапазон между ...
         hQ ~ Первый элемент и ...
           е ~ Последний элемент.

Желе , 8 байт

ṂrṀmIg/$

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

Заметки:

• Работайте только на какой-то старой версии Jelly. ( это коммит например) (где guse fractions.gcd, у которого знак результата совпадает с входным знаком, вместо math.gcdкоторого всегда возвращают положительное значение).

• Ссылка TIO выше - это ссылка Python 3 TIO, код Python состоит из исходного кода Jelly из коммита, о котором я упоминал выше, за исключением всего (3 файла), упакованного в один и тот же файл (для запуска TIO) и dictionary.pyуменьшенного до только несколько строк. Тем dictionary.pyне менее, не имеет отношения к этому ответу, так как он не использует сжатую строку. ( “...»конструкция)

Объяснение:

Во-первых, поскольку непрерывный сегмент удаляется и остается по крайней мере 3 элемента, в старом списке остаются два последовательных числа, и все дельты будут кратны шагу. Поэтому список gcdразностей ( Iприращений) будет абсолютным значением шага.

К счастью, gcdподписано (см. Примечание выше)

Так что программа делает:

ṂrṀ

Увеличение целочисленного диапазона от Ṃминимума до Ṁаксиума.

m

Модульный, выбрать каждый n-й элемент.

Ig/$

$Цепочка Monadic ( ) объединяет I(приращения, различия) и g/(сокращает gcdэлементы списка). Если приращения положительны, то значение gcdбудет положительным, а возвращаемый список будет слева направо (с увеличением) и наоборот.

MATL , 13 байт

1)0GdYkG0)3$:

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

Объяснение:

Consider the example input [2 14 17]:
           # implicit input, STACK: [[2 14 17]]
1)         # push 1, index, STACK: [2]
0G         # push 0, duplicate input, STACK: [2, 0, [2 14 17]]
d          # take differences, STACK: [2, 0, [12, 3]]
Yk         # get value in [12, 3] nearest to 0, STACK: [2, 3]
G0)        # get last element in input, STACK: [2, 3, 17]
3$:        # 3-input :, computes 2:3:17, the range from 2 to 17 by 3
           # STACK: [[2 5 8 11 14 17]], implicit output.

JavaScript (ES6), 92 90

Отредактируйте 2 байта, сохраненных благодаря Арно

Легко, так как достаточно проверить разницу между первыми двумя и двумя последними. Но все еще невероятно долго.

s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

Меньше гольфа

s=>{
  a =s[0]
  b =s[1]
  z = s.pop()
  y = s.pop()
  d = b-a
  e = z-y
  d = e*e>d*d?d:e  
  n = (z-a)/d+1
  return [...Array(n)].map((_,i) => a + i*d)
}

Тест

var F=
s=>(e=(z=s.pop(a=s[0]))-s.pop(d=s[1]-a),[...Array((z-(a-=d=e*e>d*d?d:e))/d)].map(_=>a+=d))

var test=`In: 2 5 8 14 17 Out: 2 5 8 11 14 17
In: 2 5 17 Out: 2 5 8 11 14 17
In: 2 14 17 Out: 2 5 8 11 14 17
In: 21 9 6 3 Out: 21 18 15 12 9 6 3
In: 10 9 5 Out: 10 9 8 7 6 5
In: 1 10 91 100 Out: 1 10 19 28 37 46 55 64 73 82 91 100`.split`\n`
.map(r=>r.split`Out`.map(x=>x.match(/\d+/g)))

test.forEach(([i,k])=>{
  var o=F(i.slice(0))
  var ok = o+''==k
  console.log(ok?'OK':'KO',i+' => '+o)
})

Wolfram Language (Mathematica) , 50 байтов

Range[#&@@#,#[[-1]],#&@@Differences@#~SortBy~Abs]&

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

Рубин , 65 62 55 54 байта

->l{a,*,b,c=l;[*a.step(c,[l[1]-a,c-b].min_by(&:abs))]}

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

-1 байт благодаря Джастину Маринеру

Haskell , 73 69 байтов

f(h:t)=do(#)<-[(-),(+)];[h,h#minimum(abs<$>zipWith(-)t(h:t))..last t]

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

J , 49, 47 46 байтов

(0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{.

Вдохновленный решением Эмигны.

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

 (0-[:<./2|@-/\]){.@[&]\({.<.{:)+[:i.{:(+*)@-{. - fork of 3 verbs

                        ({.<.{:)+[:i.{:(+*)@-{. - generates a list in the entire range of values
                                     {:     -{. - last minus first element  
                                       (+*)@    - adds the signum of the difference
                                 [:i.           - makes a list 
                       ({.<.{:)                 - the smallest of first and last elements                                     
                               +                - adds the offset to the list (translates all elements according to the first one)

 (0-[:<./2|@-/\])                               - finds the step
         2|@-/\]                                - the absolute differences between all consecutive elements
    [:<./                                       - the smallest one
  0-                                            - negate (for splitting)

                 {.@[&]\                        - splits the list from the right verb into left verb's result sublists and takes their first elements

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

Шелуха , 9 байт

m←C▼Ẋ≠⁰…⁰

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

Большое спасибо H.PWiz за половину количества байтов, указав, что применение …к списку повышает его! ...

C # (.NET Core) , 167 + 13 = 180 145 + 13 = 158 байт

a=>{int x=a[1]-a[0],y=a[2]-a[1],d=x*x<y*y?x:y,s=Math.Abs((a[a.Length-1]-a[0])/d),i=0,j=a[0];var r=new int[s+1];for(;i<=s;j+=d)r[i++]=j;return r;}

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

+13 за using System;

Удивительно, но этот вызов имел больше нюансов, чем я изначально ожидал.

Подтверждения

-22 байта сохранено из-за некоторых простых упрощений из @DLosc.

DeGolfed

a=>{
    int x = a[1]-a[0],        // difference between first and second numbers
        y = a[2]-a[1],        // difference between second to last and last numbers
        d = x*x < y*y? x : y, // smallest absolute value difference
        s = Math.Abs((a[a.Length-1] - a[0]) / d), // number of steps in the reconstructed sequence (not the number of elements)
        i = 0,                // step position
        j = a[0];             // next number in reconstructed sequence

    var r = new int[s+1];

    // reconstruct the sequence
    for(; i <= s; j+=d)
        r[i++]=j;

    return r;
}

Python 2 , 147 байт

from fractions import*
a=input()
b=[j-i for i,j in zip(a[:-1],a[1:])]
l=min(gcd(i,j)for i in b for j in b)
print list(range(a[0],a[-1]+l/abs(l),l))

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

Python 2 , 78 байт

lambda a:range(a[0],a[-1],[min,max][a[0]>a[1]](a[1]-a[0],a[-1]-a[-2]))+[a[-1]]

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

Желе , 8 байт

ṂrṀmILÞṪ

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

постоянный ток , 64 байта

?dsx[ksE0_1]sg[scdlcr-d2^vdK>gK0=g+sqz1<l]dslx[pdlE+dlx!=Z]dsZxp

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

Japt , 12 байт

ÌõUg Uäa ñ g

Попытайся

объяснение

Создайте массив целых чисел ( õ) от последнего элемента входного массива ( Ì) до первого ( Ug). Рассчитайте шаг между элементами, получив все две пары элементов из входных данных и уменьшив их на абсолютную разницу ( Uäa), затем отсортировав ( ñ) этот массив и получив первый элемент ( g).