Software Programming

Kunuk Nykjaer

Code Challenge by the Trustpilot Development Team

with 6 comments


On the news

I heard Trustpilot got a huge funding.

I stumbled on their website to get some Idea what kind of company they were and to get some inspiration of how they build their website.

Then I saw they were looking for new developers and decided to see what they were looking for to get an idea of how the company operate, the tech behind the company.

They have an anagram puzzle which must be solved in order to apply for a job.
Wow, that is a very interesting concept.

Disclaimer

I will not give any spoiler, the secret phrase will not be given.

Code challenge

A programming task to test that the candidate is able to fit the job description.
The designed the assignment webpage in the Matrix movie theme.

They also have one for a frontend developer
http://followthewhiterabbit.trustpilot.com/fe/index.html

That challenge is quickly solved if you know some frontend, but in the end, they want you to create a Trustpilot widget (html component) and submit that along with your resume.
Great concept. They want to test that you can solve a realistic assignment before you are called in for an interview.


This one is for a backend developer.
http://followthewhiterabbit.trustpilot.com/cs/step3.html

You’ve made an important decision. Now, let’s get to the matter.

We have a message for you. But we hid it.
Unless you know the secret phrase, it will remain hidden.

Can you write the algorithm to find it?

Here is a couple of important hints to help you out:
– An anagram of the phrase is: “poultry outwits ants”
– The MD5 hash of the secret phrase is “4624d200580677270a54ccff86b9610e”
Here is a list of english words, it should help you out.

Type the secret phrase here to see if you found the right one
Trustpilot Development Team


The list of English words contains 99175 words.
When you type in the secret phase, the phase is translated to a SHA256 hash key which forms a part of the url which contains information of how to apply.

Ok I get it. Hash is for verification. I cannot derive the anagram words out of the MD5 hash value.
The SHA256 hash function generates a cryptic hash value, which forms part of a url. That means I cannot guess the url result.


Anagram puzzle illustrated with Legos

The Lego pieces represent the letters. The way the Lego’s are arranged represent the words.

This Lego (poultry outwits ants)
lego

Is an anagram of this Lego (the sentence we are searching for)
lego

Because they have the same amount of piece types and colors
lego

This represents a part of the sentence, an English word from the list
lego

This represents a part of the sentence, an English word from the list
lego

This represents a part of the sentence, an English word from the list
lego

They form the phrase we are looking for when taken together and arranged in a specific way.
lego

We can build Lego buildings by combining items from the list.
We know we have found the correct Lego building (secret phrase) when the MD5 function gives the provided value.


Easy solution?

This puzzle made me curious and I wanted to see if there was a ‘quick win’.
By looking at the phrase “poultry outwits ants” I get a feeling there is trustpilot word in there.
After subtracting trustpilot I got left “y ouw ants”. Yah the phrase must be “trustpilot wants you”

I type that in and expected the ‘quick win’.

To my surprise I get this page.


Yes! That is indeed an anagram of the text, you got the drift.

But you were just guessing. It is not the magic phrase.

There is no way around it. Create an algorithm to solve it for real!

Go back, and try again!


Huh?! They expected I would guess that. Cool, respect to the Trustpilot dev team to create such a puzzle that anticipated my move.
All right, well played Trustpilot dev team, well played. Game on, I take the challenge, I want to solve this.

I tried other moves to get my ‘quick win’.

I typed 4624d200580677270a54ccff86b9610e.html as part of the url which is MD5 hash which I hoped would be same as the expected url but got.

Nope 🙂

In hindsight, kinda weak try by me because SHA256 and MD5 don’t produce the same result.


They were also looking for a frontend developer and had a task which I solved and noticed it had /fe/ as part of the solution url.
I tried to substitute the url with /be/ but alas I got.

Nope 🙂


I tried to lookup the MD5 hash on md5 cracker online but no luck, no result.

Ok no quick win for me.
I have to solve this the ‘correct’ way if I want to see the result page.

This is a well-designed and fun programming challenge with the Matrix theme.
It is clearly that they have put some time and effort in building these coding challenges.
Text animations, well-thought concept, fonts and colors.

Kudos to the Trustpilot dev team.


Analysis

"poultry outwits ants"
and
"trustpilot wants you"

Have three words.
And with the two spaces in the anagram I suspect it must be 3 words from the english word list.

I sure hope so, else I suspect that this could be a subset sum problem.
If it could be any 1 to N words from the list which satisfies the anagram condition then I suspect that would be a NP-complete problem and game over for me.
Not feasible for me to solve with my knowledge and with given dataset.

Not likely to be the case as it would be like to give a challenge which is impossible to solve.
Like this XKCD 🙂 http://xkcd.com/287/

The way it is phrased in the assignment and by the anagram example suggest that it is three words from the English list in a specific order.


Goal

So the goal is clear. Find 3 words from the list in a specific order which gives the MD5 hash value "4624d200580677270a54ccff86b9610e".

Brute forcing the list with ~ 100.000 words is not feasible in a reasonable time.

Strategy

Minimize the list and filter words out which cannot be part of the solution, then when the list is small enough, do brute force for a solution.

One of the ways to test whether a is an anagram of a' is to sort and compare them.
When the list is small enough, we take three words from the list, combine the words and sort them.

Taking all possible 3 words from a list has the running time O(n^3) where n is the list length.
That means with the strategy the list must be reduced from the ~100.000 items to about in few thousands at most to get a running time within few minutes at most.

If the sorted value is the same as the sorted anagram solution, we have a 3-word candidate for a solution.
The 3-word are arranged in the possible 6-ways they can be combined and a MD5 hash is calculated. If the calculated hash value is "4624d200580677270a54ccff86b9610e", then we have found the 3-word sentence we were looking for.

Result

After coding for a while, I managed to filter and reduce the list to 1659 items.
I did the brute forcing and one matching candidate appeared after the algorithm completed in about 1 minute.

I typed in the solution.
The page navigated me to the congratulations page.

Congratulations! You found the secret phrase. Are you the One?! 😉

You’re curious and you’re up for a challenge! So we like you already.

Well, that was fun. Thanks for fun puzzles Trustpilot 🙂

Advertisements

Written by kunuk Nykjaer

June 2, 2015 at 8:40 am

Posted in Algorithm

Tagged with ,

6 Responses

Subscribe to comments with RSS.

  1. You can reduce the search space even further by grouping words from the wordlist that are anagrams of each other. That way you can get down to 1179 “keys” (sorted words) you need to combine into . Finally you can expand those keys to all available combinations and permutate those to get all possible anagrams. Still time consuming but faster.

    Johannes Edstoft Hansen

    July 26, 2016 at 9:24 pm

  2. Hi, how did you solve the front-end puzzle?

    Dan

    December 26, 2016 at 5:57 pm

    • Using the Chrome Dev Tools, DOM manipulation and frontend knowledge about how CSS, JS, HTML works.

      kunuk Nykjaer

      January 3, 2017 at 12:00 pm

      • Hello Mr. Kunuk,

        What exactly is to be solved in the front end developer challenge? All I see is a paragraph with random characters.

        Shreyash Payasam

        January 23, 2017 at 1:15 pm

      • Maybe this can give you a hint https://css-tricks.com/data-uris/

        kunuk Nykjaer

        January 24, 2017 at 3:19 pm

      • omg! what was I thinking of course! Thank you Mr. Kunuk!

        Shreyash Payasam

        January 24, 2017 at 4:35 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: