The Advent of Code is a global programming challenge to solve 25 puzzles each year in December. Alteryx Community members solve these puzzles in Designer and share solutions to earn badges. This article is part of a blog series that shares advanced Alteryx problem-solving techniques for these challenges and more!
Introduction
One of the great benefits of Alteryx is that it hides complex code behind a collection of colorful tools that can easily be placed onto the canvas and connected in hundreds of ways to transform your input into the desired output. That being said, there are still benefits that come from having an understanding of programming fundamentals and algorithms. A well-developed algorithm, after all, is essentially just a clever way to solve a problem efficiently. During the Advent of Code 2024, Day 18’s problem, two different algorithms were needed to achieve the optimal solution: Breadth First Search (BFS) to solve each maze and Binary Search to find the first unsolvable maze.
Problem Summary
I appreciate the effort that Eric Wastl, the creator of Advent of Code, puts into crafting a story for each of the problems. For Day 18, we are trapped inside the memory of a computer with bytes falling down on top of us, and we need to try to escape as quickly as we can. It turns out we are on a 71x71 grid, starting at coordinates (0,0), and our goal is to get to the point (70, 70). Each byte takes up a single point on the grid, becoming an obstacle we must navigate around to get to our destination.
Our puzzle input is the grid location of each obstacle in the order that it will appear, and our goals are:
Part 1: Find the fewest moves needed to escape after the first 1024 bytes have blocked our path
Part 2: Determine which byte is the first to block our way so that we can no longer escape!
Source: memegenerator.net
Solving a Maze
We won’t be able to make any progress on this problem until we are able to find the shortest distance between both corners of the grid, which I will henceforth refer to as a maze since we will have obstacles to navigate around. At first this can seem like a daunting task. There are many possible paths to take, and checking all possibilities would be time-consuming and inefficient. Instead, imagine we took a large bucket of water and poured it out at the start of the maze. The water would spread out in all directions, flooding the space, until eventually, the first wave would reach the exit (assuming it can be reached at all). This is the foundation for the Breadth First Search algorithm, which is technically defined as:
A graph traversal (or maze solving) algorithm, in which all of a node’s nearest neighbors are visited before visiting their nearest neighbors
That nearest neighbor search will continue until every point in the maze has been visited that can be visited. The true power of this algorithm is achieved when you realize that you never need to visit a position that’s already been visited before since that will never yield the shortest possible solution. It’s like walking in a circle before leaving the start of the maze; the circle only adds to the distance you walk.
Building a maze solver using BFS on a simple 2D grid in Alteryx isn’t too hard if you already know your way around Designer. To start, you’ll need to build an Iterative macro where your iteration input tracks grid positions of the maze and the distance to get to each from the origin (initialize all distances to -1 except for the origin, which requires 0 steps to arrive at). Like so:
[Minimum Score] conveys the shortest distance from the starting point
Make sure that all positions that are occupied by obstacles are removed from the input, and we are ready to build the Iterative Macro:
First, get the immediate neighbors of all visited positions. In this problem, we can only move Left, Right, Up, or Down. The Generate Rows Tool can create all four cases for us, followed by the Formula Tool to increment the distance traveled by 1.
Next, we update the shortest distance for all previously unvisited points, making sure we union everything back together so that we don’t lose any data.
Finally, we format and output our data. We’ll know that we are done iterating when there are no new spaces visited on a single iteration (i.e. [Count] = 0 Filter above)
And that’s it. We can now solve a maze efficiently in Alteryx!
Binary Search - Intro
The second part of the problem then asks us how many obstacles must be placed before the maze becomes unsolvable. At first, you may have the urge to set up another iterative macro and place the obstacles one-by-one, checking to see if the maze is solvable using the fancy new macro we put together. Unfortunately, you’ll be waiting for a while because there are THOUSANDS of mazes to test. But what if I told you we could get to the same answer by checking only 12 mazes? That would be something! That’s the power of a binary search.
This algorithm only works on sorted lists by repeatedly cutting the list in half and disregarding the half that doesn’t meet our criteria. In our case, for example, if we check the maze formed using half of the obstacles, and it is solvable with our fancy macro, then we know that all prior mazes (which have fewer obstacles) must be solvable too. Similarly, if the halfway-point maze is blocked off, then adding more obstacles won’t serve to change anything as we still cannot get to the exit. Thus, in both cases we can disregard (and no longer waste precious computing resources checking) half of the mazes in our remaining list. But why stop there? We can cut the remaining half in half again and perform the same process as before on a smaller search space. Eventually we will only have one maze to check, which gives us our answer.
Binary Search - Alteryx
Now that we understand the binary search algorithm, let’s build it in Alteryx! First, we’ll need an Iterative macro to handle the successive halving of our search space and maze checking. The actual implementation of binary search is pretty simple and involves 3 components:
1. Dual Pointers
I labeled mine [Min] and [Max]. We will be iterating on these two values to perform the search. They store the lower and upper bounds, respectively, that define the section of our data that we are evaluating, and as we progress through our search, these two values will get closer and closer together, like a telescope zooming in on the answer.
The bottom Tool Container has the Macro Input Tool that we iterate on, which only contains one row with the current values of both [Min] & [Max]. The average of those two values gives us our third column [Mid], which marks the index of the maze that we will test, which is built in the top Tool Container
2. Evaluate the Mid-Point
The top Tool Container sets up and runs the BFS maze-solving algorithm that we set up earlier to determine if the maze is solvable. The bottom Tool Container gets the position of the last added obstacle, which will be our answer when we are ready to output.
3. Throw out Half or… Output!
We remove half of the mazes using an if statement: If the maze is still solvable, then only consider mazes with more obstacles than [Mid]. Otherwise, the current maze is blocked, so we only want to search mazes with fewer than [Mid] obstacles. When our two pointers overlap (a.k.a. are equal), then we’ve found the key maze, the first maze, that is unsolvable. The position of the final obstacle that constructed this maze is the answer to Part 2!
Conclusion
When implemented and utilized properly, these algorithms provide powerful and highly efficient solutions with use cases well beyond solving mazes: Logistics, IT Network analysis, Code Analysis, Load testing, etc. Every algorithm has its place, and these two are certainly worth keeping in your tool belt!
