Over the weekend I was perusing the web, and came across the programming problem, finding the longest non-decreasing subsequence in a grid, and I wanted to tackle it. I'm a web developer by profession, and sometimes, honestly, I feel like I fit the bill described by Jeff. I don't feel that I chose web development because I'm too stupid for anything else, I just happen to have a passion for it. But I do feel that a lot of what Jeff says is true. I feel like what I do in and day out really isn't that hard and doesn't challenge me. Sure, I bind click handlers like nobody's business, make things pretty and even communicate with a database from time to time, but lets be honest...its just not that big of a deal. (Ok, except for tricky CSS inheritance issues :) )
So anyway, from time to time I look up interesting problems I want to try to solve or enter code challenges, to keep my mind sharp and challenge myself. So that's how I came to this. Also though, wanting to test Atwood's law, I wrote it in JavaScript, even if it makes no sense. :)
Basically, the algorithm first finds the smallest number in the grid, then begins at that point to inspect each adjacent cell for a number matching specified criteria. Cells are pre-filtered so they don't have to be inspected if they don't match specified criteria. Of course a matching number is also added to the filtering indices array, so we don't look at it again. This process repeats until no adjacent cell can be found that matches given criteria.
So the question for you is, what suggestions do you have for me to optimize and improve my current algorithm? Things I already want to implement:
- Create a few more functions like
matches_criteria()anddo_assignments()ti minimize repeating myself. - Use recursion instead of a loop and in other places to improve code readability.
- Implement my own
copy_object()function instead of using jQuery'sextend(). I don't need all the functionality of.extend(). Thus becoming library independent and avoiding overhead from including jQuery. - I also feel like I just need to simplify it, and Im not exactly sure where I can simplify most.
I'm looking for any suggestions, from JavaScript-specific performance tips to general algorithm suggestions.
(function($) {
"use strict";
var day_lookup = {
"0": "Sunday",
"1": "Monday",
"2": "Tuesday",
"3": "Wednesday",
"4": "Thursday",
"5": "Friday",
"6": "Saturday"
};
var today = day_lookup[new Date().getDay()];
var initial_number_data = {
value: null,
grid_location: {
row: null,
column: null
}
};
function valid_grid(grid) {
var this_row = [];
var next_row = [];
for (var i = 0; i < grid.length; i++) {
this_row = grid[i];
// if there is another row
if (typeof(next_row = grid[i + 1]) !== "undefined") {
// make sure we have the same number of columns in each row
// there can be an arbitrary number of rows and columns but
// each row has to have the same number of columns, whatever
// that number is.
if (this_row.length !== next_row.length) {
return false;
}
}
}
// if we made it through the for loop all rows have been checked
// and the grid is valid.
return true;
}
function print_grid(grid) {
var grid_row_strings = [];
for (var i = 0; i < grid.length; i++) {
grid_row_strings.push(grid[i].join(" -- "));
}
console.log(grid_row_strings.join("\n"));
}
// checks to see if the row and column have already been added
// to the path
function is_already_indexed(indices, grid_location) {
for (var i = 0; i < indices.length; i++) {
if (indices[i].row === grid_location.row && indices[i].column === grid_location.column) {
return true;
}
}
return false;
}
function is_equal(obj1, obj2) {
for (var prop in obj1) {
if (typeof obj1[prop] === "object" && typeof obj2[prop] === "object") {
if (!is_equal(obj1[prop], obj2[prop])) {
return false;
}
} else {
if (obj1[prop] !== obj2[prop]) {
return false;
}
}
}
return true;
}
function calc_smallest_number(grid) {
console.time("calc_smallest_number");
var smallest_number = $.extend(true, {}, initial_number_data);
var current_value = 0;
var iterations = 0;
// loop through rows
for (var i = 0; i < grid.length; i++) {
console.log("examining row: " + i);
// loop through columns of a row
for (var j = 0; j < grid[i].length; j++) {
console.log("examining column: " + j);
current_value = grid[i][j];
// number is less than the stored smallest number, set the current number as
// the smallest number.
if (smallest_number.value === null || current_value < smallest_number.value) {
console.log("setting smallest_number.value to " + current_value);
smallest_number.value = current_value;
console.log("setting smallest_number.grid_location.row to: " + i);
// now store the location of this number so we can access it later
smallest_number.grid_location.row = i;
console.log("setting smallest_number.grid_location.column to: " + j);
smallest_number.grid_location.column = j;
iterations++;
}
}
iterations++;
}
console.log("It took "+ iterations +" iterations to determine the smallest number in the following grid:");
print_grid(grid);
console.log("Time needed to determine the smallest number in the grid:");
console.timeEnd("calc_smallest_number");
console.log("***********************************************");
console.log("Smallest number: " + smallest_number.value);
console.log("***********************************************");
return smallest_number;
}
window.find_longest_sequence = function(grid) {
if (!valid_grid(grid)) {
console.log("The following grid is invalid:");
print_grid(grid);
console.log("Please pass a valid grid to find_longest_sequence and enjoy your " + today +".");
return false;
}
// graph is valid...lets dig in...
// first lets get the smallest number in the grid.
var smallest_number = calc_smallest_number(grid);
// awesome, we have the smallest number and its location in the grid
// now lets start searching...
var current_num = $.extend(true, {}, smallest_number);
var next_num = $.extend(true, {}, initial_number_data);
var row = null;
var column = null;
var backwards = $.extend(true, {}, initial_number_data);
var below = $.extend(true, {}, initial_number_data);
var forwards = $.extend(true, {}, initial_number_data);
var above = $.extend(true, {}, initial_number_data);
var bottom_right = $.extend(true, {}, initial_number_data);
var bottom_left = $.extend(true, {}, initial_number_data);
var top_right = $.extend(true, {}, initial_number_data);
var top_left = $.extend(true, {}, initial_number_data);
var needle = $.extend(true, {}, initial_number_data);
var found_next_num_candidate = false;
var found_next_num = false;
var done = false;
var indices = [];
var path = [];
var indices_to_add = [];
var iterations = 0;
// begin search algorithm....
// order of searching is...
// 1. look backwards
// 2. look below
// 3. look forward
// 4. look above
// 5. look down and to the right
// 6. look down and to the left
// 7. look up and to the right
// 8. look up and to the left
// determine next biggest number and keep going
console.time("find_longest_sequence");
while (!done) {
console.log("Pushing "+ current_num.value +" onto path.");
// push the current value onto the path.
path.push(current_num.value);
row = current_num.grid_location.row;
column = current_num.grid_location.column;
// reset all searchers
backwards = $.extend(true, {}, initial_number_data);
forwards = $.extend(true, {}, initial_number_data);
above = $.extend(true, {}, initial_number_data);
bottom_right = $.extend(true, {}, initial_number_data);
bottom_left = $.extend(true, {}, initial_number_data);
top_right = $.extend(true, {}, initial_number_data);
top_left = $.extend(true, {}, initial_number_data);
// reset holder of indices that need to be added to the indices
// array but have not yet been added.
indices_to_add.length = 0;
// backwards.grid_location.row = row;
// backwards.grid_location.column = column - 1;
backwards.value = (grid[row] && grid[row][column - 1]) ? grid[row][column - 1] : false;
// console.log("backwards: " + backwards);
if (backwards.value) {
backwards.grid_location = {
row: row,
column: column - 1
};
if (!(backwards.value >= current_num.value)) {
indices_to_add.push(backwards.grid_location);
}
}
// below.grid_location.row = row + 1;
// below.grid_location.column = column;
below.value = (grid[row + 1] && grid[row + 1][column]) ? grid[row + 1][column] : false;
// console.log("below: " + below);
if (below.value) {
below.grid_location = {
row: row + 1,
column: column
};
if (!(below.value >= current_num.value)) {
indices_to_add.push(below.grid_location);
}
}
// forwards.grid_location.row = row;
// forwards.grid_location.column = column + 1;
forwards.value = (grid[row] && grid[row][column + 1]) ? grid[row][column + 1] : false;
// console.log("forwards: " + forwards);
if (forwards.value) {
forwards.grid_location = {
row: row,
column: column + 1
};
if (!(forwards.value >= current_num.value)) {
indices_to_add.push(forwards.grid_location);
}
}
// above.grid_location.row = row - 1;
// above.grid_location.column = column;
above.value = (grid[row - 1] && grid[row - 1][column]) ? grid[row - 1][column] : false;
// console.log("above: " + above);
if (above.value) {
above.grid_location = {
row: row - 1,
column: column
};
if (!(above.value >= current_num.value)) {
indices_to_add.push(above.grid_location);
}
}
// bottom_right.grid_location.row = row + 1;
// bottom_right.grid_location.column = column + 1;
bottom_right.value = (grid[row + 1] && grid[row + 1][column + 1]) ? grid[row + 1][column + 1] : false;
// console.log("bottom_right: " + bottom_right);
if (bottom_right.value) {
bottom_right.grid_location = {
row: row + 1,
column: column + 1
};
if (!(bottom_right.value >= current_num.value)) {
indices_to_add.push(bottom_right.grid_location);
}
}
// bottom_left.grid_location.row = row + 1;
// bottom_left.grid_location.column = column - 1;
bottom_left.value = (grid[row + 1] && grid[row + 1][column - 1]) ? grid[row + 1][column - 1] : false;
// console.log("bottom_left: " + bottom_left);
if (bottom_left.value) {
bottom_left.grid_location = {
row: row + 1,
column: column - 1
};
if (!(bottom_left.value >= current_num.value)) {
indices_to_add.push(bottom_left.grid_location);
}
}
// top_right.grid_location.row = row - 1;
// top_right.grid_location.column = column + 1;
top_right.value = (grid[row - 1] && grid[row - 1][column + 1]) ? grid[row - 1][column + 1] : false;
// console.log("top_right: " + top_right);
if (top_right.value) {
top_right.grid_location = {
row: row - 1,
column: column + 1
};
if (!(top_right.value >= current_num.value)) {
indices_to_add.push(top_right.grid_location);
}
}
// top_left.grid_location.row = row - 1;
// top_left.grid_location.column = column - 1;
top_left.value = (grid[row - 1] && grid[row - 1][column - 1]) ? grid[row - 1][column - 1] : false;
// console.log("top_left: " + top_left);
if (top_left.value) {
top_left.grid_location = {
row: row - 1,
column: column - 1
};
if (!(top_left.value >= current_num.value)) {
indices_to_add.push(top_left.grid_location);
}
}
found_next_num_candidate = false;
found_next_num = false;
if ((needle = $.extend(true, {}, backwards)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, below)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, forwards)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, above)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, bottom_right)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, bottom_left)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, top_right)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if ((needle = $.extend(true, {}, top_left)) && needle.value && !is_already_indexed(indices, needle.grid_location) && needle.value >= current_num.value && (needle.value <= next_num.value || is_equal(next_num, initial_number_data))) {
next_num = $.extend(true, {}, needle);
found_next_num_candidate = true;
}
if (found_next_num_candidate) {
current_num = $.extend(true, {}, next_num);
next_num = $.extend(true, {}, initial_number_data);
found_next_num = true;
indices_to_add.push(current_num.grid_location);
}
// push all succesfully indexed positions in the grid
// onto the indicies array if they arent already there.
for (var i = 0; i < indices_to_add.length; i++) {
if (!is_already_indexed(indices, indices_to_add[i])) {
console.log("Pushing index:");
console.log(JSON.stringify(indices_to_add[i], null, 4));
console.log("onto indices array in loop iteration "+ iterations + ".");
indices.push(indices_to_add[i]);
}
}
if (!found_next_num) {
done = true;
}
iterations++;
}
console.log("It took "+ iterations +" iterations to determine the longest non-decreasing sequence for the following grid:");
print_grid(grid);
console.log("Time needed to determine the longest non-decreasing sequence in the grid:");
console.timeEnd("find_longest_sequence");
console.log("========================================================");
console.log("Longest non-decreasing sequence: " + path.join("->"));
console.log("========================================================");
console.log("Enjoy your "+ today +"!");
};
})($KOBJ); // jQuery is aliased to $KOBJ in my environment.
(function() {
"use strict";
find_longest_sequence([[8, 2, 4],
[0, 7, 1],
[3, 7, 9]]); // this call produces the sequence: 0->2->4->7->7->9
})();
Original Problem Description:
Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals) in a rectangular grid of numbers in a language of your choice. The solution should handle grids of arbitrary width and height. For example, in the following grid, one legal path (though not the longest) that could be traced is 0->3->7->9 and its length would be 4. 8 2 4 0 7 1 3 7 9 The path can only connect adjacent locations (you could not connect 8 -> 9). The longest possible sequence for this example would be of length 6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->9.
Update:
As pointed out by Stuart, my algorithm has a fatal wrong assumption. I assume in the algorithm that the longest non-decreasing sequence will always start at the smallest number in the grid. This is wrong. Passing the following grid:
[[0, 9, 8],
[9, 9, 4],
[1, 2, 3]]
to find_longest_sequence() function produces the following sequence:
0->9->9->9
which is clearly not the the longest increasing sequence. This happens because my algorithm assumes that its always starting from the right position, and so if it cant find any positions that match criteria in any adjacent cells, it assumes its automatically found the longest non decreasing sequence in the grid, when really its only found the longest non-decreasing sequence for that starting position. Stuart, thanks a ton! This is a huge help! I'm excited to fix this and come back with my updated solution for further review.
Updates to come...
[[0, 9, 8], [9, 9, 4], [1, 2, 3]], for example, does it get the correct sequence[1, 2, 3, 4, 8, 9]? \$\endgroup\$