# AoCG2021 Day 19: To Hire or To Fire

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

• Can we assume that the manual will be ordered by x in (x, y) as in all given test cases? Dec 19, 2021 at 10:03
• 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?
– Neil
Dec 19, 2021 at 11:53
• @Ezhik since this isn't my challenge, I'll ask Bubbler Dec 19, 2021 at 20:05
• @Ezhik and Neil, No and no. You can't assume anything other than those specified in the challenge. Dec 19, 2021 at 21:45
• @Neil 2 seconds with 3 workers. I guess I had to specify that the "rest" counts until all jobs are completed. Dec 20, 2021 at 21:46

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

• 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. Dec 20, 2021 at 23:18
• @Bubbler Fixed!
– G B
Dec 21, 2021 at 9:14
• 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 Dec 21, 2021 at 23:51
• @lonelyelk I don't think so. If you look at the spec, 8 is the right solution.
– G B
Dec 22, 2021 at 4:44
• I see! I was reading the problem wrong. Dec 22, 2021 at 9:25

# 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]>
$$$$


# Charcoal, 138 135 bytes

≔⌈Ｅθ⌈ιηＦη⊞θ⟦⊕ι⁰⟧Ｆη«⊞υ⁰≔Ｅ⊕η⁰ζ≔Ｅ⊕ι⁰εＷΦ⊕η‹§ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«≔Ｅκ∨⌈ＥΦθ⁼λ§ν¹§ζ§ν⁰¦⁰δ≔§κ⌕δ⌊δκ⊞υ⁺⊟υ⌈⟦⁰⁻⌊δ§ε⁰⟧ＵＭε⌈⟦λ⌊δ⟧§≔ζκ⁺κ⌊ε§≔ε⌕ε⌊ε§ζκ»»Ｉ⊕⌕υ⌈υ


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

≔⌈Ｅθ⌈ιη


Find the number of jobs.

Ｆη⊞θ⟦⊕ι⁰⟧


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.

Ｆη«


Try up to as many workers as jobs.

⊞υ⁰


Start with 0 seconds of rest.

≔Ｅ⊕η⁰ζ


≔Ｅ⊕ι⁰ε


ＷΦ⊕η‹§ζλ⬤θ∨§ζ§ν⁰⁻λ§ν¹«


Repeat while there are jobs that can be started.

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


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.

ＵＭε⌈⟦λ⌊δ⟧


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.

»»Ｉ⊕⌕υ⌈υ


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

# 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!

• Dec 19, 2021 at 1:29
• – Neil
Dec 19, 2021 at 9:02
• Dec 19, 2021 at 10:18
• @Ezhik Thank you, updated the post. Dec 19, 2021 at 13:56
• Fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4. Dec 20, 2021 at 23:14

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

• 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. Dec 20, 2021 at 23:18

# Rust, 15111085 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 :(
• Fails with input [(1, 2), (1, 3), (3, 4), (3, 5), (3, 6), (3, 7)], which should give 4. Dec 20, 2021 at 23:16

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