HomeAll PostsAuthorsMy ProfileAboutLogin
Luis Martinez
Nov 10, 2022

Designing Wordie: Wordie Clone DSA, Part I: Data Architecture

In this post I would like to discuss one approach to designing the popular mobile app game Wordie. 

As an introduction, let's first discuss the two major aspects in building a small application (such as Wordie): data architecture, and data implementation. 

Data architecture is the first aspect to consider as it provides you with the building blocks to build your app. Imagine you wanted to build a 20-stories building, and you start the construction process using whatever comes at hand without first gathering the required materials; you may end up with some kind of construction, but it would hardly be the original 20-stories building. The same way, before we start writing any code for our app, we need to gather the data structures (the building blocks) that will be required for developing the app. You may not have all of the required building blocks to build the whole thing, but you should have enough building blocks to start your building process with a strong foundation (also, a strong foundation allows us to develop apps that scale).

The second aspect, data implementation, refers to how we properly use our building blocks in the context of the development environment (React JS, in this case; but it could be VUE, or Angular, etc.). In this post, I will focus on data architecture; data implementation is discussed in the second post of this series. 

Ok, with this, let's take a look at an example of Wordie, in case you haven't seen the game before (or try it for yourself here): 

As you can see, the game consists of guessing a five-letters word in six tries. For each try, you get hints through the tiles color as whether the letter is in the correct position (green), misplaced (yellow), or not in the word at all (gray).

The first thought that came to my mind was, "I'm going to need to build a command-line interface (CLI) for taking user inputs". Since I was going to use React , I further thought,"Uh, I'm going to need a Node JS backend for the CLI to process the user inputs". Well, it turns out that you can process user inputs right from React, using JavaScript. Hence, we don't actually need a backend to perform the core functionalities of the app (we would need a backend if we wanted to store user results statistics or require user login). So, the app only needs a frontend, and we process user inputs right from the browser (more on this later). 

So the next step was to gather the app's data building blocks. Since I had been practicing Data Structures and Algorithms, I was purposefully looking to use what I had been learning to build the app. And it turned out that the final data model I came up with for the app was a direct result of the things I had been learning.

Let's start with the board, which is the major component of the app (the keyboard is an external dependency, and so, I'll not be covering the keyboard in this post). The board is a 6x5 grid (6 rows, and 5 columns), and we can model the board using a matrix. A matrix is a bi-dimensional array (an array whose values consist of arrays). Let's take a look at a JavaScript 6x5 matrix of empty strings:

let matrix = [
   ["", "", "", "", ""],    
   ["", "", "", "", ""],    
   ["", "", "", "", ""],    
   ["", "", "", "", ""],    
   ["", "", "", "", ""],    
   ["", "", "", "", ""]
]

Each row in the matrix contains 5 columns, and the value for each column is an empty string. Say that we want to place the letter "W" in the [5, 1] cell (row 6, column 2; cell values are zero-indexed); we would do the following:

matrix[5][1] = "W";

// which produces, matrix => 
[
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "W", "", "", ""]
]

Or, say we now want the last row to be "GRAPH", we would do

matrix[5][0] = "G";
matrix[5][1] = "R";
matrix[5][2] = "A";
matrix[5][3] = "P";
matrix[5][4] = "H";

// matrix => 
[
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["G", "R", "A", "P", "H"]
]

So, changing a given value of a matrix is a constant time operation (O(1)), as long as we know the row index and the column index before hand. 

In the game, the user cannot proceed to the next row until done with the current row. So in our above example of an initial matrix with empty strings, following the game rules, the "GRAPH" word would need to go on row 1 instead of row 6. The idea of processing inputs in the order of first appearance is related to the queue data structure. In a queue, values that come first are processed first. In JavaScript, we can represent a queue using an array (there is a formal way of representing queues, but it is out of scope for this post). Let's take a look at an example of a queue

let queue = [0,1,2,3,4,5]

The first value of the queue is 0, the second value is 1, and so on and so forth. In a queue, the first value is processed first, then the next value. Say we want to access the first value in the queue, and extract the first value from the queue, respectively; we would do 

let queue = [0,1,2,3,4,5]

// access first value in queue
const firstValue = queue[0];
// firstValue => 0
// queue => [0,1,2,3,4,5]

// extract (remove) first value from queue
const extracted = queue.shift();
// extracted => 0
// queue => [1,2,3,4,5]

const nextExtractedValue = queue.shift();
// nextExtractedValue => 1;
// queue => [2,3,4,5];

How is a queue related to the game? Well, we can use a matrix to represent the board, and we can use a queue to represent the order of row processing in the board, with the first value of the queue representing the current row being processed. So we can start the game by doing this

let rows = [0,1,2,3,4,5];

let board = [
   ["", "", "", "", ""], 
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""]
]

let current_row = rows[0];
// current_row => 0

We can access the current row in the board by calling board[current_row]. For the above example, accessing row 1 (index 0) would be board[current_row], which yields board[0], which yields ["", "", "", "", ""].When we are done with the first row, we can call rows.shift() to remove the row and proceed to the next row. We reinitialize the current row by calling current_row = rows[0], which will return 1 (as we had performed a rows.shift() before). 

The final major step is to access the next available position the user is to type in. To keep track of the next available position we use a pointer, which is an integer variable, like so

let current_position = 0;

So combining the matrix, the queue, and the pointer, we get the current row and the next available position to start the game:

let rows = [0,1,2,3,4,5];
let board = [
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
]

let current_row = rows[0];
let current_position = 0;

To access the next available position in the board, we call

board[current_row][current_position];

When the user types for first time, we'll process the first cell on row 1 (row index 0, column index 0) with whatever the user typed (assuming typed a letter). We will update the board matrix with the user input, and increase the current position pointer by 1

board[current_row][current_position] = "{userInput}"  //a letter

current_position = current_position + 1;

This way, the next time the user types we'll be at column 2 (column index 1). We'll rerun the two above lines, which will update the board with the second user input and move the next available position to column 3. Basically, with this set up, we can update the board matrix with the user input one letter at a time in the current row.

Now, what if the user presses the Backspace key (for deleting)? We need to run some logic before performing a deletion: we first decrease the current position by 1, and then delete the contents of the updated position:

current_position = current_position - 1;

board[current_row][current_position] = "";

There are some edge cases here though, such as, "What if the user presses the Backspace key when the pointer is at position 0?" Well, that's something that needs to be handled in the code using conditional statements. For this case, we would only allow Backspace processing only if the value for the current_position pointer is greater than 0 and less than or equal to 5:

// Basic logic for handling Backspace key
if(key === "BACKSPACE") {
   if(current_position > 0 && current_position <= 5) {
      current_position -= 1;
      board[current_row][current_position] = "";
   }
}

You might be wondering, "Where does the 5 come from in current_position <= 5?" Well, the last available position is column index 4 (the fifth letter in the current row). At this point, our pointer variable will increase to 5. So, if user types for backspace and pointer is value 5, that means we are going to delete the last letter in the current row. Therefore, as long as the pointer is at most 5, we can process that backspace input.

So far we have performed three major operations for the game:

  1. Update the board matrix (board[row_index][col_index] = "a letter")
  2. Access the current row in the board (board[rows[0]])
  3. Move the pointer to next available position (pointer = pointer + 1)

With these operations we can perform the initial processing of user input. Each of the above operations runs in constant time (O(1)) and, hence, using this combination of data structures allows us to handle individual user input in constant time, which is nice. 

Let us now introduce a dynamic way of generating the data structures we've discussed so far. Say we want an mxn matrix (m rows, n columns); we can use this code

let matrix = new Array(m).fill(0).map(() => new Array(n).fill(""))

And so, generating a 6x5 matrix with empty strings will be

let matrix = new Array(6).fill(0).map(() => new Array(5).fill(""))

To generate a queue with 6 values starting at 0 until index 5, we write

let queue = new Array(6).fill(0).map((val, index) => index);

The pointer stays the same, namely,

let pointer = 0;

When done with the current row, we call queue.shift(), and then we access the next row by calling board[queue[0]]. 

Processing a Word

To process a word, we need to run a loop, and compare each value of our board matrix for the current row with the value of the target word at the corresponding position; so if row 1 in our board contains "STACK", and the target word is "SLACK", we compare board[current_row][0] with target[0], and board[current_row][1] with target[1], and so forth. Here we can introduce an assertion matrix to keep track of whether the comparison for each letter was either a match, a miss, or a close, and we can use that matrix to add background color to the board after or while the word is being processed. The assertion matrix will be the same size as the board matrix, just that we are going to update the assertion matrix with codes, say (code 0 means missed, code 1 means close, and code 2 means match). An example of such an assertion matrix after processing row 1 with "STACK" as user input and "SLACK" for target word would be 

assertion_matrix = [
   [ 2,  0,  2,  2,  2],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""],
   ["", "", "", "", ""]
]

and we can use these codes to dynamically add CSS class names to our HTML code containing our board so the cells get color. Or even better, we can just use string codes (as opposed to numbers) in the assertion matrix and directly add those strings to the class names. 

So with this combination of data structures you can build a Wordie game, and also implement advanced features, such as adding placeholders and editing a specific cell in the current row. And, hey, Wordie Clone DSA contains all of these. 

Let's now move to user input detection.

Detecting User Input

In our React component, we can attach a keydown event listener on the HTML document. The most convenient way of doing this is in an useEffect hook. We also need to get a reference for the HTML document (the page where React is running) so we can have control of when we attach (or also detach) the event listener. So we do

// import statements...
const MyBoardComponent= () => {
  const page = useRef(null);
  const yourKeydownFunction = useCallBack((key) => {
     if(ALPHABET[key]) {
       // process the key; update your board matrix
     }
     // do more things
  },[anydependenciesinKeydownFunction])

  useEffect(() => {
    // makes sure event listener is only attached once
    if(!page.current) {
      page.current = document;
      page.current.addEventListener('keydown', yourKedownFunction, true);
    }
  },[yourKeydownFunction])

  return (
    // code for rendering board
  )
}
export default MyBoardComponent;

With this, you'll be able to detect any key the user presses on their device. 

You can find the full code that powers the board for Wordie Clone DSA in the components/Board.js file in the github repository for Wordie Clone.

You can play with Wordie Clone DSA at this link .

Happy coding!!!