# Reconstruct an arithmetic sequence

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

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 ; the shortest answer in each language wins.

• Related Commented Nov 22, 2017 at 6:23
• Would've been interesting to have the input in the form 2 5 ... 17 Commented Nov 22, 2017 at 8:38
• Related Commented Jun 17, 2022 at 8:10

f(a:b:c)|s<-[a,b..last c],all(elems)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!

• Though this is pretty, it seems it doesn't always work: [1,3,4,5] gives [1,3,5].
– xnor
Commented Nov 23, 2017 at 6:12
• And I think all(elems)c should fix it with the same byte count.
– xnor
Commented Nov 23, 2017 at 16:55

# 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

# 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.

# 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. • Yay! Beats the 05AB1E answer by 1 byte! Commented Nov 22, 2017 at 8:56 • Using gcd instead of min made us tie. Too bad I get a gcd with sign, otherwise I'd be at 7 ;) Commented Nov 22, 2017 at 10:26 # Python 2, 1049789837167 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. • You can save 3 bytes by replacing b if b%c else c with [c,b][b%c>0]. Commented Nov 22, 2017 at 8:38 • @ChasBrown Thanks, though I soon came up with a better approach. Commented Nov 22, 2017 at 9:44 • Nice with the key=abs! It seems that hereabouts, people often omit the f= part unless a recursive function is used; so you could save 2 bytes that way. Commented Nov 22, 2017 at 9:56 • Also, replace a[-1]-a[-2] with a[2]-a[1] - the logic is the same, and you get another 2 bytes. Commented Nov 22, 2017 at 10:11 • 60 bytes – ovs Commented Nov 22, 2017 at 15:15 # 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.  • Presort Q so you can sort and take the first element instead of abs(GCD(Q)) as in %hS.+SQ}hQe for 11 bytes. Test suite Commented Nov 23, 2017 at 10:11 # 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.splitOut.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) }) • a-=d=e*e>d*d?d:e should work and save 2 bytes. Commented Nov 23, 2017 at 9:57 • @Arnauld it works indeed thanks Commented Nov 25, 2017 at 11:45 # 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.  # R, 62 bytes function(x)seq(x[1],tail(x,1),min(abs(d<-diff(x)))*sign(d[1]))  Try it online! # Wolfram Language (Mathematica), 50 bytes Range[#&@@#,#[[-1]],#&@@Differences@#~SortBy~Abs]&  Try it online! • Does a "list of numbers" include having the numbers as individual arguments? If so, it looks like you could save a good number of bytes. Commented Nov 23, 2017 at 10:47 • @numbermaniac I don't think so, since there isn't a builtin that fetches the last input... Commented Nov 23, 2017 at 19:09 • Ahh...true. Forgot about that. Commented Nov 23, 2017 at 23:27 • You can use {##} and Last@{##} but the best I could get with that was 51 bytes. Commented Nov 23, 2017 at 23:40 # 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 • You can save a byte by removing h, leaving you with a,*,b,c. Try it online! Commented Nov 22, 2017 at 10:47 # 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; }  # Japt, 12 10 bytes ÌõUÎUäa rm  Try it ÌõUÎUäa rm :Implicit input of array U Ì :Last element UÎ :First element õ :Range [first,last] with step size Uä : Consecutive pairs of U a : Reduced by absolute difference r : Reduce by m : Minimum  # Vyxal, 7 bytes ḣtṡ?¯ġḞ  Try it Online! # Acc!!, 318 bytes Count n while 1 { _+N%8*8^n Count i while 0^(_/8^n) { _*n^n Count i while n-i { _+_/n^n/8^i%2*n^(_%n+1)+_/n^n/8^i%4/2 } ((_/n^2-_/n)+0^((_/n^(_%n)%n-_/n^(_%n-1)%n)/(_/n^2%n-_/n%n))*(_/n^(_%n)-_/n^(_%n-1)-_/n^2+_/n))%n+_/n^(_%n)%n*n+_/n%n*n^2 Count i while (_/n-_/n^2+_%n)%n { Write 49)*(_/n^2%n Write 9 _+_%n*n^2 } } }  Try it online! Takes input as a newline-separated unary array and outputs a tab-separated unary array. ## Explanation # Format of accumulator: # input: # + buffer # parsing: # + buffer*n^n # + arr[0]*n + arr[1]*n^2 + ... # supports upto n - 1 elements # + len(arr) # print: # + curr*n^2 # + end*n # + diff # # NOTE: Each element in 'arr' is stored as one more than its actual value. Count n while 1 { _+N%4*4^n # buffer[n] = getchar()%8 # if buffer[n] == '\0': Count i while 0^(_/4^n) { # Convert accumulator to parsing type _*n^n # Loop to parse into arr Count i while n-i { # _ # + n^(_%n+1) # arr[len(arr)] += 1 # + _/n^n/4^i%4/2 # len(arr) = buffer[i] == '\n' _+n^(_%n+1)+_/n^n/4^i%4/2 } # Convert accumulator to print type # _/n%n*n^2 # curr = arr[0] # + _/n^(_%n)%n*n # end = arr[len(arr) - 1] # + ... # diff = ((arr[len(arr) - 1] - arr[len(arr) - 2]) or (arr[1] - arr[0])) % n # chosen based on which is closer to zero _/n%n*n^2+_/n^(_%n)%n*n+((_/n^2-_/n)+0^((_/n^(_%n)%n-_/n^(_%n-1)%n)/(_/n^2%n-_/n%n))*(_/n^(_%n)-_/n^(_%n-1)-_/n^2+_/n))%n # while curr != end + diff: Count i while (_/n-_/n^2+_%n)%n { Write 49)*(_/n^2%n-1 # Print '1' (curr % n - 1) times Write 9 # Print '\t' _+_%n*n^2 # curr += diff } } }  # Haskell, 73 69 bytes f(h:t)=do(#)<-[(-),(+)];[h,h#minimum(abs<$>zipWith(-)t(h:t))..last t]


Try it online!

• I found a 63 byte solution but it's pretty different from yours. Should I make a separate post? Commented Nov 22, 2017 at 16:13
• @user1472751 I'm not Laikoni, but this site was intended for competition, as well as collaboration. So I would post it. Commented Nov 22, 2017 at 16:50

# 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!

# Jelly, 8 bytes

ṂrṀmILÞṪ


Try it online!

# 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!...

• @HP.Wiz X_X I didn’t know Husk does list ranges like that... Are you sure you don’t want to post it as your own separate answer? Commented Nov 22, 2017 at 17:01
• @HP.Wiz Thanks a loooot! Commented Nov 22, 2017 at 17:03
• Also, can F⌋ be replaced by ▼? Commented Nov 22, 2017 at 17:07
• @H.PWiz @_@ Why does that even work? Commented Nov 22, 2017 at 17:10
• The smallest (absolute) difference will be the original difference. The only reason for gcd was to deal with negative deltas Commented Nov 22, 2017 at 17:12

# 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!

# 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!

• 77 bytes
– ovs
Commented Nov 22, 2017 at 15:21

# dc, 64 bytes

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


Try it online!

# Uiua 0.12.0-dev.1, 19 bytes

\+⊂⊢:▽÷,⟜⍜⌵/↧≡/-◫2.


Try it out!