23
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – DLosc Nov 22 '17 at 6:23
  • \$\begingroup\$ Would've been interesting to have the input in the form 2 5 ... 17 \$\endgroup\$ – schnaader Nov 22 '17 at 8:38

19 Answers 19

9
\$\begingroup\$

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!

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

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can save 3 bytes by replacing b if b%c else c with [c,b][b%c>0]. \$\endgroup\$ – Chas Brown Nov 22 '17 at 8:38
  • \$\begingroup\$ @ChasBrown Thanks, though I soon came up with a better approach. \$\endgroup\$ – Colera Su Nov 22 '17 at 9:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Chas Brown Nov 22 '17 at 9:56
  • 1
    \$\begingroup\$ Also, replace a[-1]-a[-2] with a[2]-a[1] - the logic is the same, and you get another 2 bytes. \$\endgroup\$ – Chas Brown Nov 22 '17 at 10:11
  • 1
    \$\begingroup\$ 60 bytes \$\endgroup\$ – ovs Nov 22 '17 at 15:15
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Steven H. Nov 23 '17 at 10:11
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yay! Beats the 05AB1E answer by 1 byte! \$\endgroup\$ – user202729 Nov 22 '17 at 8:56
  • \$\begingroup\$ Using gcd instead of min made us tie. Too bad I get a gcd with sign, otherwise I'd be at 7 ;) \$\endgroup\$ – Emigna Nov 22 '17 at 10:26
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ a-=d=e*e>d*d?d:e should work and save 2 bytes. \$\endgroup\$ – Arnauld Nov 23 '17 at 9:57
  • \$\begingroup\$ @Arnauld it works indeed thanks \$\endgroup\$ – edc65 Nov 25 '17 at 11:45
2
\$\begingroup\$

Wolfram Language (Mathematica), 50 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – numbermaniac Nov 23 '17 at 10:47
  • \$\begingroup\$ @numbermaniac I don't think so, since there isn't a builtin that fetches the last input... \$\endgroup\$ – JungHwan Min Nov 23 '17 at 19:09
  • \$\begingroup\$ Ahh...true. Forgot about that. \$\endgroup\$ – numbermaniac Nov 23 '17 at 23:27
  • \$\begingroup\$ You can use {##} and Last@{##} but the best I could get with that was 51 bytes. \$\endgroup\$ – numbermaniac Nov 23 '17 at 23:40
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can save a byte by removing h, leaving you with a,*,b,c. Try it online! \$\endgroup\$ – Justin Mariner Nov 22 '17 at 10:47
1
\$\begingroup\$

Haskell, 73 69 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I found a 63 byte solution but it's pretty different from yours. Should I make a separate post? \$\endgroup\$ – user1472751 Nov 22 '17 at 16:13
  • \$\begingroup\$ @user1472751 I'm not Laikoni, but this site was intended for competition, as well as collaboration. So I would post it. \$\endgroup\$ – H.PWiz Nov 22 '17 at 16:50
  • \$\begingroup\$ @user1472751 Nice approach! Please go ahead and post it as your own answer. \$\endgroup\$ – Laikoni Nov 22 '17 at 18:11
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @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? \$\endgroup\$ – Mr. Xcoder Nov 22 '17 at 17:01
  • \$\begingroup\$ @HP.Wiz Thanks a loooot! \$\endgroup\$ – Mr. Xcoder Nov 22 '17 at 17:03
  • \$\begingroup\$ Also, can F⌋ be replaced by ? \$\endgroup\$ – H.PWiz Nov 22 '17 at 17:07
  • \$\begingroup\$ @H.PWiz @_@ Why does that even work? \$\endgroup\$ – Mr. Xcoder Nov 22 '17 at 17:10
  • \$\begingroup\$ The smallest (absolute) difference will be the original difference. The only reason for gcd was to deal with negative deltas \$\endgroup\$ – H.PWiz Nov 22 '17 at 17:12
1
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 77 bytes \$\endgroup\$ – ovs Nov 22 '17 at 15:21
0
\$\begingroup\$

Jelly, 8 bytes

ṂrṀmILÞṪ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

dc, 64 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.