It’s that time of the year again where F#ers come together and write a bit about
what they enjoy.
I really enjoyed this years Advent of code and
while I only did a few of the exercises in F# I want to write about one
algorithm that helped out in quite a few of the exercises.
The Algorithm I’m talking about is the
A* algorithm.
Ok what is this
It’s a very general algorithm that helps you find an optimal path
in some kind of graph and so it’s often corelated with path-finding
algorithms.
And indeed one of the AoC days (day 13)
was all about finding the shortest Path in a maze.
Here is what the program I’m gonna show you here found for my input to this day:
#..###.#...#..#....##.#...#....#....#..#.#.##...## #O#..#.##.#######.#.#.####.##.###...##.#..#.###... #OO#.#.##.#....##...#..#.####.####...#..#..#..#.#. ##OO##.##.#..#...###.#.....#.....##.######....#..# ..#O##..########.#.#####...#..##.##.#.....##.###.# #..OOOOOOOOO.###.....#####.#####....#..##..#.###.. ###.##.####O..#.##....#..#.#..#.##.####.##....#### #.#..#.##.#O#.######..#.##..#.####..#.#######..### .###......#OO#..#..####.###..#..#.#.##..#.......## .####..###.#O##.#.#...#..#.#.##.##......#..####..# ..######.###O.###..##.#..###..##.#..##.####...#..# #..##..#.OOOO..###.#..###......#.#####..#.#...#... .......##O##.#.....#....#.##.#.###..#.#.####..##.# #####.#.#O##...###.##...##.#..#..##.##...#######.. ...##..##O#.###..#.###.#.##.#..#..##.#.....#..#### .#.###.#OO#...#.##...#..#.#..#.......##..#.##..##. ##..#..#O######.#####.#..###..##.###.####...#..... ....##.#O##..#...##.#.##.####..#.###....#...#..### ##...#..OOOO.#......#.....#.###...########.#####.# ###.#######O########.##.#.###.##...##..#.#.##..#.# .##.#...###O##OOO#.##.#..#.....##....#.##......#.# .##.#.....#OOOO#OO#.##.#.####.#.#.##..#.#####.##.# ...###.##.#.###.#O##.###...##..##.#.#......##.#..# .#..##.#..##..##.O.#.....#..##.#..#..##..#.##.#.## ###....#...###.#.O.##.#####.#..#..##.#####..###.#. .#.##.###.#..#.##O#.###..#..##.#####..........#.## .####..##..#.#.##OO#OOOOO#...#.#..#####.##.##.##.# ...#.#...#..##..##OOO###O##.##..#..##.#.##.#...#.# #..##.##..#.###.#.####.#O##.###.#.....#....#.#.### ##..#######..#..#.....##OOOO.#..######.##..#..#... .###..#......#..###.#.#.###OO#.....#.##.###.#..### #..##.#..########.###.###.##O##..#.#..###.#..#.##. .#...####....#.......#...#.#O#####.#.#...###.....# ...#....#..#.#.##..#.###..##O##...##.###.####.##.. ############.#.#####....#.#.OOOO#.##......#.#.#.## #..##..#....##..#....##.#.#..##O#....##.#.##..#.## #....#.##.#.#.#.#.###.#..######O#.###.#.##.#..#... ##.#..#.#.#.##..##..##.#.....#OO###.##...#.###.##. .##.#...#.##.#...#.#.######..#O#..##.#.#.#.#.##### #.#..###...#.##.##.##..##.#..#OO...#.#..##.....### .###.#.#.#.####.##..#.....##..##...#..#.####....## .###..##..#...#.....#..######..##.####...######..# ..#.#.#.#..##.#.##.#####..#.##.##.##.#....#...#...
The path it’ll find are the O
‘s – if you run code
(available here)
you will get it with some colors too.
By the way the solution runs in about 200ms on my system which without even
memoizing the wall-positions.
Day 13 was not the only day where you could use this algorithm – there where
many more (the famous Day11 comes to mind).
How does the algorithm work
It’s a basic breadth-first search algorithm which means that it will put nodes
it should look into in the future in a queue in such a way that it will first
serach in notes on the same level, which has the big advantage that these
way to search will find always find a shortest path first.
The problem is that node-count you have to look at a level can become
really huge fast.
This is where A* shines: it uses a heuristic (just a functions you have to
provide that will guess the distance/cost to the goal and then will first
look at the nodes where this is minimal.
As most of these algorithms it uses a visited
set as well to mark nodes
it already looked at (so you don’t revisit nodes if there are loops in the
graph).
some details
The algorithm as I choose to implement it uses this structure:
type private Runtime<'node when 'node : comparison> = { heuristic : 'node -> Score neighbours : 'node -> 'node seq isGoal : 'node -> bool distance : 'node -> 'node -> Score visitedNodes : Set<'node> openNodes : Priority<'node> gScores : Map<'node,Score> fScores : Map<'node,Score> cameFrom : Map<'node,'node> }
to keep track of the search.
heuristic
is the mentioned function provided by the user (based on the
problem) that should guess the distance/cost to the goal-node. It’s important
that you don’t overestimate the cost (better keep really conservative).
Because if you overestimate the algorithm will degenerate into a depth-first-
search and it’s likely that you don’t find a optimal solution (as the algorithm
stops at the first found node that is recognized as a goal).-
neighbours
create the neighbours (children) of a node and is user-provided
too – the algorithm uses this function to generate the next nodes. -
isGoal
is user-provided and is used to decide if a node is a goal (the
algorithm will stop at the first such node it finds) -
distance
is the final user-provided function – it calculates the distance
or cost between two nodes. The algorithm uses this only for a child and it’s
parent and in the example bellow it’s just constant 1. -
visitedNodes
is the set of nodes the algorithm already visited – no node in
here will be revisited. -
openNodes
is the set of nodes the algorithm can look at next. As stated
above it’s important that the algorithm can get the minimal of these based
on the heuristic and the cost of the path taken so far. This is why you should
really use a good priority queue/heap
here. For this example I just missused a F#-Map
structure which is not optimal
(it has noO(1)
access to the min. element) but it’s sufficient 😉 -
gScore
: keeps track of the costs on the path taken to a node so far – the
algorithm updates this when it finds better paths to a node as well. -
fScore
: is the acutal cost to a node plus the heuristic from that node to
the goal. The algorithm uses these for the priority queue inopenNodes
The algorithm is initialized by providing the needed function in this structure:
type Config<'node when 'node : comparison> = { heuristic : 'node -> Score neighbours : 'node -> 'node seq distance : 'node -> 'node -> Score isGoal : 'node -> bool }
You can find the complete implementation on github
and it’s a bit boring and really just the direct translation from the
pseudocode on Wikipedia.
Example Day13
So the complete example for day 13 works like this:
module Maze = let private bits n = let gen n = if n <= 0 then None else Some (n % 2, n / 2) Seq.unfold gen n let private oneBits n = bits n |> Seq.filter ( ( <> ) 0) |> Seq.length let isWall favNumber (x,y) = let nr = x*x + 3*x + 2*x*y + y + y*y + favNumber oneBits nr % 2 = 1 let private dist (x,y) (x',y') = abs (x'-x) + abs (y'-y) let private validCoord (x,y) = x >= 0 && y >= 0 let private neighbours favNumber (x,y) = [ (x-1,y); (x,y-1); (x+1,y); (x,y+1) ] |> Seq.filter (fun pos -> validCoord pos && not (isWall favNumber pos)) let findPath favNumber fromPos toPos = let config : Algorithm.Config<_> = { heuristic = fun pos -> dist pos toPos neighbours = neighbours favNumber distance = fun _ _ -> 1 isGoal = fun pos -> pos = toPos } in config |> Algorithm.aStar fromPos
If you want to have some fun take this algorithm/file and see if you can tackle
day 11 with it
hint: you should override the comparision/equals for your node to take
advantage of the strucutre of the problem – a simple heursitic is to count
everyhting on floor 4 as 0, everything on floor 3 as 1, everything on floor 2 as
2 and floor 3 as 3.
Happy Christmas everyone