Gridlock

For a coding challenge that I did recently, I wrote a function that took in an input of a matrix of size N x N and output whether or not it was valid. In order for the matrix to be valid, it had to have each of the numbers up until N in both the columns and the rows. For example, this is one possible grid, which would be submitted as an array of arrays: [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]].

Since this satisfies the conditions, the function would return “VALID”.

Sudoku

Though I have never played it before, this problem was supposed to be designed to check sub-grids in a Sudoku game. Here are a couple of resources about Sudoku in case you would like to learn more.

Sudoku - New York Times Number Puzzles

Sudoku

Solution

This is my solution to the problem, which I will explain below!

function checkSubSudoku(matrix) {
let lengthOfMatrix = matrix.length;
let i;
let n;
let theIntegers = [];
let copyOfMatrix = [];
let areTheRowsValid;
let areArraysInMatrixSameSize;
let flattenedMatrix = matrix.flat();
let allAreIntegers;
//check to see whether all of the items in the arrays are positive integers
for(let a = 0; a < flattenedMatrix.length; a++){
if (Math.sign(flattenedMatrix[a])===1){
if (!allAreIntegers || allAreIntegers === true){
allAreIntegers = true;
}
else {
allAreIntegers = false;
}
}
else {
allAreIntegers = false;
}
}
if(!allAreIntegers){
return "INVALID"
}
else{
//check that the length of each of the arrays within the array are the same size
for(let w = 0; w < lengthOfMatrix; w++){
if(matrix[w].length === lengthOfMatrix){
if(!areArraysInMatrixSameSize || areArraysInMatrixSameSize === true){
areArraysInMatrixSameSize = true;
}
else{
areArraysInMatrixSameSize = false;
}
}
else{
areArraysInMatrixSameSize = false;
}
}
if(!areArraysInMatrixSameSize){
return "INVALID"}
else{
//set the variable theIntegers to see what numbers must be in each row and column of the matrix
for(n = 0; n < lengthOfMatrix; n++){
theIntegers.push(n+1);
}
theIntegers = parseInt(theIntegers.join(""))
//create a copy of the matrix in order to be able to sort without modifying the original array
for(let i = 0; i < lengthOfMatrix; i++){
let sliceOfMatrix = matrix.slice(i, i+1).flat();
let sortedSlice = sliceOfMatrix.sort((a, b)=>{
return a-b})
copyOfMatrix.push(sortedSlice);
}
//check each row of the copy to make sure it includes each number
for(let h = 0; h < lengthOfMatrix; h++){
if(parseInt(copyOfMatrix[h].join(""))===theIntegers){
if(!areTheRowsValid || areTheRowsValid === true){
areTheRowsValid = true;
}
else{
areTheRowsValid = false;
}
}
else{
areTheRowsValid = false;
}
}
//create an array of the columns
let copyForColumns = [];
for(let g = 0; g < lengthOfMatrix; g++){
let arrayToPush = [];
for (h = 0; h < lengthOfMatrix; h++){
arrayToPush.push(matrix[h][g])
}
copyForColumns.push(arrayToPush.sort((a, b)=> {return a-b}))
}
//check each column to make sure it includes all of the numbers
let areTheColumnsValid;
for(let d = 0; d < lengthOfMatrix; d++){
if(parseInt(copyForColumns[d].join(""))===theIntegers){
if(!areTheColumnsValid || areTheColumnsValid === true){
areTheColumnsValid = true;
}
else{
areTheColumnsValid = false;
}
}
else{
areTheColumnsValid = false;
}
}
//   return either "VALID" or "INVALID"
if(areTheRowsValid && areTheColumnsValid){
return "VALID";
}
else{
return "INVALID";
}
}
}
}

Damage Control

In the first couple of steps, I am doing damage control, anticipating edge cases. First, I check to see whether all of the items in the arrays are positive integers. I flatten the nested array to make one long array of items; then I check each of these items and use Math.sign() to determine whether they are positive integers. Math.sign() returns 1 if what is put in between the parentheses is a positive integer, -1 if what is placed there is a negative number, 0 if 0 is put there, and NaN if the value is anything else put in between quotation marks, for example “,”.

Fun fact: whether you put a number such as 91 in between quotation marks or not, like this: Math.sign(“91”) or this: Math.sign(91), it will return 1. The same goes for negative numbers, which will cause Math.sign to return -1. However, Math.sign(,) will throw an error, while Math.sign(“,”) will return NaN.

One of many example of why coding is a good time!

Math.sign()

If the current item in the loop through the flattened matrix passes the test, and if the variable areAllIntegers either has not been set yet or has been set to true, then it remains true, being set to true again. If areAllIntegers has been set to false, though, it remains false, since one non-positive integer or other value like a punctuation mark means that the whole grid is invalid. If the current item in the for loop does not pass the test of Math.sign(), then whether areAllIntegers has not been set yet, has been set to true, or has already been set to false, it will be set to false. Another way I could have done this would have been to use a while loop, so that once the variable is set to false, the loop exits, as none of the other values need to be checked.

Next, I see whether the input arrays within the matrix are all the same size. This follows a similar pattern to the first test, though it is on the non-flattened matrix. We don’t have to check the values within the arrays at this point; we just want to take the length of them. This follows the same pattern as the one above as far as setting the variable areArraysInMatrixSameSize to true or false goes.

If either of those tests fail (if either areArraysInMatrixSameSize or areAllIntegers have a value of false), the function exits, returning “INVALID”. Otherwise, it goes on to the next step.

Damage control

The Next Step: Checking the Rows

After that, I set the value of theIntegers by running a for loop that goes through the length of the input matrix starting from the counter of n = 0 and pushes n+1 into an array that is then joined and parsed into a number with parseInt. The result of this is that if the input matrix is [[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]], then theIntegers is 1234. This will be used as the point of comparison for what is in each of the rows and columns later on.

Next, I create a copy of the matrix. The reason that I do this is because I am going to be sorting each of the arrays in the matrix to check them against theIntegers to make sure that all of the numbers are included in each row. I do not want to alter the original input matrix, because I will also be checking the column in a separate step and can’t do that if the original input matrix is changed.

To create a copy of the matrix, I implemented another for loop starting at 0 and incrementing up until the length of the matrix. At each step of the for loop, I took a slice of the matrix — one of the arrays in the wrapping array, starting from the beginning of the matrix and going until the end.* I sorted it and pushed it into copyOfMatrix. So, copyOfMatrix ended up being not an exact replica of the original input matrix but a sorted version of it. This was so that in the next step of the function, I could check each sorted array to see if it included all of the requisite numbers.

*To review how to make a shallow copy of the matrix, I consulted a few websites. I am not sure which of them convinced me to try using the slice method, so here are links to all of them.

Deep copying Javascript Arrays

ES6 Way to Clone an Array 🐑 | SamanthaMing.com

How to clone an array in JavaScript

Because the coding challenge ended up being an exercise in my over-attachment to the for loop, I ran another for loop with a counter of zero incrementing up until the length of the matrix. Here is where I join the sorted array at the current location in the loop and parse it with parseInt before comparing it to theIntegers. If it matches theIntegers, then I go through the same true/false process of setting the variable areTheRowsValid as I did earlier in the first two conditions of the function. At the end of the loop, if areTheRowsValid is false, I could (and should) exit and return “INVALID”.

However, I did it a little less efficiently, going ahead and checking the columns before making any final determinations one way or another about the validity of this poor matrix which has already been through a lot.

The Columns

So! On to the columns!

Next, I create an array of arrays of columns. This is an act of imagination, since we don’t actually have a grid and have to imagine the nested arrays stacked on top of each other.

I return to the friendly for loop, but unfortunately for those of you keeping track of time complexity, this time it is a nested for loop. At the first level of the for loop, I initialize an empty array called arrayToPush. Then in the inner loop, I push matrix[h][g] into arrayToPush. What that means is that with a grid that looks like this:

matrix[h] will be the column, and [g] will represent the row. So, on the first loop through, matrix[h][g] will be matrix[0][0], then matrix[0][1], matrix[0][2], and matrix[0][3], or [1, 2, 3, 4]. After that first nested loop through, arrayToPush is pushed into the empty array copyForColumns, though it is sorted first.

The next nested loop through would be matrix[1][0], matrix[1][1], matrix[1][2], and matrix[1][3], or [2, 3, 4, 1]. At this point, you might notice that the rows and columns with the same index position are actually the same (e.g. row one is the same as column one, row two is the same as column two, etc.). I did not let that observation deter me, because, not being familiar with this type of problem beforehand, it was not clear to me whether that is the way it always ends up as a rule. If it is, though, then checking the columns would be unnecessary.

Report back to me if you would like to discuss or tell me what is what.

In the next step, I do the same thing that I did to check whether the rows were valid, looping through copyForColumns, joining each array, and parsing the array with parseInt before comparing that value to theIntegers.

In the final step, if both areColumnsValid and areRowsValid are true, then the function returns “VALID”. Otherwise, it returns “INVALID”.

And that is the end of my story about grids.

Gridlock