Reconstruct an arithmetic sequence

Question

Given a finite arithmetic sequence of positive integers with some terms removed from the middle, reconstruct the whole sequence.

The task

Consider an arithmetic sequence: a list of positive integers in which the difference between any two successive elements is the same.

2 5 8 11 14 17

Now suppose one or more integers is removed from the sequence, subject to the following constraints:

• The integers removed will be consecutive terms of the sequence.
• The first and last integers in the sequence will not be removed.
• At least three integers will remain in the sequence.

For the above sequence, possible removals include:

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

Your task: Given one of these partial sequences, reconstruct the original full sequence.

Details

You may assume input is valid (has a solution) and is missing at least one term. All numbers in the sequence will be positive (> 0) integers. The sequence may have a positive or negative difference between terms (i.e. it may be increasing or decreasing). It will not be a constant sequence (e.g. 5 5 5).

Your solution may be a full program or a function. Any of the default input and output methods are acceptable.

Your input and output may be a string (with any reasonable delimiter), a list of strings, or a list of numbers. You may represent the numbers in whatever base is convenient for your language.

Please mention any unusual I/O methods/formats in your submission, so others will be able to test your code more easily.

Test cases

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

---

This is code-golf; the shortest answer in each language wins.

Answer 1

Haskell, 63 bytes

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

Try it online!

Basically works by trying to build the result from the front and, if that fails, from the back. This uses the fact that the first and last members of the input will always be correct, the fact that deleted members have to be consecutive, and the fact that there will always be at least three items in the input. All I have to do is assume that the second or second-to-last members are accurate and check if it works. Luckily Haskell has really beautiful syntax for creating arithmetic series.

EDIT: thanks to @xnor for pointing out a bug and providing a solution!

Answer 2

05AB1E, 9 8 bytes

Ÿs¥¿Äô€н

Try it online!

Explanation

• Construct the range [first, ..., last] with a difference of +/-1
• Calculate deltas of the input
• Get the absolute value of the gcd of the deltas
• Split the full range in chunks of that size
• Get the first element of each chunk

Saved 1 byte using gcd of deltas instead of min delta, inspired by user202729

Answer 3

Brachylog v2, 9 bytes

⊆.s₂ᵇ-ᵐ=∧

Try it online!

This is a function submission. The Brachylog interpreter can be made to evaluate a function as though it were a full program by giving it Z as a command line argument; in this case, the input is specified in the format, e.g., [1, 2, 4] and the output is returned in a similar format, e.g. Z = [1, 2, 3, 4]. (Of course, for a function submission, the input and output aren't in any format at all; they're just lists.)

This actually solves a harder problem than the one the OP asked for: it works out the shortest arithmetic sequence of integers containing the specified values in the specified order, regardless of whether the deletions are consecutive or not. Because it uses brute force, it can be very slow if many values are deleted.

Explanation

The program has three main parts.

⊆ finds a supersequence of the input (i.e. a sequence that has the input as a subsequence). When there's more than one possible output from a Brachylog program, the output chosen is the first output in tiebreak order, and the tiebreak order is determined by the first command in the program that has an opinion on it; in this case, ⊆ specifies an order that favours short outputs over long ones. So the output we'll get will be the shortest supersequence of the input that obeys the restrictions in the rest of the program.

. … ∧ is used to output the value it sees as input (i.e. the supersequence in this case), but also assert that a specific condition holds on it. In other words, we're outputting the shortest supersequence that obeys a specific condition (and ignoring any intermediate results used to see if it obeys the condition).

Finally, we have s₂ᵇ-ᵐ =, i.e. "all the deltas of the sequence are equal", the condition we're applying to the output. (The return value from this is a list of deltas, rather than the supersequence itself, which is why we need the . … ∧ to ensure that the right thing is output.)

Brachylog is held back here by not having any builtins that can handle calculation of deltas, applying an operation to overlapping pairs from a list, or the like. Instead, we have to say what we mean explicitly: s₂ᵇ finds all (ᵇ) substrings (s) of length 2 (₂) (the use of ᵇ is required to keep a link between unknowns in the substrings and in the supersequence; the more commonly used ᶠ would break this link). Then -ᵐ does a subtraction on each of these pairs to produce a delta. It's annoying to have to write out five bytes s₂ᵇ-ᵐ for something that most modern golfing languages have a builtin for, but that's the way that codegolf goes sometimes, I guess.

Answer 4

Pyth, 11 bytes

%hS.+SQ}hQe

Try it here!

Thanks to Steven H. for saving a byte!

Pyth, 12 bytes

%.aiF.+Q}hQe

Try it here!

How it works

%.aiF.+Q}hQe ~ Full program.

     .+Q     ~ Get the deltas.
   iF        ~ Reduce by GCD.
 .a          ~ Absolute value.
%            ~ Modular. Get every nth element of...
        }    ~ The inclusive numeric range between...
         hQ  ~ The first element, and...
           e ~ The last element.

Answer 5

Python 2, 104 97 89 83 71 67 60 bytes

Thanks to Chas Brown for saving 4 bytes.
Thanks to ovs for saving 7 bytes.

Input the list by arguments.

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

Try it online!

Explanation:

Since the removed are consecutive, it is enough to check the differences between two pairs of consecutive elements.

Answer 6

Jelly, 8 bytes

ṂrṀmIg/$

Try it online!

Notes:

• Only work on some old version of Jelly. (this commit for example) (where g use fractions.gcd, which have the result sign the same as input sign, instead of math.gcd, which always return positive value).

• The TIO link above is Python 3 TIO link, the Python code consists of Jelly source code from the commit I mentioned above, with the exception of everything (3 files) packed into the same file (for TIO to run) and dictionary.py has been reduced to only some lines. Nevertheless dictionary.py is unrelated to this answer, as it does not use compressed string. (the “...» construct)

Explanation:

First, because a continuous segment is deleted and at least 3 elements remains, there are two consecutive numbers in the old list remain, and the deltas will all be multiples of the step. Therefore the gcd of the differences (I, increments) list will be the absolute value of the step.

Fortunately the gcd is signed (see note above)

So the program does:

ṂrṀ

An increasing integer range from the Ṃinimum to the Ṁaximum.

m

Modular, pick every n'th element.

Ig/$

Monadic ($) chain combine I (increments, differences) and g/ (reduce gcd over elements of the list). If the increments are positive then the gcd will be positive and the returning list will be left-to-right (increasing), and vice-versa.

Answer 7

JavaScript (ES6), 92 90

Edit 2 bytes saved thx Arnauld

Easy, as it is enough to check the differences between the first two and the last two. But still unbelievably long.

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

Less golfed

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

Answer 8

MATL, 13 bytes

1)0GdYkG0)3$:

Try it online!

Explanation:

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.

Answer 9

Wolfram Language (Mathematica), 50 bytes

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

Try it online!

Answer 10

Ruby, 65 62 55 54 bytes

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

Try it online!

-1 byte thanks to Justin Mariner

Answer 11

Haskell, 73 69 bytes

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

Try it online!

Answer 12

J, 49, 47 46 bytes

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

Inspired by Emigna's solution.

How it works:

 (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

Try it online!

Answer 13

Husk, 9 bytes

m←C▼Ẋ≠⁰…⁰

Try it online!

Thanks a lot to H.PWiz for halving the byte count, by pointing that applying … on a list rangifies it!...

Answer 14

C# (.NET Core), 167+13=180 145+13=158 bytes

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

Try it online!

+13 for using System;

Surprisingly, this challenge had more nuance that I initially anticipated.

Acknowledgements

-22 bytes saved due to some neat simplifications from @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;
}

Answer 15

Python 2, 147 bytes

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

Try it online!

Answer 16

Python 2, 78 bytes

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

Try it online!

Answer 17

Japt, 12 bytes

ÌõUg Uäa ñ g

Try it

---

Explanation

Generate an array of integers (õ) from the last element of the input array (Ì) to the first (Ug). Calculate the step between elements by getting all two element pairs from the input & reducing them by absolute difference (Uäa) then sorting (ñ) that array and taking the first element (g).

Answer 18

Jelly, 8 bytes

ṂrṀmILÞṪ

Try it online!

Answer 19

dc, 64 bytes

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

Try it online!