I’ve written my F# code to solve Advent of Code Day 18 Part 1. While it seems to work fine with other simple demo inputs, it stuck with the following input

`################# #i.G..c...e..H.p# ########.######## #j.A..b...f..D.o# ########@######## #k.E..a...g..B.n# ########.######## #l.F..d...h..C.m# ################# `

Tehre is reference solution in Python which is correct and quick, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

I’ve tried with concurrency vs a queue, with a tree vs a grid/map (see my github history) but with no luck until now.

The principal part of the code is described below. It should fall under a breadth first search (BFS) algorithm.

Here is how the single step by which I elaborate the solution.

`let next (step:Step) (i:int) (solution: Solution) (fullGrid: Map<char,Map<char,Grid>>) : Solution = let branches = solution.tree.branches let distance = solution.tree.distance + branches.[i].distance let area = branches.[i].area //let newbranches, back, keys = match step with | SpaceStep -> failwith "not expected with smart grid" | KeyStep -> let keys = area :: solution.keys let grid = fullGrid.[area] let tree = grid2tree area distance keys grid {keys=keys; tree=tree} `

The fullGrid is supposed to contain the matrix of distances. The wrapping solver is simply a recursion or queue based version of the BFS.

`let findSolution (keynum:int) (solution: Solution) (fullGrid: Map<char,Map<char,Grid>>) : Solution option = let mutable solution_queue : queue<Solution> = MyQueue.empty solution_queue <- enqueue solution_queue solution let mutable mindistance : int option = None let mutable alternatives : Solution list = List.empty while (MyQueue.length solution_queue > 0) do let solution = dequeue &solution_queue let solution = {solution with tree = grid2tree solution.tree.area solution.tree.distance solution.keys fullGrid.[solution.tree.area]} let branches = solution.tree.branches if (branches = [||] ) then if solution.keys.Length = keynum then updateMin &mindistance &alternatives solution else match mindistance with | Some d when d < solution.tree.distance + (solution.tree.branches |> Array.map (fun t -> t.distance) |> Array.min) -> () | _ -> let indexes = [|0..branches.Length-1|] |> Array.sortBy(fun idx -> ((if isKey branches.[idx].area then 0 else 1) , branches.[idx].distance)) for i in indexes do if branches.[i].area = '#' then failwith "not expected with smart grid" else if branches.[i].area = Space then failwith "not expected with smart grid" else if (Char.IsLower branches.[i].area) then let solutionNext = next KeyStep i solution fullGrid if solutionNext.keys.Length = keynum then updateMin &mindistance &alternatives solutionNext else solution_queue <- enqueue solution_queue solutionNext else if (Char.IsUpper branches.[i].area) then failwith "not expected with smart grid" match alternatives with | [] -> None | alternatives -> alternatives |> List.minBy(fun a -> a.tree.distance) |> Some `