Welcome to the Treehouse Community
Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.
Looking to learn something new?
Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.
Start your free trial
mersadajan
21,306 PointsIsn't this method a bit inefficient?
If I understand it correctly this method checks for a group of four spaces that are owned by the same player in the horizontal, vertical and diagonal direction. It does that every time a token is placed, going through the whole board every time. It would have been way more efficient to check for token by the same owner relative to the last placed token. That would be a max of three steps in all directions except up.
5 Answers
Steven Parker
229,732 PointsCode examples in the courses will often not be the most efficient, sometimes deliberately to more clearly illustrate a basic concept.
Noticing ways to improve the example code is simply evidence of your learning progress. Good job!
Jason Larson
8,353 PointsYes, this code is horribly inefficient, and while that bugs me, what bugs me more is the fact that it would be super easy to make it more efficient (at least potentially). The biggest inefficiency with the code the way it is written is not that it checks every sequence, but the fact that it doesn't STOP checking once it has found a winning sequence. If you simply change the action on the if statements to return true (or even win = true; return win;), then you at least prevent the code for checking all of the other spaces after you've already found a winning sequence. If a winning sequence isn't found, then you are still checking all the spaces and returning false.
Joseph Lander
Full Stack JavaScript Techdegree Graduate 27,764 PointsYes, this was how I was trying to think of it. Not that I had a working solution but the idea is that you only need to check on col you have placed the token for vertical, only on the row placed for horizontal and with the same 'gradient' that is suggested for diagonals in the solution.
On the other hand, would developers look at certain scenarios and say that the problem will not be scaled to a point where the inefficiency is an issue and argue that time spent finessing is itself adding time to the problem?
Mathias Jeppesen
7,602 PointsChallenged myself to find a more efficient solution.
I updated checkForWin() and added checkDirection().
/**
* Evaluates the current target in 4 directions (vertical, horizontal and both diagonals) and checks how many tokens with the same owner is linked to the target.
* @iterations is the amount of spaces we need to check in a given direction
* @param {Object} target - Our current target space.
* @return {boolean} Boolean value evaluating win if a sequence of 4 or more is made.
*/
checkForWin(target) {
let iterations = 3;
return 1 + this.checkDirection(target, iterations, 0, 1) >= 4 || // Check for vertical win
1 + this.checkDirection(target, iterations, -1, 0) + this.checkDirection(target, iterations, 1, 0) >= 4 || // Check for horizontal win
1 + this.checkDirection(target, iterations, -1, 1) + this.checkDirection(target, iterations, 1, -1) >= 4 || // Check for diagonal win (this: /)
1 + this.checkDirection(target, iterations, -1, -1) + this.checkDirection(target, iterations, 1, 1) >= 4; // Check for other diagonal win (this: \)
}
/**
* Function that checks how many spaces with matching owner is directly linked to the original space.
* The function is recursive and calls itself a maximum of 'iterations' times or until in finds a space where the owners doesn't match.
* @param {Object} current - Our current target space.
* @param {number} iterations - How many more spaces we need to check in the given direction. (Max number of times the function runs).
* @param {number} offsetX - The x-offset from our current target to the space to be checked.
* @param {number} offsetY - The y-offset from our current target to the space to be checked.
* @return {number} Number value of how many spaces with matching owner is linked to the original space.
*/
checkDirection(current, iterations, offsetX, offsetY) {
if (!(typeof this.board.spaces[current.x + offsetX] == 'undefined')) {
if (!(typeof this.board.spaces[current.x + offsetX][current.y + offsetY] == 'undefined')) {
const next = this.board.spaces[current.x + offsetX][current.y + offsetY];
if (next.owner === current.owner) {
return (iterations === 0) ? 1 : this.checkDirection(next, iterations - 1, offsetX, offsetY) + 1;
}
}
}
return 0;
}
The previous algorithm evaluated the entire board every time a new token was placed. This made it perform a lot of unnessecary checks which can be calculated to this:
-
O(nm):
- 4nm -9n -9m + 18 | n = board width, m = board height.
- Which in our case is 69 checks every time we place a token.
My algorithm only evaluates the surrounding tokens in the various directions.
- O(1):
- min: n, max: 3n | n = number of sub-directions away from the placed token. (min = 7, max = 21)
I hope the code is understandable. Any comments or tips is appreiated.
JASON LEE
17,351 PointsI used a similar approach albeit not as clean. It used recursion and got it to work, but then I realized later it only works if the winning token is dropped at the 'edge point' of the 4-in a row. For instance, if the winning drop occurs in the middle of the 4-row sequence it doesn't work. As long as your code tests for that then great job.
Trevor Maltbie
Full Stack JavaScript Techdegree Graduate 17,020 PointsTrevor Maltbie
Full Stack JavaScript Techdegree Graduate 17,020 PointsWhat would that look like?