BFS: From Alice to Mendix

Theo Schutte
Mar 24 · 7 min read
Figure 0 Run, Alice! Before you lose the white rabbit out of your sight!

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.

Figure 1 How breadth first search works. Source: https://www.codingame.com/learn/BFS

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):

  1. Problem Statement
  2. Object Representation
  3. Solution Strategy
  4. Experimentation

On the ground, she finds strange numbers ranging from 1 to 16, see figure 2.

Figure 2 The labyrinth from the top view with x and y-axis. On each cell you see a number, what does it say?

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).

Figure 3 The node with Alice is the root. Can you already find the shortest path from Alice to Rabbit?

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.

Figure 4 For each cell, the distance is calculated to the root

Step 6: When all nodes are found by BFS, then from Rabbit, count the distance backward till you find Alice, see figure 5.

Figure 5 The shortest path from Rabbit to Alice highlighted in green. You probably already figured out the shortest path, didn’t you?

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.

Alice and the white rabbit united. Score 100%! I written out my JavaScript code, yanked it through the test cases and felt pride seeing the 100% score I achieved. My excitement raised, as I visualized a Mendix application from this challenge so that I could show off that I know BFS.

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.

Figure 6 How it now looks like in the Mendix application, where you can find this Labyrinth preconfigured. Click on one of the buttons in the top, Alice or Rabbit, and place them somewhere in the Labyrinth.

A template grid is great for two-dimensional arrays. In JavaScript, I use a 2D Array as a list of 4 other lists, containing 4 cells. In Mendix, I cannot save a list in a list. However, with adding x y coordinates to the Node entity, I achieved something similar. When you select a cell in the application, you will see its coordinates in white.

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.

Figure 7 Every cell is bordered

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.

Figure 8 Depending on the value, the position of the borders (walls) are calculated. Can you figure out which values are the basic values the other values are based on?

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.

What you could also do is have a go at solving the CodinGame challenge yourself or other CodinGame challenges in Mendix. Solving the puzzles of CodinGame in JavaScript helps me improve my problem-solving skills. It brings me patience, as I struggle with some still after several days. Solving the puzzles myself on paper, helps me understand the problem.

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.

Mendix Community

Theo Schutte

Written by

Courageous, curious and accepting rapid application developer at MxBlue, trying to make it on this tiny planet

Mendix Community

The community-sourced publication for low-code

More From Medium

More from Mendix Community

More from Mendix Community

Riding the Nashorn in Mendix

More on Low Code from Mendix Community

More on Mendix from Mendix Community

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade