Coding challenge accepted - game board navigation using open and completed tasks FIFOs

I was involved in a couple of minor coding challenges that involved exploring a square space or board. I don't know any navigation algorithms so I implemented breadth first and depth first searching of the board using an open task list and a completed tasks list. Legal moves are added to the open task list. Each legal move is then checked to determine the following legal moves. Those are posted to the open task list where they are then picked up later and further explored.

Two of those challenges involved taking a specific number of steps. One asked how many squares could be touched in a specific number of steps. The other asked how many places you could end up in exactly a specific number of steps.

Sample `Dart` code can be found in this GitHub repo https://github.com/freemansoft/AdventOfCode-2023-Dart/tree/features/2023/solutions on the 2023 branch.

Video

Content

I've been calling these open and completed tasks but you can also think of it as a FIFO of moves with a  set of completed operations.  The two problems are

1. We have a rectangular game board
2. We want to know how many squares we can cover within a specific number of moves.
3. We want to know what squares we can end up on with an exact number of moves.

Assumptions: 

1. The field in the problem is too large to use recursion.  We have plenty of memory but not stack space for 1,000,000 calls.
2. We are going to use a similar technique for two similar problems.
3. We are going to track all our next steps on various paths by storing them in a FIFO as they are identified.

Algorithm

1. Create a task for the first square.  This bootstraps the process by giving us something to act on
2. Pull the first task/square from the open items FIFO.  Consider this the current square
3. Create a task for each possible square we can move to that is immediately adjacent to the current square. Put those tasks into the open tasks  FIFO
1. Ignore any task that has an exact match in the active or completed task sets. This truncates the exploration of nodes that were reached from more than one place.
4. Optionally can prune completed squares when the items stored in the completed set with some temporal issue like the # of steps that were taken to get there.
5. Repeat steps 2 and 3

Breadth First vs Depth First

• We can explore all the first steps and then all the next steps of the same count.  This is a breadth-first search that consumes all of the options at a given distance before moving on to the next depth/step.
• We can explore all the way down from a first state to an end state and then explore the peers of the last step and the peers of the steps above that. This is a depth-first calculation that threads out all the way to the end before backing up and doing that again.

Implementation Comment

• Open Tasks as a FIFO is breadth-first
• Open Tasks as a LIFO is depth-first

The duplicate rejection process means that we search the Active Tasks and Completed Tasks stores every time we put a new square into the processing queue.  My Dart program was 20x faster when I implemented the Tasks stores using Sets instead rather than Lists when my task objects implemented equals() and hashCode() for the fields we dedupe against.

Four steps

The playing field on the left shows that we covered 5 squares when moving 4 squares to the right. The original square and the 4 squares we stepped in.

The playing field on the right shows where we would end up if we took exactly 4 steps.  Even numbers of steps results in possible landing places being every other step because we can always step back one and then out one again.   So a 4-step operation could generate results 2 and 4 steps away from the start point.

The left-hand diagram shows all the locations we could visit taking 4 steps in all directions.  The right -hand diagram shows all the locations we could end up on if we took exactly 4 steps.

This is a partial example of the first couple of rounds of stepping and step evaluations when looking for total square coverage. The table shows how we populate and consume the open task set as we move and fill the completed task set.  Duplicates, those that are to be processed or have already been completed, are ignored.

Our tasks contain just the row and column of the square being evaluated.

This is a partial example of the first couple of rounds of stepping and step evaluations. The table shows how we populate and consume the open task set as we move and fill the completed task set.  Duplicates, those that are to be processed or have already been completed, are ignored.

Our tasks contain the number of steps to get here plus the row and column of the square being evaluated.  This lets us move back over a square as long as it is part of a different step.

Most of these problems include impediments or restrictions on movement through squares. The evaluation table generates fewer open tasks because the blockers remove some of the options.  The table above had 8 open tasks by the end of this table while this one only has one.

Detours and Routing Squares

Squares can have different features that change how we travel through them.  Some force a direction change or split our travel into multiple directions. 

I created a definition for each space type that tells us how we leave a square based on the direction vector we came from.  Each square is bound to the definition for its square type.  When we enter a square, we can look at the 4 definitions and find the one that matches our entry delta (row-delta, col-delta).  That definition tells us all the ways we leave the square.   We add the outbound row and col delta to the current cell location to give us a list of target squares.

A pass-through square would let (-1,0) → (+1,0) and (+1,0) → (-1,0).   A right angle splitter could have two exits so (-1,0) could exit on →(0,-1) and →(0,+1). Both of the exits are posted as tasks to be processed separately later. 

Ex:  We enter square (3.3) from the left or (0,-1).  It is a splitter from that direction so the exit vectors are [(-1,0), (+1,0)]  going out the top and the bottom.  Add the square location to the exit vectors and we know we are entering [(3-1, 3+-), (3+1, 3+0)] or [(2,3), (4,3)].

Revision History

Created 2023/12