25
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – pxeger
    Mar 7 at 6:42

27 Answers 27

13
\$\begingroup\$

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!

\$\endgroup\$
11
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ this is pure genius! \$\endgroup\$
    – DialFrost
    Mar 8 at 3:35
7
\$\begingroup\$

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

Ruby, 36 bytes

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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`.
\$\endgroup\$
1
  • 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 at 14:12
5
\$\begingroup\$

JavaScript (Node.js), 40 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 44 bytes: f=lambda n,i=2:n and[n[0]]+f(n[i>n[0]:],i+1). \$\endgroup\$ Mar 7 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\$ Mar 7 at 8:00
5
\$\begingroup\$

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

K (ngn/k), 6 bytes

(-':)#

Try it online!

Explanation

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

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.

\$\endgroup\$
3
\$\begingroup\$

APL+WIN, 13 bytes

Prompts for input

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

Try it online! Thanks to Dyalog APL Classic

\$\endgroup\$
3
\$\begingroup\$

Halfwit, 7.5 bytes

MZ;RZMR[$

Try It Online!

I think I made it too minimalistic...

enter image description here

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
\$\endgroup\$
5
  • 5
    \$\begingroup\$ Half-bit? Do you mean half-byte? \$\endgroup\$
    – pxeger
    Mar 7 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 at 17:49
  • 1
    \$\begingroup\$ @pxeger Oops lol :) - I think I'll just leave it like that \$\endgroup\$
    – emanresu A
    Mar 7 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\$ Apr 21 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 at 9:18
3
\$\begingroup\$

Julia 1.0, 29 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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

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

\$\endgroup\$
3
\$\begingroup\$

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

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

Perl 5, 39 bytes

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

Try it online!

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

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.

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

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

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

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

Pyth, 9 bytes

hM.Tm*d]d

Try it online!

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

Charcoal, 9 bytes

FAW‹ⅉι⟦Iι

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

FA

Loop over the input list.

W‹ⅉι

Repeat until the appropriate line is reached...

⟦Iι

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

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

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, ...]
\$\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.