Trello test

I was about to create a Trello board when i saw the positions tab. Like a moth attracted by the light, I clicked on it (after all, I love the product and was curious about what positions were being offered).
And BOOM, there it was: nodejs developer. Curiously, clicked on the link, and found that to apply, I needed to solve the following problem:

Write JavaScript (or CoffeeScript) code to find a 9 letter string of characters that contains only letters from: ‘acdegilmnoprstuw’ such that the hash(the_string) is 956446786872726.

Normally, I would not pay attention to this kind of problems. I was not even thinking on applying, but don’t know why, I got engaged to the problem and solved it in the background thinking. Apparently the hash function gave higher numbers for longer strings, and higher values for using latter letters from the alphabet (or it seemed so). 30 minutes of coding and testing after that, lead to the following solution. It works. And is making a very low number of tests to get the solution. 88 comparisons actually for the sample. It could make even less comparisons by using binary traversal of the alphabet. And it does not take into attention the expected word length hint.
The solution is written in the worst javascript ever. imperative but has no side-effects. I am more curious about what they’d expect from a solution than the solution itself. Algorithm complexity ? Functional code ? …

Is this a general inverse hash algorithm ? of course not. This is only possible because it is a very simple hash function.


/**
 * Original hash function.
 * @param alphabet {string} alphabet composing the guessed words
 * @param s {string} string to get hash for
 *
 * @return {number} string hash value
 */
function hash (alphabet, s) {
    var h = 7;
    for(var i = 0; i  find) {
            letters.pop();
            break;
        } else if ( hashValue===find ) {
            // lucky boy
            return word;
        }
    }
    
    // guess the hashed word
    for( var currentCharIndex=0; currentCharIndex < letters.length; currentCharIndex++ ) {

        for( var index=0; index  find ) {
                letters[ currentCharIndex ]= alphabet[index-1];
                break;
            }
        }
    }

    return "not found :(";
}

// get the word with the given hash. 
// takes 88 iterations on the double nested for loop.
// result: trellises
console.log( find( "acdegilmnoprstuw", 956446786872726 ) );

// takes 44 iterations.
// result: leepadg
console.log( find( "acdegilmnoprstuw", 680131659347 ) );

Advertisements

Typescript

It’s not been the first time I have to deal with a gigantic Javascript codebase. While most of the side projects I’ve been writing are no more than 5K loc, CAAT was near 30K, and in my current job I will likely end up managing a codebase between 50-100k loc.
It is fairly complicated to keep things up and running in such a big codebase when I have to defer error checking to the runtime environment and different people contribute code. The nature of the code I write is mostly visual. Things that a human being won’t be able to spot whether they are right or wrong tend to be quite complicated to automate, either at unit or functional testing levels. For example, is that gradient-filled shape right ?, etc.
While writing CAAT, I had to manage all the basic platform stuff on my own: (prototypical) inheritance, module management, dependencies, … all had to be either solved on my own, or by using external libraries, not by the language itself. Good news is that Javascript can mostly fix itself.
Basic features for a typed language, like code refactor, keeping up with correct VM code for performance or hinting code for performance is something so tied to the core of my development that I simply don’t want to deal with it on my own.
For this and so many other reasons I took a shot on Typescript.

Conclusion: it pays by itself after 10 minutes of using it. Specially when putting the stress in long-term maintainability and code quality.

Let me enumerate some of the goods I get while writing Typescript code:

  • Refactor: my IDE recognizes the code semantically. It allows for deep type and elements refactor on-the-fly.
  • ES6: Typescript brings to the table many ES6 language features. By the time ES6 is around, all my typescript code will almost be a one-to-one mapping which does not need any change.
  • Strong typed. Modern Javascript VM make deep type inference to JIT the code. While Typescript is not executable in the browser and has to be transpiled to javascript, since it is strong typed will guarantee type consistency, something that will for sure help to your codebase performance.
  • Javascript VM-friendly transpiled code. While some time ago it was expected to define properties in prototypes, but at the same time, keeping prototype chains sort, today, if you want to take advantage of hidden classes and already optimized code, properties should be injected in constructor functions.
  • Solved extension mechanism. It ships with a very simple prototypical extension mechanism.
  • Solved modularity. Module information will be written for you.
  • Super light overhead. Resulting code is just the original code without the type information.
  • Since 1.4, union types and type aliases will leverage the Typescript capabilities, switching from type:any to a union type.
  • No learning curve at all.

Nowadays, there are Typescript mapping files for all major libraries around: webgl, nodejs, (node io ?? :), webaudio, etc. And being myself so close to HTL5 gaming, most modern HTML5 engines are either written in Typescript, like CocosJS or Egret, or have Typescript mappings like Phaser.

I’d rather have a compiler on my side. Ever.