2
\$\begingroup\$

Preamble

I am trying to learn JavaScript by writing code and looking up documentation, one problem at a time. I am already familiar with several "dynamic" languages, so I'm hoping to be productive quickly. This may not be the perfect way to learn the language, but I don't have the time to pick up a book right now.

The following code works, but feels much more like clumsy Python than proper JavaScript. I commented the code as much as I can, so understanding it shouldn't be very difficult.

Can you please show me how to do this in a "better" JS way?

Note that I run this outside of the browser using Node.js if that makes any difference

Exercise

(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013).

Let's consider a set of Arrays (A1, A2, A3, ... ,An) of variable sizes. All the elements in these arrays are integers. All the arrays are sorted in an ascending order.

A sandwich is a set of indices (i1, i2, i3, ..., in) such as:

A1[i1] <= A2[i2] <= A3[i3] <= .. <= An[in] where <= is the inequality sign for "lesser than or equal"

For example, consider the following arrays:

A1 = [1, 5, 7, 10]
A2 = [2, 6, 6, 8, 12]
A3 = [4, 5, 9]

Here are some examples of valid sandwiches of the above set:

  • (0, 0, 0) Because 1 <= 2 <= 4
  • (1, 3, 2) Because 5 <= 8 <= 9

Given a set of arrays given as input, write a program that will calculate the number of valid sandwiches.

You are free to format your input in any way you want, and use any language you want. If your language of choice has a builtin function that does this (or something close enough), avoid using it.

Code

/*
 * A is an array of ints.
 * 
 * Returns true if the input array is sorted in an ascending order.
 * 
 */
function sorted_ascend(A) {
    for (var i=0; i<A.length-1; ++i) {
        if (A[i] > A[i+1]) {
            return false;
        }
    }
    return true;
}

/*
 * A is a set of arrays
 * ind is a list of indices
 * 
 * This function will return true if ind is a sandwich to the set A
 * It does so by verifying that the following list is sorted:
 * 
 * # List comprehension in a Python-fashion
 * [ A[i][ind[i]] for i in range(0, len(A)) ]
 * 
 */
function is_sandwich (A, ind) {
    if (ind.length !== A.length) {
        return false;
    }

    var l = [];

    for (var i=0; i<ind.length; ++i){
        l.push(A[i][ind[i]]);
    }

    return sorted_ascend(l);
}


/*
 * face is an object
 * times is an integer
 * 
 * repeat ``face'' on an array, ``times'' times
 * e.g., array.repeat_push("hello", 3) pushes "hello" 3 times.
 * 
 * I use this function to initialize an array with a 0 repeated avariable number of times.
 * Is there a better way to do this?
 * 
 */
function repeat_face (face, times) {
    l = [];
    for (var i=0; i<times; ++i) {
        l.push(face);
    }

    return l;
}

/*
 * ind is an array of indices
 * ref is array holding the max values for each cell
 * 
 * The function returns true if each element of ind is lesser than its equivalent in ref
 * It returns false otherwise
 */
function valid_ind(ind, ref) {

    if (ind === undefined || ind.length !== ref.length) {
        return false;
    }

    for (var i=0; i<ref.length; ++i) {
        if (ind[i] >= ref[i]) {
            return false;
        }
    }

    return true;
}

/*
 * ind is an array holding the previous value.
 * ref is a reference array, holding the max value for each cell.
 * 
 * Starting with the rightmost cell, increment the value of ind until reaching the maximum 
 * defined in ref. Once the maximum is reached, reset to 0 and increment the cell on the left.
 * 
 * Do this recursively until all the cells reach their maximum.
 * Then return undefined, to mark the end of the generation process.
 * 
 */
function incr_ind(ind, ref) {
    carry = 1;
    for (var i=ref.length-1; i>=0; --i) {
        ind[i] += carry;
        carry =0;

        if (ind[i] >= ref[i]) {
            ind[i] = 0;
            carry = 1;
        }
    }

    return (carry === 0) ? ind : undefined;
}

/*
 * A is a set of arrays
 * 
 * Generate the valid lists of indices lexicographically 
 * i.e., 
 * {{0, 0, ..., 0}, {0, 0, ..., 1}, ..., {0, 0, ..., |An|}, 
 * {0, 0, ..., 1, 0}, {0, 0, ..., 1, 1}, ..., {|A0|, |A1|, ...,  |An|}}
 * 
 * 
 */
function all_indices(A) {
    // replace each array in A by its length
    // this is used to control the max value of each cell 
    // in the indices array.
    lengths_set = A.map(function (x) {
                            return x.length;});

    // initial indice array is [0, 0, 0, ..., 0]
    ind = repeat_face(0, A.length);

    // this array will hold all the valid indices.
    indices = [];

    // as long as the ind list is valid, append it to indices and increment.
    while (valid_ind(ind, lengths_set)) {
        indices.push(ind.slice());
        ind = incr_ind(ind, lengths_set);
    }

    return indices;
}

/*
 * array_set is an array containing all the input arrays.
 * 
 * Bruteforcing: Generate all the possible indices then filtering according
 * to the is_sandwich() test.
 */
function sandwiches(array_set) {
    return all_indices(array_set).filter(function(x) {
                                             return is_sandwich(this, x);
                                         }, array_set);
}

// main function
(function () {

     A1 = [1, 5, 7, 10];
     A2 = [2, 6, 6, 8, 12];
     A3 = [4, 5, 9];

     S = sandwiches([A1, A2, A3]);

     console.log(S);
     console.log(S.length);

})();

And here's the output I get:

[ [ 0, 0, 0 ],
  [ 0, 0, 1 ],
  [ 0, 0, 2 ],
  [ 0, 1, 2 ],
  [ 0, 2, 2 ],
  [ 0, 3, 2 ],
  [ 1, 1, 2 ],
  [ 1, 2, 2 ],
  [ 1, 3, 2 ],
  [ 2, 3, 2 ] ]
10
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Haven't gone over your code in detail, but I've noticed quite a few implied globals in your functions; i.e. variables you haven't declared with a var keyword, like l in repeat_face. Without the var declaration, l will be defined in the global scope, which could bite you later. \$\endgroup\$ – Flambino Oct 24 '12 at 4:14
3
\$\begingroup\$

Probably the biggest problem is that you forget var keywords every now and then. In JavaScript, these are required or the variable will implicitly be global. Yes, your program will execute, but you'll end up with a bunch of global variables you didn't expect. Bad.

Since you're a Python person it's probably expected that you'll omit a few vars every now and then. To prevent it, run your scripts in "strict mode": put the string "use strict"; (with quotes) at the top of your program or any functions you want it to apply to. In strict mode, omitting a var keyword is an error.

I went through and I think I caught all the missing vars.

function repeat_face (face, times) {
    var l = [];

function incr_ind(ind, ref) {
    var carry = 1;

function all_indices(A) {
    // replace each array in A by its length
    // this is used to control the max value of each cell 
    // in the indices array.
    var lengths_set = A.map(function (x) {
                            return x.length;});

    // initial indice array is [0, 0, 0, ..., 0]
    var ind = repeat_face(0, A.length);

    // this array will hold all the valid indices.
    var indices = [];

// main function
(function () {

     var A1 = [1, 5, 7, 10],  // Note the comma: In JS, you can merge consecutive var statements like I've done here. It's generally considered good style.
         A2 = [2, 6, 6, 8, 12],
         A3 = [4, 5, 9],
         S = sandwiches([A1, A2, A3]);

Other minor things:

In JavaScript we usually use camelCase instead of underscored_names, however there is a significant minority that use underscores. Since you're from Python, where underscores is the preferred style, feel free to continue that. Just know that when you see other people's code, camelCase is quite a bit more popular.

A very common pattern in JavaScript is the module pattern. Essentially what this involves is wrapping all your code in an immediately-invoked function expression, and returning what you want to "export" to calling code. This helps cut down on globals. So your code would look like:

// File: utils.js
window.utils = (function () {
    // Define repeat_face, incr_ind, all_indices, etc, everything except your main function.

    return {
        repeat_face: repeat_face,
        incr_ind: incr_ind,
        // etc
    };
})();

// File: main.js
(function (utils) {
    // Do your main logic
})(utils);

A similar form of this is the AMD (Asynchronous Module Definition) pattern which has become quite popular recently. You might want to learn about it, as it has a bunch of advantages over the module pattern (which it basically is an improved version of). See for example http://requirejs.org/docs/whyamd.html.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would add, that you (@rahmu) could also look into CoffeeScript. It compiles to JavaScript, but is very much inspired by Python (and Ruby and even Haskell) in terms of syntax. Personally speaking, I love it, but you do still need to know a fair amount of JavaScript since that's what it actually is. But it's much nicer to write. \$\endgroup\$ – Flambino Oct 24 '12 at 16:57
  • \$\begingroup\$ +1 to CoffeeScript. It's indentation based like Python so it should feel very familiar to you @rahmu. \$\endgroup\$ – Peter C Oct 24 '12 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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