A string hash problem

Earlier this week I was looking through various software developer jobs and I came across this one by Fog Creek. They've posted the following interesting problem, which is the subject of this post.
Find a 9 letter string of characters that contains only letters from


such that the `hash(the_string)` is


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
I had no clue what to do when I first read this. In fact, my first attempt was to brute force my way through \({16}^{9}\sim 68\cdot {10}^9\) possibilities. Obviously we need a better method than that.
from typing import Optional
from itertools import product

alphabet = 'acdegilmnoprstuw'

def hash(string: str) -> int:
    Quick implementation of the hash function.

    string : str
        String to be hashed.
    h : int
        Hash of the input string.
    h = 7
    for character in string:
        h = h * 37 + alphabet.rfind(character)

    return h

def bruteFindString(hashToFind: int) -> Optional[str]:
    Find the string by brute force (-- a really bad idea).

    hashToFind : int
        Hash of some string we'd like to find.

    string : Optional[str]
        String whose hash equals hashToFind or None if no string was found.
    for charSubset in product(alphabet, repeat=9):
        string = ''.join(charSubset)
        if hash(string) == hashToFind:
            return string
Somehow we need to find a bias in the hash algorithm and exploit it. The first clue came when I plotted a histogram of the range of this function for random n-character strings from alphabet.
There are 16 major groups (surprise), and, looking closely, one notices that the left 8 groups of bins are a mirror image of those on the right. In other words, this hash function has an overwhelmingly biased image.

Thinking this could be related to polynomials, I started reading about string hash functions. It turns out we may write polynomials in a recursive manner, so
\begin{align}\sum_{i=0}^{n}a_{i}x^{i}&=a_{0}+a_{1}x+\cdots+a_{n}x^{n}\\&=a_{0}+x\left(a_{1}+x\left(a_{2}+\cdots+x\left(a_{n-1}+a_{n}x\right)\cdots\right)\right).\end{align}This is called Horner's method. Therefore, our hash algorithm above in expanded form is little more than the computation of a polynomial
\begin{align}h\left(x\right)&=a_{0}+a_{1}x+\cdots+a_{8}x^{8}+7\cdot x^{9},\end{align}evaluated at \(x=37\). Stated in this manner, it's at once easy to see that we're tasked with finding coefficients \(a_{0},\cdots,a_{8}\in\left[0,15\right]\subset\mathbb{Z}\) such that \(h\left(37\right)=945924806726376\). Thus, yes, there's \(16^{9}\) possible coefficient arrangements, but we can use what we know about polynomials to narrow down that search space.

First we remove the constant (I've called it a bias) \(7\cdot{37}^9\) from the resulting hash, which is also the smallest value of the hash function for a 9 character string consisting of aaaaaaaa, i.e. when \(\forall a_{i}=0\). Now, we need to find \(a_{i}\) in the equation
\begin{align}36192628160837&=\sum_{i=0}^{8}a_{i}37^{i}.\end{align}After a little more reading about the polynomial vector space, I noticed that we basically have a polynomial defined over a finite field \(\mathbb{Z}/16\mathbb{Z}\). Moreover, there's a lot of material online about finite (Galois) fields and polynomials. While writing this post, I found this set of slides to be really helpful and informative.

My solution, then, is to iterate from the largest to smallest degree polynomial basis and determine the largest coefficient a basis term (evaluated at \(x={37}\)) can have before, for instance \(37^i>36192628160837\), and subtract it. The code looks as follows.
from operator import itemgetter

def findString(hashToFind: int, letterSubsetLength: int) -> str:
    Find the string whose hash matches hashToFind.

    hashToFind : int
        Hash of some string we'd like to find.
    letterSubsetLength : int
        Number of letters used, subset of letters.

    hashedString : str
        String whose hash equals the hashToFind.

        letterSubsetLength is less than 1.
    if letterSubsetLength < 1:
        raise ValueError('Expected positive subset length')

    unBiasedHash = hashToFind - 7 * pow(37, letterSubsetLength)
    coefficients = []

    for i in range(letterSubsetLength - 1, -1, -1):
        # Determine the largest value a polynomial coefficient
        # can be before the basis is larger than the hash
        power = pow(37, i)
        coeff = unBiasedHash // power
        unBiasedHash -= coeff * power

    hashedString = ''.join(itemgetter(*coefficients)(alphabet))

    return hashedString
Of course, this implementation assumes you'll give it the hash value of a string that was hashed with hash above, and you can insert all these checks to ensure you don't get an IndexError or some other exception, but it solves this basic problem.
$ ./hashProblem.py 
I think the answer is 'promenade'