type Config<'a> = 
    {
        neighbours: 'a -> seq<'a>
        gCost: 'a -> 'a -> float
        fCost: 'a -> 'a -> float
        maxIterations: int option
    }

let search<'a when 'a : comparison> start goal config : seq<'a> option =

    let rec reconstructPath cameFrom current =
        seq {
            yield current
            match Map.tryFind current cameFrom with
            | None -> ()
            | Some next -> yield! reconstructPath cameFrom next
        }

    let rec crawler closedSet (openSet, gScores, fScores, cameFrom) =
        match config.maxIterations with 
        | Some n when n = Set.count closedSet -> None
        | _ ->
            match List.sortBy (fun n -> Map.find n fScores) openSet with
            | current::_ when current = goal -> Some <| reconstructPath cameFrom current 
            | current::rest ->
                let gScore = Map.find current gScores
                let next =
                    config.neighbours current 
                    |> Seq.filter (fun n -> closedSet |> Set.contains n |> not)
                    |> Seq.fold (fun (openSet, gScores, fScores, cameFrom) neighbour ->
                        let tentativeGScore = gScore + config.gCost current neighbour
                        if List.contains neighbour openSet && tentativeGScore >= Map.find neighbour gScores 
                        then (openSet, gScores, fScores, cameFrom)
                        else
                            let newOpenSet = if List.contains neighbour openSet then openSet else neighbour::openSet
                            let newGScores = Map.add neighbour tentativeGScore gScores
                            let newFScores = Map.add neighbour (tentativeGScore + config.fCost neighbour goal) fScores
                            let newCameFrom = Map.add neighbour current cameFrom
                            newOpenSet, newGScores, newFScores, newCameFrom
                        ) (rest, gScores, fScores, cameFrom)
                crawler (Set.add current closedSet) next
            | _ -> None

    let gScores = Map.ofList [start, 0.]
    let fScores = Map.ofList [start, config.fCost start goal]
    crawler Set.empty ([start], gScores, fScores, Map.empty)

let isWall (x, y) =
    let bits = System.Convert.ToString(x*x + 3*x + 2*x*y + y + y*y + 1350, 2)
    bits |> Seq.filter ((=) '1') |> Seq.length |> fun x -> x % 2 = 1

let neighbours (x, y) =
    let found = seq [ (x+1, y); (x, y+1); (x-1, y); (x, y-1) ]
    found |> Seq.filter (fun (nx, ny) -> 
        nx >= 0 && ny >= 0 &&
        not <| isWall(nx, ny))

let gScore _ _ = 1.
let fScore (x, y) (gx, gy) = 
    sqrt ((float gx - float x)**2. + (float gy - float y)**2.)

// part 1
match search (1, 1) (31, 39) {neighbours=neighbours; gCost=gScore; fCost=fScore; maxIterations=None} with
    | Some path -> 
        printfn "%d" <| Seq.length path - 1
    | None -> printfn "0"

// part 2
let mutable count = 0
for i = 0 to 51 do
    for j= 0 to 51 do
        if i+j <= 52 && not (isWall(i, j)) && not (Set.contains (i,j) (Set.ofList [ (0, 51); (0, 52); (51, 0); (52, 0) ])) 
        then
            match search (1, 1) (i, j) {neighbours=neighbours; gCost=gScore; fCost=fScore; maxIterations=None} with
                | Some path -> 
                    if Seq.length path - 1 <= 50 then
                        count <- count + 1
                | None -> ()

printfn "%d" count