Tag: slow

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