type Node<'T> = { Value : 'T; Next : Node<'T> option }         // 1

​

type Stack<'T>() =

    inherit System.Object()                                 // 2

​

    let mutable First : Node<'T> option = None                 // 3

    let mutable N = 0

​

    member x.Push item =

        let oldFirst = First

        First <- Some { Value = item; Next = oldFirst }     // 4

        N <- N + 1

        () 

​

    member x.Pop() =

        match First with                                     // 5

        | Some x -> 

            First <- x.Next

            N <- N - 1

            Some x.Value

        | None -> None

​

    member x.IsEmpty                                         // 6

        with get() = 

            match First with

            | Some _ -> false

            | None -> true

​

    member x.Size with get() = N

​

    override x.ToString() =

        let oldFirst = First

        let rec PrintLoop (node: Node<'T> option) =                // 7

            match node with

            | Some x -> 

                printfn "%A " x.Value

                PrintLoop x.Next

                ()

            | None -> ()

        PrintLoop oldFirst                                         // 8

        base.ToString()    

​

(* Your Domain definition *)

​

type Coordinate = ( int * int)

​

type Location = ( string * Coordinate )

​

type Bounds = ( int * int )

​

let AllLocations : Location list =

    ("Bristol" , (0,0)):: ("London", (200, 20)) :: ("Oxford",(180, 70))::("Birmingham",(130,120))::("Wolverhampton",(120,120))::("Tewkesbury",(10,100))::("Manchester",(10,200))::

    ("Carlisle",(30,300))::("Glasgow",(40,400))::("Edinburgh",(50,400))::[]

​

(* 

This section defines the problem.

You define six areas

1. A type to define a tuple solution e.eg  type Solution = (int * int)

2. A function to calculate an estimated value from a partial solution

3. A function to choose the lower of two estimates

4. A function to split this partial solution into other

   partial solutions and to load them in to the stack

5. An initial solution

6. An estimate for the initial solution

*)

​

type Solution = (Location option *  Location option * Location option * 

                 Location option *  Location option * Location option *

                 Location option *  Location option * Location option *

                 Location option * Location list)

type PartialSolution = Location option list

type NextChange = int

type Soln2 = (PartialSolution * NextChange)

​

let estimate solution = 

    (* First, deconstruct the solution *)

    let Some (a , b, c, d, e, f, g, h,i,j, unallocated) = solution

    (* Then calculate the estimate *)

    10

let compare newBestEstimateSoFar  bestEstimateSoFar =

    (* 

    The estimates don't need to be simple integers.  So

    this test could be replaced with something more complex.

    *)

   newBestEstimateSoFar < bestEstimateSoFar

let splitCalcs (stack : Stack<'T>)  solution =

    (* First, deconstruct this solution *)

    let (a , b, c, d, e, f, g, h,i,j, unallocated) = solution

    (* Then apply any constraints before creating new solutions *)

    match a with

    | None -> stack.Push solution

    | Some (locn,(x,y)) -> stack.Push solution

​

​

let initialSolution : Solution = 

    (Some ("London",(200,20)),  Some ("Bristol" , (0,0))   , Some ("Oxford",(180, 70)), Some ("Birmingham",(130,120)), Some("Wolverhampton",(120,120)), Some ("Tewkesbury",(10,100)), Some("Manchester",(10,200)), Some ("Carlisle",(30,300)), Some ("Glasgow",(40,400)),  Some ("Edinburgh",(50,400))  , [])    

​

let initialEstimate = 1 + (estimate initialSolution)

​

(* 

None of the code below needs changing.  It is completely generic

*)

let  chooseLowerEstimate thisEstimate bestEstimate = 

     match (compare thisEstimate bestEstimate) with

     | true -> (thisEstimate, true)

     | false -> (bestEstimate, false)

let rec minimise (stack: Stack<'T>) bestSolutionSoFar bestEstimateSoFar =

    let topSolution = stack.Pop()

    // printfn "%A" stack.Size

    match topSolution with

    | None -> ( bestSolutionSoFar, bestEstimateSoFar )

    | Some solution -> 

        let thisEstimate = estimate solution                    

        let (newBestEstimateSoFar, newIsBetter) =

            chooseLowerEstimate thisEstimate bestEstimateSoFar

        match  (newIsBetter) with             

        | true -> 

            splitCalcs stack solution  (* Split solution and add to srack *)

            minimise stack solution newBestEstimateSoFar

        | false ->

            minimise stack bestSolutionSoFar bestEstimateSoFar

​

(*

The following code kicks off the evaluation.  There should be no need to change it

*)

let stak = Stack<Solution>()

stak.Push(initialSolution)

let bestSolution = minimise stak initialSolution initialEstimate

printfn "%A " bestSolution