Packages
fixpoint
0.7.1
0.22.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/solver/constraints/propagators/sum.ex
defmodule CPSolver.Propagator.Sum do
use CPSolver.Propagator
import CPSolver.Variable.View.Factory
@moduledoc """
The propagator for Sum constraint.
Sum(y, x) constrains y to be a sum of variables in the list x.
"""
@spec new(Common.variable_or_view(), [Common.variable_or_view()]) :: Propagator.t()
def new(y, x) do
args = [minus(y) | x]
new(args)
|> Map.put(:state, initial_state(args))
end
defp initial_state(args) do
{sum_fixed, unfixed_vars} =
Enum.reduce(args, {0, MapSet.new()}, fn arg, {sum_acc, unfixed_acc} ->
var = Interface.variable(arg)
(var.fixed? && {sum_acc + Interface.min(arg), unfixed_acc}) ||
{sum_acc, MapSet.put(unfixed_acc, var.id)}
end)
%{sum_fixed: sum_fixed, unfixed_vars: unfixed_vars}
end
@impl true
def variables([y | x]) do
[
set_propagate_on(y, :domain_change)
| Enum.map(x, fn x_el -> set_propagate_on(x_el, :bound_change) end)
]
end
@impl true
def filter(args) do
filter(args, initial_state(args))
end
@impl true
def filter(all_vars, %{sum_fixed: sum_fixed, unfixed_vars: unfixed_vars} = _state) do
unfixed_vars =
Enum.filter(all_vars, fn v -> MapSet.member?(unfixed_vars, Interface.id(v)) end)
# unfixed_vars = Map.values(unfixed_vars)
{sum_min, sum_max} = sum_min_max(sum_fixed, unfixed_vars)
filter_impl(unfixed_vars, sum_min, sum_max)
end
defp filter_impl(variables, sum_min, sum_max) do
(unsatisfiable(sum_min, sum_max) && :fail) ||
case update_partial_sums(variables, sum_min, sum_max) do
{new_sum_min, new_sum_max} ->
## Enforce idempotence: we'll run filtering until there's no changes
((new_sum_min != sum_min ||
new_sum_max != sum_max) && filter_impl(variables, new_sum_min, new_sum_max)) ||
:ok
:fail ->
:fail
end
end
defp update_partial_sums(variables, sum_min, sum_max) do
Enum.reduce_while(variables, {sum_min, sum_max}, fn v, {s_min, s_max} ->
min_v = min(v)
max_v = max(v)
new_max = maybe_update_max(v, max_v, removeAbove(v, -(s_min - min_v)))
new_min = maybe_update_min(v, min_v, removeBelow(v, -(s_max - max_v)))
new_sum_min = s_min + new_min - min_v
new_sum_max = s_max + max_v - new_max
(unsatisfiable(new_sum_min, new_sum_max) && {:halt, :fail}) ||
{:cont, {new_sum_min, new_sum_max}}
end)
end
## Some optimization: if removeAbove/removeBelow don't change the domain,
## save the additional max/min call.
defp maybe_update_max(_var, current_max, :no_change) do
current_max
end
defp maybe_update_max(var, _current_max, _domain_change) do
max(var)
end
defp maybe_update_min(_var, current_min, :no_change) do
current_min
end
defp maybe_update_min(var, _current_min, _domain_change) do
min(var)
end
defp sum_min_max(sum_fixed, unfixed_variables) do
Enum.reduce(unfixed_variables, {sum_fixed, sum_fixed}, fn v, {s_min, s_max} = _acc ->
{s_min + min(v), s_max + max(v)}
end)
end
@impl true
def update(%{state: state, args: args} = sum_propagator, changes) do
new_state =
Enum.reduce(changes, state, fn
{var_id, :fixed}, %{sum_fixed: sum_fixed, unfixed_vars: unfixed_vars} = acc ->
if MapSet.member?(unfixed_vars, var_id) do
fixed_value = min(Propagator.find_variable(args, var_id))
new_sum = fixed_value + sum_fixed
new_unfixed_vars = MapSet.delete(unfixed_vars, var_id)
acc
|> Map.put(:sum_fixed, new_sum)
|> Map.put(:unfixed_vars, new_unfixed_vars)
else
acc
end
_, acc ->
acc
end)
Map.put(sum_propagator, :state, new_state)
end
defp unsatisfiable(sum_min, sum_max) do
sum_min > 0 || sum_max < 0
end
end