Optimizing the Lookup Function

An Inelegant Solution 

This is the current chip lookup function in BitNGo:

1 2 3 4 5 6 7 8 9 10 11

function check_boards(ltr, nm) //puts chips in played numbers { for(i=0; i<boards.length; i++) //checks each board { if(boards[i][ltr].includes(nm)) //if it includes the number... { boards[i][ltr][boards[i][ltr].indexOf(nm)] = "X"; //it marks it as "X" } } console.table(boards[0]); }

This is a terrible solution because in it, we check every board in game.

Let's say we have 8 boards playing, and only 2 of them contain the number that has been played. With this function, we would be unnecessarily, checking every board in the game. To avoid this, I have come up with the idea of indexing every board into an array, that way, we know which boards to look for.

The idea came to me a couple of days ago, but it was today in Anatomy class that I decided to start working in the concept. See, I'm not much of a memorizing person, so using the time from that class to actually work on problem solving was something that I very much enjoyed

This is the sketch that I did while not paying attention to my professor:

The last part is the most important one, since I actually give details on how the code should be there. I also wrote how the index should look like.

The boards_index array will contain 75 arrays inside of it. Each array is in an n position, and each board that contains said n number, will have its id inside said n position array. Let me explain more clearly:

The way it works is, for example, the board with the id number 0, may have the numbers 2, 5, 9, 10 and 12 in the letter B. So, we add the number 0 (the board id) inside the arrays of boards_index[2], boards_index[5], boards_index[9], boards_index[10], and boards_index[12]. We repeat the same process for each and every number in every table. This may take a little longer but in the long run, I believe it may be worth it.

Creating the Index

To create the index itself, we need to declare an array that contains 76 empty arrays inside itself. Technically, we only need 75, but since array numbers work in a weird way, we are only going to use the array 1 to 75, leaving the array 0 unused.

To create this index, we could technically do an ugly:

var boards_index = [[], [], [], [], ... and so on 76 times.

But we can be better than that, so, to do create said array, we just write the following lines of code:

1 2	var num_of_empty_arrays = 76; var boards_index = Array.from({ length: numEmptyArrays }, () => []);

That way we create the array we needed without actually writing "[]" 76 times.

Indexing the Boards Upon Creation

The new code for create_boards() looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

function create_boards() //creates a number of boards depending on number_of_boards { for(i = 0; i<number_of_boards; i++) { var used_numbers = []; //contains all the already used numbers in the board var id = i.toString(); //assigns an id to each board, starting from 0 var board = [[],[],[],[],[]]; //a subarray for each bingo letter board.unshift(id); //puts the id before the letters on the board console.table(board); for(l = 1; l<6; l++) { for(n = 0; n<5; n++) { var newnum = random(((15 * l - 15) + 1), (15 * l)); //creates a new number based on the letter while(used_numbers.includes(newnum)) { newnum = random(((15 * l - 15) + 1), (15 * l)); //if the number already exists in the table, another one is created } used_numbers.push(newnum); //pushes the new number inside the used_numbers array board[l].push(newnum); //pushes the new number inside its letter array boards_index[newnum].push(id); //pushes the board id into the boards index } } boards.push(board); //pushes the new board inside the boards array } for(i=0; i<boards.length; i++) //function that already puts a chip in the center of the board { boards_index[boards[i][3][2]].splice(boards_index[boards[i][3][2]].indexOf(i), 1); boards[i][3][2] = "X"; } }

It's pretty much the same, with a few additions.

boards_index[newnum].push(id); only puts the board id inside the index.

Important

The for loop at the end is in charge of not indexing the board id inside the number that belongs to the center of the board. Why? Well, because that number will be replaced with an "X", because most bingo boards don't have a number in the center. So, indexing that number would cause the program to later check for that number without it actually being there, causing lots of trouble; but the last for loop prevents that.

Looking for the played number

For the last part of this optimization routine, we need to fix the function that searches the number that has been played.

Turns out, it is actually pretty simple. I know it looks scary because of how much stuff is crammed inside these brackets, but trust me, it's not that hard once you get the hang of it.

The function looks like this:

1 2 3 4 5 6 7 8

function check_boards(ltr, nm) //puts chips in played numbers { for(i=0; i<boards_index[nm].length; i++) //for every board id inside the played number array... { boards[boards_index[nm][i]][ltr][boards[boards_index[nm][i]][ltr].indexOf(nm)] = "X"; //look at said number inside the board that we are currently searching } console.table(boards[0]); }

And there you go, that's it. We only go exactly where we need to go.

Let's visualize the difference in their functioning

Now, I'm going to illustrate how different each function works, and I'm going to demonstrate just how important the last changes are.

In game, a chip is played, let's say, I26.

The number 26 can only appear in 5 boxes in a bingo table (the boxes corresponding to the numbers between 16 and 30).

Of course, we can represent this mathematically:

Where N is the amount of boxes, and S is the possible numbers from which we can choose from.

So, with those probabilities, we know that around a third of boxes will contain a certain number.

This means, that in a group of 10 boards, only around 3 will contain a specific played number.

Let's visualize how the functions would work in a scenario like that.

Demonstration

So let's say we have 10 boards, and the number I26 is played. It is likely that around 3 boards will contain said number. But how can the computer look for those numbers and actually mark them? It needs an algorithm.

Older Function

In this function, we iterate through every single board, despite some of them not having the played number (26).

This results in 10 board lookups, as shown in the animation below:

Newer Function, with indexed boards

However, in this new function, we make use of the index that we created earlier to easily locate which boards are the ones containing the number that we are looking for (26).

Remember, this is not 100% accurate to how to function itself works; things such as the index array and the id of the boards are not exactly the same as in the code.

Here is the animation for said function:

As you can see, it is significantly fast in comparison to the older function.

Considering that in average, around a third of the total boards contain a played number, we can say that we skip the lookup time for 2/3 of the total boards in game.

So, with this new function, we decreased the computing time for looking up boards, by 66%.

This is not the end, as with this one function, I'm going to keep updating and optimizing the rest of the program, to decrease the computer power used as much as possible. Thanks for reading!

.