Grid Algorithms

This week… Dungeons & Dragons!

OK, not really D&D, but close. During my first mock interview with interviewing.io (a fantastic platform, by the way — check them out!) I was asked to solve a problem involving a board-game-like set-up, sort of like the well-known Dungeons & Dragons role-playing game. The exercise read something along the lines of given a numerical input, create a 2-dimensional map measuring the length and width of the input value (e.g., if the input is 5, we want a 5 X 5 grid with a total of 25 spaces). Next, randomly populate the board with 1 of 4 characters (‘M’, ‘t’, ‘#’, ‘ ’). The caveat? Monster characters cannot be adjacent or diagonal from each other.

I must admit I was pretty nervous. I hope clarity and confidence will come with time and practice but for now…

The grid I was asked to build was, in fact, an array of arrays with x amount of rows & x amount of columns (x being the input value). For example, given an input of 3, the generated grid should look like this:

I planned to:

1. Instantiate a new array with x number of nested arrays.
2. Randomly populate the columns of these arrays (or rows) with any one of the 4 given characters.
3. Loop through the individual rows to make sure Monster characters were not adjacent nor diagonal from one another.

After some feedback from my interview, I was challenged to think of a more optimal solution. Instead of looping through the entire grid more than once, why not create, populate, and check as the grid is being built? Also, do we really need to look left, for example, when were at the left-most column? How about up when were at the top-most row? Ready to accept the challenge, here’s what I came up with:

1) Define the exterior array or grid.

2) Create a while loop that will push x number of rows onto the said grid.

3) Set up two conditionals: one deals with row one, the other with rows 2 onward.

4) A second nested while loop takes care of populating each row. While row.length < input, generate a random number that will serve as the index when choosing a random character from the array of characters:

if (grid.length == 1) {
   while (row.length < input) {
      index = Math.floor(Math.random() * characters.length);
      ...
   }
}

5) A third nested while loop takes care of any adjacent Monsters. Starting at col 2 (index 1), if and as long as the randomly generated character is a Monster and so is the previous input [‘#’, ‘M’, ?], we want to go back to the drawing board to reassign character:

if (grid.length == 1) {
   ...
   while (
      row.length >= 1 &&
      characters[index] === "M" &&
      row[col - 1] === "M"
   ) {
      index = Math.floor(Math.random() * characters.length);
   }
   row.push(characters[index]);
   col++;
   ...
 }
}

6) If the chosen character is not a Monster, we simply push it into the row, remembering to increase row before moving on to the following index.

7) For rows two and up, we want to follow the same steps as above yet with a slight but important variation. Remember, Monsters cannot be diagonal from each other, and we now have previous rows to account for.

if (grid.length > 1) {
  let previousRow = grid[subArr];
  while (row.length < input) {
    index = Math.floor(Math.random() * characters.length);
    while (
      characters[index] === "M" &&
      ( previousRow[col + 1] === "M" ||
        previousRow[col - 1] === "M" ||
        previousRow[col] === "M" ||
        row[col - 1] === "M")
    ) {
      index = Math.floor(Math.random() * characters.length);
    }
    row.push(characters[index]);
    col++;
  }
  subArr++;
}

In addition to checking if the randomly generated character is a Monster, we also need to make sure that neither the previous character in the current row nor the characters to the top, top-left, nor top-right are also monsters. If any of these are also Monsters, then we need to generate another character randomly.

8. With these conditions in place, we should now be all set!

Although I failed this technical challenge, it was quite fun and interesting!

Have you encountered a similar challenge during a technical interview? How did you approach the problem? I’d love to hear about it!

As always, thanks for reading! 🐉