Disclaimer: This post contains my solution to a HackerRank programming puzzle. If you wish to solve this problem yourself, please do so before reading this post! Also, I am still very new to Clojure and functional programming, so solutions are surely not the most ideal/idiomatic!
I recently came across HackerRank, a site with programming puzzles, and decided to try one out. The site’s still in a closed beta, so the only challenge that’s currently available is the “SpaceX” challenges. The premise is as follows:
Emily is an astronaut applying to be a part of the SpaceX project. To get the job, she must interview with a series of researchers, following this interview pattern:
She asks a factual question first, which the scientist answers in an encrypted string. The scientist immediately responds with a different string that she has to decrypt with the same key as the first. The encryption algorithm is the same for all questions.
Here’s the first challenge:
Emily: Who is the author of the book Three O’Clock Dinner?
Scientist: Mrvhsklqh Slqfnqhb
Scientist: I work for “hljkw kxqguhg dqg iliwb-wzr” hours a year. How many hours do I work?
The first 10,000 challenges follow this pattern. When I first saw this output, I noticed that the capitalization and non-alphabetic characters seemed to be preserved. I also noticed that word boundries seemed to be preserved, too. Could it be a simple substitution cipher?
Since I’ve been playing with Clojure recently, I fired up a REPL to see if I could solve the cipher.
Solving the Cipher
Googling the “Three O’Clock Dinner” tells me that Josephine Pinckney is the author. So, I started comparing the difference between the ASCII values of the coresponding characters…
1 2 3 4 5 6
So everything looks to be shifted down 3 characters. Let’s apply this to the encrypted answer:
1 2 3 4
We can pick out the words to see that the answer is 852, but clearly, substracting 3 for all characters isn’t going to produce the correct result. This is because only alphabetic characters are shifted. Also, the ‘y’ in ‘fifty’ seems to be missing. That’s becuase the cipher wraps letters; the encrypted character, ‘b’, should be shifted, like ‘a’ –> ‘z’ –> ‘x’ –> ‘y’. I whipped up the following function to shift a single character:
1 2 3 4 5 6 7 8
Dropping in this function, we get:
1 2 3 4
To speed things up, I wrote another function to take the encrypted question, it’s answer, and the encrypted number to figure out the shift width, and shift the encrypted number.
1 2 3 4 5 6
I did these three just to verify that things were working.
I quickly realized that obtaining the shift width is the tricky part of these problems. For the first challenge, it was -3, but turns out to be different between challenges. But more importantly, I had to make a Google search for each challenge… Clearly, not most efficient way to solve this
Let’s leverage the fact that all of the answers are really just a number that’s been spelled-out. There’s a pretty small set of words that can be in each answer. If we cosider each word individually, we can reduce the set of spelled-out numbers by a good amount just by the word’s length (eg. “zlclu” must be “three”, “seven”, “eight”, “fifty”, or “sixty”). Lastly, we igore words that don’t have a consistent shift width our encrypted word.
If we do this for each encrypted word and find a common shift width, we can decypher the spelled-out number.
Extracting the Value
Since a challenges is answered by providing the numeric value of the spelled-out number, we need to be able to parse the strings that we have decrypted.
After a quick search, I didn’t find an existing Clojure library for this, so I took a stab at it myself. It turned out to be a relatively simple set of functions to solve this.
1 2 3 4
Check out the source here
With the ability to solve these challenges progamatically, the only thing remaining steps are requesting challenges and submitting answers.
You can check out the full source of my solution on GitHub.
Although this wasn’t a particularly difficult programming puzzle to solve, it was a fun exercise to practice my Clojure skills.
Thanks to the @HackerRank guys for putting up the puzzles!