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 no`O(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 in`openNodes`

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**

Pingback: F# Advent Calendar in English 2016 – Sergey Tihon's Blog()

Pingback: F# Weekly #52, 2016 – Sergey Tihon's Blog()