### 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

acdegilmnoprstuw

such that the hash(the_string) is

945924806726376

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.

Parameters
----------
string : str
String to be hashed.

Returns
-------
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).

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

Returns
-------
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.

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

Returns
-------
hashedString : str
String whose hash equals the hashToFind.

Raises
------
ValueError
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
coefficients.append(coeff)
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