3 people like it.
Like the snippet!

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<int> 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 = 2
//               Kickboards = 1 }

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>

Previous Version Next Version Raw view Test code New version

More information

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