In my congratulations to Rich Hickey, I mentioned that clojure influenced my code, but that I never wrote any professionally. I did, however, apply to a job opening at FogCreek/Trello with clojure code. They gated the application process with a programming question.
I call this code the most consequential clojure code I ever wrote because it got me an interview at FogCreek, which ultimately ended up in me working at Trello for almost seven years, during which we were acquired by Atlassian.
Since the question has been publicly answered many times, and is no longer used, I’ll reproduce it here:
Find a string of characters that contains only letters from “acdegilmnoprstuw” such that the hash(the_string) is 910897038977002.
If hash is defined by the following pseudo-code:
hash (s) {
h = 7
letters = "acdegilmnoprstuw"
for(i = 0; i < s.length; i++) {
h = (h * 37 + letters.indexOf(s[i]))
}
return h
}
For example, if we were trying to find the string where hash(the_string) was 680131659347, the answer would be “leepadg”.
I chose to use clojure because I didn’t know how big the value of h was going to get and wanted access to clojure’s implementation of BigInteger, which is seamless. All integer math in clojure promotes up to whatever size integer it needs. Once I thought of using clojure, I realized that it would be seen as a fun choice by the developers reviewing the code since FogCreek had a reputation of hiring developers that were interested in weird programming languages (see wasabi).
If you don’t want any hints on how to solve this, stop here.
So, they are asking you to invert the hash() function. In general, hash functions should not be invertible, but this hash is made by using simple lossless integer arithmetic with * and +, which both have inverses (/ and -). Each step of the function is invertible, so the function itself is invertible.
I decided to start with just implementing their pseudocode in clojure.
(defn fchash [arg]
(let [letters "acdegilmnoprstuw"]
(loop [h 7 s arg]
(if-let [c (first s)]
(recur (+ (* h 37) (.indexOf letters (int c))) (rest s))
h))))
And to make sure this was correct, I evaluated (fchash "leepadg") to make sure I got 680131659347.
There are a few tricks to inverting the code.
First, you need to figure out when the loop is done. You don’t know how long the string is supposed to be, so you need to detect somehow that you are done. For this, note that the hash is originally seeded with the number 7, so we expect that we’ll eventually get back to this number in the inverted version.
Second, you need to figure out what number was added after the hash was multiplied by 7. To get that, you can use mod 37 because the number must be less than the length of the letters string (which is 16) and 16 is less than 37, so using mod gets you the number that was added to the hash after it was multiplied by 37.
That should be enough to attempt an answer (in whatever language). If you want to see what I submitted, look here: Clojure inverse hash.