# Complete a sequence using its distances

Given $$\A = (a_1,\dots,a_k)\ k\ge2 $/extract_tex] a sequence of positive integers, in which all elements are different. Starting from $$\i=2$$/extract_tex], while $$\a_i\in A:\$$ (until the last element) • If $$\d=|a_i-a_{i-1}|\$$ is not already in $$\A\$$, append $$\d\$$ to $$\A\$$ • Increase $$\i\$$ Output the completed sequence. This is ## Example In: 16 21 11 2 16 21 11 2 5 --^ 16 21 11 2 5 10 --^ 16 21 11 2 5 10 9 --^ 16 21 11 2 5 10 9 3 --^ 16 21 11 2 5 10 9 3 --^ 16 21 11 2 5 10 9 3 1 --^ 16 21 11 2 5 10 9 3 1 6 --^ 16 21 11 2 5 10 9 3 1 6 --^ 16 21 11 2 5 10 9 3 1 6 --^ Out: 16 21 11 2 5 10 9 3 1 6  • You should explain stopping and simply not appending more clearly then. For me it reads to stop doing anything. Jun 5, 2020 at 13:16 • @Noodle 9 The if condition is inside a while loop that continues until the index reaches the last element in \A\. I can't say while \i\le k\ because \A\ will probably get extended with new element, so the condition has to be while \a_i \in A\ Jun 5, 2020 at 13:26 • Yeah, sure I see that now. But questions are always better when they're totally clear. Jun 5, 2020 at 13:50 • I couple of weeks is recommended so all these warts can be sorted out. Jun 5, 2020 at 14:03 • @DomenicoModica Your new wording, "without repetition", can still be interpreted as "without contiguous elements being equal". If you mean "all elements are different", write it like that, or with a similar unambiguous phrase Jun 5, 2020 at 15:21 ## 26 Answers # 05AB1E, 6 5 bytes Δ¥Ä«Ù  Try it online! Δ until the output doesn't change: ¥Ä absolute differences « concatenate to the original input Ù only keep unique values  • You beat me to it. I was about to post an answer.. Only difference is that I had üα instead of ¥Ä. :) Jun 5, 2020 at 13:13 • @KevinCruijssen Apparently this wasn't optimal, since all differences are computed in every iteration, we can just concatenate with the original input. – ovs Jun 6, 2020 at 9:53 • Oh, I wouldn't have thought of that, but you're indeed correct. Nice golf! Jun 6, 2020 at 10:32 # Python 2, 57 bytes l=input() d=0 for i in l:l+={abs(d-i)}-set(l);d=i print l  Try it online! • 48 bytes in Python 3 by mutating the input: Try it online! Feb 26, 2022 at 15:32 # J, 17 16 bytes (~.@,2|@-/$)^:_  Try it online! ### How it works (~.@,2|@-/$$)^:_
(           )^:_   until output does not change
2   /\]       for each neighboring pair
|@-          get the absolute difference
,              append the result to the list
~.@               and remove duplicates


# Ruby, 40 bytes

->a,i=0{a|=[(p(a[i])-a[i+=1]).abs];redo}


Try it online!

Takes an array a as input and adds unique new elements to it using the set append operator |=. Terminates by throwing a rescuable TypeError (which is now allowed) when attempting to subtract beyond the last element of the array. By that point all of the required output has already been printed to STDOUT.

# Ruby, 48 bytes

->a,i=0{a|=[(p(A).-a[i+=1]||0).abs]while A=a[i]}


Try it online!

This version avoids the TypeError at a cost of 8 bytes.

# R, 68 57 bytes

v=scan();while(any(F-(F=v)))v=unique(c(v,abs(diff(v))));v


Try it online!

Edit: -9 bytes thanks to Giuseppe, and -2 more from (F-(F=v)) (had to be tested to see whether that would work...)

Boringly follows the instructions in the question, in the same order...

• 64 bytes keeping your recursive function or 63 bytes with a while loop. I think taking input from scan() while using a while loop would also save bytes. Jun 5, 2020 at 20:27
• Thanks Giuseppe! ...and I even managed to squeeze-out 2 more... Jun 5, 2020 at 20:50

# APL (Dyalog Unicode), 14 bytes SBCS

{⍵,⍵~⍨|2-/⍵}⍣≡


Try it online!

Same method as the J answer; I came up with this on my own :) also ended up being 3 bytes shorter, at least atm.

• f 2 3 4 5 return 2 3 4 5 1 1 1 0 0
– user58988
Jul 9, 2020 at 2:42
• You can fix ^ and shorten the code by replacing ⍵,⍵~⍨ (set difference then concat) with ∪⍵, (concat then unique). Try it online! Jul 9, 2020 at 7:09

# Perl 5 -pl, 58 bytes

$d=abs$a[$;]-$a[++$;],/\b$d\b/||s/$/$d/ while(@a=split)>$ Try it online! Ungolfed: # with -pl the special var$_ is initialized with the input line string
while(
@a = split    # array @a = the numbers currently in the $_ special var and$i++ < @a     # and the $i index (counter) is less than the length of @a # in the golfed version$; is used instead of $i ){$d = abs $a[$i] - $a[$i-1] # $d = non-zero absolute diff btw element$i and $i-1 and !/\b$d\b/              # and $d unseen before? \b is "borders" around digits and s/$/ $d/ # and if so append space and$d to $_ } # with -pl the current$_ and \n is printed


Run:

$echo 16 21 11 2 | perl -pl program_58_bytes.pl 16 21 11 2 5 10 9 3 1 6  • Save two bytes by replacing and with ,. One byte by removing the ! and replacing the && by a ||. And another byte by using split instead of /\d+/g. Try it online! Jun 6, 2020 at 0:50 • Thanks @Abigail ! This makes Perl beat JavaScript for once :-) Jun 6, 2020 at 0:52 • Nice one! I kept playing with -F and List::MoreUtils but couldn't get a shorter solution! Another couple of minor changes can save you three more bytes: move the ++ to where you currently have $i-1, use $; instead of $i and reverse the condition of the while to use the implicit ; added by -p: Try it online!. Also, you probably need to acknowledge that it's  Perl 5 + -pl  in the header... Jun 7, 2020 at 14:09
• Thanks to @DomHastings also. The implicit ; feels almost too nasty, but in war and golf... :-) Jun 8, 2020 at 12:17

# Gaia, 9 bytes

e⟨:ọȯ¦|⟩°


Try it online!

Note that the documentation states that ȯ is sign of z when z is a numeric type, but it's actually abs...

e		# eval input as Gaia code (push as a list)
⟨	⟩°	# until there's no change:
:		# dup the list
ọ		# take the differences
ȯ¦		# take the absolute values
|		# and set union


@F{@F}=@F;{$d=abs($F[0]-$F[1]);$F{$d}++or$F[@F]=$d;say shift@F;@F>1&&redo}say@F  Try it online! Reads in a line of input, with the integers space separated. Outputs the sequence with each number on a different line. How does it work? It gets the input in the array @F (due to the -a command line argument). In the hash %F it stores the numbers already in @F (here we use the given that all numbers in sequence are positive integers). Then, in a loop, we find the distance between the first two elements of @F; if not seen before, we add it to @F (and %F). We then remove the first element of @F and print it. We exit the loop if only one element is left, which is printed just before exiting the program. The sequence can never contain a zero, as that requires two subsequent elements to be the same, but that is not allowed. # Charcoal, 21 bytes Ｗ⁻Ｅθ↔⁻κ∧λ§θ⊖λθＦι⊞θκＩθ  Try it online! Link is to verbose version of code. Explanation: Ｗ⁻Ｅθ↔⁻κ∧λ§θ⊖λθ  Generate the absolute differences between adjacent elements of the input and filter out those appearing in the input. Ｆι⊞θκ  While there were any new values, push them to the input and repeat. Ｉθ  Output the result. # Jelly, 8 7 bytes ;IAQƲÐL  -1 byte thanks to @JonathanAllan. Try it online. Explanation:  # Full program taking a single list argument ÐL # Repeat until the result no longer changes, Ʋ # using the previous four links as monads: I # Get the forward differences of the current list A # Take their absolute values ; # Merge it to the current list Q # And uniquify it # (after which it is output implicitly as result)  • Either of ÐL or ƬṪ do what ÐĿṪ does (first one is a built-in for it, second uses the Ƭ alias for ÐĿ). I may have gone with ;ạƝQƊÐL. Jun 5, 2020 at 18:35 • @JonathanAllan Ah oops, I copied the wrong one apparently from the Quicks wiki page.. Not sure how that happened.. :S Thanks for the -1, I will use ÐL! As for Ɲ, is that something like apply on overlapping pairs (similar as ü in 05AB1E)? I can't find Ɲ in neither the Atoms nor Quicks wiki pages though, so I guess it's rather new? Jun 5, 2020 at 18:58 • It's on the quicks page "Apply a dyadic link or a monadic chain for all pairs of neighbouring elements". Jun 5, 2020 at 19:00 • @JonathanAllan Wth.. my Ctrl+F function just yet gave no results for sure, I even tried it twice by copying the Ɲ from your first comment. :/ But it's indeed there. I'm really confused about Google Chrome rn.. Ah well, thanks for the -1. Jun 5, 2020 at 19:04 # K (Kona), 14 bytes {?x,_abs-':x}/  Try it online! Similar to J and APL answers. # Pyth, 10 bytes u{+GaM.:G2  Try it online! u{+GaM.:G2 u Apply inner function until a repeat is found, current value G, starting with input .:G2 Find all sublists of length 2 aM Absolute difference between each pair +G Append to G { Deduplicate Implicit print  # Japt-h, 10 6 bytes £=âUäa  Try it £=âUäa :Implicit input of array U £ :Map = :Reassign to U, for the next iteration â :Setwise union of U and Uä :Consecutive pairs of U a : Reduced by absolute difference  # Raku, 45 bytes {|$_,{|keys abs([-] @_[++$,$++])∖@_}...^!*}


Try it online!

### Explanation

{                                         }    # Anonymous codeblock
...        # Generating a sequence
|$_, # Starting with the input { } # Where we add to the sequence abs([-] ) # The absolute difference @_[++$,$++] # Of the next pair of elements |keys ∖@_ # Set subtracting the sequence ...!* # Continue until we run out of pairs  # Wolfram Language (Mathematica), 5751 46 bytes -11 bytes thanks to att! #//.a_:>Keys@Counts@Join[a,Abs@Differences@a]&  Try it online! Pure function. Takes a list as input and returns another list as output. It just repeatedly appends the absolute differences to the end of the list and removes duplicates, until the list no longer changes. • 51 bytes – att Jul 8, 2020 at 2:52 • DeleteDuplicates@ -> Keys@Counts@ for 46 – att Dec 1, 2021 at 2:07 # Factor + math.unicode, 47 bytes [ [ dup differences vabs ∪ ] to-fixed-point ]  Try it online! ## Explanation • [ ... ] to-fixed-point Do [ ... ] to the input until it stops changing.  ! { 16 21 11 2 } dup ! { 16 21 11 2 } { 16 21 11 2 } differences ! { 16 21 11 2 } { 5 -10 -9 } vabs ! { 16 21 11 2 } { 5 10 9 } ∪ ! { 16 21 11 2 5 10 9 } (set union) ! (etc...)  # JavaScript (ES6), 63 bytes f=(a,i=0)=>(v=a[i]-a[++i])?f([...new Set(a).add(v>0?v:-v)],i):a  Try it online! # Io, 59 bytes Port of the Python 2 answer. method(x,a :=0;x foreach(i,x=x push((i-a)abs)unique;a=i);x)  Try it online! # Retina, 8468 66 bytes Edit: Saved 16 18 bytes thanks to @Neil !! This answer is now mildly competitive :P \d+ * ^ # {#( _+)(_*)(\1(_*).*)$1$2#$3 $2$4
)D _+
^ |#

_+
$.&  Try it online! Not the shortest answer to this question, but it was fun to golf anyway :) Explanation \d+ *  Convert each input number to unary (using _'s) ^ #  Insert a # at the start of the input { )  Run the following 2 stages in a loop until the input stops changing: #( _+)(_*)(\1(_*).*)$1$2#$3 $2$4


Take the two numbers to the right of the # and remove the maximal number of _'s from each. This results in the absolute difference between the two numbers. Append this result to the end of the list.

D _+


Deduplicate. If the number that was just added matches a number already in the list, remove it.

^ |#

_+
$.&  Once the loop breaks, remove the # and leading space, and convert back to decimal • I didn't think to try this in Retina, but now you've answered it, I think you can save 4 bytes by performing the subtraction as you match the two values, and more usefully I think you can save a massive 13 bytes by using a Deduplicate stage. – Neil Jun 7, 2020 at 22:47 • @Neil Wow, thanks! I might have missed something though because I ended up with 68 bytes rather than 67 Jun 8, 2020 at 0:12 • I didn't have the \b on the Deduplicate; I don't know whether that's an error in my code. On the other hand, if that works, that makes yours 66! Your byte saving came from having the space inside $1 - I erroneously had it outside, so my other golfs were only able to bring the score down to 67.
– Neil
Jun 8, 2020 at 0:23
• (Oh, and your loop only has 2 stages now.)
– Neil
Jun 8, 2020 at 0:23
• Looks like that works! I had misunderstood how the Deduplicate stage was working Jun 8, 2020 at 0:38

# Java (JDK), 90 bytes

l->{for(int i=0,v;i+1<l.size();)if(!l.contains(v=Math.abs(l.get(i++)-l.get(i))))l.add(v);}


Try it online!

# PHP, 96 78 bytes

for($a=$argv;$n=$a[++$i];print"$n ")in_array($v=abs($n-$a[$i+1]),$a)?:$a[]=\$v;


Try it online!

EDIT: 18 bytes saved with the help of Domenico Modica, thanks!

• 16 bytes saved without array_shift and without outputting the script name :D. Jun 8, 2020 at 12:55
• @DomenicoModica Nice! Also removed the brackets, print doesn't need them Jun 8, 2020 at 14:02

# Wolfram Language (Mathematica), 50 bytes

#//.l:_[___,b_,a_,___]:>l<>d/;FreeQ[l,d=Abs[b-a]]&


Try it online!

Takes a sequence with any head. If the sequence is already complete, returns it unchanged. Otherwise, returns the completed sequence in a StringJoin.

<> (StringJoin) is short, flattens Lists, does not operate on integer (non-string) arguments, and is Flat. It's also not Orderless, so can store ordered data.

      _[             ]                           (* match a nonatomic expression with any head, *)
l:                                           (*  and name it l. it contains: *)
b_,a_,                               (*   two adjacent numbers, b,a, *)
___,      ___                            (*   as close to the front as possible, *)
/;                   (* subject to the condition that *)
FreeQ[l,d=Abs[b-a] (*  |b-a| is not in l. *)
#//.                  :>l<>d                     (* while the condition holds, append |b-a|. *)


# APL(NARS), 22 chars, 44 bytes

{⍬≡k←∪⍵∼⍨∣2-/⍵:⍵⋄∇⍵,k}


test:

  f←{⍬≡k←∪⍵∼⍨∣2-/⍵:⍵⋄∇⍵,k}
f 16 21 11 2
16 21 11 2 5 10 9 3 1 6
f 2 3 4 5
2 3 4 5 1


# UiuaSBCS, 14 bytes

⍥(◴⊂:⌵↘1°\+.)∞


Try it!

⍥(◴⊂:⌵↘1°\+.)∞
⍥(          )∞  # to fixed point
.    # duplicate
↘1°\+     # differences
⌵          # abs
⊂:           # append
◴             # deduplicate


# J-uby, 39 bytes

:!~&:|%(~:each_cons&2|:*&(:<<&:-|:abs))


Attempt This Online!

## Explanation

:!~ & :| % (~:each_cons & 2 | :* & (:<< & :- | :abs))
:!~ &                                                  # Until fixed point...
:| % (                                        )  #   Union of input and...
:<< & :- | :abs    #     absolute differences of...
~:each_cons & 2 | :* & (               )   #     consecutive pairs
`