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:

  1. Create a few more functions like matches_criteria() and do_assignments() ti minimize repeating myself.
  2. Use recursion instead of a loop and in other places to improve code readability.
  3. Implement my own copy_object() function instead of using jQuery's extend(). I don't need all the functionality of .extend(). Thus becoming library independent and avoiding overhead from including jQuery.
  4. 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...

  • 1
    Does your function actually work? If the grid you pass to it is [[0, 9, 8], [9, 9, 4], [1, 2, 3]], for example, does it get the correct sequence [1, 2, 3, 4, 8, 9]? – Stuart Aug 13 '13 at 21:07
  • 1
    oh my example is wrong! But anyway have you tested it on a few cases like that? From a glance your function seems to me unlikely to work in such cases. – Stuart Aug 13 '13 at 21:15
  • Aha! It does not! I make a false assumption about starting at the smallest number! That doesn't necessarily mean it will be the longest non-decreasing sequence! Thanks for the catch! – Alex Aug 13 '13 at 21:50
  • @Stuart Btw thanks for taking the time to go through it and find issues! I know its a fair bit of code thats not really in the best state right now. :) – Alex Aug 13 '13 at 22:12
up vote 1 down vote accepted

Aside from the fact that your algorithm doesn't work in cases where there is a solution that does not start with the smallest number, I would say that you are doing everything in an unnecessarily complex way, particularly in the way you use objects for all of the numbers and having to make copies of the initial_number_data all the time.

For example, calc_smallest_number could be simplified to:

function calcSmallestNumber(grid) {
    var r;
    for (var i = 0; i < grid.length; i++) {
        for (var j = 0; j < grid[i].length; j++) {
            if (!r || grid[i][j] < r.value) {
                r = {
                    value: grid[i][j],
                    gridLocation: {row: i, column: j}
                };
            }
        }
     }
     return r;
 }

Then in the main function find_longest_sequence you have a load of repetition which could be avoided in a number of possible ways, such as by using a list of coordinate offsets representing the different directions, something like this:

var directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];
for (var i = 0; i < directions.length; i++) {
    neighbouringLocation = {
       row: myPoint.gridLocation.row + directions[i][0],
       column: myPoint.gridLocation.column + directions[i][1]
    };
    // do stuff with neighbouringLocation
}
  • Yeah I was thinking about just using an array of arrays with two values to store locations. Looping over each direction and doing stuff in that specific iteration with a location would drastically reduce repeating myself. Also I really like what you did with calc_smallest_number(). +1 – Alex Aug 13 '13 at 22:24
  • This week has been a busy one. Hopefully have some updates this weeekend. – Alex Aug 17 '13 at 6:00

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.