#@title $`$AND$\_$OR$\_$Scheduler$`$ implementation

class AND$\_$OR$\_$Scheduler$($object$)$:

def $\_\_$init$\_\_($self$)$:

# It is up to you to implement the initialization.

### YOUR SOLUTION HERE

self.tasks $=\{\}$ # Dictionary to store tasks and their dependencies

self.completed $=$ set$()$ # Set to store completed tasks

self.available $=$ set$()$ # Set to store tasks available for execution

def add$\_$and$\_$task$($self$,$ t$,$ dependencies$)$:

$"""$Adds an AND task t with given dependencies."""

### YOUR SOLUTION HERE

self.tasks$[$t$]=[$set$($dependencies$),$ 'and'$]$ # Store task with its dependencies and type

self.available.update$($dependencies$)$ # Update available tasks with dependencies

def add$\_$or$\_$task$($self$,$ t$,$ dependencies$)$:

$"""$Adds an OR task t with given dependencies."""

### YOUR SOLUTION HERE

self.tasks$[$t$]=[$set$($dependencies$),\text{'}$or$\text{'}]$ # Store task with its dependencies and type

self.available.update$($dependencies$)$ # Update available tasks with dependencies

@property

def done$($self$)$:

### YOUR SOLUTION HERE

return len$($self$.$tasks$)==$ len$($self$.$completed$)$

@property

def available$\_$tasks$($self$)$:

$"""$Returns the set of tasks that can be done in parallel.

A task can be done if:

$-$ It is an AND task, and all its predecessors have been completed, or

$-$ It is an OR task, and at least one of its predecessors has been completed.

And of course, we don't return any task that has already been

completed."""

### YOUR SOLUTION HERE

return self.available $-$ self.completed

def mark$\_$completed$($self$,$ t$)$:

$"""$Marks the task t as completed, and returns the additional

set of tasks that can be done $($and that could not be

previously done$)$ once t is completed."""

### YOUR SOLUTION HERE

self.completed.add$($t$)$ # Mark task as completed

added$\_$tasks $=$ set$()$

for task, details in self.tasks.items$()$: # Iterate through tasks

deps, task$\_$type $=$ details

if $(($task$\_$type $==$ 'and' and all$($d in self.completed for d in deps$))$ or

$($task$\_$type $==\text{'}$or$\text{'}$ and any$($d in self.completed for d in deps$)))$:

self.available.add$($task$)$ # Add task to available if all dependencies are completed

added$\_$tasks.add$($task$)$

return added$\_$tasks

def show$($self$)$:

$"""$You can use the nx graph to display the graph. You may want to ensure

that you display AND and OR nodes differently."""

### YOUR SOLUTION HERE

and$\_$tasks $=[$k for k$,$ v in self.tasks.items$()$ if v$[1]==$ 'and'$]$ # Extract AND tasks

or$\_$tasks $=[$k for k$,$ v in self.tasks.items$()$ if v$[1]==\text{'}$or$\text{'}]$ # Extract OR tasks

print$("$AND Tasks:", and$\_$tasks$)$

print$("$OR Tasks:", or$\_$tasks$)$

s $=$ AND$\_$OR$\_$Scheduler$()$

s$.$add$\_$and$\_$task$(\text{'}$a$\text{'},[\text{'}$b$\text{'},\text{'}$c$\text{'}])$

assert s$.$available$\_$tasks $==\{\text{'}$b$\text{'},\text{'}$c$\text{'}\}$

r $=$ s$.$mark$\_$completed$(\text{'}$b$\text{'})$

assert r $==$ set$()$

assert s$.$available$\_$tasks $==\{\text{'}$c$\text{'}\}$

r $=$ s$.$mark$\_$completed$(\text{'}$c$\text{'})$

assert r $==\{\text{'}$a$\text{'}\}$

assert s$.$available$\_$tasks $==\{\text{'}$a$\text{'}\}$

r $=$ s$.$mark$\_$completed$(\text{'}$a$\text{'})$

assert r $==$ set$()$

assert s$.$available$\_$tasks $==$ set$()$