After talking about Double Squares and Peg Game, here is the last of the serie: Studious Student.

At first it may look like the easiest problem, however there is a trap here. Reading the problem quickly may let you think “oh, I just do alphabetical order and stick the words together”, but no. If you think that you’re doomed. I say that because I saw an example code on internet (in Java) which does exactly that while claiming to provide the right answer for this Facebook puzzle.

Facebook helped you a lot by putting this special case in the examples provided in the page (if it was me, I wouldn’t give it out that easily). Let’s have a look at this example:

5 jibw ji jp bw jibw

If you just order this in alphabetical order, you get “﻿bw ji jibw jibw jp”, but this is not the right answer. The right answer would be “bw jibw jibw ji jp”. That’s because alphabetical order will count a word which is equal to the beginning of the next word as having precedence. This rule is irrelevant here since all the words are concatenated into a single string.

At this third problem I was still feeling brutal, so I wrote another bruteforcing code. I noticed the maximum of word count was rather low (9 words) which makes bruteforcing a viable solution again. Going through all the possible permutations for a given set is easy (with some recursive function calls) and with only 9 elements to play with, the maximum number of values I would have to test was 362880. Of course it’ll take some time, but not that much (actually it took 30 seconds to run in PHP).

I just generate every single possible permutation, and I compare it with my “current lowest”. If the new one is lower I replace the “current lowest”, then continue to the next value. Simple. And provides the expected result.

~

As I said my only regret here is having Facebook include the trap in the example values given on the page. But still, it must have cleared a lot of the “I never read exercice texts” guys.

So, that’s all for now. I’ll be doing this again next week after the first round!