Skip to content

Instantly share code, notes, and snippets.

@saip106

saip106/brute_force_zero_sum.js

Last active August 29, 2015 14:14
Show Gist options
  • Save saip106/636484aec0d131febc35 to your computer and use it in GitHub Desktop.
Save saip106/636484aec0d131febc35 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
brute_force_zero_sum.js
function create_empty_is_visited_matrix(numberOfRows, numberOfColumns) {
var result = [];
for(var i = 0; i < numberOfRows; i++) {
result[i] = [];
for(var j = 0; j < numberOfColumns; j++) {
result[i][j] = false;
}
}
return result;
}
function clone_matrix(matrix) {
var result = [];
for(var i = 0; i < matrix.length; i++) {
result[i] = [];
for(var j = 0; j < matrix[i].length; j++) {
result[i][j] = matrix[i][j];
}
}
return result;
}
function has_zero_sum(matrix, row, column, currentSum, isVisitedMatrix) {
if(row > 0) {
var up = row - 1;
if(isVisitedMatrix[up][column] === false) {
var clone = clone_matrix(isVisitedMatrix);
clone[up][column] = true;
var updatedSum = currentSum - matrix[up][column];
console.log(up, column, updatedSum);
if (updatedSum === 0) {
return true;
}
var result = has_zero_sum(matrix, up, column, updatedSum, clone);
if (result === true) {
return true;
}
}
}
if(row < matrix.length - 1) {
var down = row + 1;
if(isVisitedMatrix[down][column] === false) {
var clone = clone_matrix(isVisitedMatrix);
clone[down][column] = true;
var updatedSum = currentSum - matrix[down][column];
console.log(down, column, updatedSum);
if (updatedSum === 0) {
return true;
}
var result = has_zero_sum(matrix, down, column, updatedSum, clone);
if (result === true) {
return true;
}
}
}
if(column > 0) {
var left = column - 1;
if(isVisitedMatrix[row][left] === false) {
var clone = clone_matrix(isVisitedMatrix);
clone[row][left] = true;
var updatedSum = currentSum + matrix[row][left];
console.log(row, left, updatedSum);
if (updatedSum === 0) {
return true;
}
var result = has_zero_sum(matrix, row, left, updatedSum, clone);
if (result === true) {
return true;
}
}
}
if(column < matrix[row].length - 1) {
var right = column + 1;
if(isVisitedMatrix[row][right] === false) {
var clone = clone_matrix(isVisitedMatrix);
clone[row][right] = true;
var updatedSum = currentSum + matrix[row][right];
console.log(row, right, updatedSum);
if (updatedSum === 0) {
return true;
}
var result = has_zero_sum(matrix, row, right, updatedSum, clone);
if (result === true) {
return true;
}
}
}
console.log('end of path');
return false;
}
function does_matrix_have_zero_sum(matrix) {
for(var i = 0; i < matrix.length; i++) {
for(var j = 0; j < matrix[i].length; j++) {
var isVistedMatrix = create_empty_is_visited_matrix(matrix.length, matrix[i].length);
isVistedMatrix[i][j] = true;
console.log('starting new' ,i, j, matrix[i][j]);
var result = has_zero_sum(matrix, i, j, matrix[i][j], isVistedMatrix);
if (result === true) {
return true;
}
}
}
return false;
}
var matrix = [];
matrix[0] = [1,2,3];
matrix[1] = [3,2,1];
matrix[2] = [1,4,2];
var isVistedMatrix = create_empty_is_visited_matrix(matrix.length, matrix[2].length);
isVistedMatrix[2][0] = true;
console.log(does_matrix_have_zero_sum(matrix));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment