In what order will the downloads complete?

Question

Background

Recently, I was installing updates on my pc with Pacman (I use arch btw) and noticed the order it downloaded files was like this

• Start with the largest 4 downloads
• When a download completes, start downloading the next biggest file.

Since the biggest file takes the longest to download, you'll often see the second or third biggest actually complete first. Interesting.

Challenge

Given a list of download sizes, eg 50, 40, 30, 20, 11, and the amount of downloads that can be running simultaneously, output the order the downloads will complete (eg 4). Assume all downloads run at the same speed.

Output should be a the sizes of the downloads in the order they complete. The ways to represent a list or the numbers in the list is very flexible.

Worked Out Example

Suppose we have files 50mb, 40mb, 30mb, 20mb, 11mb and an allowed parallelism of 4.

• We start downloading the 4 largest, which is the 50, 40, 30, and 20.
• The 20mb will complete first. At this point, we start downloading the 11mb file.
• The 30mb file now has just 10 megabytes left so it will complete next. Now the 11 mb file has just 1 mb left, so it will finish next.
• Now the 40 mb file has 9 mb left, so it will complete second to last.
• Finally, the 50 mb file finishes downloading.

Allowed assumptions

You may assume no two downloads will complete at the same time.

You may assume all the sizes will be unique

You may assume all sizes are positive, nonzero integers

You may assume the length of the input list is not less than the given maximum parallelism

Test Cases

[5,4,3,2], 4 -> [2, 3, 4, 5]
[50,40,30,20,11], 4 -> [20, 30, 11, 40, 50]
[50,40,30,20,11,12], 4 -> [20, 30, 12, 40, 11, 50]
[51,40,30,20,11,12,106], 4 -> [30, 40, 20, 51, 12, 11, 106]
[51,40,30,20,11,13,106,500,401,302,201,116,121,1068,1], 6 -> [121, 201, 116, 51, 302, 106, 20, 40, 30, 1, 11, 13, 401, 500, 1068]
[60,50,30,29,20], 4 -> [29, 30, 20, 50, 60]

Feel free to suggest more test cases

Example Code

def download_sort(numbers: list[int], parallelism: int):
    numbers.sort()
    initial = [numbers.pop() for i in range(parallelism)]
    active = [[i,i] for i in initial]
    while len(numbers)>0 or len(active)>0:
        active.sort(key=lambda i:i[1], reverse=True)
        next = active.pop()
        yield next[0]
        for i in active:
            i[1]-=next[1]
        if len(numbers)>0:
            next_value = numbers.pop()
            active.append([next_value, next_value])

Answer 1

Bash + GNU parallel, 69 bytes

+1 byte (nice): Neil points out sort needs -n, otherwise 100<11

p=$1
shift
xargs -n1<<<$@|sort -nr|parallel -j $p "sleep {}&&echo {}"

Attempt This Online! (ATO does not ship parallel)

Call with max jobs as first argument, and then every number in any order as additionnal arguments (e.g. par.bash 4 50 40 30 20 11 12).

I tried to be better than this, unfortunately i am not good enough to do anything better. Sort of uses sleepsort.

Answer 2

Python, 80 bytes

Thanks @att for -3

lambda l,p,S=sorted:S(l,key={x:(p:=[min(p)+x]+S(p)[1:])for x in S(l)[::-1]}.get)

Attempt This Online!

Previously, cleaner but longer:

Python, 83 bytes

lambda l,p,S=sorted:S(l,key={x:(p:=[min(p)+x]+S(p)[1:])[0]for x in S(l)[::-1]}.get)

Attempt This Online!

Takes the parallelism p in unary as a list of 1s.

How?

First builds a map (dictionary) download length -> E.T.A. by going from longest to smallest dl while maintaining a list of the E.T.A.s of the currently downloading items. The input parameter p serves as this list initialised to all 1s. Once the map is built it is used as a key for sorting the download items by their E.T.A.s.

Answer 3

Vyxal, 22 12 11 bytes

ẋ£sṘµw¥s+:£

Try it Online!

Now uses an idea stolen from Albert.Lang's Python answer of only maintaining a list of queue lengths, and sorting by those, except there turns out to be an absurdly short way to do this.

 £          # Set the register (list of queue lengths) to
ẋ           # <parallelism> copies of <downloads>
            # In older versions of this, this was a list of 0s, but any numeric list will work
            # since lists are lexicographically compared by the first element, and it saves a byte
  sṘ        # Sort the list of downloads backwards
    µ       # And sort this list by, for each n, 
      ¥s    # Taking the register, sorting it, 
        +   # And adding
     w      # n to the first element
         :£ # Then resetting the register, and using its current value to sort
            # since two downloads will never finish at the same time, 
            # This is sorting by the head, i.e. the ETA of the current value

Answer 4

Python 3.8 (pre-release), 115 113 109 bytes

• -2 thanks to UnrelatedString
• -4 thanks to xnor

def f(F,p):
 F.sort();q=zip(*[F[-p:]]*2)
 for t in F[~p::-1]+F[-1:]*p:(n,i),*q=q;yield i;q+=(n+t,t),;q.sort()

Try it online!

Answer 5

K (ngn/k), 28 27 bytes

{y@<(&x){-':y+\x@<x}\y@:>y}

Try it online!

Port of emanresu A's Vyxal solution.

                    y@ >y   descending times
y@<                   :     sort by:
   (&x){          }\          scan with initial state (empty):
              x@<x              sort ascending
        -':y+\                  add new time to first position

Answer 6

Python3, 162 bytes

def f(F,p):
 q,s=[],[]
 F=sorted(F)
 while F+q:
  q+=[[F.pop()]*2for _ in F[:p-len(q)]]
  Q=[]
  for a,b in q:
   if a:Q+=[(a-1,b)]
   else:s+=[b]
  q=Q
 return s

Try it online!

Answer 7

JavaScript (ES6), 146 bytes

Expects (array)(n) and returns a space-separated string.

Probably not the shortest algorithm.

b=>g=(n,a=b.sort((a,b)=>b-a).map(s=>[s,--n<0&&n,s]))=>(c=a.sort(([r,w],[R,W])=>!w-!W||R-r).pop())?c[2]+" "+g(a.map(a=>a[1]?a[1]++:a[0]-=c[0]),a):a

Try it online!

Method

Initialization

We first sort the input array from largest to smallest file size.

We turn each entry into a triplet \$(r,w,s)\$ where:

• \$r\$ is the remaining number of bytes to download (initially set to the original size)
• \$w\$ is the waiting time, set to \$0\$ for the first \$n\$ files, and then \$-1\$, \$-2\$, ... and so forth for the next ones
• \$s\$ is the original size

Iterations

At each iteration:

• We sort the triplets by their downloading status first (\$w=0\$ vs \$w\neq0\$) and \$r\$ second.
• We look for the triplet \$c\$ of the next completed file: the one with the smallest \$r\$ among those for which \$w=0\$.
• We remove this entry from the list and append the original file size \$c[2]\$ to the output.
• We update all remaining triplets:
  • if \$w=0\$, we subtract \$c[0]\$ (the number of bytes that has just been downloaded) from \$r\$
  • if \$w\neq0\$, we increment \$w\$ (i.e. we make it advance by one position in the waiting queue)

Answer 8

Jelly, 15 14 12 11 bytes

ṢUṢ+"¥ɼÞɓxɼ

Try it online!

-1 with slightly less stateful register use

-2 by actually porting directly

-1 by thinking

Takes the list on the left, and the max parallelism \$p\$ on the right, as a full program--relies on the register being initialized to a scalar. Port of emanresu A's port of Albert.Lang's approach.

        ɓ      First,
          ɼ    set the register to itself (initially 0)
         x     repeated a number of times equal to
        ɓ      the max parallelism.
ṢU             Then, sort the downloads descending.
     ¥ Þ       Sort those by the results of mapping in order:
  Ṣ   ɼ        Sort the register (times used) ascending
   +"          and add the time being sorted to the first element of that
      ɼ        then set the register to that result and use it as the sort key.
  Ṣ "  Þ       (Lists compare lexicographically, so the first element is used.)

Jelly, 22 20 19 18 bytes

ṢUSÞ;"¥ƒḟ`€}µÄẎỤịẎ

Try it online!

-2 further porting emanresu A's actual solution after further discussion in chat

-1 with a slightly more clever way of getting the empty lists after way too many failed attempts

-1 by throwing that out because I remembered I don't need the singletons any more

Takes the list on the left, and the max parallelism \$p\$ on the right. Port of emanresu A's approach as described in chat, before she actually posted it.

ṢU                    Sort the list descending.
        ḟ`            Starting with an empty list
          €}          for each [1 .. p],
       ƒ              reduce it by:
  SÞ                  Sort by sum,
      ¥               then
    ;"                zipwith append the implicitly-singleton new download.
              Ẏ       Concatenate
             Ä        the cumulative sums of each queue,
               Ụ      grade up,
                ị     and index into
            µ         the original queues
                 Ẏ    concatenated.

Jelly, 38 29 bytes

ṢU;S$⁹¡ż`ṫḊṢḢṖạƊṭ@ɗƒ¥ƤḣɗṪ€€ḟƝ

Try it online!

-9 by directly tracking the original identity of each in-progress download instead of inferring it afterwards. That's what took me the most time to get working in the first place 😭😭😭

Takes the list on the left, and the max parallelism \$p\$ on the right. A """simple""" iterative approach which reduces with the in-progress downloads as the accumulator state.

ṢU                                Sort the list descending,
  ;S$                             then append the sum of the list
     ⁹¡                           p times.
  ;S$⁹¡            ƒ              The sums fill in for idle threads,
           ṢḢ                     as they'll never be smaller than real downloads.
       ż`                         Pair every element with itself.
                     Ƥ            For every nonempty prefix of
         ṫ                        the p'th element onwards,
          Ḋ                       remove the first element
         ṫḊ           ḣ           (so there's no overlap with the starting set,
          Ḋ        ƒ Ƥ            and so the first reduce is a no-op)
                    ¥             then
                      ḣ           starting with the first p downloads,
                  ɗƒ              reduce the prefix by:
           Ṣ                      Sort the current downloads ascending,
            Ḣ                     take the first element (= maximum),
             Ṗ                    remove its last element,
              ạ                   and subtract that from
             Ṗ                    the first elements of
            Ḣ  Ɗ                  every other element
             Ṗạ                   without affecting their last elements;
                ṭ@                append the next largest download to start.
                         Ṫ        Take the last element of
                          €       each pair
                           €      in each download set,
                            ḟƝ    and return the one missing in each next step.

Answer 9

Charcoal, 54 bytes

≔⟦⟧υＷ⁻θυ⊞υ⌈ιＵＭυ⟦ιι⟧Ｗυ«Ｗ⌊⌊υＦ⎇›Ｌυη…υηυＵＭλ⁻μ¬νＩ✂⌊υ¹≔Φυ⌊κυ

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

≔⟦⟧υＷ⁻θυ⊞υ⌈ι

Sort the input into descending order.

ＵＭυ⟦ιι⟧

Map each download into its relative duration and original length.

Ｗυ«

Repeat until all downloads complete.

Ｗ⌊⌊υ

Repeat until one download completes.

Ｆ⎇›Ｌυη…υηυ

Loop over only the running downloads.

ＵＭλ⁻μ¬ν

Decrement the time remaining.

Ｉ✂⌊υ¹

Output the original length of the completed download.

≔Φυ⌊κυ

Remove the completed download from the list.

51 bytes to port @Albert.Lang's algorithm:

≔Ｅη⁰ηＷ⌈⁻θＥυ⌊κ§≔η⌕η⌊η⌈§⊞Ｏυ⟦⁺⌊ηιι⟧±¹≔⟦⟧ηＷ⁻υη⊞η⌊ιＩＥη⊟ι

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

≔Ｅη⁰η

Start with all parallel tasks ready.

Ｗ⌈⁻θＥυ⌊κ

Process the downloads in descending order of size.

§≔η⌕η⌊η⌈§⊞Ｏυ⟦⁺⌊ηιι⟧±¹

Take the earliest completed download, add it to the current download's size and save that with the size, then also update that download's new completion time.

≔⟦⟧ηＷ⁻υη⊞η⌊ιＩＥη⊟ι

Sort the downloads by start time and output their lengths.

Answer 10

C (clang), 118 bytes

with -Wl,-z,execstack flags by @ceilingcat

s[9999];f(*r,*a,n,p){for(n=qsort(a,n,4,"\x8b\6+\7Ã")-p;n++<1e4;)n<1?s[*a++]=*a:s[n]?*r++=s[n],s[n]=0,s[*a+++n]=*a:0;}

Try it online!

C (clang), 128 bytes

s[9999];c(*a,*b){return*b-*a;}f(*r,*a,n,p){for(n=qsort(a,n,4,c)-p;n++<1e4;)n<1?s[*a++]=*a:s[n]?*r++=s[n],s[n]=0,s[*a+++n]=*a:0;}

Try it online!

Answer 11

05AB1E, 16 14 bytes

Å0©I{RΣ®{ćy+š©

Port of @emanresuA's Vyxal answer, which in turn is a port of @Albert.Lang's Python answer, so make sure to upvote both of those answers as well!
-2 bytes thanks to @emanresuA

Inputs in the order \$parallelism,list\$.

Try it online or verify all test cases.

Explanation:

Å0             # Push a list of the first (implicit) input amount of 0s
  ©            # Store it in variable `®` (without popping)
   I           # Push the second input-list
    {R         # Sort it in reversed order
      Σ        # Then sort it further by:
       ®       #  Push list `®`
        {      #  Sort it
         ć     #  Extract head; push first item and remainder list separately
          y+   #  Add the current value to this first item
               #  (which will either add 0 to each value; or add the values at the
               #  same positions in the lists together)
            š  #  Prepend it back to the list
             © #  Store this as new `®` (without popping)
               # (after the sortBy, output the sorted list implicitly)

Answer 12

JavaScript (Node.js), 97 bytes

(x,t=0,h=[])=>g=n=>h[t]||n--?x+x?g(n,h[t+(u=x.sort((a,b)=>a-b).pop(t+=!!t))]=u):h.flat():g(0,++t)

Try it online!

-6B Arnauld

Not pretty but

Answer 13

Pip -xp, 44 bytes

Wl|DN:a#l<b&a?uPU[i0]+@YlPUPOaUi&FI:DlBMUSNu

Attempt This Online!

Ungolfed/commented

This solution simulates the download process one tick at a time. There's probably a shorter solution to be had by porting someone else's approach; I haven't looked into it yet.

The -xp flags mean that command-line arguments are evaluated as Pip values (letting us take the list input as a single arg) and lists are output in repr form.

;; a is the list of tasks that haven't been queued up yet
;; b is the maximum parallelism number
;; l is the list of ticks remaining for the currently executing tasks
;; i is the current tick
;; u is the list of [completion time, task] pairs
;; Initially, a and b are command-line args, l is [], i is 0, and u is nil

; Sort a in descending numerical order
DN: a
; Loop while either a or l is nonempty:
W a | l {
  ; Check if the number of tasks currently executing is less than the max
  ; parallelism, and, if so, if there are any tasks waiting to be queued up
  I #l < b & a {
    ; Pop the next task from a and push it to l
    l PU POa
    ; Calculate that task's completion time: current tick plus length of task
    Y i + @l
    ; Push [completion time, task] to u
    u PU [y; @l]
  } EL {
    ; Else, move to the next tick
    U i
    ; Decrement all elements of the ticks-remaining list
    D l
  }
  ; Filter out any tasks that have 0 ticks remaining
  FI: l
}
; Sort u numerically (ascending by completion time)
SN: u
; For each [completion time, task] pair in u, return the second element of the pair
B MU u

Answer 14

Uiua, 17 bytes

F ← ⊏⍏◌⤚∧˜(.⍜⊢+⍆)⊙⊚⇌⍆

Try it online!

This would be 16 bytes with F ← ⊏⍏⊸⬚∘\(⍜⊢+⍆)⊚:⇌⍆ if the scan function wasn't annoying and had parity with reduce

Answer 15

Pip, 19 bytes

YOGb{Y[a]+SNy}SKDNa

Attempt This Online! Port of several other golflang answers, posted by DLosc's request (-2 thanks to DLosc).

Y                   # Yank into the y variable
 OG                 # A grid of 1s of size
   b                # <paralellism>
                DN  # Reverse sort
                  a # The download list
    {        }SK    # And sort by the function:
          SN        # Reverse sort
            y       # the list of queue lengths
      [a]+          # Add the current download to the first
     Y              # Yank that into the y variable
              SK    # And use [the first item of] that list to sort the downloads