NewGenSolver.fsx

#r "nuget: MathNet.Numerics.FSharp"
#r "nuget: Expecto"
#r "nuget: Expecto.FsCheck"

#time



module BigInteger =

    open System
    open MathNet.Numerics

    let fromInt (x : int) = bigint(x)

    let toInt (x : bigint) = int x



module Set =

    open System
    open MathNet.Numerics


    let calc op (s1 : Set<_>) (s2 : Set<_>) =
        Seq.allPairs s1 s2
        |> Seq.map (fun (x1, x2) -> x1 |> op <| x2)
        |> Set.ofSeq


    let gcd (xs : bigint seq) = 
        Euclid.GreatestCommonDivisor(xs |> Array.ofSeq)


    let lcm (xs : bigint seq) = 
        Euclid.LeastCommonMultiple(xs |> Array.ofSeq)



module Types =

    open System
    open MathNet.Numerics


    /// The minimal value in
    /// a `Range`. Can be inclusive
    /// or exclusive.
    type Minimum =
        | MinIncl of BigRational
        | MinExcl of BigRational


    /// The maximum value in
    /// a `Range`. Can be inclusive
    /// or exclusive.
    type Maximum =
        | MaxIncl of BigRational
        | MaxExcl of BigRational



    type Range =
        {   
            Minimum : Minimum option
            Multiples : bigint Set
            Delta : BigRational option
            Maximum : Maximum option
        }


    type Operators =
        | Mult
        | Div
        | Add
        | Subtr



module Operator =

    open Types

    let inline getOp op =
        match op with
        | Mult -> (*)
        | Div -> (/)
        | Add -> (+)
        | Subtr -> (-)



module Range =

    open System
    open MathNet.Numerics

    open Types



    let isBetween min max x =
        match min, max with
        | Some (MinIncl min), Some (MaxIncl max) -> min >= x && x <= max
        | Some (MinIncl min), Some (MaxExcl max) -> min >= x && x <  max
        | Some (MinExcl min), Some (MaxIncl max) -> min >  x && x <= max
        | Some (MinExcl min), Some (MaxExcl max) -> min >  x && x <  max
        | Some (MinIncl min), None               -> min >= x 
        | Some (MinExcl min), None               -> min >  x 
        | None,               Some (MaxExcl max) ->             x <  max
        | None,               Some (MaxIncl max) ->             x <= max
        | None, None -> true


    let create min max delta mults =
        { 
            Minimum = min
            Multiples = 
                match delta with
                | Some d ->
                    mults 
                    |> Seq.filter (fun x ->
                        x
                        |> BigRational.FromBigInt
                        |> ((*) d)
                        |> isBetween min max
                    )
                    |> Set.ofSeq
                | None -> Set.empty
            Delta = delta
            Maximum = max
        }


    let createFromIntMultiples delta mults =
        mults
        |> Seq.map BigInteger.fromInt
        |> Set.ofSeq
        |> create None None (Some delta) 

    let unrestricted = create None None None Set.empty


    let toSet (r : Range) = 
        match r.Delta with
        | None   -> Set.empty 
        | Some d ->
            r.Multiples
            |> Set.map BigRational.FromBigInt
            |> Set.map ((*) d)


    let scale up range n =
        match range.Delta with
        | None -> range
        | Some d ->
            {
                range with
                    Multiples =
                        range.Multiples
                        |> Set.map (fun x -> 
                            if up then x * n else x / n
                        )
                    Delta = 
                        let n = n |> BigRational.FromBigInt
                        if up then d / n else d * n
                        |> Some
            }

    let scaleUp = scale true

    let scaleDown = scale false

    /// filters out all r2 multiples that 
    /// cannot divide any of the r1 multiples
    let nonDivisible r1 r2 =
        r2.Multiples
        |> Set.filter (fun m2 ->
            r1.Multiples
            |> Set.exists (fun m1 -> m1 % m2 = 0I)
            |> not
        )


    let intersectWith r2 r1 =
        {
            r2 with
                Multiples = 
                    if r2.Multiples |> Set.isEmpty then r1.Multiples
                    else
                        r1.Multiples 
                        |> Set.intersect r2.Multiples 
                Delta =
                    if r2.Delta |> Option.isNone then r1.Delta
                    else
                        r2.Delta
                        // should check the same as r1
        }        


    let calc op (r3 : Range) (r1 : Range) (r2 : Range) =
        // scale r1 if division to make it 
        // divisible by r2
        let r1 =
            if op <> Div then r1
            else
                nonDivisible r1 r2
                |> Set.lcm
                |> scaleUp r1 

        match r1.Delta, r2.Delta with
        | Some d1, Some d2 ->
            let delta =
                match op with
                | Add | Subtr _ when d1 = d2 -> d2 
                | Mult | Div -> 
                    d1 |> (op |> Operator.getOp) <| d2
                | _ -> 
                    failwith (sprintf "cannot process") 

            let between x = 
                match r3.Delta with
                | None   -> true
                | Some d ->
                    x
                    |> BigRational.FromBigInt
                    |> ((*) d)
                    |> isBetween r3.Minimum r3.Maximum

            { 
                Minimum = r3.Minimum
                Multiples =
                    set [
                        for x1 in r1.Multiples do
                            for x2 in r2.Multiples do
                                match op with
                                | Mult  -> x1 * x2
                                | Div   -> if x1 % x2 = 0I then x1 / x2
                                | Add   -> x1 + x2
                                | Subtr -> if x1 - x2 > 0I then x1 - x2
                    ]
                    |> Set.filter between
                Delta = Some delta
                Maximum = r3.Maximum
            }
            |> intersectWith r3
        | _ -> 
            // Need to do min max calculations
            failwith "not implemented yet"


    let multiply = calc Mult

    let divide = calc Div

    let add = calc Add

    let subtr = calc Subtr



open System
open MathNet.Numerics
open Types


let testRange op r1Multiples r1Delta r2Multiples r2Delta =
    let r1 = r1Multiples |> List.map BigInteger.fromInt |> Range.create None None (Some r1Delta)
    let r2 = r2Multiples |> List.map BigInteger.fromInt |> Range.create None None (Some r2Delta)
    // r3 = r1 op r2
    let r3 = Range.calc op Range.unrestricted r1 r2

    let s1 = r1 |> Range.toSet
    let s2 = r2 |> Range.toSet

    let s3 = 
        let s3 = Set.calc (op |> Operator.getOp) s1 s2
        match op with 
        | Div ->
            // assume div is also discreet
            let d = r1Delta / r2Delta
            s3
            |> Set.filter (fun x ->
                (x / d).Denominator = 1I
            )
        | Subtr ->
            s3
            // negative values not allowed
            |> Set.filter (fun x -> x > 0N)
        | _ -> s3

    if r3 |> Range.toSet = s3 then printfn "pass set test"
    else
        printfn "failed set test"
        printfn "== Actual"
        r3
        |> Range.toSet
        |> Seq.iteri (fun i x ->
            printfn $"{i}. {x}"
        )
        printfn "== Expected"
        s3
        |> Seq.iteri (fun i x ->
            printfn $"{i}. {x}"
        )

    let test s act exp =
        printfn "test: %s" s
        if act.Delta= exp.Delta then printfn "pass delta test"
        else
            printfn "failed delta test"
            printfn "== Actual"
            printfn $"{act.Delta}"
            printfn "== Expected"
            printfn $"{exp.Delta}"

        if exp.Multiples
           |> Seq.forall (fun x -> act.Multiples |> Seq.exists ((=) x)) then 
           printfn "pass multiples test"
        else
            printfn "failed multiples test"
            printfn "== Actual"
            act.Multiples
            |> Seq.iteri (fun i x ->
                printfn $"{i}. {x}"
            )
            printfn "== Expected"
            exp.Multiples
            |> Seq.iteri (fun i x ->
                printfn $"{i}. {x}"
            )


    match op with
    | Mult  ->
        // r3 = r1 * r2
        // r1 = r3 / r2
        test "r1 = r3 / r2" (Range.calc Div r1 r3 r2) r1
        // r2 = r3 / r1
        test "r2 = r3 / r1" (Range.calc Div r2 r3 r1) r2 
    | Div   -> 
        // r3 = r1 / r2
        // r1 = r3 * r2
        test "r1 = r3 * r2" (Range.calc Mult r1 r3 r2) r1
        // r2 = r1 / r3
        test "r2 = r1 / r3" (Range.calc Div r2 r1 r3) r2 
    | Add   ->
        // r3 = r1 + r2
        // r1 = r3 - r2
        test "r1 = r3 - r2" (Range.calc Subtr r1 r3 r2) r1
        // r2 = r3 - r1
        test "r2 = r3 - r1" (Range.calc Subtr r2 r3 r1) r2 
    | Subtr -> 
        // r3 = r1 - r2
        // r1 = r3 + r2
        test "r1 = r3 + r2" (Range.calc Add r1 r3 r2) r1
        // r2 = r1 - r3
        test "r2 = r1 - r3" (Range.calc Subtr r2 r1 r3) r2 



testRange Mult [1;2;3] 2N [1;2;3] 3N 
testRange Mult [2;3;4] 2N [1;2;3] 3N 
testRange Mult [2;3;4] 2N [2;3;4] 3N 
testRange Mult [2;3;4] 2N [12;13;14] 3N 
testRange Mult [1..99] 2N [1..100] 3N 
testRange Mult [1;2;3] (1N/2N) [1;2;3] (1N/3N) 
testRange Mult [2;7;15] 2N [3;8;12] 3N 

testRange Div [1;2;3] 4N [1;2;3] 2N 
testRange Div [2;3;4] 2N [1;2;3] 3N 
testRange Div [2;3;4] 2N [2;3;4] 3N 
// fails
testRange Div [2;3;4] 2N [12;13;14] 3N 
testRange Div [1..100] 2N [1..99] 3N 
testRange Div [1;2;3] (1N/2N) [1;2;3] (1N/3N) 
// fails
testRange Div [6;7;15] 2N [3;8;12] 3N 

testRange Add [1;2;3] 4N [1;2;3] 4N 
testRange Add [2;3;4] 2N [1;2;3] 2N 
testRange Add [2;3;4] 2N [2;3;4] 2N 
testRange Add [2;3;4] 2N [12;13;14] 2N 
testRange Add [1..100] 2N [1..99] 2N 
testRange Add [1;2;3] (1N/2N) [1;2;3] (1N/2N) 
testRange Add [2;7;15] 2N [3;8;12] 2N 

testRange Subtr [2;3;4] 4N [1;2;3] 4N 
testRange Subtr [2;3;4] 2N [1;2;3] 2N 
testRange Subtr [3;4;5] 2N [2;3;4] 2N 
testRange Subtr [12;13;14] 2N [2;3;4] 2N 
testRange Subtr [2..100] 2N [1..99] 2N 
testRange Subtr [2;3;4] (1N/2N) [1;2;3] (1N/2N) 
// fails
testRange Subtr [2;7;15] 2N [13;18;112] 2N 

// fix for failing tests
let r1 = Range.createFromIntMultiples 2N [2;3;4] 
let r2 = Range.createFromIntMultiples 3N [12;13;14]

let r1' =
    Range.nonDivisible r1 r2
    |> Set.lcm
    |> Range.scaleUp r1 

r1 |> Range.toSet = (r1' |> Range.toSet)

Range.nonDivisible r1' r2 = Set.empty

testRange Div (r1'.Multiples |> Set.map int |> Set.toList) (r1'.Delta |> Option.get)
              (r2.Multiples  |> Set.map int |> Set.toList) (r2.Delta  |> Option.get)

Note:

let r1' =
    Range.nonDivisible r1 r2
    |> Set.lcm
    |> Range.scaleUp r1 

should probably be

let r1' =
    r2.Multiples
    |> Set.lcm
    |> Range.scaleUp r1 

to get all possible results. However is this needed in the context of GenSolver where: r3 = r1 / r2 and for example r3 = a * b and both a and b are incremental? Then r3 already has a fixed delta. In that case scaling shouldn't occur.

So, scaling is only relevant when the result is still undetermined and there is no other way to calculate the delta for the result.