21
\$\begingroup\$

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 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]
\$\endgroup\$
1

23 Answers 23

9
\$\begingroup\$

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 ]
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -1 byte. \$\endgroup\$
    – pajonk
    Jul 6 at 20:40
  • \$\begingroup\$ @pajonk - Ah, yes, thanks! Looks like I was too smug to get a shorter approach... \$\endgroup\$ Jul 6 at 21:06
5
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 16 bytes: ZÝ.¡›}嬮‚‚éн}˜¦ \$\endgroup\$ Jul 6 at 15:09
  • 1
    \$\begingroup\$ 15 bytes: 0šüŸε¦¤®s‚‚éн}˜ \$\endgroup\$ Jul 6 at 15:31
  • \$\begingroup\$ @CommandMaster I was about to post a 2 bytes save by porting the Husk answer when I saw your 16 byter, and after I was done editing you commented your 15 byter. Thanks for the nice save in bytes! :) \$\endgroup\$ Jul 6 at 15:43
  • 1
    \$\begingroup\$ @KevinCruijssen Nice! Husk saves 2 more bytes by porting your port back again... \$\endgroup\$ Jul 6 at 16:05
4
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ 59 I believe. \$\endgroup\$
    – loopy walt
    Jul 6 at 15:39
  • \$\begingroup\$ @loopywalt very interesting idea. But since it modified most parts here, maybe you can post it as another entry. \$\endgroup\$
    – tsh
    Jul 7 at 2:14
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

Haskell, 69 bytes

g x y|x+1==y=[y]|x+2==y=[x+1,y]|True=[0,y]
f a=concat$zipWith g(0:a)a

Attempt This Online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Here are a couple of easy improvements to get 63 bytes I encourage taking another look at the Haskell tips page. There's a lot of good stuff there. \$\endgroup\$
    – Wheat Wizard
    Jul 6 at 9:00
  • 1
    \$\begingroup\$ 49 bytes. \$\endgroup\$
    – alephalpha
    Jul 6 at 11:21
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • 3
    \$\begingroup\$ "You can represent ellipses in the output as any constant value other than a positive integer". So why wouldn't 0 be acceptable? \$\endgroup\$ Jul 6 at 20:35
  • \$\begingroup\$ Only because of the qualifier For the convenience of strongly typed programming, my assumption was that if you are returning a list in a strongly typed language you may keep all the items of the same type, whereas I'm returning data via STDOUT so it feels like I'd be taking liberties! \$\endgroup\$ Jul 7 at 5:39
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Almost identical approach to my AWK answer, minuse the bit twiddling :) \$\endgroup\$
    – Jonah
    Jul 7 at 2:15
2
\$\begingroup\$

J, 34 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!

\$\endgroup\$
2
\$\begingroup\$

Vyxal, 15 bytes

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

Try it Online!

Uses 0 for ellpisis.

\$\endgroup\$
2
  • \$\begingroup\$ The output of [1,2,3,5,6] should be [1,2,3,4,5,6], not [1,2,3,0,5,6]. Same for [3,5,7,8,10] ([...,3,4,5,6,7,8,9,10], not [...,3,0,5,0,7,8,0,10])... \$\endgroup\$ Jul 6 at 20:07
  • 1
    \$\begingroup\$ @DominicvanEssen Argh, overlooked that rule. Fixed. \$\endgroup\$
    – Steffan
    Jul 6 at 20:12
1
\$\begingroup\$

Brainfuck, 71 bytes

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

Ungolfed program (a port of my Haskell solution)

Script to test it

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

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!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ |c,a| -> |c,&a|, *a -> a. \$\endgroup\$
    – alephalpha
    Jul 6 at 10:58
1
\$\begingroup\$

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.  
\$\endgroup\$
1
\$\begingroup\$

C (clang), 76 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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 71: p;f(*a,n){for(p=0;n--;)printf("%d %d "+(++p==*a)*3,p+1<*a?0:p,p=*a++);} \$\endgroup\$
    – att
    Jul 6 at 20:44
  • \$\begingroup\$ "%d %d "+(++p==*a)*3 nice trick \$\endgroup\$ Jul 7 at 13:55
  • \$\begingroup\$ @att Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Jul 7 at 15:02
1
\$\begingroup\$

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.

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

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice. On my gnu awk installation the -va=0 is superfluous, as any undefined variable is initialized to zero by default, so this would count as only 44 bytes. \$\endgroup\$ Jul 7 at 5:37
  • \$\begingroup\$ @DominicvanEssen Thanks for pointing that out. \$\endgroup\$
    – Jonah
    Jul 7 at 22:57
1
\$\begingroup\$

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

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.

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

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!

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

Charcoal, 24 bytes

IE⊕Φ⌈θ№⁺θ⊖θ⊕ι∧№⊞O⁺θ⊕θ¹ιι

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)
 E                          Map over values
                  θ         Input array
                 ⁺          Concatenated with
                    θ       Input array
                   ⊕        Vectorised increment
               ⊞O           Concatenated with
                     ¹      Literal integer `1`
              №             Contains
                      ι     Current value
             ∧              Logical And
                       ι    Current value
I                           Cast to string
                            Implicitly print
\$\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.