Justify string algorithm [closed]

Question

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)

     hello world there ok then                              = hello......world......there.......ok.......then     hello                                                  = .....................hello.....................     ok then                                                = ok.........................................then     this string is almost certainly longer than 48 I think = this.string.is.almost.certainly.longer.than.48.     two words                                              = two.......................................words     three ok words                                         = three.................ok..................words     1 2 3 4 5 6 7 8 9                                      = 1....2....3.....4.....5.....6.....7.....8.....9

(I replaced the spaces with periods to illustrate)

The length of spaces between words may never differ by more than one.

I have written a PHP solution, but I am more interested in what algorithms people can come up with to solve the problem. It was my first whiteboard question at a job interview ever, and I'm afraid a combination of factors made me take way longer than I should have.

Answer 1

Here's what I came up with. I added the optional $char parameter so you can see what it's outputting - Of course you can pull it inside the function so the prototype matches the requirement.

function justify($str_in, $desired_length, $char = '_') {      // Some common vars and simple error checking / sanitation     $return = '';     $str_in = trim( $str_in);     $desired_length = intval( $desired_length);      // If we've got invalid input, we're done     if( $desired_length <= 0)         return $str_in;      // If the input string is greater than the length, we need to truncate it WITHOUT splitting words     if( strlen( $str_in) > $desired_length) {         $str = wordwrap($str_in, $desired_length);         $str = explode("\n", $str);         $str_in = $str[0];     }      $words = explode( ' ', $str_in);     $num_words = count( $words);      // If there's only one word, it's a simple edge case     if( $num_words == 1) {         $length = ($desired_length - strlen( $words[0])) / 2;         $return .= str_repeat( $char, floor( $length)) . $words[0] . str_repeat( $char, ceil( $length));     } else {         $word_length = strlen( implode( '', $words));          // Calculate the number of spaces to distribute over the words         $num_words--; // We're going to eliminate the last word         $spaces = floor( ($desired_length - $word_length) / $num_words);         $remainder = $desired_length - $word_length - ($num_words * $spaces);          $last = array_pop( $words);         foreach( $words as $word) {             // If we didn't get an even number of spaces to distribute, just tack it on to the front             $spaces_to_add = $spaces;             if( $remainder > 0) {                 $spaces_to_add++;                 $remainder--;             }              $return .= $word . str_repeat( $char, $spaces_to_add);         }         $return .= $last;     }     return $return; } 

And the test cases:

$inputs = array(      'hello world there ok then',     'hello',     'ok then',     'this string is almost certainly longer than 48 I think',     'two words',     'three ok words',     '1 2 3 4 5 6 7 8 9' );  foreach( $inputs as $x) {     $ret = justify( $x, 48);     echo 'Inp: ' . $x . " - strlen(" . strlen( $x) .  ")\n";     echo 'Out: ' . $ret . " - strlen(" . strlen( $ret) .  ")\n\n"; } 

And the output:

Inp: hello world there ok then - strlen(25) Out: hello_______world_______there_______ok______then - strlen(48)  Inp: hello - strlen(5) Out: _____________________hello______________________ - strlen(48)  Inp: ok then - strlen(7) Out: ok__________________________________________then - strlen(48)  Inp: this string is almost certainly longer than 48 I think - strlen(54) Out: this_string_is_almost_certainly_longer_than_48_I - strlen(48)  Inp: two words - strlen(9) Out: two________________________________________words - strlen(48)  Inp: three ok words - strlen(14) Out: three__________________ok__________________words - strlen(48)  Inp: 1 2 3 4 5 6 7 8 9 - strlen(17) Out: 1_____2_____3_____4_____5_____6_____7_____8____9 - strlen(48) 

And a demo!

Edit: Cleaned up the code, and it still works :).

Answer 2

Made it a personal challenge to not use any loops/recursion or regex with callbacks. I used a single explode() and a single implode() to achieve this. Great success!

The Code

function justify($str, $maxlen) {     $str = trim($str);      $strlen = strlen($str);     if ($strlen >= $maxlen) {         $str = wordwrap($str, $maxlen);         $str = explode("\n", $str);         $str = $str[0];         $strlen = strlen($str);     }      $space_count = substr_count($str, ' ');     if ($space_count === 0) {         return str_pad($str, $maxlen, ' ', STR_PAD_BOTH);     }      $extra_spaces_needed = $maxlen - $strlen;     $total_spaces = $extra_spaces_needed + $space_count;      $space_string_avg_length = $total_spaces / $space_count;     $short_string_multiplier = floor($space_string_avg_length);     $long_string_multiplier = ceil($space_string_avg_length);      $short_fill_string = str_repeat(' ', $short_string_multiplier);     $long_fill_string = str_repeat(' ', $long_string_multiplier);      $limit = ($space_string_avg_length - $short_string_multiplier) * $space_count;      $words_split_by_long = explode(' ', $str, $limit+1);     $words_split_by_short = $words_split_by_long[$limit];     $words_split_by_short = str_replace(' ', $short_fill_string, $words_split_by_short);     $words_split_by_long[$limit] = $words_split_by_short;      $result = implode($long_fill_string, $words_split_by_long);      return $result; } 

Short (348 chars)

function j($s,$m){$s=trim($s);$l=strlen($s);if($l>=$m){$s=explode("\n",wordwrap($s,$m));$s=$s[0];$l=strlen($s);}$c=substr_count($s,' ');if($c===0)return str_pad($s,$m,' ',STR_PAD_BOTH);$a=($m-$l+$c)/$c;$h=floor($a);$i=($a-$h)*$c;$w=explode(' ',$s,$i+1);$w[$i]=str_replace(' ',str_repeat(' ',$h),$w[$i]);return implode(str_repeat(' ',ceil($a)),$w);} 

Algorithm / Code explanation

1. Handle the two exceptions (string longer than max length or only one word).
2. Find the average space needed between each word ($space_string_avg_length).
3. Create a long and short fill string for use between the words, based on ceil() and floor() of the $space_string_avg_length, respectively.
4. Find out how many long fill strings we need. ($limit+1).
5. Split the text based on how many long fill strings we need.
6. Replace spaces in the last part of the array, made by the split, with the short fill strings.
7. Join the split text back together with the long fill strings.

Testing

$tests = array(     'hello world there ok then',     'hello',     'ok then',     'this string is almost certainly longer than 48 I think',     'two words',     'three ok words',     '1 2 3 4 5 6 7 8 9' );  foreach ($tests as $test) {     $len_before = strlen($test);     $processed = str_replace(' ', '_', justify($test, 48));     $len_after = strlen($processed);     echo "IN($len_before): $test\n";     echo "OUT($len_after): $processed\n"; } 

Results

IN(25): hello world there ok then OUT(48): hello_______world_______there_______ok______then IN(5): hello OUT(48): _____________________hello______________________ IN(7): ok then OUT(48): ok__________________________________________then IN(54): this string is almost certainly longer than 48 I think OUT(48): this_string_is_almost_certainly_longer_than_48_I IN(9): two words OUT(48): two________________________________________words IN(14): three ok words OUT(48): three__________________ok__________________words IN(17): 1 2 3 4 5 6 7 8 9 OUT(48): 1_____2_____3_____4_____5_____6_____7_____8____9 

See it run!