diff options
author | Brian Chu <brianmchu42@gmail.com> | 2022-01-06 16:59:50 -0800 |
---|---|---|
committer | Brian Chu <brianmchu42@gmail.com> | 2022-01-06 16:59:50 -0800 |
commit | 6701539057f5e6790f46d602d0bfe7a7cb1317b3 (patch) | |
tree | cc0b7bbbc81f4460e4c618ead2178858ce6e1d55 | |
parent | b95d404ee6df9ae95a4ff214b376b3509568277e (diff) | |
download | AdventOfCode2016-6701539057f5e6790f46d602d0bfe7a7cb1317b3.tar.gz |
solution for day 13
-rw-r--r-- | day13.fsx | 80 |
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 |