Biorąc pod uwagę skończoną sekwencję arytmetyczną dodatnich liczb całkowitych z niektórymi terminami usuniętymi ze środka, zrekonstruuj całą sekwencję.

Zadanie

Rozważmy ciąg arytmetyczny: listę dodatnich liczb całkowitych, w których różnica między dowolnymi dwoma kolejnymi elementami jest taka sama.

2 5 8 11 14 17

Załóżmy teraz, że z sekwencji usunięto jedną lub więcej liczb całkowitych, z zastrzeżeniem następujących ograniczeń:

• Usunięte liczby całkowite będą kolejnymi warunkami sekwencji.
• Pierwsza i ostatnia liczba całkowita w sekwencji nie zostaną usunięte.
• W sekwencji pozostaną co najmniej trzy liczby całkowite.

W powyższej kolejności możliwe usunięcia obejmują:

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

Twoje zadanie: Biorąc pod uwagę jedną z tych częściowych sekwencji, zrekonstruuj oryginalną pełną sekwencję.

Detale

Możesz założyć, że dane wejściowe są prawidłowe (ma rozwiązanie) i brakuje co najmniej jednego terminu. Wszystkie liczby w sekwencji będą dodatnimi (> 0) liczbami całkowitymi. Sekwencja może mieć dodatnią lub ujemną różnicę między warunkami (tzn. Może rosnąć lub maleć). To nie będzie stała sekwencja (np 5 5 5.).

Twoje rozwiązanie może być pełnym programem lub funkcją . Każda z domyślnych metod wejścia i wyjścia jest akceptowalna.

Dane wejściowe i wyjściowe mogą być ciągiem (z dowolnym rozsądnym ogranicznikiem), listą ciągów lub listą liczb. Możesz reprezentować liczby w dowolnej bazie dogodnej dla twojego języka.

W zgłoszeniu należy podać wszelkie nietypowe metody / formaty We / Wy, aby inni mogli łatwiej przetestować kod.

Przypadki testowe

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

To jest golf golfowy ; najkrótsza odpowiedź w każdym języku wygrywa.

Haskell , 63 bajty

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

Wypróbuj online!

Zasadniczo działa, próbując zbudować wynik z przodu, a jeśli to się nie powiedzie, z tyłu. Wykorzystuje to fakt, że pierwszy i ostatni element wejściowy zawsze będzie poprawny, fakt, że usunięte elementy muszą być następujące po sobie, oraz fakt, że zawsze będą zawierały co najmniej trzy elementy wejściowe. Wszystko, co muszę zrobić, to założyć, że członkowie przedostatni lub przedostatni są dokładni i sprawdzić, czy to działa. Na szczęście Haskell ma naprawdę piękną składnię do tworzenia serii arytmetycznych.

EDYCJA: dzięki @xnor za wskazanie błędu i dostarczenie rozwiązania!

05AB1E , 9 8 bajtów

Ÿs¥¿Äô€н

Wypróbuj online!

Wyjaśnienie

• Skonstruuj zakres [pierwszy, ..., ostatni] z różnicą +/- 1
• Oblicz delty danych wejściowych
• Uzyskaj wartość bezwzględną gcd delty
• Podziel pełny zakres na kawałki tej wielkości
• Zdobądź pierwszy element każdego kawałka

Zapisano 1 bajt gcd of deltaszamiast min delta, zainspirowany przez użytkownika202729

Brachylog v2, 9 bajtów

⊆.s₂ᵇ-ᵐ=∧

Wypróbuj online!

To jest przesłanie funkcji. Interpretator Brachylog może być tak oceniany, jakby był pełnym programem, podając go Zjako argument wiersza poleceń; w takim przypadku dane wejściowe są określone w formacie np., [1, 2, 4]a dane wyjściowe są zwracane w podobnym formacie, np Z = [1, 2, 3, 4]. (Oczywiście w przypadku przesyłania funkcji dane wejściowe i wyjściowe nie są w żadnym formacie; są to tylko listy.)

To faktycznie rozwiązuje trudniejszy problem niż ten, o który poprosił OP: opracowuje najkrótszą arytmetyczną sekwencję liczb całkowitych zawierających określone wartości w określonej kolejności, niezależnie od tego, czy usunięcia są kolejne, czy nie. Ponieważ używa brutalnej siły, może być bardzo powolny, jeśli wiele wartości zostanie usuniętych.

Wyjaśnienie

Program składa się z trzech głównych części.

⊆znajduje nadsekwencję danych wejściowych (tj. sekwencję, która ma dane wejściowe jako podsekwencję). Gdy istnieje więcej niż jedno możliwe wyjście z programu Brachylog, wybrane wyjście jest pierwszym wyjściem w kolejności rozstrzygania, a kolejność rozstrzygania jest określana przez pierwsze polecenie w programie, które ma o nim opinię; w tym przypadku ⊆określa kolejność, która faworyzuje krótkie wyniki nad długimi. Otrzymane przez nas dane wyjściowe będą najkrótszą kolejnością danych wejściowych, która jest zgodna z ograniczeniami w pozostałej części programu.

.… ∧Służy do wyprowadzenia wartości, którą widzi jako dane wejściowe (tj. W tym przypadku nadsekwencję), ale także do zapewnienia, że ​​określony warunek ją zachowuje. Innymi słowy, wyprowadzamy najkrótszą nadsekwencję spełniającą określony warunek (i ignorujemy wszelkie wyniki pośrednie zastosowane w celu sprawdzenia, czy spełnia on warunek).

Wreszcie mamy s₂ᵇ-ᵐ =, tj. „Wszystkie delty sekwencji są równe”, warunek, który stosujemy do wyniku. (Zwracana z tego wartość to lista delt, a nie sama supersekwencja, dlatego potrzebujemy .…, ∧aby upewnić się, że właściwa rzecz jest wyprowadzana).

Brachylog jest tutaj powstrzymywany, ponieważ nie ma żadnych wbudowanych programów, które mogłyby obsługiwać obliczenia delt, stosowania operacji na nakładających się parach z listy lub tym podobnych. Zamiast tego musimy wyraźnie powiedzieć, co mamy na myśli: s₂ᵇznajduje wszystkie ( ᵇ) podciągi ( s) o długości 2 ( ₂) (użycie ᵇjest wymagane do utrzymania połączenia między niewiadomymi w podciągach i nadsekwencjach; częściej używane ᶠto zerwie połączyć). Następnie -ᵐodejmuje każdą z tych par, aby utworzyć deltę. To denerwujące, że trzeba napisać pięć bajtów s₂ᵇ-ᵐdla czegoś, co ma wbudowane większość współczesnych języków gry w golfa, ale tak właśnie wygląda czasem codegolf.

Python 2, 104 97 89 83 71 67 60 bajtów

Dzięki Chas Brown za oszczędność 4 bajtów.
Dzięki ovs za oszczędność 7 bajtów.

Wprowadź listę według argumentów.

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

Wypróbuj online!

Wyjaśnienie:

Ponieważ usuwane są kolejne, wystarczy sprawdzić różnice między dwiema parami kolejnych elementów.

Pyth , 11 bajtów

%hS.+SQ}hQe

Wypróbuj tutaj!

Dzięki Stevenowi H. za uratowanie bajtu!

Pyth , 12 bajtów

%.aiF.+Q}hQe

Wypróbuj tutaj!

Jak to działa

% .aiF. + Q} hQe ~ Pełny program.

     . + Q ~ Uzyskaj delty.
   iF ~ Zmniejszenie przez GCD.
 .a ~ Wartość bezwzględna.
% ~ Modułowy. Zdobądź każdy n-ty element ...
        } ~ Uwzględniający zakres liczbowy między ...
         hQ ~ Pierwszy element i ...
           e ~ Ostatni element.

Galaretka , 8 bajtów

ṂrṀmIg/$

Wypróbuj online!

Uwagi:

• Działa tylko na niektórych starych wersjach Jelly. ( na przykład to zatwierdzenie ) (gdzie guse fractions.gcd, którego znak wyniku jest taki sam jak znak wejściowy, zamiast math.gcd, który zawsze zwraca wartość dodatnią).

• Powyższy link TIO to link TIO Pythona 3, kod Pythona składa się z kodu źródłowego Jelly z zatwierdzenia, o którym wspomniałem powyżej, z wyjątkiem wszystkiego (3 plików) spakowanych w tym samym pliku (do uruchomienia TIO) i dictionary.pyzostał zredukowany do tylko niektóre linie. Niemniej jednak dictionary.pynie ma to związku z tą odpowiedzią, ponieważ nie używa skompresowanego łańcucha. ( “...»konstrukcja)

Wyjaśnienie:

Po pierwsze, ponieważ ciągły segment jest usuwany i pozostają co najmniej 3 elementy, na starej liście pozostają dwie kolejne liczby, a wszystkie delty będą wielokrotnościami kroku. Dlatego lista gcdróżnic ( Iprzyrostów) będzie wartością bezwzględną kroku.

Na szczęście gcdjest podpisany (patrz uwaga powyżej)

Tak więc program:

ṂrṀ

Rosnący zakres liczb całkowitych od Ṃminimalnej do Ṁmaksymalnej.

m

Modułowy, wybierz co n-ty element.

Ig/$

$Łańcuch Monadic ( ) łączy I(przyrosty, różnice) i g/(redukuje gcdelementy listy). Jeśli przyrosty są dodatnie, to gcdbędzie dodatnie, a lista powracająca będzie od lewej do prawej (rosnąca) i odwrotnie.

MATL , 13 bajtów

1)0GdYkG0)3$:

Wypróbuj online!

Wyjaśnienie:

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

Edytuj 2 bajty zapisane dzięki Arnauld

Łatwo, ponieważ wystarczy sprawdzić różnice między dwoma pierwszymi i dwoma ostatnimi. Ale wciąż niewiarygodnie długo.

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

Mniej golfa

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

Test

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 bajtów

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

Wypróbuj online!

Rubinowy , 65 62 55 54 bajtów

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

Wypróbuj online!

-1 bajt dzięki Justin Mariner

Haskell , 73 69 bajtów

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

Wypróbuj online!

J , 49, 47 46 bajtów

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

Zainspirowany rozwiązaniem Emigny.

Jak to działa:

 (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

Wypróbuj online!

Łuska , 9 bajtów

m←C▼Ẋ≠⁰…⁰

Wypróbuj online!

Wielkie dzięki H.PWiz do zmniejszenia o połowę liczby bajtów, wskazując, że stosowanie …na liście rangifies go! ...

C # (.NET Core) , 167 + 13 = 180 145 + 13 = 158 bajtów

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

Wypróbuj online!

+13 dla using System;

Co zaskakujące, wyzwanie to miało więcej niuansów, niż początkowo oczekiwałem.

Podziękowanie

-22 bajty zapisane z powodu pewnych zgrabnych uproszczeń @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 bajtów

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

Wypróbuj online!

Python 2 , 78 bajtów

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

Wypróbuj online!

Galaretka , 8 bajtów

ṂrṀmILÞṪ

Wypróbuj online!

dc , 64 bajty

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

Wypróbuj online!

Japt , 12 bajtów

ÌõUg Uäa ñ g

Spróbuj

Wyjaśnienie

Wygeneruj tablicę liczb całkowitych ( õ) z ostatniego elementu tablicy wejściowej ( Ì) do pierwszej ( Ug). Oblicz krok między elementami, pobierając wszystkie dwie pary elementów z danych wejściowych i zmniejszając je o różnicę bezwzględną ( Uäa), a następnie sortując ( ñ) tę tablicę i biorąc pierwszy element ( g).