Skip to content

Instantly share code, notes, and snippets.

@zahid
Created March 27, 2014 05:33
Show Gist options
  • Save zahid/9800989 to your computer and use it in GitHub Desktop.
Save zahid/9800989 to your computer and use it in GitHub Desktop.
Sevenify Problem
/* This is my implementation of the problem regarding replacing the element in the row and column of each instance of a 7 with 7s. I did this without allocating extra memory by just keeping track of the rows and columns that needed to be 'sevenified' and I did it in the end in one pass, therefore not having to rewrite 7s over and over again. My efficiency for sevenify's element reassignment, at the worst case, is O(m+n) or O((m+n) + (m*n)) if you include the cycles to create the locations hash.
I would test this by checking that:
- clone works properly (I tested to check for deep copying)
- test fillRow (and fillColumn) work on a single row (and column) with no 7s present
- test fillRow (and fillColumn) work on a single row (and column) with one 7 present
- test fillRow (and fillColumn) work on a single row (and column) with all elements set to 7
zahid mahir
*/
var cloneMatrix = function (matrixx) {
var clonedMatrix = [];
for (var i = 0; i < matrixx.length; i++) {
clonedMatrix[i] = matrixx[i].slice(0);
}
return clonedMatrix;
};
var fillRow = function (arr, row) {
for (var i = 0; i < arr[0].length; i++) {
arr[row][i] = 7;
}
};
var fillColumn = function (arr, column) {
for (var i = 0; i < arr.length; i++) {
arr[i][column] = 7;
}
};
var matrixToString = function (matrixx) {
var dump = '';
matrixx.forEach(function (col) {
col.forEach(function (element) {
dump += element + ' ';
});
dump += '\n';
});
return dump;
};
var sevenify = function (matrixx) {
var clonedMatrix = cloneMatrix(matrixx);
var locations = {
rows : {},
columns : {}
};
for (var i = 0; i < matrixx.length; i++) {
for (var j = 0; j < matrixx[0].length; j++) {
if(matrixx[i][j] == 7) {
locations.rows[i] = true;
locations.columns[j] = true;
}
}
}
for (var row in locations.rows) {
fillRow(clonedMatrix, row);
}
for (var column in locations.columns) {
fillColumn(clonedMatrix, column);
}
return clonedMatrix;
};
// assume standard n x m matrix
var testMatrix = [
[1, 8, 1, 4, -1],
[2, 3, 8, 2, 1],
[8, 3, 1, 7, 7]
];
console.log('original');
console.log(matrixToString(testMatrix));
var sevenifiedMatrix = sevenify(testMatrix);
console.log('sevenified');
console.log(matrixToString(sevenifiedMatrix));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment