Javascript job task

This is not typical javascript problem, this is a part from one job interview application where are combined mathematics and arrays. I like problem solving and because of that write it here.

Problem description

Write JavaScript code to find a 9 letter string of characters that contains only letters from acdegilmnoprstuw such that the hash(the_string) is 956446786872726 if hash is defined by the following pseudo-code:

Int64 hash (String s) {
    Int64 h = 7
    String letters = "acdegilmnoprstuw"
    for(Int32 i = 0; i < s.length; i++) {
        h = (h * 37 + letters.indexOf(s[i]))
    }
    return h
}

For example, if we were trying to find the 7 letter string where hash(the_string) was 680131659347, the answer would be "leepadg".

Analyse

We have pseudo code and we can write hash function, but before that let's analyse pseudo code. We have input string "leepadg", output hash value 680131659347, key string "acdegilmnoprstuw" and some algorithm h = (h * 37 + letters.indexOf(s[i])). Hash function translate string "leepadg" to hash value 680131659347 by key through algorithm, step by step.

How it's work?

Let's analyse first step with focus on small part of algorithm: letters.indexOf(s[i]). That return position of input string character inside key. Eg. if we look input string "leepadg", and if we are at first char "l" we will get the postition of character "l" inside key. In this case it is index 6.

And steps are:

[l] 7 * 37 + 6 = 265
[e] 265 * 37 + 3 = 9808
[e] 9808 * 37 + 3 = 362899
[p] 362899 * 37 + 10 = 13427273
[a] 13427273 * 37 + 0 = 4968089101
[d] 496809101 * 37 + 2 = 18381936739
[g] 18381936739 * 37 + 4 = 680131659347

That is how hash function works: input string is "leepadg" and output is 680131659347. Hash is calculated by algo and key "acdegilmnoprstuw".

Reverse engineering

As we know how hash function works, now we need to write decrypter - function what will return string when we enter hash value. Inside decrypter hash value will be translated and recalculated in steps (loop) that in every step we get an character. Also need to notice that we will go in reverse order and final desired string will be filled by characters in reverse order.

In that case in first step starting hash value 680131659347 need return char "g", and so on. Also as you can see inside hash function, hash value is obtained multiplying by 37 and because of that inside decrypter we need in every step divide hash by 37. However it's not enough because we will have reminder - but in this process remainder is very important. We know that our secret string has 7 characters and in first step reminder will show us fourth index from key string ("acdegilmnoprstuw" and key[4]="g").

If all this is confused maybe it's better to show decrypter function:

function decrypt(h) {
var charpos = [];
var remainder = 0;
var secword = [];
var hashnum = h;
var letters = 'acdegilmnoprstuw';

	for( i = 7; i > 0; i-- ){		
		remainder = ( hashnum % 37 );
		charpos[i] = remainder;
		hashnum = (hashnum - remainder)/37;
		secword[i-1] = letters.charAt(charpos[i]);		
	}

       return secword.join(''); // array of chars to string
}

Right now it's easy to solve the problem from the beginning and find secret string with 9 characters where hash value is 956446786872726. That part I left to you.
All this for me was interesting and fun and gives me an idea to build Joomla plugin for some specific cases. Thanks to the creators of this javascript problem.