| Bytes | Lang | Time | Link |
|---|---|---|---|
| 118 | C clang | 241116T163116Z | jdt |
| 019 | Pip | 241119T210133Z | emanresu |
| 017 | Uiua | 241119T114102Z | janMakos |
| 097 | JavaScript Node.js | 241116T134654Z | l4m2 |
| 044 | Pip xp | 241118T211746Z | DLosc |
| 014 | 05AB1E | 241118T082645Z | Kevin Cr |
| 109 | Python 3.8 prerelease | 241117T000628Z | STerliak |
| 011 | Vyxal | 241116T222027Z | emanresu |
| 054 | Charcoal | 241115T195350Z | Neil |
| 011 | Jelly | 241116T191727Z | Unrelate |
| 080 | Python | 241117T060255Z | Albert.L |
| 027 | K ngn/k | 241117T145931Z | att |
| 146 | JavaScript ES6 | 241115T183254Z | Arnauld |
| 162 | Python3 | 241115T223147Z | Ajax1234 |
| 069 | Bash + GNU parallel | 241115T160826Z | Themooni |
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;}
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;}
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
Uiua, 17 bytes
F ← ⊏⍏◌⤚∧˜(.⍜⊢+⍆)⊙⊚⇌⍆
This would be 16 bytes with F ← ⊏⍏⊸⬚∘\(⍜⊢+⍆)⊚:⇌⍆ if the scan function wasn't annoying and had parity with reduce
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)
-6B Arnauld
Not pretty but
Pip -xp, 44 bytes
Wl|DN:a#l<b&a?uPU[i0]+@YlPUPOaUi&FI:DlBMUSNu
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
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)
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()
Vyxal, 22 12 11 bytes
ẋ£sṘµw¥s+:£
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
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.
Jelly, 15 14 12 11 bytes
ṢUṢ+"¥ɼÞɓxɼ
-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Þ;"¥ƒḟ`€}µÄẎỤịẎ
-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$⁹¡ż`ṫḊṢḢṖạƊṭ@ɗƒ¥ƤḣɗṪ€€ḟƝ
-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.
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)
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)
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.
K (ngn/k), 28 27 bytes
{y@<(&x){-':y+\x@<x}\y@:>y}
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
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
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)
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
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.