Let me guide you through my journey, how I went from solving a puzzle of CodinGame, to making a small application in Mendix, while I illustrate Breadth First Search. First, we go to the wonderland of Alice.
Alice followed the rabbit down the hole, into the mysterious wonderland of CodinGame. The rumors of this realm say that it is filled with strange programmers solving trivial programming challenges to try out all kinds of algorithms, such as Breadth First Search (BFS), see figure 1.
Alice is determined to not lose the white rabbit out of her sight. She runs after the white rabbit into the Labyrinth. The white rabbit has proven to be too fast. The moment she steps in, she lost the white rabbit. She stops for a moment, as she realizes just running after that white rabbit will get her in bigger trouble. She decides to approach this problem structurally. Alice grabs a pen and paper from her backpack and starts scribbling down all kinds of notes. She follows these for four problem-solving steps (see https://youtu.be/vEq6vmKIJwo):
- Problem Statement
- Object Representation
- Solution Strategy
On the ground, she finds strange numbers ranging from 1 to 16, see figure 2.
Alice is such a smart girl, that she finds a connection between the number of walls of the cell and the value on the ground. For a little girl, she is an extraordinary patient, solving this problem first in her notebook, before she rushes in to drag and drop all kinds of logic into a modeler.
1 Problem statement.
She thinks of her problem statement, using the formulation “Given input, I want to reach output”: Given this labyrinth with cells containing values for the walls, I want to find the shortest path between me and the rabbit.
2 Object Representation
Alice looks around and determines the object representation, which is like figuring out the domain model in Mendix. There is the Labyrinth, which is a collection of cells, we call nodes, containing a value ranging from 1 to 15. From the value, Alice is able to deduce to which nodes it is connected to. The Labyrinth is a graph. Node on x 0 and y 0 is connected to node x 0 and y 1. This means that Node 0,0 is the parent of Node 0,1. Because the graph is undirected, meaning that from node 0,0 you can go to node 0,1, but from node 0,1 you can also go back to node 0,0.
Alice is content with the entities Graph and Node.
3 Solution Strategy
She thinks of a strategy to approach this labyrinth. For finding the shortest path, she decides to use Breadth First Search.
Step 1: She first needs to connect all the nodes of the Labyrinth. With the value, she can calculate to which child the parent is connected to. 1 for Down Wall, 2 for Left Wall, 4 for Top Wall and 8 for Right Wall. Therefore, node 1,2 with value 5 has a top wall, 5–4 = 1 and a down wall 1–1 = 0.
Step 2: Start the BFS. The node she is standing on is the root, see figure 3. That node is added first to the queue, which is a list where all the nodes go into waiting to be processed by BFS. Think of a queue like a line where you are waiting to get in your favorite attraction of the theme park. The first that gets in the queue, is the first that gets out of the queue (and into the attraction) (First In First Out FIFO).
Step 3: While queue contains nodes, which are eagerly waiting to have their turn on BFS
Step 4: Take the node front in the queue and get its children
Step 5: For each child, set the distance to Alice and add it to the queue, see figure 4.
Step 6: When all nodes are found by BFS, then from Rabbit, count the distance backward till you find Alice, see figure 5.
Now Alice figured out her strategy, so she takes out her BFF, her Best Friend Forever, not to be confused with BFS. These kids are spoiled with gadgets, as she takes out a drone she can even program herself! She programs her BFF with her solution. The drone flies out. Calculates the shortest path from Alice to the Rabbit. Then returns to guide Alice to the white rabbit.
Alice and Rabbit are united. Who knows how long that lasts, before the white rabbit takes a look at his clock and sees he is running late, as always.
Connecting the input with the output in Mendix was not my biggest challenge, as I already figured out my pseudocode. My biggest challenge was how to present the input and the output to the user. How do I let the user configure the labyrinth? The Jabberwocky I had to defeat was getting the front-end dynamic. She was resting in the cave of the Template Grid.
I made some rough sketches, which looked similar to figure 6.
Making the template grid dynamic, where different cells have different borders, was the hardest part. You can click on a random cell and then click on a nearby cell. This results in those two cells connected and the wall between them removed. With CSS I could give the cells borders. However, I did not want to give all the cells the same borders, as shown in figure 7. The user had to have the possibility to remove walls.
When you remove walls in the application, the cells immediately get connected in the back end and the value, ranging from 1–15, gets updated. Covering this part, connecting the cells of the grid, was the hardest step of my pseudocode.
Besides, the borders had to be dynamic, depending on a value from 1 till 15, see figure 8.
To defeat this Jabberwocky, I reached into the app store and found my Vorpal sword: Dynamic Classes. For every number you see in figure 8, I had to have a different class. For example, I had class border10, with border-left and border-right. I succeeded in making the borders dynamic, but the Jabberwocky was not defeated yet. Only the contents of the cell got bordered, but not the whole cell.
I hid myself in the castle called Google, and there I found my next weapon: Inline-block. I added that to the container of the dynamic class and the Jabberwocky breathed her last fire.
However, the Jabberwocky did leave me wounded, as I did not manage to make the whole front-end dynamic. You see a 4 by 4 grid, height 4 and width 4. You can enter the height. However, you cannot enter the width, as that is fixed in the template grid.
With my Jabberwocky defeated and the Labyrinth was shown correctly, with all its dynamic borders, implementing step 2 till 6 were not that difficult anymore. All the nodes were also already associated correctly with each other, which made it easy to retrieve them and go through them one by one.
Have a play at it yourself. You can pick the preconfigured Labyrinth, which was used in this blog. Then click the Alice button to place Alice somewhere in the Labyrinth. Click the Rabbit button to place Rabbit somewhere. First calculate the distance, using BFS. Then you can find the shortest path to Rabbit, see step 6 of my pseudo-code. You can also choose to configure your own Labyrinth and try to make it difficult on the BFS I implemented.
Making an application out of it in Mendix is a whole other challenge. I already understand the problem, but do I truly understand it enough to shape it into an application, where the user can enter input and read the output. Making it in Mendix forces me to think about how I want to present the input and the output to the user. Making applications in Mendix is easy, which opens up a new view to look at the puzzle and to approach it.