# Shift Scheduling
```elixir
Mix.install(
[
{:guesswork, "~> 0.8"},
{:kino, "~> 0.14"},
{:kino_explorer, "~> 0.1.23"}
], consolidate_protocols: false)
```
## Shift Scheduling
```elixir
import Guesswork.Ast
require Explorer.DataFrame, as: DF
alias Guesswork.Ast.And
alias Guesswork.Ast.Fact
alias Guesswork.Ast.Assign
alias Guesswork.Ast.OneOf
alias Guesswork.Ast.Variable
alias Guesswork.Ast.Is
alias Guesswork.Answer.Result
```
Shift Scheduling is another interesting use case for logic programming.
It fits well since constraints are easily expressed in logic.
First we'll set up some basic data types to help run tests and display
the result using `Kino`.
This will clean up our logical statements by pushing the more standard elixir
statements out of the queries and into these modules.
```elixir
defmodule Shift do
@derive [Guesswork.Ast.Entity]
defstruct [:bartender, :barback, :waiter]
def new(bartender, barback, waiter) do
%__MODULE__{bartender: bartender, barback: barback, waiter: waiter}
end
def valid?(%__MODULE__{bartender: bartender, barback: barback, waiter: waiter}) do
bartender != barback and bartender != waiter and barback != waiter
end
def member?(%__MODULE__{bartender: bartender, barback: barback, waiter: waiter}, value) do
Enum.member?([bartender, barback, waiter], value)
end
def to_kino_row(shift, day) do
Map.merge(Map.from_struct(shift), %{day: day})
end
end
defmodule Schedule do
@derive [Guesswork.Ast.Entity]
defstruct [:monday, :tuesday, :wednesday, :thursday, :friday, :saturday, :sunday]
def new(monday, tuesday, wednesday, thursday, friday, saturday, sunday) do
%__MODULE__{
monday: monday,
tuesday: tuesday,
wednesday: wednesday,
thursday: thursday,
friday: friday,
saturday: saturday,
sunday: sunday,
}
end
def to_list(%__MODULE__{
monday: monday,
tuesday: tuesday,
wednesday: wednesday,
thursday: thursday,
friday: friday,
saturday: saturday,
sunday: sunday
}) do
[monday, tuesday, wednesday, thursday, friday, saturday, sunday]
end
def count_shifts(schedule, worker) do
to_list(schedule)
|> Enum.count(&Shift.member?(&1, worker))
end
defimpl Kino.Render do
def to_livebook(schedule) do
[:monday, :tuesday, :wednesday, :thursday, :friday, :saturday, :sunday]
|> Enum.zip_with(Schedule.to_list(schedule), &Shift.to_kino_row(&2, Atom.to_string(&1)))
|> Kino.DataTable.new(keys: [:day, :bartender, :barback, :waiter])
|> Kino.Render.to_livebook()
end
end
end
```
Here is our first attempt at the shift scheduling query.
First we precompute all the valid shifts using a `for` comprehension and a filter.
Then we use `OneOf`s and `is`es to build the query.
There are just two things to note.
First, is the use of the pin operator (`^`) to pull in a variable from outside the `term`.
Second, is how we are using `Enum.shuffle/1` to in the `OneOf`s.
If you try running the query without them it is much slower.
This is because the shifts need to be different on different days, so starting with
different lists of shift means we are more likely to hit shifts that don't conflict
with each other.
```elixir
possible_shifts = for bartender <- ["bob", "paul", "jenny", "chris"],
barback <- ["bob", "milly", "joe", "paul", "jenny"],
waiter <- ["milly", "jenny", "bob"] do
Shift.new(bartender, barback, waiter)
end
|> Enum.filter(&Shift.valid?/1)
answer = term(And.new([
# Assign shifts to days.
OneOf.new(monday, Enum.shuffle(^possible_shifts)),
OneOf.new(tuesday, Enum.shuffle(^possible_shifts)),
OneOf.new(wednesday, Enum.shuffle(^possible_shifts)),
OneOf.new(thursday, Enum.shuffle(^possible_shifts)),
OneOf.new(friday, Enum.shuffle(^possible_shifts)),
OneOf.new(saturday, Enum.shuffle(^possible_shifts)),
OneOf.new(sunday, Enum.shuffle(^possible_shifts)),
# Build the schedule.
is(schedule, fn monday, tuesday, wednesday, thursday, friday, saturday, sunday ->
Schedule.new(monday, tuesday, wednesday, thursday, friday, saturday, sunday)
end),
# The days specific workers aren't available.
is(false, fn monday -> Shift.member?(monday, "bob") end),
is(false, fn monday -> Shift.member?(monday, "chris") end),
is(false, fn tuesday -> Shift.member?(tuesday, "jenny") end),
is(false, fn thursday -> Shift.member?(thursday, "milly") end),
is(false, fn saturday -> Shift.member?(saturday, "bob") end),
# The limits on the number of shifts each worker wants.
is(true, fn schedule -> Schedule.count_shifts(schedule, "bob") >= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "joe") <= 2 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "chris") <= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "milly") <= 3 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "jenny") >= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "paul") <= 4 end),
]))
|> Guesswork.query(1)
```
Finally, We'll extract the schedule and use the `Kino` integration we built
previously to display it.
```elixir
{:bound, schedule} = answer.answer_sets
|> List.first()
|> get_in(["schedule"])
schedule
```
## More Idomatic Queries
Our last query works, but it isn't really ideal.
Instead of building in a script, we should be using a `Guesswork.KnowledgeBase`
to compile the information we need.
Furthermore, instead of using the `for` comprehension we really should be using
`Guesswork`'s own tools to calculate it, since building a valid shift is really
the same problem as building a valid schedule, just simpler.
Most of the changes below ar in the `ShiftKB`.
We establish which workers can do what using `deffact`, and then we can build a
rule that says a shift has one of each type of worker, and must statisfy
`Shift.valid?/1`.
The final query ends up looking a lot like our first query, only we use
`Guesswork.Ast.Fact`s to pull in the information the `ShiftKB` holds instead of
using the pin operator.
In fact, the query event acts very similarly to the first query; when `Guesswork`
sees repeated `Guesswork.Ast.Fact`s, it pulls a cached version of the stream that
has been partially evaluated in advance.
You should note that this is not done by default since precomputation on recursive
queries can lead to infinate searches.
```elixir
defmodule ShiftKB do
use Guesswork.KnowledgeBase.Collection
for worker <- ["bob", "paul", "jenny", "chris"] do
deffact bartender(^worker)
end
for worker <- ["bob", "milly", "joe", "paul", "jenny"] do
deffact barback(^worker)
end
for worker <- ["bob", "milly", "jenny"] do
deffact waiter(^worker)
end
defrule shift(shift) do
Fact.new(:bartender, [w1])
Fact.new(:barback, [w2])
Fact.new(:waiter, [w3])
Is.new(shift, [w1, w2, w3], &Shift.new/3)
Is.new(true, [shift], &Shift.valid?/1)
end
end
answer = Guesswork.query(term(
And.new([
# Assign shifts to days.
Fact.new(:shift, [monday]),
Fact.new(:shift, [tuesday]),
Fact.new(:shift, [wednesday]),
Fact.new(:shift, [thursday]),
Fact.new(:shift, [friday]),
Fact.new(:shift, [saturday]),
Fact.new(:shift, [sunday]),
# Build the schedule.
is(schedule, fn monday, tuesday, wednesday, thursday, friday, saturday, sunday ->
Schedule.new(monday, tuesday, wednesday, thursday, friday, saturday, sunday)
end),
# The days specific workerss aren't available.
is(false, fn monday -> Shift.member?(monday, "bob") end),
is(false, fn monday -> Shift.member?(monday, "chris") end),
is(false, fn tuesday -> Shift.member?(tuesday, "jenny") end),
is(false, fn thursday -> Shift.member?(thursday, "milly") end),
is(false, fn saturday -> Shift.member?(saturday, "bob") end),
# The limits on the number of shifts each worker wants.
is(true, fn schedule -> Schedule.count_shifts(schedule, "bob") >= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "joe") <= 2 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "chris") <= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "milly") <= 3 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "jenny") >= 4 end),
is(true, fn schedule -> Schedule.count_shifts(schedule, "paul") <= 4 end),
])
), 1, knowledge_base: ShiftKB, precompute_count: 25)
```
Finally, we can again extract the schedule and see the displayed table.
```elixir
{:bound, schedule} = answer.answer_sets
|> List.first()
|> get_in(["schedule"])
schedule
```
