1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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
|