Fill in the next numbers

Question

Given a list of integers, output a list where the \$ i \$th element of the list equals the first number in the input list which is \$ \ge i \$, until there are no such numbers.

For example, if the input is:

2 3 5 7 11

then we "expand" the sequence out to show where the gaps are:

_ 2 3 _ 5 _ 7 _ _ __ 11     # input
1     4   6   8 9 10        # gaps

Now we fill in the blanks with the next number that is in the sequence in each case:

2 2 3 5 5 7 7 11 11 11 11
1     4   6    8  9 10

This is the output.

Test cases

[1]               -> [1]
[3]               -> [3, 3, 3]
[1, 2, 3]         -> [1, 2, 3]
[1, 3, 4, 9]      -> [1, 3, 3, 4, 9, 9, 9, 9, 9]
[2, 3, 5, 7, 11]  -> [2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11]

Rules

You may assume the input list is non-empty, strictly increasing, and only contains positive integers
You may use any standard I/O method
Standard loopholes are forbidden
This is code-golf, so the shortest code in bytes wins!

\$\begingroup\$ Sandbox \$\endgroup\$
– pxeger
Mar 7, 2022 at 6:42 — pxeger, Mar 7, 2022 at 6:42

pajonk · Accepted Answer · 2022-03-07 06:47:51Z

13

R, 30 bytes

Or R>=4.1, 23 bytes by replacing the word function with a \.

function(x)rep(x,diff(c(0,x)))

Try it online!

answered Mar 7, 2022 at 6:47

pajonk

16k3 gold badges21 silver badges66 bronze badges

Add a comment |

loopy walt · Accepted Answer · 2023-01-21 17:19:21Z

12

Python 3, 37 bytes (@Jitse)

f=lambda l=[],*L:l and[l]*l+f(*L)[l:]

Try it online!

Original Python 3, 38 bytes

f=lambda l,*L:(l,)*l+(L and f(*L)[l:])

Try it online!

Takes the splatted input and returns a tuple.

How?

This is entirely based on the observation that the first original number k, say, will occur k times in the output. Working back to front we can treat each number k[n] as if it were the first and at the next iteration n-1 replace the k[n-1] excess copies of k[n] with copies of k[n-1].

edited Jan 21, 2023 at 17:19

answered Mar 8, 2022 at 0:13

loopy walt

16.7k2 gold badges10 silver badges69 bronze badges

1

\$\begingroup\$ this is pure genius! \$\endgroup\$
– DialFrost
Mar 8, 2022 at 3:35
\$\begingroup\$ 37 bytes \$\endgroup\$
– Jitse
Jan 17, 2023 at 12:52
\$\begingroup\$ @Jitse Nice. Somehow, I would have expected this to be a syntax error but it isn't. \$\endgroup\$
– loopy walt
Jan 21, 2023 at 17:22

Add a comment |

Dominic van Essen · Accepted Answer · 2022-03-07 15:20:20Z

BQN, 5 bytes

+`⁼/⊢

Try it at BQN online REPL

BQN has a lovely 'undo' modifier (⁼) which calculates the inverse of any function, where this is possible.
Here we use it with cumulative sum (+` ) to get the cumulative differences starting from zero.
After that we just need to replicate (/) the input values (⊢) this number of times.

   /    # Replicate the elements of
    ⊢   # the right-hand argument
        # by 
  ⁼     # undo the
+`      # cumulative sum of 
        # the right-hand argument

G B · Accepted Answer · 2022-03-07 06:53:30Z

6

Ruby, 36 bytes

->l{x=0;l.flat_map{|a|[a]*(-x+x=a)}}

Try it online!

answered Mar 7, 2022 at 6:53

G B

21.9k1 gold badge20 silver badges53 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2022-03-07 08:47:03Z

6

Vyxal, 4 bytes

ẋ∩vg

Try it Online!

ẋ    # Repeat the numbers by themselves
     # [[2, 2], [3, 3, 3], [5, 5, 5, 5, 5]]
 ∩   # Transpose
     # [[2, 3, 5], [2, 3, 5], [3, 5], [5], [5]]
  vg # Get the minimum of each

edited Mar 7, 2022 at 8:47

answered Mar 7, 2022 at 6:43

emanresu A

37.8k5 gold badges91 silver badges217 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2022-03-08 01:26:50Z

6

PARI/GP, 35 bytes

a->vector(a[#a],n,[m|m<-a,m>=n][1])

Attempt This Online!

a->                                   Define a function with argument `a`
   vector(                        )   that returns a vector
          a[#a],                      whose length is the last term of `a`
                n,                    and the `n`th term
                  [m|m<-a,    ][1]    is the first `m` in `a` such that
                          m>=n        `m` is larger than `n`.

edited Mar 8, 2022 at 1:26

answered Mar 7, 2022 at 8:28

alephalpha

48k7 gold badges62 silver badges175 bronze badges

6

\$\begingroup\$ Could you add an explanation? Since this is language of the month, that would give those of us who don't know the language a bit of an on-ramp. \$\endgroup\$
– Sundar R
Mar 7, 2022 at 14:12

Add a comment |

tsh · Accepted Answer · 2022-03-07 07:12:22Z

5

JavaScript (Node.js), 40 bytes

a=>a.map(g=n=>n>o.push(n)&&g(n),o=[])&&o

Try it online!

answered Mar 7, 2022 at 7:12

tsh

34.7k2 gold badges33 silver badges126 bronze badges

Add a comment |

ophact · Accepted Answer · 2022-03-07 08:01:15Z

5

Python 3.8 (pre-release), 43 bytes

f=lambda n,i=2:n and[n[0]]+f(n[[i]>n:],i+1)

Try it online!

Thanks @dingledooper for -2 bytes.

edited Mar 7, 2022 at 8:01

answered Mar 7, 2022 at 7:54

ophact

3,1641 gold badge6 silver badges24 bronze badges

2

\$\begingroup\$ 44 bytes: f=lambda n,i=2:n and[n[0]]+f(n[i>n[0]:],i+1). \$\endgroup\$
– dingledooper
Mar 7, 2022 at 7:56
1

\$\begingroup\$ Actually, there's 43 bytes: f=lambda n,i=2:n and[n[0]]+f(n[[i]>n:],i+1). \$\endgroup\$
– dingledooper
Mar 7, 2022 at 8:00

Add a comment |

Razetime · Accepted Answer · 2022-03-07 11:46:22Z

5

K (ngn/k), 6 bytes

(-':)#

Try it online!

Explanation

(-':)#
(-':)  deltas
     # replicate

answered Mar 7, 2022 at 11:46

Razetime

27.1k3 gold badges27 silver badges71 bronze badges

1

\$\begingroup\$ Nice! I just threw together {,/(-':x)#'x} for K4 but this is much more impressive! \$\endgroup\$
– mkst
Mar 9, 2022 at 9:30
\$\begingroup\$ It's quite useful to be following the development of ngn/k :P \$\endgroup\$
– Razetime
Mar 9, 2022 at 13:38
\$\begingroup\$ i think this should work in the current k9 build as well) \$\endgroup\$
– Razetime
Mar 9, 2022 at 13:41

Add a comment |

chunes · Accepted Answer · 2022-03-07 08:03:48Z

4

Factor, 44 bytes

[ dup last iota [ '[ _ > ] find ] with map ]

Try it online!

Let \$L\$ be the last element of the input. Then map \$[0..L)\$ to the first element of the input that is greater.

answered Mar 7, 2022 at 8:03

chunes

24k3 gold badges21 silver badges51 bronze badges

Add a comment |

Graham · Accepted Answer · 2022-03-07 07:45:48Z

3

APL+WIN, 13 bytes

Prompts for input

(-2-/0,v)/v←⎕

Try it online! Thanks to Dyalog APL Classic

answered Mar 7, 2022 at 7:45

Graham

6,10614 silver badges11 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2022-03-07 08:50:28Z

3

Halfwit, 7.5 bytes

MZ;RZMR[$

Try It Online!

I think I made it too minimalistic...

Explanation

M ;       # Map over each value...
 Z        # Fill an array of length (itself) with (itself)
   R      # Reduce by (taking two lists)
    Z     # Zip
     M    # For each pair...
      R   # Reduce by...
       [  # If the first is truthy (nonzero)...
        $ # return it, otherwise return the other value

answered Mar 7, 2022 at 8:50

emanresu A

37.8k5 gold badges91 silver badges217 bronze badges

5

\$\begingroup\$ Half-bit? Do you mean half-byte? \$\endgroup\$
– pxeger
Mar 7, 2022 at 9:38
3

\$\begingroup\$ Given the image, I feel obligated to mention that the name "Samwise" is roughly based on the Old English for "halfwit." \$\endgroup\$
– DLosc
Mar 7, 2022 at 17:49
1

\$\begingroup\$ @pxeger Oops lol :) - I think I'll just leave it like that \$\endgroup\$
– emanresu A
Mar 7, 2022 at 18:51
\$\begingroup\$ I've posted my first Halfwit answer. A few questions/suggestions: 1) is there an easier way to push 4? 2) I would try to remove the BigInt/int error when you use operations on mixed types. 3) Can anything be done with strings? The challenge originally asked for a space-delimited string of integers, but I don't think Halfwit has anything useful to split those spaces? Although it does allow for string inputs, I assume the language is primarily designed for int/int-lists (and it converts strings to codepoint integers), right? \$\endgroup\$
– Kevin Cruijssen
Apr 21, 2022 at 13:42
1

\$\begingroup\$ @KevinCruijssen strings are represented as charcodes, and there’s not much you can do with them. Halfwit’s very experimental lol \$\endgroup\$
– emanresu A
Apr 30, 2022 at 9:18

Add a comment |

MarcMush · Accepted Answer · 2022-03-07 15:23:33Z

3

Julia 1.0, 29 bytes

!x=[fill.(x,diff([0;x]))...;]

Try it online!

answered Mar 7, 2022 at 15:23

MarcMush

6,49511 silver badges17 bronze badges

Add a comment |

Sundar R · Accepted Answer · 2022-03-07 19:50:42Z

3

MATL, 6 bytes

0yhdY"

Try it online!

Take a diff and repelem the input that many times (same as @pajonk's R answer among others).

I thought this sounded ideal for an interp1 based answer, but that comes out to 16 bytes: 0ihttX>:IG1)5$Yn Try it online!

answered Mar 7, 2022 at 19:50

Sundar R

6,61218 silver badges33 bronze badges

Add a comment |

Sundar R · Accepted Answer · 2022-03-07 20:14:55Z

3

Octave, 26 bytes

@(v)repelem(v,diff([0,v]))

Ideone link (TIO's version of Octave doesn't seem to have repelem.)

This started off as seeing if I'd have better luck with interp1 on Octave directly (than via MATL), but it's again longer here, at 45 bytes:

@(v,w=[0,v])interp1(w,w,1:max(v),'next',v(1))

Try it online!

(the w=[0,v] is because interp1 doesn't like operating on single element vectors like the [3] testcase, wants at least two elements.)

answered Mar 7, 2022 at 20:14

Sundar R

6,61218 silver badges33 bronze badges

Add a comment |

DLosc · Accepted Answer · 2022-03-07 23:22:10Z

3

Pip, 13 11 bytes

-2 bytes by porting Neil's Charcoal answer because I was seriously overthinking things

FngT Ui=Pn0

Takes input as separate command-line arguments; gives output as lines of stdout. Attempt This Online!

Explanation

FngT Ui=Pn0
             ; i is 0, g is list of command-line args (implicit)
Fng          ; For each n in g:
   T         ;   Till
     Ui      ;   increment i
       =     ;   equals
        Pn   ;   print n:
          0  ;     No-op

edited Mar 7, 2022 at 23:22

answered Mar 7, 2022 at 23:07

DLosc

39.4k5 gold badges72 silver badges135 bronze badges

Add a comment |

Aiden Chow · Accepted Answer · 2022-03-08 01:51:37Z

3

Desmos, 45 bytes

M=l.max
f(l)=[\{l<i:M,l\}.\min\for i=[1...M]]

Try It On Desmos!

Try It On Desmos! - Prettified

I feel like this could be a bit shorter, though I don't see it at the moment. I tried to take out the two uses of l.max but the strategies I tried didn't work. Also that piecewise expression is a bit annoying, though I don't see a shorter way (it causes me to add \'s everywhere in the list comprehension. Without the \'s the code won't work.).

answered Mar 8, 2022 at 1:51

Aiden Chow

13.3k1 gold badge15 silver badges53 bronze badges

Add a comment |

DLosc · Accepted Answer · 2022-03-08 06:16:51Z

HBL, 9 bytes

-(2*(<1.?)(2-.(10.

The online interpreter doesn't support zip-with yet, but here's a version with a hacked-together reimplementation of zip-with on the first line: Try it!

Explanation

-(2*(<1.?)(2-.(10.
          (2       )   Zip
            -          with the subtraction function:
             .          The input list, and
              (1  )     Cons
                0        0 to
                 .       the input list
                       Result: pairwise differences
    (<   )             For each item in
       .               the input list:
      1                 cons it to
        ?               nil
                       Result: input list but with each number in a singleton list
 (2                 )  Zip those two lists
   *                   with the list-repetition function
                       Result: for each n in the input list, a length-n list of n's
-                      Flatten

AZTECCO · Accepted Answer · 2022-03-08 11:05:25Z

3

Haskell, 37 34 bytes

f l=do(a,b)<-zip(0:l)l;b<$[a+1..b]

Try it online!

Saved 3 Bytes thanks to @Unrelated String suggesting using do notation which reveals how emphatic Haskell is.

Old version

f l=(\(a,b)->b<$[a+1..b])=<<zip(0:l)l

edited Mar 8, 2022 at 11:05

answered Mar 7, 2022 at 23:47

AZTECCO

10.8k1 gold badge14 silver badges58 bronze badges

\$\begingroup\$ Gorgeous! But also 3 bytes shorter with do (unfortunately taking it all the way is 1 longer). \$\endgroup\$
– Unrelated String
Mar 8, 2022 at 2:02

Add a comment |

Jonathan Allan · Accepted Answer · 2022-03-07 13:29:19Z

Jelly, 4 bytes

xŻI$

A monadic Link that accepts a strictly increasing list of positive integers and yields a non-strictly increasing list of positive integers.

Try it online!

How?

If the input is A=[a1, a2, a3, ...] then the output needs to be a1 a1s followed by a2-a1 a2s then a3-a2 a2s etc.

xŻI$ - Link: strictly increasing list of positive integers, A
   $ - last two links as a monad - f(A=[a1, a2, a3, ...]):
 Ż   -   prepend a zero -> [0, a1, a2, a3, ...]
  I  -   incremental differences -> [a1, a2-a1, a3-a2, ...]
x    - times (vectorises) -> [a1, ..., a1, a2, ..., a2, a3, ...]

Kjetil S · Accepted Answer · 2022-03-07 20:24:27Z

2

Perl 5, 39 bytes

sub{$l=0;map{($_)x($l+=$r=$_-$l,$r)}@_}

Try it online!

edited Mar 7, 2022 at 20:24

answered Mar 7, 2022 at 18:41

Kjetil S

5,89710 silver badges21 bronze badges

Add a comment |

Giuseppe · Accepted Answer · 2022-03-08 01:38:02Z

2

R, 41 bytes

function(x)x[cumsum(y<-1:rev(x)%in%x)+!y]

Try it online!

Quite a lot longer than pajonk's answer, but a nice little bit of index calculation all the same.

This ports to other matrix languages such as, for instance, MATL, but it's longer than the diff approach there as well.

answered Mar 8, 2022 at 1:38

Giuseppe

28.6k3 gold badges31 silver badges103 bronze badges

Add a comment |

chunes · Accepted Answer · 2023-01-17 11:06:59Z

2

Arturo, 42 bytes

$[a][map 1..max a'x[min select a'y[y>=x]]]

Try it

$[a][                 ; a function taking an argument a
  map 1..max a'x[     ; map over the range 1..max(a) and assign current value to x
    min select a'y[   ; select the smallest number in a that...
      y>=x            ; is greater than or equal to x
    ]                 ; end select
  ]                   ; end map
]                     ; end function

answered Jan 17, 2023 at 11:06

chunes

24k3 gold badges21 silver badges51 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2023-01-17 12:33:37Z

2

JavaScript (Node.js), 38 bytes

a=>a.map(g=n=>n>++i?[n,g(n)]:n,i=0)+''

Try it online!

answered Jan 17, 2023 at 12:33

l4m2

23.9k2 gold badges23 silver badges91 bronze badges

Add a comment |

Unrelated String · Accepted Answer · 2022-03-07 06:43:03Z

1

Jelly, 4 bytes

x)o/

Try it online!

Shamelessly sandbox sniped, but I didn't start it :P

 )      For each element of the input, as a monadic chain:
x       repeat it by itself.
  o/    Reduce the resulting list of lists by logical OR.

answered Mar 7, 2022 at 6:43

Unrelated String

21.3k3 gold badges29 silver badges55 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-03-07 09:17:51Z

05AB1E, 8 7 6 bytes

Å1*ζ€ß

-1 byte porting @emanresuA's Vyxal answer

Try it online or verify all test cases.

Original 8 7 bytes answer:

0š¥Å1*˜

Try it online or verify all test cases.

Explanation:

         #  e.g. input=[2,3,5]

Å1       # Map each value in the (implicit) input-list to that many 1s
         #  → [[1,1],[1,1,1],[1,1,1,1,1]]
 *       # Multiply each to the (implicit) input-list at the same positions
         #  → [[2,2],[3,3,3],[5,5,5,5,5]]
  ζ      # Zip/transpose; swapping rows/columns, using " " as filler
         #  → [[2,3,5],[2,3,5],[" ",3,5],[" "," ",5],[" "," ",5]]
   €ß    # Get the minimum of each inner list, ignoring the " "
         #  → [2,2,3,5,5]
         # (after which the resulting list is output implicitly)

0š       # Prepend a 0 to the (implicit) input-list
         #  → [0,2,3,5]
  ¥      # Pop and push its deltas/forward-differences
         #  → [2,1,2]
   Å1*   # Similar as above
         #  → [[2,2],[3],[5,5]]
      ˜  # Flatten this list of lists
         #  → [2,2,3,5,5]
         # (after which the resulting list is output implicitly)

rebane2001 · Accepted Answer · 2022-03-07 11:10:45Z

1

Python 3.8 (pre-release), 75 bytes

def f(a):
 s=[i:=(c:=a[-1])]
 while i:=i-1:s=[c:=[c,i][i in a]]+s
 print(s)

Try it online!

Ungolfed:

def fill_numbers(original):
    current_number = last_valid = original[-1]
    result = [original[-1]]
    while current_number-1 > 0:
        current_number -= 1
        if current_number in original:
            last_valid = current_number
        result = [last_valid] + result
    print(result)

answered Mar 7, 2022 at 11:10

rebane2001

3071 silver badge4 bronze badges

Add a comment |

sinvec · Accepted Answer · 2022-03-07 11:27:02Z

1

Pyth, 9 bytes

hM.Tm*d]d

Try it online!

answered Mar 7, 2022 at 11:27

sinvec

1,9435 silver badges28 bronze badges

Add a comment |

Neil · Accepted Answer · 2022-03-07 11:40:07Z

1

Charcoal, 9 bytes

ＦＡＷ‹ⅉι⟦Ｉι

Try it online! Link is to verbose version of code. Explanation:

ＦＡ

Loop over the input list.

Ｗ‹ⅉι

Repeat until the appropriate line is reached...

⟦Ｉι

... output the current value on its own line.

answered Mar 7, 2022 at 11:40

Neil

170k12 gold badges72 silver badges275 bronze badges

Add a comment |

dneustadt · Accepted Answer · 2023-01-18 07:53:40Z

1

PHP, 71 bytes

$n=[];for($i=max($a);$i;$i--){$n=[in_array($i,$a)?$h=$i:$h??$i,...$n];}

Try it online!

Ungolfed:

$n = [];
for ($i = max($a); $i; $i--) {
  $n = [in_array($i, $a) ? $h = $i : $h ?? $i, ...$n];
}

edited Jan 18, 2023 at 7:53

answered Jan 18, 2023 at 1:06

dneustadt

1713 bronze badges

Add a comment |

Fill in the next numbers

Test cases

Rules

30 Answers 30

R, 30 bytes

Python 3, 37 bytes (@Jitse)

Original Python 3, 38 bytes

How?

BQN, 5 bytes

Ruby, 36 bytes

Vyxal, 4 bytes

PARI/GP, 35 bytes

JavaScript (Node.js), 40 bytes

Python 3.8 (pre-release), 43 bytes

K (ngn/k), 6 bytes

Explanation

Factor, 44 bytes

APL+WIN, 13 bytes

Halfwit, 7.5 bytes

Explanation

Julia 1.0, 29 bytes

MATL, 6 bytes

Octave, 26 bytes

Pip, 13 11 bytes

Explanation

Desmos, 45 bytes

HBL, 9 bytes

Explanation

Haskell, 37 34 bytes

Jelly, 4 bytes

How?

Perl 5, 39 bytes

R, 41 bytes

Arturo, 42 bytes

JavaScript (Node.js), 38 bytes

Jelly, 4 bytes

05AB1E, 8 7 6 bytes

Python 3.8 (pre-release), 75 bytes

Pyth, 9 bytes

Charcoal, 9 bytes

PHP, 71 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
array
or ask your own question.