Add in the blanks

Question

In this challenge you will be given a list of positive integers which represents some range of integers which has been truncated for display. Your job is to find the missing bits and insert ellipses to show that that part has been truncated.

The input will always be strictly ascending and if two consecutive values differ by more than 1 then we know some data has been removed in between them.

For example if the input is:

1,2,3,4,20,21,22

Then since 4 and 20 differ by more than 1 we insert an ellipsis between them:

1,2,3,4,...,20,21,22

However if the consecutive values differ by exactly two, then we just reinsert the missing value (their mean), since an ellipsis doesn't actually save any space when it's just covering 1 value.

So for example if the input is:

1,2,3,5,6

Then 3 and 5 differ by more than 1 so data has been removed between them, but they differ by 2 so we just insert the missing 4.

1,2,3,4,5,6

Additionally if the first value is greater than 1 we know that something has been truncated off the front. So we add an ellipsis, or if the first value is 2, a 1 as the first value. We can't know that something has been truncated off the end so we never add anything there.

Task

Given a list of positive strictly-ascending integers as input output the list with the proper insertions. You can represent ellipses in the output as any constant value other than a positive integer. For the convenience of strongly typed programming, you may also output a list of optional values with the null value representing ellipses.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[1,2,3,4,20,21,22] -> [1,2,3,4,...,20,21,22]
[1,2,3,5,6] -> [1,2,3,4,5,6]
[2,3,4,9] -> [1,2,3,4,...,9]
[3,5,7,8,10] -> [...,3,4,5,6,7,8,9,10]
[1,20,23] -> [1,...,20,...,23]

Answer 1

JavaScript (ES10),  45  43 bytes

Uses undefined for ellipses.

a=>a.map(p=v=>[[[],v-1][v+~p],p=v]).flat(2)

Try it online!

Commented

a =>             // a[] = input array, e.g. [ 1, 3, 6 ]
  a.map(p =      // initialize p to a zero'ish value
  v =>           // for each value v in a[]:
    [            //   build an array:
      [          //     according to v - p - 1, append:
        [],      //       an empty array if it's 0
        v - 1    //       v - 1 if it's 1
                 //       implicitly: undefined for anything else
      ][v + ~p], //
      p = v      //     append v and update p to v
    ]            //   end of array
  )              // end of map(); this gives:
                 //   [ [ [], 1 ], [ 2, 3 ], [ undefined, 6 ] ]
  .flat(2)       // apply .flat() at depth 2 to clean this up:
                 //   [ 1, 2, 3, undefined, 6 ]

Answer 2

R, 69 68 bytes

Edit: -1 byte thanks to pajonk

\(x){F[i<-cumsum(2-!(j=diff(c(0,x))-1))]=x;F[-i]=(x*(j<2))[j>0]-1;F}

Attempt This Online!

Uses -1 as the ellipsis character.

How?

j=diff(c(0,x))-1    # get the differences between adjacent elements -1
!j                  # zero for consecutive integers, 1 otherwise
i=cumsum(2-!j)      # indices of original elements, leaving gaps for ellipses or new elements-in-gaps
F[i]=x              # fill-in the elements into vector F
F[-i]=              # fill-in the gaps with...
      (x...)[j>0]-1 # one less than the subsequent original value...
        *(j<2)      # ...adjusted to zero if the gap was >2
F                   # finally, return F

Answer 3

K (ngn/k), 24 bytes

,/0{((0;();x-1)x-y),x}':

Try it online!

Uses 0N for ellipses.

Explanation

• 0{...}': pairwise map with placeholder 0 (y is prev elem, x is next elem)...
  • (0;();x-1)x-y get elem of list (0;();x-1) at index x - y
  • ,x append x
• ,/ flatten

Answer 4

05AB1E, 22 19 17 15 bytes

0šüŸε¦¤®s‚‚éн}˜

Uses -1 for ellipsis, but could alternatively use another 1-byte alternative (e.g. 0, "", " ", "\n", "abcdefghijklmnopqrstuvwxyz", etc.) by replacing the ®.

-3 bytes porting @MamaFunRoll's K (ngn/k) answer
-2 bytes porting @DominicVanEssen's Husk answer
-2 bytes thanks to @CommandMaster with yet another different approach

Try it online or verify all test cases.

Explanation:

          #  Example input: [2,3,5,9,13]
0š        # Prepend a 0 to the (implicit) input-list
          #  STACK: [0,2,3,5,9,13]
  ü       # For each overlapping pair {a,b}:
   Ÿ      #  Push a list in the range [a,b]
          #   STACK: [[0,1,2],[2,3],[3,4,5],[5,6,7,8,9],[9,10,11,12,13]]
ε         # Map over each inner list:
          #   STACK1: [0,1,2] ;        STACK2: [5,6,7,8,9]
 ¦        #  Remove the first item
          #   STACK1: [1,2] ;          STACK2: [6,7,8,9]
  ¤       #  Push the last item (without popping the list)
          #   STACK1: [1,2],2 ;        STACK2: [6,7,8,9],9
   ®      #  Push -1, the ellipsis value
          #   STACK1: [1,2],2,-1 ;     STACK2: [6,7,8,9],9,-1
    s     #  Swap the top two values on the stack
          #   STACK1: [1,2],-1,2 ;     STACK2: [6,7,8,9],-1,9
     ‚    #  Pair them together
          #   STACK1: [1,2],[-1,2] ;   STACK2: [6,7,8,9],[-1,9]
      ‚   #  Pair the two lists together
          #   STACK1: [[1,2],[-1,2]] ; STACK2: [[6,7,8,9],[-1,9]]
       é  #  Sort by length (shortest to longest)
          #   STACK1: [[1,2],[-1,2]] ; STACK2: [[-1,9],[6,7,8,9]]
        н #  Pop and leave the first inner list
          #   STACK1: [1,2] ;          STACK2: [-1,9]
}         # After the map
          #  STACK: [[1,2],[3],[4,5],[-1,9],[-1,13]]
 ˜        # Flatten the resulting list of lists
          #  STACK: [1,2,3,4,5,-1,9,-1,13]
          # (after which the result is output implicitly)

Answer 5

Haskell, 69 63 49 bytes

• -6 bytes thanks to @Wheat Wizard
• -14 bytes thanks to @alephalpha

g(x,y)|y>x+2=[0,y]|1>0=[x+1..y]
f a=zip(0:a)a>>=g

Attempt This Online!

Answer 6

Python 3, 62 bytes

lambda a:sum([[~-i*(i-2in[0]+a),i][i-1in[0]+a:]for i in a],[])

Try it online!

Use 0 for ellipses.

For each value i in input:

• If i - 1 is already included in input, or i - 1 is 0, we need insert nothing before it;
• Otherwise, if i - 2 is already included in input, or i - 2 is 0, we need insert i - 1 before it;
• Otherwise, we insert ... before it.

Answer 7

Perl 5 + -p -M5.10.0, 35 bytes

If using a 0 is acceptable this would be 31 bytes, but that feels a bit cheaty...

$;=$_*say$--1?"...":$_-1if$-=$_-1-$

Try it online!

Answer 8

Wolfram Language (Mathematica), 40 bytes

##&[Pick[#>p+2||++p,p<#],p=#]&/@(p=0;#)&

Try it online!

Represents ellipses by True.

##&[Pick[#>p+2||++p,p<#],p=#]&/@(p=0;#)&
                                 p=0    starting from 0,
                              /@(   ;#) for each element:
         #>p+2                            True if current-previous>2,
              ||++p                         otherwise previous+1,
    Pick[          ,p<#]                      but omit if =current
##&[                    ,p=#]           prepend and update previous

Answer 9

Jelly, 13 11 bytes

ŻṖ‘ż¹FQµIỊa

Try it online!

0 for ellipses.

Ż              Prepend a 0,
 Ṗ             trim the last element,
  ‘            increment,
   ż¹F         flat-interleave with the original input,
      Q        and uniquify.
       µ  a    Zero out any elements of the result which
        I      have a difference with the next element
         Ị     greater than 1.

Answer 10

Vyxal, 15 bytes

Gɾ‡?cḊƛḢ[h?c∧;f

Try it Online!

Uses 0 for ellpisis.

Answer 11

PARI/GP, 50 bytes

a->b=0;concat([if(c-b<3,[b+1..b=c],[x,b=c])|c<-a])

Attempt This Online!

Use x for ellipses.

Answer 12

Brainfuck, 71 bytes

,[[->+>+<<]>>[-<<+>>]<<<[->-<]+>-[-[<<.>-]<[>>-.+<<-<]>]<[-<]>>[-]>.>,]

Ungolfed program (a port of my Haskell solution)

Script to test it

Answer 13

Rust, 135 130 bytes

-5 bytes thanks to @alpehalpha

|v:Vec<i8>|v.iter().scan(0,|c,&a|Some((match a-*c{1=>vec![a],2=>vec![a-1,a],_=>vec![-1,a]},*c=a).0)).flatten().collect::<Vec<_>>()

Attempt This Online!

Answer 14

Python 2, 57 bytes

p=1
for n in input():
 if p<n:print-~p/n*p
 print n;p=n+1

Try it online!

A program that takes in a list on STDIN and prints the output values on separate lines.

Answer 15

J, ³⁴ 31 bytes

0(}.(+_*_1>])2-/\])@~.@,<:,@,.]

Try it online!

This was surprisingly difficult to golf in J and the K approach ended up being longer than either of these.

Idea

We take a two pass strategy:

• First we insert the numbers below each number.
• Then we check if there are any gaps greater than 1. If so, we replace those gaps with infinity _.

How

Consider 2 3 4 9:

• <:...,.] Decrement zipped with original input:

  1 2
  2 3
  3 4
  8 9
  

• 0...~.@,...,@ Flatten, prepend 0, and take the unique:

  0 1 2 3 4 8 9
  

• }.(...)2-/\] On the left hand side, kill the 0, on the right hand side take consecutive deltas:

  1 2 3 4 8 9  (...) _1 _1 _1 _1 _4 _1 
  

• _*_1>] Turn every entry less than _1 on the right into infinity:

  0 0 0 0 _ 0
  

• + And add that to the left side:

  1 2 3 4 _ 9
  

J, first approach, 34 bytes

[:;]<@~.@,~"+]+_3>.@%@+3<.2-~/\0,]

Try it online!

Answer 16

R, 75 bytes

\(x,y=c(0,x))for(i in x-1){if(!i%in%y)show(`if`((i-1)%in%y,i,0));show(i+1)}

Attempt This Online!

Answer 17

Husk, 16 14 bytes

Edit: -2 bytes by stealing Kevin Cruijssen's improvements in his port of this!

ΣẊö◄LSeoe0→t…Θ

Try it online!

Uses 0 for ellipsis; could use any other integer by exchanging the 0 at position 10 in the code.

             Θ     # add a zero at the start of the list; 
 Ẋȯ                # now, for every pair of elements:
            …      #  fill gaps with numeric ranges,
           t       #  and discard the first element,
     Se            #  then make a 2-element list of this and
       oe0→        #  just the last element preceded by zero,
   ◄L              #  and select the element with minimum length;
Σ                  # finally, flatten the resulting list-of-lists.  

Answer 18

C (clang), ⁷⁶ 71 bytes

p;f(*a,n){for(p=0;n--;)printf("%d %d "+(++p==*a)*3,p+1<*a?0:p,p=*a++);}

Try it online!

Saved 5 bytes thanks to att!!!

Inputs a pointer to an array of positive integers and its length (because pointers in C carry no length info).
Prints out the filled in array using \$0\$ for ellipses.

Answer 19

Charcoal, 24 bytes

ＩＥ⊕Φ⌈θ№⁺θ⊖θ⊕ι∧№⊞Ｏ⁺θ⊕θ¹ιι

Try it online! Link is to verbose version of code. Uses 0 to represent an ellipsis. Explanation:

     θ                      Input array
    ⌈                       Maximum
   Φ                        Filter on implicit 0-indexed range
        θ                   Input array
       ⁺                    Concatenated with
          θ                 Input array
         ⊖                  Vectorised decrement
      №                     Contains
            ι               0-indexed value
           ⊕                Incremented (i.e. 1-indexed)
  ⊕                         Incremented (back to 1-indexed values)
 Ｅ                          Map over values
                  θ         Input array
                 ⁺          Concatenated with
                    θ       Input array
                   ⊕        Vectorised increment
               ⊞Ｏ           Concatenated with
                     ¹      Literal integer `1`
              №             Contains
                      ι     Current value
             ∧              Logical And
                       ι    Current value
Ｉ                           Cast to string
                            Implicitly print

Answer 20

Ruby, 50 45 bytes

->l{a=0;l.map{|x|p x-a<2?a:0if x>a+=1;p a=x}}

Try it online!

Thanks Jonah for -2 bytes and a different approach which saved 3 more bytes.

Answer 21

AWK, 44 bytes

{d=$0-a;if(d>1)print d==2?$0-1:0;print a=$0}

Try it online!

Thanks to Dominic van Essen for pointing out that 5 bytes needed to initialize the variable a on TIO aren't needed on GNU awk, and so shouldn't count in the score.

Outputs 0 for ....

Answer 22

Pyth, 17 bytes

Inspired by Arnauld's JavaScript answer

.n,Le<[YtdG)aZ=Zd

Try it online! or Try all test cases

Uses the lowercase alphabet as the ellipsis (could alternatively use 0 or empty string).

.n,Le<[YtdG)aZ=Zd
                    Implicitly initialize Z to 0
   L                Left map over the input with variable d
      [    )        3-element list of...
       Y              ... the empty list
        td            ... (d - 1)
          G           ... the lowercase alphabet
     <              Keep the first N elements of that list, where...
            aZd      ... N = the absolute difference of Z and d
              =Zd   (Set Z to d)
    e               Take the last element of the resulting list
  ,                 Create a two-element list of (result, current element)
.n                  Flatten

Answer 23

Retina 0.8.2, 73 bytes

\d+
$*
^
,
(^|\b1+),(?=11\1\b)
$&1$1,
(^|\b1+),(?=11\1)
$&...,
^,

1+
$.&

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

^
,

Prefix 0 (in unary).

(^|\b1+),(?=11\1\b)
$&1$1,

Where two consecutive integers differ by 2, insert the missing integer.

(^|\b1+),(?=11\1)
$&...,

Where two consecutive integers differ by more than 1, insert an ellipsis.

^,

Remove the leading 0.

1+
$.&

Convert to decimal.

Answer 24

Haskell + hgl, 36 bytes

x#y=y:>(y#*0++[x+1])!!P2 x

pax(#)<K0

Attempt This Online!

Explanation

This works a lot like the other Haskell answer. First we define (#) which takes two values x and y, it returns

• [x+1,y] if x is y-1
• [0,y] if x is between -2 and y-2
• [y] otherwise

It does this by constructing a list of y 0s followed by x+1 and then indexing it by x+2. The result is prepended to [y].

Once we have this function we start by adding 0 to the front of the input and then we perform a map and concat on the pairs in the augmented input using (#).

Parser version, 55 bytes

g x=hd<~lA<kB<gt<pl x

tl<sk(fp2 0<g 2++(p2*^P1)<g 1)<K0

Attempt This Online!

Reflection

The non-parser version is fine. It's a finicky problem which means it's a little long. I ultimately don't see anything to be improved.

The parser version is too long and there are some things to be improved here.

• We have (>~) to return the right value, and (<~) to return the left value, we should have a function to allow the application of an arbitrary rule to combine the two. Sort of like a combination of l2 and bn.
• It would be nice to have something like kBs which returns the result as a string instead of a symbol.

Answer 25

Setanta, 90 87 bytes

Uses 0 for ....

gniomh(l){m:=[]x:=0le i idir(0,fad@l){i=l[i]m+=(i>x+1&[i<x+3|0&i-1,i])|[i]x=i}toradh m}

try-setanta.ie link