StackOverflow challenge: Replicate (almost) HTML text-align justify

Was browsing through /r/php when I stumbled across a post titled “Fun (if you’re like me) question on stackoverflow“. It links to a StackOverflow post where someone says:

Just tanked a job interview where I was asked to implement a function with this signature: function justify($str_in, $desired_length) It needs to mimic what HTML’s text-align: justify would do, here’s some examples (desired_length = 48)

Quite an interesting little test, I thought. Has zero practical world application, but it does require the person to have a somewhat analytical mind and problem solving skills. Also a reasonable knowledge of PHP. So I thought I would have a go (without looking at others’ solutions). 10 minutes later a working script which does exactly what was requested.

Quick walkthrough

We start off by exploding the string into separate lines and looping through each one. Start with the simplest first: if the line is already over 48 characters in length then simply truncate the string and replace the spaces with dots. Next we want to explode the words into an array, which allows us to handle the second simplest test case: single words. If there is only one word then simply use str_pad().

Multiple words now. The hardest part (though not very). We need to work out how many dots we need, and how many that should be between each word (don’t forget to floor() it so we have a whole number!). The problem is this can leave fractions, so work out how many extra dots we need. We can then loop over each word and add the dots. If we have any extra dots then we can output just one of them—there will never be more than 1 extra dot per word as then that would mean the dots per word would increase!

A nice way to spend 10 minutes whilst watching a Euro 2012 game.

The resulting PHP

function justify($strIn, $desiredLength) {
    // First lets split the lines into an array
    $strIn = explode("\n", $strIn);
    // Loop over each line to test
    foreach ($strIn as $line) {
        // Strip whitespace from beginning and end
        $line = trim($line);
        // Is the string longer than 48 characters?
        if (strlen($line) >= $desiredLength) {
            // Cut it down to 48 characters and replace the spaces with dots
            echo str_replace(' ', '.', substr($line, 0, 48)) . '<br />';
        // Less than 48 characters
        // Split words into an array
        $words = explode(' ', $line);
        // How many words are there?
        $wordCount = count($words);
        // Are we dealing with only one word?
        if ($wordCount == 1) {
            // One word, just str_pad it
            echo str_pad($words[0], $desiredLength, '.', STR_PAD_BOTH) . '<br />';

        // Multiple words
        $stringLengthMinusDots = strlen(implode('', $words));
        $dotsRequired = $desiredLength - $stringLengthMinusDots;

        // How many dots do we need inbetween each word?
        // Note: We want to deduct 1 from $wordCount, we do not want dots after the last word
        $inbetween = floor($dotsRequired / (count($words) - 1));
        $inbetweenOver = $desiredLength - ($stringLengthMinusDots + ($inbetween * ($wordCount - 1)));
        // How many dots have we outputted?
        $dotsOutputted = 0;
        // Loop over the words
        foreach ($words as $index => $word) {
            // Echo out the word
            echo $word;
            // Have we already gone over our allowance?
            if ($dotsOutputted >= $dotsRequired) {
            // Do we have extra dots that we need to output?
            else if ($inbetweenOver >= 1) {
                // Extra dot, deduct one from our over count, increase the output dot count
                echo '.';
            // Echo dots and add to count
            echo str_repeat('.', $inbetween);
            $dotsOutputted += $inbetween;
        // New line
        echo '<br />';

// And run the function
justify('hello world there ok then
ok then
this string is almost certainly longer than 48 I Think so needs to be shorter
two words
three ok words
1 2 3 4 5 6 7 8 9', 48);

Update: Just saw someone on the StackOverflow post performed a benchmark with peoples answers. Run 100,000 times mine clocked in at 2.3 seconds on a 2011 MacBook Pro using MAMP (with quite a few applications running!). I imagine this will be faster than the users “single core Ubuntu VM”, though, so not too scientific…