25
\$\begingroup\$

Given \$A = (a_1,\dots,a_k)\ k\ge2 \$ a sequence of positive integers, in which all elements are different.

Starting from \$i=2\$, 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
Improve this question
\$\endgroup\$
11
  • 2
    \$\begingroup\$ You should explain stopping and simply not appending more clearly then. For me it reads to stop doing anything. \$\endgroup\$
    – Noodle9
    Jun 5, 2020 at 13:16
  • 2
    \$\begingroup\$ @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\$ \$\endgroup\$
    – Domenico
    Jun 5, 2020 at 13:26
  • 2
    \$\begingroup\$ Yeah, sure I see that now. But questions are always better when they're totally clear. \$\endgroup\$
    – Noodle9
    Jun 5, 2020 at 13:50
  • 1
    \$\begingroup\$ I couple of weeks is recommended so all these warts can be sorted out. \$\endgroup\$
    – Noodle9
    Jun 5, 2020 at 14:03
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Luis Mendo
    Jun 5, 2020 at 15:21

24 Answers 24

Reset to default
8
\$\begingroup\$

05AB1E, 6 5 bytes

Δ¥Ä«Ù

Try it online!

Δ         until the output doesn't change:
 ¥Ä           absolute differences
   «          concatenate to the original input
    Ù         only keep unique values
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You beat me to it. I was about to post an answer.. Only difference is that I had üα instead of ¥Ä. :) \$\endgroup\$
    – Kevin Cruijssen
    Jun 5, 2020 at 13:13
  • 1
    \$\begingroup\$ @KevinCruijssen Apparently this wasn't optimal, since all differences are computed in every iteration, we can just concatenate with the original input. \$\endgroup\$
    – ovs
    Jun 6, 2020 at 9:53
  • \$\begingroup\$ Oh, I wouldn't have thought of that, but you're indeed correct. Nice golf! \$\endgroup\$
    – Kevin Cruijssen
    Jun 6, 2020 at 10:32
6
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 48 bytes in Python 3 by mutating the input: Try it online! \$\endgroup\$
    – pxeger
    Feb 26, 2022 at 15:32
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Giuseppe
    Jun 5, 2020 at 20:27
  • 1
    \$\begingroup\$ Thanks Giuseppe! ...and I even managed to squeeze-out 2 more... \$\endgroup\$
    – Dominic van Essen
    Jun 5, 2020 at 20:50
4
\$\begingroup\$

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.

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

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
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Abigail
    Jun 6, 2020 at 0:50
  • \$\begingroup\$ Thanks @Abigail ! This makes Perl beat JavaScript for once :-) \$\endgroup\$
    – Kjetil S
    Jun 6, 2020 at 0:52
  • 1
    \$\begingroup\$ 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... \$\endgroup\$
    – Dom Hastings
    Jun 7, 2020 at 14:09
  • 1
    \$\begingroup\$ Thanks to @DomHastings also. The implicit ; feels almost too nasty, but in war and golf... :-) \$\endgroup\$
    – Kjetil S
    Jun 8, 2020 at 12:17
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

perl -M5.010 -a, 79 bytes

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Jonathan Allan
    Jun 5, 2020 at 18:35
  • \$\begingroup\$ @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? \$\endgroup\$
    – Kevin Cruijssen
    Jun 5, 2020 at 18:58
  • \$\begingroup\$ It's on the quicks page "Apply a dyadic link or a monadic chain for all pairs of neighbouring elements". \$\endgroup\$
    – Jonathan Allan
    Jun 5, 2020 at 19:00
  • \$\begingroup\$ @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. \$\endgroup\$
    – Kevin Cruijssen
    Jun 5, 2020 at 19:04
2
\$\begingroup\$

K (Kona), 14 bytes

{?x,_abs-':x}/

Try it online!

Similar to J and APL answers.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 57 51 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 51 bytes \$\endgroup\$
    – att
    Jul 8, 2020 at 2:52
  • \$\begingroup\$ DeleteDuplicates@ -> Keys@Counts@ for 46 \$\endgroup\$
    – att
    Dec 1, 2021 at 2:07
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Retina, 84 68 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

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Jun 7, 2020 at 22:47
  • \$\begingroup\$ @Neil Wow, thanks! I might have missed something though because I ended up with 68 bytes rather than 67 \$\endgroup\$
    – math junkie
    Jun 8, 2020 at 0:12
  • \$\begingroup\$ 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. \$\endgroup\$
    – Neil
    Jun 8, 2020 at 0:23
  • 1
    \$\begingroup\$ (Oh, and your loop only has 2 stages now.) \$\endgroup\$
    – Neil
    Jun 8, 2020 at 0:23
  • \$\begingroup\$ Looks like that works! I had misunderstood how the Deduplicate stage was working \$\endgroup\$
    – math junkie
    Jun 8, 2020 at 0:38
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 16 bytes saved without array_shift and without outputting the script name :D. \$\endgroup\$
    – Domenico
    Jun 8, 2020 at 12:55
  • 1
    \$\begingroup\$ @DomenicoModica Nice! Also removed the brackets, print doesn't need them \$\endgroup\$
    – Kaddath
    Jun 8, 2020 at 14:02
1
\$\begingroup\$

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|. *)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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...)
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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