Packages
fixpoint
0.8.42
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/all_different_fwc.ex
defmodule CPSolver.Propagator.AllDifferent.FWC do
use CPSolver.Propagator
@moduledoc """
The forward-checking propagator for AllDifferent constraint.
"""
@impl true
def reset(args, nil, _opts) do
{initial_unfixed_vars, initial_fixed_values} = initial_reduction(args)
%{unfixed_vars: initial_unfixed_vars, fixed_values: initial_fixed_values}
end
def reset(args, %{fixed_values: fixed_values, unfixed_vars: unfixed_vars} = _state, _opts) do
{unfixed_vars, delta, total_fixed} =
Enum.reduce(
unfixed_vars,
{unfixed_vars, MapSet.new(), fixed_values},
fn idx,
{unfixed_acc, delta_acc, total_fixed_acc} =
acc ->
case get_value(args, idx) do
nil ->
acc
value ->
{MapSet.delete(unfixed_acc, idx), add_fixed_value(delta_acc, value),
add_fixed_value(total_fixed_acc, value)}
end
end
)
{final_unfixed_vars, final_fixed_values} = fwc(args, unfixed_vars, delta, total_fixed)
%{unfixed_vars: final_unfixed_vars, fixed_values: final_fixed_values}
end
defp initial_reduction(args) do
Arrays.reduce(
args,
{0, {MapSet.new(), MapSet.new()}},
fn var, {idx_acc, {unfixed_map_acc, fixed_set_acc}} ->
{idx_acc + 1,
(fixed?(var) && {unfixed_map_acc, add_fixed_value(fixed_set_acc, min(var))}) ||
{MapSet.put(unfixed_map_acc, idx_acc), fixed_set_acc}}
end
)
|> elem(1)
|> then(fn {unfixed_vars, fixed_values} ->
fwc(args, unfixed_vars, fixed_values, fixed_values)
end)
end
@impl true
def arguments(args) do
Arrays.new(args, implementation: Aja.Vector)
end
@impl true
def variables(args) do
Enum.map(args, fn x_el -> set_propagate_on(x_el, :fixed) end)
end
@impl true
def filter(all_vars, state, changes) do
{unfixed_vars, fixed_values} =
if state do
{state.unfixed_vars, state.fixed_values}
else
initial_reduction(all_vars)
end
{updated_unfixed_vars, updated_fixed_values} =
filter_impl(all_vars, unfixed_vars, fixed_values, changes)
{:state, %{unfixed_vars: updated_unfixed_vars, fixed_values: updated_fixed_values}}
end
defp filter_impl(all_vars, unfixed_vars, fixed_values, changes) when is_map(changes) do
{new_unfixed_vars, new_fixed_values, all_fixed_values} =
prepare_changes(all_vars, unfixed_vars, fixed_values, changes)
fwc(all_vars, new_unfixed_vars, new_fixed_values, all_fixed_values)
end
defp prepare_changes(all_vars, unfixed_vars, previously_fixed_values, changes) do
Enum.reduce(
changes,
{unfixed_vars, MapSet.new(), previously_fixed_values},
fn {idx, :fixed}, {unfixed_vars_acc, fixed_values_acc, all_fixed_values_acc} = acc ->
if MapSet.member?(unfixed_vars_acc, idx) do
updated_vars = MapSet.delete(unfixed_vars_acc, idx)
fixed_value = get_value(all_vars, idx)
{updated_vars, add_fixed_value(fixed_values_acc, fixed_value),
add_fixed_value(all_fixed_values_acc, fixed_value)}
else
acc
end
end
)
end
defp fwc(all_vars, unfixed_vars, current_delta, accumulated_fixed_values) do
{updated_unfixed_vars, _fixed_values, new_delta} =
Enum.reduce(
unfixed_vars,
{unfixed_vars, current_delta, MapSet.new()},
fn idx, {unfixed_vars_acc, fixed_values_acc, new_delta_acc} ->
case remove_all(get_variable(all_vars, idx), fixed_values_acc) do
## No new fixed variables
false ->
{unfixed_vars_acc, fixed_values_acc, new_delta_acc}
new_fixed_value ->
{MapSet.delete(unfixed_vars_acc, idx),
MapSet.put(fixed_values_acc, new_fixed_value),
MapSet.put(new_delta_acc, new_fixed_value)}
end
end
)
updated_accumulated_fixed_values = MapSet.union(accumulated_fixed_values, new_delta)
if MapSet.size(new_delta) == 0 do
{updated_unfixed_vars, updated_accumulated_fixed_values}
else
fwc(all_vars, updated_unfixed_vars, new_delta, updated_accumulated_fixed_values)
end
##
end
## Remove values from the domain of variable
## Note: if the variable gets fixed at some point,
## we can stop by checking if the fixed value is already present in the set of values.
## If that's the case, we'll fail (duplicate fixed value!),
## otherwise we exit the loop, as there is no point to continue.
defp remove_all(nil, _values) do
false
end
defp remove_all(variable, values) do
Enum.reduce_while(
values,
false,
fn value, _acc ->
case remove(variable, value) do
:fixed ->
fixed_value = min(variable)
(MapSet.member?(values, fixed_value) && throw(:fail)) || {:halt, fixed_value}
_not_fixed ->
{:cont, false}
end
end
)
end
defp add_fixed_value(fixed_values, nil) do
fixed_values
end
defp add_fixed_value(fixed_values, value) do
(MapSet.member?(fixed_values, value) && throw(:fail)) ||
MapSet.put(fixed_values, value)
end
defp get_value(_variables, nil) do
nil
end
defp get_value(variables, idx) do
case get_variable(variables, idx) do
nil ->
nil
var ->
(fixed?(var) && min(var)) || nil
end
end
defp get_variable(variables, idx) do
(idx && Propagator.arg_at(variables, idx)) || nil
end
end