Advent with a Star

All text and code copyright (c) 2016 by Carsten König. Used with permission.

Original post dated 2016-12-23 available at http://gettingsharper.de/2016/12/23/advent-with-a-star/

By Carsten König

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 search 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 its 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 actual 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

results matching ""

    No results matching ""