Packages
fixpoint
0.19.3
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/sum2.ex
defmodule CPSolver.Propagator.Sum2 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 arguments(args) do
Vector.new(args)
end
defp initial_state(args) do
{_idx, minimums, maximums, sum_min, sum_max} =
args
|> Enum.reduce({0, Map.new(), Map.new(), 0, 0}, fn var,
{idx_acc, mins_acc, maxes_acc,
sum_min_acc, sum_max_acc} ->
next_idx = idx_acc + 1
min = min(var)
max = max(var)
{next_idx, Map.put(mins_acc, idx_acc, min), Map.put(maxes_acc, idx_acc, max),
sum_min_acc + min, sum_max_acc + max}
end)
(unsatisfiable?(sum_min, sum_max) && fail()) ||
%{minimums: minimums, maximums: maximums, sum_min: sum_min, sum_max: sum_max}
end
@impl true
def variables([y | x]) do
[
set_propagate_on(y, :bound_change)
| Enum.map(x, fn x_el -> set_propagate_on(x_el, :bound_change) end)
]
end
@impl true
def filter(all_vars, nil, changes) do
filter(all_vars, initial_state(all_vars), changes)
end
def filter(vars, state, changes) when map_size(changes) > 0 do
updated_state =
Enum.reduce(changes, state, fn
{pos, domain_change}, state_acc ->
var = Propagator.arg_at(vars, pos)
update_state_impl(var, pos, domain_change, state_acc)
end)
(unsatisfiable?(updated_state) && fail()) ||
{:state, updated_state}
## TODO: cut variables according to new partial sums
end
def filter(vars, state, changes) when map_size(changes) == 0 do
(state && state) || initial_state(vars)
end
defp update_state_impl(var, pos, :min_change, %{sum_min: sum_min, minimums: mins} = state) do
new_min = min(var)
current_min = Map.get(mins, pos)
%{state | sum_min: sum_min + new_min - current_min, minimums: Map.put(mins, pos, new_min)}
end
defp update_state_impl(var, pos, :max_change, %{sum_max: sum_max, maximums: maxes} = state) do
new_max = max(var)
current_max = Map.get(maxes, pos)
%{state | sum_max: sum_max + new_max - current_max, maximums: Map.put(maxes, pos, new_max)}
end
defp update_state_impl(
var,
pos,
domain_change,
%{
sum_min: sum_min,
minimums: mins,
sum_max: sum_max,
maximums: maxes
} = state
)
when domain_change in [:fixed, :bound_change] do
fixed_value = min(var)
current_max = Map.get(maxes, pos)
current_min = Map.get(mins, pos)
%{
state
| sum_max: sum_max + fixed_value - current_max,
maximums: Map.put(maxes, pos, fixed_value),
sum_min: sum_min + fixed_value - current_min,
minimums: Map.put(mins, pos, fixed_value)
}
end
defp update_state_impl(_var, _pos, _domain_change, state) do
state
end
defp unsatisfiable?(sum_min, sum_max) do
sum_min > 0 || sum_max < 0
end
defp unsatisfiable?(%{sum_min: sum_min, sum_max: sum_max} = _state) do
unsatisfiable?(sum_min, sum_max)
end
defp fail() do
throw(:fail)
end
end