Skip to content

Project Euler Problem 83

May 26, 2012

Although Project Euler Problem 83 seems further generalization of Problem 81 and Problem 82, solution is not based on any of those.

I came up with working solution in couple of minutes after reading thru A* Pathfinding for Beginners. The role of open list plays an F# PowerPack’s HashMultiMap carrying path cost as key and path end location as value. Closed list is a standard .NET HashSet carrying processed locations. We begin with placing left corner element with cost and coordinates into open list.

Each step is quite trivial – take one of the points with current minimal cost from open list; remove it from there; find all points reachable in one step from it; those of them that are not in closed list yet put into open list with newly calculated cost. If the just processed point is not a target point, place it into the closed list and repeat the step; otherwise finish, the cost associated with target point is the answer.

open System
open System.IO
open Microsoft.FSharp.Collections
open System.Collections.Generic

[<Literal>]
let SIDE = 80
let matrix: int[,] = Array2D.zeroCreate SIDE SIDE

let getData (path: string) =
    use sr = new StreamReader(path)
    let line, col = ref 0, ref 0
    while not sr.EndOfStream do
        col := 0
        sr.ReadLine().Split(',')
        |> Array.iter (fun x -> matrix.[!line, !col] <- int x; incr col)
        incr line

let findMinPath (matrix: int[,]) =
    let openList = new HashMultiMap<_,_>(HashIdentity.Structural)
    let closeList = HashSet<_>()
    openList.Add(matrix.[0, 0], (0,0))
    let rec step () =
        if openList.Count = 0 then failwith "No path exists"
        let minKey = openList.Fold (fun key _ acc ->
                if key < acc then key else acc) Int32.MaxValue
        let minElem = openList.FindAll minKey |> List.head
        let cost, (x,y) = minKey, minElem
        openList.Remove minKey
        [ (x-1,y); (x+1,y); (x,y-1); (x, y+1) ] // reachable from node
        |> List.filter (fun (x,y) -> x >= 0 && y >=0 && x < SIDE && y < SIDE)
        |> List.iter (fun (x,y) ->
            if not (closeList.Contains (x,y)) then
                    openList.Add(cost + matrix.[x, y], (x,y)))
        closeList.Add(x,y) |> ignore
        if (x,y) = (SIDE-1,SIDE-1) then cost else step()
    step()

let problem083() =
    getData @"..\..\..\Datafiles\Problem081.data" // same data P.81 & 82 & 83
    findMinPath matrix
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: