Fun Javascript experiment I did over the weekend. It's a programming problem (finding the longest non-decreasing sequence in a grid) I came across and I wanted to give it a shot. This is my first iteration, so obviously it could do with some optimizations. My first inclination was to do this in C++ but I wanted to test Atwood's Law, that is, if …

fun_js_experiment.js

            (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];
                            // could use a ternary operator here, but it would be confusing and long
                            // and I like KISS. If the smallest number has not yet been set, or the current
                            // 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);
            
            (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 
            })();