1 files changed, 80 insertions, 0 deletions
diff --git a/day13.fsx b/day13.fsx
new file mode 100644
index 0000000..a20a14a
--- /dev/null
+++ b/day13.fsx
@@ -0,0 +1,80 @@
+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