Our team was looking into project / client management solutions the other day and I came across Trello. While looking around their site, I stumbled upon their developer job listing, which included a challenge to solve as part of the application process. It looked pretty fun, so I tackled it when I got home.

## The Challenge

The challenge, in a nutshell, is to reverse engineer a sample hash function. The give pseudocode for the function is as follows:

The function should work as follows: `hash("leepadg")`

returns `680131659347`

. The question is, what string returns `956446786872726`

?

## My solution

To really get an understanding of the pseudocode, I decided to implement it in `php`

. Essentially a one-to-one translation is the following:

### Reimplementing the function recursively

While going through this, it seemed to me that this would be pretty easy to implement recursively, and I definitely felt that to reverse the hash, I'd have to do it recursively. So, I rewrite the hash function using recursion. To do this, we need to also know how deep to recurse (so that we don't create an infinite recursion loop). So, as a second parameter, we are going to pass `strlen($s)`

.

### Reversing the function

So, in thinking about reversing the hash, I knew that we'd be able to at least get the last letter of the final string (ie, the `strpos($letters, $s[$j])`

) by `$number % 37`

. Then, we could reduce the number by reversing the math with `$number - ($number % 37) / 37`

. I tested this out manually, and verified that it worked, and knew this result is what we would recurse on. But, we'd need to kill recursion at some point, right? That math would just go into negative numbers. So, we'd need a test to kill the recursion. That led me to this final solution:

Notice that we need to concatenate the string as the nested functions exit.

I've got the full code available on GitHub. Thanks to Trello for a fun challenge!!