9
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2018 Day 7, Part 2.

Why I'm pxeger, not Bubbler


As soon as you and a few Elves successfully assemble the Sleigh kit, you spot another set of the same kit not so far away. But you noticed that the last Elf is slacking quite a lot but you had to work from start to end without having any free time at all.

In an attempt to fix this, you decide to take a specific number of Elves to maximize your free time.

This time, you and the Elves learned how to assemble it, so each job numbered n exactly takes n seconds to complete (instead of n + 60 seconds). And, to simplify things, the manual is given simply as a list of pairs of job numbers, each pair (x, y) meaning "job x should be completed before job y can begin". The smallest-numbered worker available (you being number 1 and the Elves being number 2, 3, ...) takes the next available job, smallest number first.

Given the example manual

[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)]

the visual order of the jobs is as follows:

  -->1--->2--
 /    \      \
3      -->4----->5
 \           /
  ---->6-----

If you take 0, 1, or 2 Elves with you (being 1, 2, 3 workers in total), the following will happen respectively:

1 worker:
you   | 333122444466666655555

2 workers:
you   | 333122444455555
elf 1 |    666666

3 workers:
you   | 333122   55555
elf 1 |    666666
elf 2 |     4444

So you get 3 seconds of rest when there are 3 workers, and no time to rest with fewer. Since there is no opportunity to do 4 jobs in parallel, the 3-worker case is the best for you. If multiple choices give the same amount of time to rest, choose the fewest number of workers.

Note that the amount of rest counts until the last job is finished. So if the input is [(4, 1), (4, 2), (4, 3)], the following happens with 3 workers and you get two seconds of rest at the end:

You: 44441__
Elf:     22
Elf:     333

Input: A description of the manual. Assume every job to be done appears in the manual, and the job numbers are consecutive from 1.

Output: The optimal total number of workers.

Standard rules apply. The shortest code in bytes wins.

Test cases

[(2, 1), (3, 2)] -> 1
[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)] -> 3
[(2, 3), (2, 5), (8, 6), (8, 4), (3, 7), (6, 7), (5, 1), (4, 1)] -> 3
+-2-+-3--+--7-+
|   +-5--|+   |
|        ||   |
+-8-+-6--+|   |
    +-4---+-1-+
1 worker:
2-3-5-8-4-1-6-7
2 worker:
22333555556666667777777
8888888844441
3 worker: (same as 4 worker; no way to parallelize [3, 4, 5, 6])
22333...44441.7777777
88888888666666
  55555

[(4, 1), (4, 2), (4, 3)] -> 3
[(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)] -> 4
\$\endgroup\$
15
  • \$\begingroup\$ Can we assume that the manual will be ordered by x in (x, y) as in all given test cases? \$\endgroup\$
    – Ezhik
    Dec 19, 2021 at 10:03
  • \$\begingroup\$ If so, can we alternatively assume that the manual will not tell you to start job z after job y before telling you to start job y after job x? \$\endgroup\$
    – Neil
    Dec 19, 2021 at 11:53
  • \$\begingroup\$ @Ezhik since this isn't my challenge, I'll ask Bubbler \$\endgroup\$
    – pxeger
    Dec 19, 2021 at 20:05
  • 1
    \$\begingroup\$ @Ezhik and Neil, No and no. You can't assume anything other than those specified in the challenge. \$\endgroup\$
    – Bubbler
    Dec 19, 2021 at 21:45
  • 1
    \$\begingroup\$ @Neil 2 seconds with 3 workers. I guess I had to specify that the "rest" counts until all jobs are completed. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 21:46

7 Answers 7

4
\$\begingroup\$

Ruby, 29, then 157 ... 106 bytes

->a,*r{(0..a.sum(&:sum)).map{x,y=a.transpose;r+=x&=x-y;a=a.map{|i,j|i>r.count(i)?[i,j]:[j,0]};x.size}.max}

Try it online!

Took me some time so I want to explain:

Just the core loop:

x,y=a.transpose;r+=x&=x-y

x and y are the jobs on the left and right side of all instructions in the manual. At any given iteration, we can only execute steps that don't depend on other jobs, so only the ones that aren't in y. At the beginning all the jobs are either in x or in y so we can get them easily.

a=a.map{|i,j|i>r.count(i)?[i,j]:[j,0]}

After each iteration we check if any job has been completed. If so, then we can remove it from all instructions where it's on the left side, and move the job on the right side to the left (and define a dummy task 0 which won't be executed anyway, to compensate for the missing right side). Next time, all jobs that are no longer blocked by others will be available in x.

x.size}.max

Final result is the max number of jobs that ran in parallel on a single iteration.

\$\endgroup\$
5
  • \$\begingroup\$ lonelyelk's answer doesn't work (fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4), so your answer is also invalid. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 23:18
  • \$\begingroup\$ @Bubbler Fixed! \$\endgroup\$
    – G B
    Dec 21, 2021 at 9:14
  • \$\begingroup\$ I'm working on this too, but it seems more tricky than initially anticipated. With your solution: p f[[[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9]]] gives 8, but 5 is enough 1227777777, _333666666, _444455555, _88888888, _999999999 \$\endgroup\$
    – lonelyelk
    Dec 21, 2021 at 23:51
  • 1
    \$\begingroup\$ @lonelyelk I don't think so. If you look at the spec, 8 is the right solution. \$\endgroup\$
    – G B
    Dec 22, 2021 at 4:44
  • \$\begingroup\$ I see! I was reading the problem wrong. \$\endgroup\$
    – lonelyelk
    Dec 22, 2021 at 9:25
3
\$\begingroup\$

TypeScript Types, 764 bytes

//@ts-ignore
type a<T,N=[]>=T extends N["length"]?N:a<T,[...N,0]>;type b<M,J=M[0|1]>=J extends J?[a<Extract<M,[{},J]>[0]>,a<J>]:0;type c<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type d<T,K=T extends T?keyof T[0]:0>=T extends T?[K]extends[keyof T[0]]?T:never:0;type e<f,g,h=0,i=[],j=[],k=g[number],l=k extends[infer A,infer B]?A extends B?A|h:h:0,>=g extends[infer Elf,...infer ElvesTail]?Elf[1]extends Elf[0]?c<Extract<f,[l,{}]>[1]>extends infer Job?e<Exclude<f,[{},Job]>,ElvesTail,l,[Job,j]extends[0,[]]?[...i,0]:i,[...j,[Job]extends[0]?[0,0]:[Job,[0]]]>:0:e<f,ElvesTail,h,i,[...j,[Elf[0],[...Elf[1],0]]]>:j extends 0[][]?i:e<f,j,h,i>;type M<m,n=[],o=never,p=[...n,[0,0]]>=m[0|1]extends Partial<n>["length"]?c<d<o>[1]>["length"]:M<m,p,o|[e<b<m>,p>,p]>

Try It Online!

Ungolfed / Explanation

// Convert a number literal to a tuple of equal length
type NumToTuple<T,N=[]> = T extends N["length"] ? N : NumToTuple<T,[...N,0]>

// Convert a manual (a union of number literal pairs)
// to a todo list (a union of [Prerequisites, Job])
type ManualToTodo<Manual, Jobs = Manual[0|1]> = Jobs extends Jobs ? [NumToTuple<Extract<Manual,[{},Jobs]>[0]>, NumToTuple<Jobs>] : 0

// Filter a union of tuples for those with the shortest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Filter a union of tuples for those with the longest first element
type LongestFirstEl<T, K=T extends T ? keyof T[0] : 0> = T extends T ? [K] extends [keyof T[0]] ? T : never : 0

// Repeatedly iterates over a list of elves, either incrementing its progress or assigning it a new job
type CalculateRestTime<
  // A union of [Prerequisites, Job]
  Todo,
  // The tuple of elves being iterated over.
  // Each elf is represented by [Job, TimeElapsed] if working, or [0, 0] if idle
  ElvesIter,
  // A union of finished jobs
  Done=0,
  // The number of steps elf #0 has rested
  RestCount=[],
  // The tuple of elves already iterated over
  ElvesAcc=[],
  /* Aliases */
  ElvesIterValues = ElvesIter[number],
  // The jobs that have been finished by later elves in the iteration 
  NewDone = ElvesIterValues extends [infer A, infer B] ? A extends B ? A | Done : Done : 0,
> = 
  // Get the first elf in ElvesIter
  ElvesIter extends [infer Elf, ...infer ElvesTail]
    // If this elf is finished or idle
    ? Elf[1] extends Elf[0]
      // Set Job to the first Job in Todo whose prerequisites have been met
      ? Shortest<Extract<Todo,[NewDone, {}]>[1]> extends infer Job
        ? CalculateRestTime<
          // Remove Job from todo
          Exclude<Todo, [{}, Job]>,
          ElvesTail,
          // Update Done
          NewDone,
          // If Job is empty and ElvesAcc is empty, increment RestCount
          [Job, ElvesAcc] extends [0, []] ? [...RestCount, 0] : RestCount,
          // Add this elf to ElvesAcc; if Job is empty, set this elf to [0, 0]; otherwise, set it to [Job, [0]]
          [...ElvesAcc, [Job] extends [0] ? [0,0] : [Job,[0]]]
        >
        // Unreachable
        : 0
      // Otherwise, increment this elf's progress
      : CalculateRestTime<
        Todo,
        ElvesTail,
        Done,
        RestCount,
        [...ElvesAcc, [Elf[0], [...Elf[1], 0]]]
      >
    // ElvesIter is empty. If all elves are idle,
    : ElvesAcc extends 0[][]
      // Return RestCount
      ? RestCount
      // Otherwise, iterate over the elves again
      : CalculateRestTime<Todo, ElvesAcc, Done, RestCount>

type Main<Manual, ElfCount=[], Results=never, NextElfCount=[...ElfCount, [0,0]]> =
  // If all jobs are less than ElfCount.
  Manual[0|1] extends Partial<ElfCount>["length"]
    // Return the best result
    ? Shortest<LongestFirstEl<Results>[1]>["length"]
    // Otherwise, add [RestTime, ElfCount] to the Results union
    : Main<Manual, NextElfCount,Results | [CalculateRestTime<ManualToTodo<Manual>, NextElfCount>, NextElfCount]>
```
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 138 135 bytes

≔⌈Eθ⌈ιηFη⊞θ⟦⊕ι⁰⟧Fη«⊞υ⁰≔E⊕η⁰ζ≔E⊕ι⁰εWΦ⊕狧ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«≔Eκ∨⌈EΦθ⁼λ§ν¹§ζ§ν⁰¦⁰δ≔§κ⌕δ⌊δκ⊞υ⁺⊟υ⌈⟦⁰⁻⌊δ§ε⁰⟧UMε⌈⟦λ⌊δ⟧§≔ζκ⁺κ⌊ε§≔ε⌕ε⌊ε§ζκ»»I⊕⌕υ⌈υ

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

≔⌈Eθ⌈ιη

Find the number of jobs.

Fη⊞θ⟦⊕ι⁰⟧

Add a dummy job 0 whose sole purpose is to come after all the other jobs, automatically accounting for the rest time at the end.

Fη«

Try up to as many workers as jobs.

⊞υ⁰

Start with 0 seconds of rest.

≔E⊕η⁰ζ

Start with no jobs started yet.

≔E⊕ι⁰ε

Start with no workers having done any jobs yet.

WΦ⊕狧ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«

Repeat while there are jobs that can be started.

≔Eκ∨⌈EΦθ⁼λ§ν¹§ζ§ν⁰¦⁰δ

Find the times at which those jobs can start, assuming a worker is free.

≔§κ⌕δ⌊δκ

Get the job that's next available.

⊞υ⁺⊟υ⌈⟦⁰⁻⌊δ§ε⁰⟧

If worker 0 is idle, add on the time to wait before the job can start to the seconds of rest.

UMε⌈⟦λ⌊δ⟧

Make all idle workers wait until this job can start. (This can mean that the worker doing the job which this job was dependent on ends up doing this job too.)

§≔ζκ⁺κ⌊ε

Mark this job as started by recording the job's finish time (which is also used to determine when a dependent job can start).

§≔ε⌕ε⌊ε§ζκ

Give this job to the first available worker and record the worker's finish time.

»»I⊕⌕υ⌈υ

Output the smallest number of workers needed to obtain the largest rest time.

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

Python3, 279 bytes:

f=lambda d,s,q:[len(q)]+([]if not q else f(d,(s:=s+[(i,q.pop(i))[0]for i in [*q] if q[i]==0]),{**{i:q[i]-1for i in q},**{b:b for a,b in d if all(i[0]in s for i in d if i[1]==b)and b not in q and b not in s}}))
g=lambda d:max(f(d,[],{a:a for a,b in d if all(j[1]!=a for j in d)}))

Try it online!

\$\endgroup\$
8
  • \$\begingroup\$ 87: Try it online! \$\endgroup\$
    – pxeger
    Dec 19, 2021 at 1:29
  • \$\begingroup\$ 78: Try it online! \$\endgroup\$
    – Neil
    Dec 19, 2021 at 9:02
  • 1
    \$\begingroup\$ 66: Try it online! \$\endgroup\$
    – Ezhik
    Dec 19, 2021 at 10:18
  • \$\begingroup\$ @Ezhik Thank you, updated the post. \$\endgroup\$
    – Ajax1234
    Dec 19, 2021 at 13:56
  • 1
    \$\begingroup\$ Fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 23:14
2
\$\begingroup\$

Pari/GP, 181 bytes

a->m=vecmax;l=n=m([m(b)|b<-a]);forvec(v=[[i,k=n^2]|i<-r=[1..n]],u=v-r;if(![v[b[1]]>u[b[2]]|b<-a],d=Vec(sum(i=1,n,(x^v[i]-x^u[i])/(x-1)));if(#d<k,l=m(d);k=#d,#d-k||l=min(l,m(d)))));l

Try it online!

Brute force. Extremely slow.

Let \$n\$ be the number of jobs. Loops over all tuples \$[v_1,\dots,v_n]\$, where \$i\le v_i\le n^2\$ (a better but longer upper bound would be \$n(n+1)/2\$). \$v_i\$ represents the ending time of job \$i\$, so the corresponding starting time is \$v_i-i\$. For each tuple, checks if it satisfies the graph.

Now we can write job \$i\$ as a polynomial \$x^{v_i-i}+\cdots+x^{v_i}\$. Let \$d\$ be the sum of these polynomials, with \$i\$ running from \$1\$ to \$n\$. Then the ending time of all the jobs is the degree of polynomial \$d\$, while the number of workers is the largest coefficient of \$d\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ lonelyelk's answer doesn't work (fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4), so both of your answers are also invalid. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 23:18
2
\$\begingroup\$

Rust, 151 110 85 426 bytes

|x:&[[_;2]]|{let(k,mut r)=(*x.iter().flatten().max()?,(0,!0));for c in 1..=k{let(mut u,mut x,[mut e,mut j])=(0,x.to_vec(),[vec![0;c],(0..=k).collect()]);while j.iter().any(|x|x>&0){for t in 0..e.len(){if j[e[t]]>1{j[e[t]]-=1}else{j[e[t]]=0;x.retain(|j|j[0]!=e[t])}}for p in 1..=k{if!e.contains(&p)&&j[p]>0&&x.iter().all(|b|b[1]!=p){for t in 0..e.len(){if j[e[t]]<1{e[t]=p;break}}}}if j[e[0]]<1{u+=1}}r=r.min((!u,c))}Some(r.1)}

Try it online!

  • -41 bytes by using iterators instead of recursion
  • -25 bytes by counting groups
  • +341 bytes by fully implementing workers to fix a new test case :(
\$\endgroup\$
1
  • \$\begingroup\$ Fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4. \$\endgroup\$
    – Bubbler
    Dec 20, 2021 at 23:16
1
\$\begingroup\$

Wolfram Language (Mathematica), 156 bytes

Min[Max@Total@IntegerDigits[2^#-2^(#-r),2,l+1]&/@Pick[{a,b}=#;s=Select[Range@Tr[r=Range[n=Max@#]]~Tuples~n,#r&&#[[b]]-b#[[a]]&],m=Max/@s,l=Min@m]]&

Try it online!

Brute force. Extremely slow.

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