Math.trunc() strips all decimal parts of a number and returns just the integer.
I got to about here:
// row sum can't repeat itself, digits must be 1-9
// col sum is same
// 3x3 areas are the same
function isValidSudoku(board: string[][]): boolean {
const validNums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for (let row = 0; row < 10; row++){
const rowSet = new Set()
for (let col = 0; col < 10; col++){
let val = board[row][col]
if (!validNums.includes(val))
if (rowSet.has(val)) return false
rowSet.add(val)
}
}
for (let row = 0; row < 10; row++){
const rowSet = new Set()
for (let col = 0; col < 10; col++){
let val = board[col][row]
if (!validNums.includes(val))
if (rowSet.has(val)) return false
rowSet.add(val)
}
}
return true
};And then got intimidated by checking which box I was “in”. Or actually, that language already gives a hint of how this might be done. More accurately, I was intimidated by checking whether the box contained a repeat of the current number.
In an answer later, I found that this nifty function does a good job at determining the box:
const boxNumber = 3 * Math.floor(i / 3) + Math.floor(j / 3)
Let’s see if I can understand this. There are 9 boxes total.
I guess one way to think about it is really just mapping the larger space of a 9x9 grid onto a 3x3 grid. With this logic, every column coordinate can be divided by 3 and floored.
Column 9 becomes column 3. Column 8 though, becomes column 2, which is no good.
Return 1
This is what I was starting with:
function isValidSudoku(board: string[][]): boolean {
// rows
for (let i = 0; i < board.length; i++){
board[i].reduce((total, num)=> {
return /^[1-9]$/.test(num) ? total + num : total;
}, 0)
}
};I guess my idea was to use a reducer to go through each row we get as the top level of our nested array, and to add everything up to make sure we didn’t, idk, have more than…45? The sum of 9+8+7+6…etc.
But that was silly. This is screaming for sets. Sets are always the best if they can be used, because their operations are all O(n)!
But the plus is that my very misguided approach did finally teach me how to use reducers. And a bit of regex.
Some more questions that came up:
Typing data structures in TS
const moo: Map<number, number> = new Map()
vs.
const moo = new Map<number, number>()
Conclusion: not sure which is better, but the first is more customary and I think both are okay. I’d look into it more but
Reviewing nullish coalescence vs Logical OR
|| is logical or, and ?? is elegantly named nullish coalescence.
Logical or is the more permissive of the two, which can make it less safe to use when the values of 0 or empty strings are on the table. If a value ends up being either of these, the righthand side of operator will be returned, which isn’t always ideal.
?? or nullish coalescence, will only return the right-hand operand (what a fancy word that I would like to use in a sentence some day!) if that value is spefically null or undefined.
The reason I wanted to use it was for a common case of Map.set() incrementation, where it’s important to treat the case where there is a map value differently than when not.
To my point, Map.get(6) + 23 will create a NaN if Map.get(6) doesn’t exist, since adding a number to undefined results in NaN
My favorite way I’ve found to deal with this so far (Map.get(6) ?? 0) + 4 but curious about other ways to handle this.
Woah! Of course! The .get() method on a map allows for a default value to be passed as a second argument! Amazing. So we can do someMap.get(6, 0) + 1. This is really what I’ve wanted all along.
Okay let’s try this…
function validSet(theSet, val, ignoreValue){
if (theSet.has(val) && val !== '.') return true
return false
}
function isValidSudoku(board: string[][]): boolean {
let result = true
let columnsSet = [...Array(9)].map(_=> new Set())
let squaresSet = [...Array(9)].map(_=> new Set())
// rows
for (let i = 0; i < board.length; i++){
const y = Math.ceil((i + 1)/3)
const rowSet = new Set()
const row = board[i]
row.forEach((col, index) => {
result = validSet(rowSet, col, '.')
rowSet.add(col)
// cols
const colSet = columnsSet[i]
result = validSet(colSet, col, '.')
// Tile by tile
let x = Math.ceil((index + 1)/3)
let tile = (y - 1) * 3 + x
const squareSet = squaresSet[tile-1]
result = validSet(squareSet, col, '.')
})
}
return result
};So…this took me an hour. With some major distractions! In many ways I’m proud of it, but it took me way too long. And! It doesn’t pass anyways. I had a pretty basic mistake, which was that I was overwriting the result variable. Fixed that:
function invalidSet(theSet, val, ignoreValue){
return theSet.has(val) && val !== '.'
}
function isValidSudoku(board: string[][]): boolean {
let columnsSet = [...Array(9)].map(_=> new Set())
let squaresSet = [...Array(9)].map(_=> new Set())
// rows
for (let i = 0; i < board.length; i++){
const y = Math.ceil((i + 1)/3)
const rowSet = new Set()
const row = board[i]
row.forEach((col, index) => {
if (invalidSet(rowSet, col, '.')) return false
rowSet.add(col)
// cols
const colSet = columnsSet[i]
if (invalidSet(colSet, col, '.')) return false
// Tile by tile
let x = Math.ceil((index + 1)/3)
let tile = (y - 1) * 3 + x
const squareSet = squaresSet[tile-1]
if (invalidSet(squareSet, col, '.')) return false
})
}
return true
};Still doesn’t pass. Here’s ChatGPT’s, which does pass
function validSet(theSet, val) {
if (theSet.has(val) && val !== '.') return false; // Return false if duplicate
theSet.add(val);
return true;
}
function isValidSudoku(board) {
let columnsSet = Array.from({ length: 9 }, () => new Set());
let squaresSet = Array.from({ length: 9 }, () => new Set());
// Iterate through rows and columns
for (let i = 0; i < 9; i++) {
const rowSet = new Set();
for (let j = 0; j < 9; j++) {
const val = board[i][j];
// Skip empty cells
if (val === '.') continue;
// Check row validity
if (!validSet(rowSet, val)) return false;
// Check column validity
if (!validSet(columnsSet[j], val)) return false;
// Check 3x3 sub-box validity
const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
if (!validSet(squaresSet[boxIndex], val)) return false;
}
}
return true; // All checks passed
}
Differences from ChatGPT’s
A)
They use Array.from({length: 5}, () => new Set()) instead which is, in my mind, trivial. I tested out the performance differences here 32) Minesweeper and they weren’t really clear to me.
B) They still create a new set for every row as we go, but they choose to access the [i][j] nesting all at once, which seems to keep things simpler. It also means the next point is executed sooner and therefore a lot of efficiently:
C) They check if the character is ’.’ for empty early on, for every character, before doing (almost) anything else. This also simplifies the validSet function and separates it into a clearer interest of concerns.
D) Instead of using Math.ceil on a i+1 index, they just use Math.floor on the index itself, which is much less confusing, and works almost exactly the same. Since this is simpler, this lets them do the Math.floor(i/3) operation inline which reads pretty well.
Yeah! Looks great. I love what they did to my function.
HOWEVER. I still haven’t worked out exactly what isn’t working in my code and I think I am due for a debugging session.
Debugging
Oh. Interesting. I can’t use a continue within a forEach loop. Or break. Good to know. Man it’s crazy, but it’s like almost all iterators make you regret using them except for trad for loops which just never us down.
HAHA.
function isValidSudoku(board: string[][]): boolean {
let columnsSet = [...Array(9)].map(_=> new Set())
let squaresSet = [...Array(9)].map(_=> new Set())
// rows
for (let i = 0; i < board.length; i++){
const y = Math.ceil((i + 1)/3)
const rowSet = new Set()
const row = board[i]
for (let index = 0; index < row.length; index++){
let col = row[index]
if (col === '.') continue
console.log({col})
if (rowSet.has(col)) return false
rowSet.add(col)
// cols
const colSet = columnsSet[index]
if (colSet.has(col)) return false
colSet.add(col)
// Tile by tile
let x = Math.ceil((index + 1)/3)
let tile = (y - 1) * 3 + x
// console.log({tile})
const squareSet = squaresSet[tile-1]
if (squareSet.has(tile-1)) return false
squareSet.add(col)
}
}
return true
};Finally got it. There were a tiny of tiny mistakes. This is a really great challenge for overall code quality and consistency practice, as well as general practice traversing through a variety of structures and just making sure that variables and indexes are being used correctly.
Return 2
Okay, I got it in 6:20. Let’s try for faster.
Finally! Got it in 2:50. Accidentally used j instead of boxIndex one time.
So I think this may be a good place to check quickly, how can I write less verbose code that is faster to write?
function isValidSudoku(board: string[][]): boolean {
type BoardSet = Set<string>
const squaresSet: BoardSet[] = Array.from({length: 9}, _=> new Set())
const columnsSet: BoardSet[] = Array.from({length: 9}, _=> new Set())
for (let i = 0; i < board.length; i++){
const row = board[i]
const rowSet: BoardSet = new Set()
for (let j = 0; j < row.length; j++){
const tile = board[i][j]
if (tile === ".") continue
// rows
if (rowSet.has(tile)) return false
rowSet.add(tile)
// columns
const columnSet = columnsSet[j]
if (columnSet.has(tile)) return false
columnSet.add(tile)
// square set
const boxIndex = Math.floor(i/3)*3 + Math.floor(j/3)
const boxSet = squaresSet[boxIndex]
if (boxSet.has(tile)) return false
boxSet.add(tile)
}
}
return true
};Here’s a creative way to reduce lines! I think it kinda makes sense, but it’s way less readable. Let’s see if I can even do this from scratch.
function isValidSudoku(board: string[][]): boolean {
type BoardSet = Set<string>
const allSets: BoardSet[][] = Array
.from({length: 3},_=> Array
.from({length: 9}, _=> new Set()))
for (let i = 0; i < board.length; i++){
for (let j = 0; j < board[i].length; j++){
const tile = board[i][j]
if (tile === ".") continue
// rows
const rowSet = allSets[0][i]
if (rowSet.has(tile)) return false
rowSet.add(tile)
// columns
const columnSet = allSets[1][j]
if (columnSet.has(tile)) return false
columnSet.add(tile)
// square set
const boxIndex = Math.floor(i/3)*3 + Math.floor(j/3)
const boxSet = allSets[2][boxIndex]
if (boxSet.has(tile)) return false
boxSet.add(tile)
}
}
return true
};Got it! Implemented this from scratch in 4:13.
Woah okay, so I tried to make it more DRY in another way, and it backfired:
function isValidSudoku(board: string[][]): boolean {
type BoardSet = Set<string>
const allSets: BoardSet[][] = Array
.from({length: 3}, _=> Array
.from({length: 9}, _=> new Set()
))
for (let i = 0; i < board.length; i++){
for (let j = 0; j < board[i].length; j++){
const tile = board[i][j]
function returnOrAdd(set){
if (set.has(tile)) return false
set.add(tile)
}
if (tile === ".") continue
// rows
const row = allSets[0][i]
returnOrAdd(row)
// columns
const col = allSets[1][j]
returnOrAdd(col)
// squares
const boxIndex = Math.floor(i/3)*3 + Math.floor(j/3)
const square = allSets[2][boxIndex]
if (square.has(tile)) return false
square.add(tile)
}
}
return true
};See how I made this closure, cleverly (😜) re-using the tile value for use when this closure is defined? Well, it turns out this doesn’t work because returning inside of a closure inside a parent function behaves differently than returning at the scope of that parent function.
This is interesting to me because it highlights how loops aren’t closures! When writing this originally, I was curious whether I could return false inside of two nested loops as a way to interrupt my function at the soonest sign of an invalid sudoku, and it turned out that the answer was yes.
So If I wanted to continue making things more DRY, I could do this:
function isValidSudoku(board: string[][]): boolean {
type BoardSet = Set<string>
const allSets: BoardSet[][] = Array
.from({length: 3}, _=> Array
.from({length: 9}, _=> new Set()
))
for (let i = 0; i < board.length; i++){
for (let j = 0; j < board[i].length; j++){
const tile = board[i][j]
function checkAndAddToSet(set){
if (set.has(tile)) return true
set.add(tile)
return false
}
if (tile === ".") continue
// rows
if (checkAndAddToSet(allSets[0][i])) return false
// columns
if (checkAndAddToSet(allSets[1][j])) return false
// squares
const boxIndex = Math.floor(i/3)*3 + Math.floor(j/3)
if (checkAndAddToSet(allSets[2][boxIndex])) return false
}
}
return true
};But personally, I think we’re going way beyond what is actually helpful. It just makes things less readable. I think there was a time when I thought that just continual encapsulation made for more readable, higher quality, easier to maintain code, and I definitely changed my mind. A few years ago at least now. The above code, in my opinion, though dryer, is worse. The closure used for encapsulation here isn’t helpful, and doesn’t really group functionality in any sort of meaningful way, it just happens to prevent the same couple lines from being repeating.
So in terms of code-line savings…I guess it saves us 6 lines. But it also introduces…5
So let’s look at our balance sheet here:
| What was improved | What was lost |
|---|---|
| we have one less line of code | readability |
Doesn’t really seem worth it, as fun as it is to encapsulate stuff. What a rush!
To go on a massive tangent here, I did some pretty customary encapsulation when I was working on a multiplayer online game, as there were a lot of game objects with various properties and inheritance in the game state on the back end and on the frontend a bit of very abstract-able behavior where those properties were interpreted into opinionated methods of rendering using 3JS.
I don’t think I did a poor job, but I will say that the inheritance-heavy OOP paradigm I ended up using certainly leads to a lot of jumping around files, and during that process I sometimes sort of forget what I’m doing sometimes, or what certain properties or methods do.
One potentially alternative in this case may be an ECS, or entity-component-system, which allows methods and properties to be defined globally and then just attached to objects. This seems like it could be a nice way to keep things flatter (less encapsulated), and hopefully more readable.