Fog Creek Software posted a puzzle on their software developer jobs page which asks you to crack a poor hashing function.

fogcreek.js

// Originally found at: http://www.fogcreek.com/jobs/dev/
/*
========================================
    Prompt
========================================
 */
// Find a 9 letter string of characters that contains only the letters
var values = 'acdegilmnoprstuw';

// such that badHash(the_string) is
var hash = 945924806726376;

// Given a hashing function
function badHash(string) {
  var h = 7;

  for (var i = 0; i < string.length; i++) {
    h = (h * 37 + values.indexOf(string[i]));
  }

  return h;
}

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

/*
========================================
    My solution
========================================
 */

var dict = makeDict(values);
var solution = unhash(hash);
console.log('solution:', solution);


function unhash(hash) {
  // Subtract the constant 37^9(7) where 9 is the length of the solution string.
  var toConvert = hash - (Math.pow(37, 9) * 7) + '';
  // Convert the decimal number to base 37.
  var base37 = convertBase(toConvert, 10, 37);
  var unhashed = '';

  // Look up resulting values in the predefined dict
  for(var i = 0; i < base37.length; i++) {
    unhashed += dict[base37.charAt(i)];
  }

  return unhashed;
}

function makeDict(string) {
  var keys = '0123456789abcdef';
  var dict = {};

  for(var i = 0; i < keys.length; i++) {
    dict[keys.charAt(i)] = string.charAt(i);
  }

  return dict;
}

function convertBase(value, from_base, to_base) {
  var range = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');
  var from_range = range.slice(0, from_base);
  var to_range = range.slice(0, to_base);

  var dec_value = value.split('').reverse().reduce(function (carry, digit, index) {
    if (from_range.indexOf(digit) === -1) throw new Error('Invalid digit `'+digit+'` for base '+from_base+'.');
    return carry += from_range.indexOf(digit) * (Math.pow(from_base, index));
  }, 0);

  var new_value = '';
  while (dec_value > 0) {
    new_value = to_range[dec_value % to_base] + new_value;
    dec_value = (dec_value - (dec_value % to_base)) / to_base;
  }
  return new_value || '0';
}