Packages
fixpoint
0.5.9
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/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
new([minus(y) | x])
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([y, x]) do
filter([y | x])
end
def filter(all_vars) do
{sum_min, sum_max} = sum_min_max(all_vars)
filter_impl(all_vars, sum_min, sum_max)
end
defp filter_impl(variables, sum_min, sum_max) do
case Enum.reduce_while(variables, {0, 0}, fn v, {s_min, s_max} ->
if sum_min > 0 || sum_max < 0 do
{:halt, :fail}
else
((removeAbove(v, -(sum_min - min(v))) == :fail ||
removeBelow(v, -(sum_max - max(v))) == :fail) && {:halt, :fail}) ||
{:cont, {s_min + min(v), s_max + max(v)}}
end
end) do
:fail ->
:fail
## Enforce idempotence: we'll run filtering until there's no changes
{new_sum_min, new_sum_max} ->
((new_sum_min != sum_min ||
new_sum_max != sum_max) && filter_impl(variables, new_sum_min, new_sum_max)) ||
:ok
end
end
defp sum_min_max(variables) do
Enum.reduce(variables, {0, 0}, fn v, {s_min, s_max} = _acc ->
{s_min + min(v), s_max + max(v)}
end)
end
end