3 people like it.

# The roller problem solved with a Constraint Programming Solver (CPS)

This is the solution of a homework the son of a friend had to solve during homeschooling and he asked a couple of his friends on how to solve the following problem: Given a kickboard has three rolls and a city roller has two rolls we want to know *how many kickboards and how many city rollers are parked*. We know two things: * The sum of all the rolls combined is 37 * There are 15 rollers (kickboards and rollers) parked Now being a developer I wanted to solve it via programming. :-D I've used the Decider library which allows you to formulate and solve the problem as following.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: ``` ``````open Decider.Csp.Integer open Decider.Csp.BaseTypes let solve rolls rollers = let (==) left right = ExpressionInteger.(=)(left, right) let expr i = ExpressionInteger(i) let kickboards = VariableInteger("kickboards", 0, rollers) let cityrollers = VariableInteger("cityrollers", 0, rollers) let constraints: IConstraint list = [ ConstraintInteger(kickboards + cityrollers == expr rollers) ConstraintInteger(kickboards * expr 3 + cityrollers * expr 2 == expr rolls) ] let variables: IVariable list = [ kickboards cityrollers ] let state = StateInteger(variables, constraints) match state.Search() with | StateOperationResult.Solved -> Some {| Kickboards = kickboards.Value Cityrollers = cityrollers.Value |} | _ -> None solve 37 15 // val it : {| Cityrollers: int; Kickboards: int |} option = // Some { Cityrollers = 8 // Kickboards = 7 } ``````
namespace Decider
namespace Decider.Csp
namespace Decider.Csp.Integer
namespace Decider.Csp.BaseTypes
val solve : rolls:int -> rollers:int -> {| Cityrollers: int; Kickboards: int |} option
val rolls : int
val rollers : int
val left : ExpressionInteger
val right : ExpressionInteger
Multiple items
type ExpressionInteger =
inherit Expression<int>
new : integer:int -> ExpressionInteger + 1 overload
member Equals : obj:obj -> bool
member Evaluate : Func<ExpressionInteger, ExpressionInteger, int>
member EvaluateBounds : Func<ExpressionInteger, ExpressionInteger, Bounds<int>>
member GetHashCode : unit -> int
member GetUpdatedBounds : unit -> Bounds<int>
member Integer : int
member IsBound : bool
member Left : Expression<int>
member Propagate : enforceBounds:Bounds<int> * result:ConstraintOperationResult -> unit
...

--------------------
ExpressionInteger(integer: int) : ExpressionInteger
ExpressionInteger(left: Expression<int>, right: Expression<int>) : ExpressionInteger
val expr : (int -> ExpressionInteger)
val i : int
val kickboards : VariableInteger
Multiple items
type VariableInteger =
inherit ExpressionInteger
new : name:string * elements:IList<int> -> VariableInteger + 1 overload
member Backtrack : fromDepth:int -> unit
member Clone : unit -> IVariable<int>
member CompareTo : otherVariable:IVariable<int> -> int
member Domain : IDomain<int>
member GetUpdatedBounds : unit -> Bounds<int>
member Instantiate : depth:int * result:DomainOperationResult -> unit + 1 overload
member Instantiated : unit -> bool
member InstantiatedValue : int
member IsBound : bool
...

--------------------
VariableInteger(name: string, elements: System.Collections.Generic.IList<int>) : VariableInteger
VariableInteger(name: string, lowerBound: int, upperBound: int) : VariableInteger
val cityrollers : VariableInteger
val constraints : IConstraint list
type IConstraint =
member Check : result:ConstraintOperationResult -> unit
member Propagate : result:ConstraintOperationResult -> unit
member StateChanged : unit -> bool
type 'T list = List<'T>
Multiple items
type ConstraintInteger =
inherit ExpressionInteger
new : expression:Expression<int> -> ConstraintInteger
member Check : result:ConstraintOperationResult -> unit
member Propagate : result:ConstraintOperationResult -> unit
member StateChanged : unit -> bool

--------------------
ConstraintInteger(expression: Expression<int>) : ConstraintInteger
val variables : IVariable<int> list
type IVariable<'T> =
inherit IComparable<IVariable<'T>>
member Backtrack : fromDepth:int -> unit
member Clone : unit -> IVariable<'T>
member Instantiate : depth:int * result:DomainOperationResult -> unit + 1 overload
member Instantiated : unit -> bool
member InstantiatedValue : 'T
member Name : string
member Remove : value:'T * result:DomainOperationResult -> unit + 1 overload
member SetState : state:IState<'T> -> unit
member Size : unit -> 'T
member ToString : unit -> string
Multiple items
val int : value:'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
val state : StateInteger
Multiple items
type StateInteger =
new : variables:IEnumerable<IVariable<int>> * constraints:IEnumerable<IConstraint> -> StateInteger
member Backtracks : int with get, set
member Constraints : IList<IConstraint> with get, set
member Depth : int with get, set
member OptimalSolution : IDictionary<string, IVariable<int>> with get, set
member Runtime : TimeSpan with get, set
member Search : unit -> StateOperationResult + 1 overload
member SearchAllSolutions : unit -> StateOperationResult
member SetConstraints : constraints:IEnumerable<IConstraint> -> unit
member SetVariables : variableList:IEnumerable<IVariable<int>> -> unit
...

--------------------
StateInteger(variables: System.Collections.Generic.IEnumerable<IVariable<int>>, constraints: System.Collections.Generic.IEnumerable<IConstraint>) : StateInteger
StateInteger.Search() : StateOperationResult
StateInteger.Search(optimiseVar: IVariable<int>, timeOut: int) : StateOperationResult
type StateOperationResult =
| Solved = 0
| Unsatisfiable = 1
| TimedOut = 2
field StateOperationResult.Solved: StateOperationResult = 0
union case Option.Some: Value: 'T -> Option<'T>
property VariableInteger.Value: int with get
union case Option.None: Option<'T>

### More information

 Link: http://fssnip.net/82G Posted: 3 years ago Author: toburger Tags: mathematics , cps , csp