Vraag Uitvullen string-algoritme [gesloten]


Ik heb net een sollicitatiegesprek gehad waarin ik werd gevraagd om een ​​functie met deze handtekening te implementeren:

function justify($str_in, $desired_length)

Het moet nastreven wat HTML's text-align: justify zou doen, hier zijn enkele voorbeelden (desired_length = 48)

    hallo wereld daar ok dan = hallo ...... wereld ...... daar ....... ok ....... dan
    hallo = ..................... hallo .....................
    ok dan = ok ......................................... dan
    deze reeks is bijna zeker langer dan 48. Ik denk dat dit heel erg zeker is.langer dan .48.
    twee woorden = twee ....................................... woorden
    drie ok woorden = drie ................. ok .................. woorden
    1 2 3 4 5 6 7 8 9 = 1 .... 2 .... 3 ..... 4 ..... 5 ..... 6 ..... 7 ..... 8 9 .....

(Ik heb de ruimtes vervangen door te illustreren perioden)

De lengte van spaties tussen woorden mag nooit meer dan één verschillen.

ik hebben een PHP-oplossing geschreven, maar ik ben meer geïnteresseerd in de algoritmen die mensen kunnen bedenken om het probleem op te lossen. Het was mijn eerste whiteboard-vraag tijdens een sollicitatiegesprek ooit, en ik ben bang dat een combinatie van factoren me veel langer heeft geduurd dan ik had moeten doen.


48
2018-06-15 21:32


oorsprong


antwoorden:


Hier is wat ik bedacht. Ik heb de optionele toegevoegd $char parameter zodat u kunt zien wat het uitvoert - u kunt het natuurlijk in de functie trekken, zodat het prototype voldoet aan de vereiste.

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;
}

En de testgevallen:

$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";
}

En de 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)

En een demo!

Bewerk: De code opgeschoond, en Het werkt nog steeds :).


11
2018-06-15 22:54



Maakte het een persoonlijke uitdaging om geen loops / recursie of regex met callbacks te gebruiken. Ik gebruikte een single explode() en een single implode() om dit te behalen. Groot succes!

De 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;
}

Kort (348 tekens)

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);}

Algoritme / code uitleg

  1. Behandel de twee uitzonderingen (tekenreeks langer dan de maximale lengte of slechts één woord).
  2. Vind de gemiddelde benodigde ruimte tussen elk woord ($space_string_avg_length).
  3. Maak een lange en korte opvulstring voor gebruik tussen de woorden, op basis van ceil() en floor() van de $space_string_avg_length, respectievelijk.
  4. Ontdek hoeveel long fill-reeksen we nodig hebben. ($limit+1).
  5. Splits de tekst op basis van het aantal long fill-reeksen dat we nodig hebben.
  6. Vervang spaties in het laatste deel van de array, gemaakt door de splitsing, met de korte opvulreeksen.
  7. Voeg de gesplitste tekst weer samen met de lange opvulstreek toe.

testen

$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";
}

resultaten

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

Zie het rennen!


10
2018-06-16 01:00



Hier is mijn oplossing zonder vervelende lussen

function justify( $str_in, $desired_length=48 ) {
    if ( strlen( $str_in ) > $desired_length ) {
        $str_in = current( explode( "\n", wordwrap( $str_in, $desired_length ) ) );
    }
    $string_length = strlen( $str_in );
    $spaces_count = substr_count( $str_in, ' ' );
    $needed_spaces_count = $desired_length - $string_length + $spaces_count;
    if ( $spaces_count === 0 ) {
        return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH );
    }
    $spaces_per_space = ceil( $needed_spaces_count / $spaces_count );
    $spaced_string = preg_replace( '~\s+~', str_repeat( ' ', $spaces_per_space ), $str_in );
    return preg_replace_callback(
        sprintf( '~\s{%s}~', $spaces_per_space ),
        function ( $m ) use( $spaces_per_space ) {
            return str_repeat( ' ', $spaces_per_space-1 );
        },
        $spaced_string,
        strlen( $spaced_string ) - $desired_length
    );
}

Opmerkingen en uitvoer ...

https://gist.github.com/2939068

  1. Ontdek hoeveel plaatsen er zijn
  2. Ontdek hoeveel spaties nodig zijn
  3. Vervang bestaande spaties door de hoeveelheid spaties (gelijkmatig verdeeld) die nodig is om te voldoen aan of om de gewenste lengte van de regel net te overschrijden
  4. Gebruik preg_replace_callback om het aantal te vervangen \s{spaces_inserted} met \s{spaces_inserted-1} nodig om de gewenste lijnlengte te bereiken

8
2018-06-15 22:39



Ik wilde zien welk algoritme het meest efficiënt was, dus heb ik wat benchmarks uitgevoerd. Ik deed 100k herhalingen van alle 7 testgevallen. (Bestond in een Ubuntu VM met één kern)

De resultaten van @ppsreejith en @Kristian AntonsenDe code is weggelaten omdat hun code crashte toen ik probeerde het uit te voeren. @PhpMyCoderDe code liep net zo lang als ik de formattering niet naar de lengte 48 heb gedaan na de constructie van het object. Daarom is het testresultaat onvolledig. (Vast)

Benchmark-resultaten

$ php justify.bench.php
Galen (justify1): 5.1464750766754
nickb (justify2): 3.8629620075226
Paolo Bergantino (justify3): 4.3705048561096
user381521 (justify5): 8.5988481044769
vlzvl (justify7): 6.6795041561127
Alexander (justify8): 6.7060301303864
ohaal (justify9): 2.9896130561829

PhpMyCoder: 6.1514630317688 (vast!)

justify.bench.php

<?php
$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'
);
$testers = array(
    'Galen' => 'justify1',
    'nickb' => 'justify2',
    'Paolo Bergantino' => 'justify3',
//    'Kristian Antonsen' => 'justify4',
    'user381521' => 'justify5',
//    'ppsreejith' => 'justify6',
    'vlzvl' => 'justify7',
    'Alexander' => 'justify8',
    'ohaal' => 'justify9'
);
// ppsreejith and Kristian Antonsen's code crashed and burned when I tried to run it
// PhpMyCoder is a special case, but his code also crashed when doing $jus->format(48);

foreach ($testers as $tester => $func) {
    $b=microtime(true);
    for($i=0;$i<100000;$i++)
        foreach ($tests as $test)
            $func($test,48);
    $a=microtime(true);
    echo $tester.'('.$func.'): '.($a-$b)."\n";
}

echo "\n";

// Fixed!
$jus = new Justifier($tests);
$b=microtime(true);

for($i=0;$i<100000;$i++) {
    $jus->format(54);
}

$a=microtime(true);
echo 'PhpMyCoder: '.($a-$b)." (Fixed!)\n";

// ALGORITHMS BELOW

// Galen
function justify1( $str_in, $desired_length=48 ) {
    if ( strlen( $str_in ) > $desired_length ) {
        $str_in = current( explode( "\n", wordwrap( $str_in, $desired_length ) ) );
    }
    $string_length = strlen( $str_in );
    $spaces_count = substr_count( $str_in, ' ' );
    $needed_spaces_count = $desired_length - $string_length + $spaces_count;
    if ( $spaces_count === 0 ) {
        return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH );
    }
    $spaces_per_space = ceil( $needed_spaces_count / $spaces_count );
    $spaced_string = preg_replace( '~\s+~', str_repeat( ' ', $spaces_per_space ), $str_in );
    return preg_replace_callback(
        sprintf( '~\s{%s}~', $spaces_per_space ),
        function ( $m ) use( $spaces_per_space ) {
            return str_repeat( ' ', $spaces_per_space-1 );
        },
        $spaced_string,
        strlen( $spaced_string ) - $desired_length
    );
}
// nickb
function justify2($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;
}
// Paolo Bergantino
function justify3($str, $to_len) {
    $str = trim($str);
    $strlen = strlen($str);

    if($str == '') return '';

    if($strlen >= $to_len) {
        return substr($str, 0, $to_len);   
    }

    $words = explode(' ', $str);
    $word_count = count($words);
    $space_count = $word_count - 1;

    if($word_count == 1) {
        return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
    }

    $space = $to_len - $strlen + $space_count;
    $per_space = $space/$space_count;

    if(is_int($per_space)) {
        return implode($words, str_pad('', $per_space, ' '));    
    }

    $new_str = '';
    $spacing = floor($per_space);
    $new_str .= $words[0] . str_pad('', $spacing);
    foreach($words as $x => $word) {
        if($x == $word_count - 1 || $x == 0) continue;
        if($x < $word_count - 1) {
            $diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x))));
            $new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' ');
        }
    }
    $new_str .= $words[$x];

    return $new_str;   
}
// Kristian Antonsen
function justify4($str_in, $desired_length)
{
    foreach ($str_in as &$line) {
        $words = explode(' ', $line);
        $word_count = count($words) - 1;
        $spaces_to_fill = $desired_length - strlen($line) + $word_count;
        if (count($words) == 1) {
            $line = str_repeat('_', ceil($spaces_to_fill/2)) . $line
                  . str_repeat('_', floor($spaces_to_fill/2));
            continue;
        }
        $next_space = floor($spaces_to_fill/$word_count);
        $leftover_space = $spaces_to_fill % $word_count;
        $line = array_shift($words);
        foreach($words as $word) {
            $extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0;
            $leftover_space -= $extra_space;
            $line .= str_repeat('_', $next_space + $extra_space) . $word;
        }
    }
    return $str_in;
}
// user381521
function justify5 ($str, $len)
{
    // split by whitespace, remove empty strings
    $words = array_diff (preg_split ('/\s+/', $str), array (""));

    // just space if no words
    if (count ($words) == 0)
        return str_repeat (" ", $len);

    // add empty strings if only one element
    if (count ($words) == 1)
        $words = array ("", $words[0], "");

    // get number of words and spaces
    $wordcount = count ($words);
    $numspaces = $wordcount - 1;

    // get number of non-space characters
    $numchars = array_sum (array_map ("strlen", $words));

    // get number of characters remaining for space
    $remaining = $len - $numchars;

    // return if too little spaces remaining
    if ($remaining <= $numspaces)
        return substr (implode (" ", $words), 0, $len);

    // get number of spaces per space
    $spaces_per_space = $remaining / $numspaces;
    $spaces_leftover = $remaining % $numspaces;

    // make array for spaces, spread out leftover spaces
    $spaces = array_fill (0, $numspaces, $spaces_per_space);
    while ($spaces_leftover--)
        $spaces[$numspaces - $spaces_leftover - 1]++;
    $spaces[] = 0; // make count ($words) == count ($spaces)

    // join it all together
    $result = array ();
    foreach ($words as $k => $v)
        array_push ($result, $v, str_repeat (" ", $spaces[$k]));
    return implode ($result);
}
// ppsreejith
function justify6($str, $to_len) {
    $str = trim($str);
    $strlen = strlen($str);

    if($str == '') return '';

    if($strlen >= $to_len) {
        return substr($str, 0, $to_len);   
    }

    $words = explode(' ', $str);
    $word_count = count($words);
    $space_count = $word_count - 1;

    if($word_count == 1) {
        return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
    }

    $space = $to_len - $strlen + $space_count;
    $per_space = floor($space/$space_count);
    $spaces = str_pad('', $per_space, ' ');
    $curr_word = implode($words, $spaces);
    while(strlen($curr_word) < $to_len){
    $curr_word = substr($curr_word,0,preg_match("[! ][".$spaces."][! ]",$curr_word)." ".preg_match("[! ][".$spaces."][! ]",$curr_word));
    }
    return $curr_word;
}
// vlzvl
function justify7($str_in, $desired_length)
{
   $str_in = preg_replace("!\s+!"," ",$str_in);   // get rid of multiple spaces
   $words = explode(" ",$str_in);   // break words
   $num_words = sizeof($words);     // num words
   if ($num_words==1) {
      return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH);
   }
   else {
      $num_chars = 0; $lenwords = array();
      for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); }
      $each_div = round(($desired_length - $num_chars) / ($num_words-1));
      for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); }
      $space_to_addcut = ($desired_length - $sum);
      for($x=0;$x<$num_words-1;$x++) {
         $words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0));
         if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); }
      }
      return substr(implode($words),0,$desired_length);
   }
}
// Alexander
function justify8($str, $length) {
  $words   = explode(' ', $str);
  if(count($words)==1) $words = array("", $str, "");
  $spaces  = $length - array_sum(array_map("strlen", $words));
  $add     = (int)($spaces / (count($words) - 1));
  $left    = $spaces % (count($words) - 1);
  $spaced  = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1));
  $spaced .= str_repeat("_", max(1, $add));
  $spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1));
  return substr($spaced, 0, $length);
}
// ohaal
function justify9($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);}


// PhpMyCoder
class Justifier {
    private $text;

    public function __construct($text) {
        if(!is_string($text) && !is_array($text)) {
            throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text));
        }

        if(is_array($text)) {
            // String arrays must be converted to JustifierLine arrays
            $this->text = array_map(function($line) {
                return JustifierLine::fromText($line);
            }, $text);
        } else {
            // Single line of text input
            $this->text = $text;
        }
    }

    public function format($width = NULL) {
        // Strings have to be broken into an array and then jusitifed
        if(is_string($this->text)) {
            if($width == null) {
                throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided');
            }

            if($width <= 0) {
                throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width);
            }

            // Break up a JustifierLine of all text until each piece is smaller or equal to $width
            $lines = array(JustifierLine::fromText($this->text));
            $count = 0;
            $newLine = $lines[0]->breakAtColumn($width);

            while($newLine !== null) {
                $lines[] = $newLine;
                $newLine = $lines[++$count]->breakAtColumn($width);
            }
        } else {
            $lines = $this->text;

            // Allow for fluid width (uses longest line with single space)
            if($width == NULL) {
                $width = -1;

                foreach($lines as $line) {
                    // Width of line = Sum of the lengths of the words and the spaces (number of words - 1)
                    $newWidth = $line->calculateWordsLength() + $line->countWords() - 1;

                    if($newWidth > $width) { // Looking for the longest line
                        $width = $newWidth;
                    }
                }
            }
        }

        // Justify each element of array
        //$output = array_map(function($line) use ($width) {
        //    return $this->justify($line, $width);
        //}, $lines);

        $output = array();
        foreach($lines as $line) {
            $output[] = $this->justify($line, $width);
        }            

        // If a single-line is passed in, a single line is returned
        if(count($output)) {
            return $output[0];
        }

        return $output;
    }

    private function justify(JustifierLine $line, $width) {
        // Retrieve already calculated line information
        $words     = $line->extractWords();
        $spaces    = $line->countWords() - 1;
        $wordLens  = $line->findWordLengths();
        $wordsLen  = $line->calculateWordsLength();
        $minWidth  = $wordsLen + $spaces;
        $output    = '';

        if($minWidth > $width) {
            throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead');
        }

        // No spaces means only one word (center align)
        if($spaces == 0) {
            return str_pad($words[0], $width, ' ', STR_PAD_BOTH);
        }

        for(;$spaces > 0; $spaces--) {
            // Add next word to output and subtract its length from counters
            $output   .= array_shift($words);
            $length    = array_shift($wordLens);
            $wordsLen -= $length;
            $width    -= $length;

            if($spaces == 1) { // Last Iteration
                return $output . str_repeat(' ', $width - $wordsLen) . $words[0];
            }

            // Magic padding is really just simple math
            $padding  = floor(($width - $wordsLen) / $spaces);
            $output  .= str_repeat(' ', $padding);
            $width   -= $padding;
        }
    }
}

class JustifierLine {
    private $words;
    private $numWords;
    private $wordLengths;
    private $wordsLength;

    public static function fromText($text) {
        // Split words into an array
        preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER);
        $words       = $matches[0];

        // Count words
        $numWords    = count($words);

        // Find the length of each word
        $wordLengths = array_map('strlen', $words);

        //And Finally, calculate the total length of all words
        $wordsLength = array_reduce($wordLengths, function($result, $length) {
            return $result + $length;
        }, 0);

        return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
    }

    private function __construct($words, $numWords, $wordLengths, $wordsLength) {
        $this->words       = $words;
        $this->numWords    = $numWords;
        $this->wordLengths = $wordLengths;
        $this->wordsLength = $wordsLength;
    }

    public function extractWords() { return $this->words; }
    public function countWords() { return $this->numWords; }
    public function findWordLengths() { return $this->wordLengths; }
    public function calculateWordsLength() { return $this->wordsLength; }

    public function breakAtColumn($column) {
        // Avoid extraneous processing if we can determine no breaking can be done
        if($column >= ($this->wordsLength + $this->numWords - 1)) {
            return null;
        }

        $width       = 0;
        $wordsLength = 0;

        for($i = 0; $i < $this->numWords; $i++) {
            // Add width of next word
            $width += $this->wordLengths[$i];

            // If the line is overflowing past required $width
            if($width > $column) {
                // Remove overflow at end & create a new object with the overflow
                $words             = array_splice($this->words, $i);
                $numWords          = $this->numWords - $i;
                $this->numWords    = $i;
                $wordLengths       = array_splice($this->wordLengths, $i);
                $tempWordsLength   = $wordsLength;
                $wordsLength       = $this->wordsLength - $wordsLength;
                $this->wordsLength = $tempWordsLength;

                return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
            }

            $width++; // Assuming smallest spacing to fit

            // We also have to keep track of the total $wordsLength
            $wordsLength += $this->wordLengths[$i];
        }

        return null;
    }
}

6
2018-06-16 08:45



Dit is mijn oplossing. Geen vervelende reguliere expressies :)

function justify($str, $length) {
  $words   = explode(' ', $str);
  if(count($words)==1) $words = array("", $str, "");
  $spaces  = $length - array_sum(array_map("strlen", $words));
  $add     = (int)($spaces / (count($words) - 1));
  $left    = $spaces % (count($words) - 1);
  $spaced  = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1));
  $spaced .= str_repeat("_", max(1, $add));
  $spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1));
  return substr($spaced, 0, $length);
}

Dit wordt mogelijk gemaakt door PHP-arrayfuncties.

Hier is de werkend voorbeeld.


4
2018-06-15 21:34



Net zo dat niemand denkt dat ik probeer ze mijn huiswerk voor mij te laten doen, dit is mijn (werkende, ik denk) oplossing.

Ik ben er niet zeker van dat ik verwacht had dat ik zoveel code op een whiteboard kon schrijven als ik erom vroeg, dus ben ik vooral nieuwsgierig om te zien hoe anderen het aanpakken zonder naar mijn code te kijken. (Ik heb het in het interview rond de foreach gehaald voordat ze 'tijd' op mij noemden, om zo te zeggen)

function justify($str, $to_len) {
    $str = trim($str);
    $strlen = strlen($str);

    if($str == '') return '';

    if($strlen >= $to_len) {
        return substr($str, 0, $to_len);   
    }

    $words = explode(' ', $str);
    $word_count = count($words);
    $space_count = $word_count - 1;

    if($word_count == 1) {
        return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
    }

    $space = $to_len - $strlen + $space_count;
    $per_space = $space/$space_count;

    if(is_int($per_space)) {
        return implode($words, str_pad('', $per_space, ' '));    
    }

    $new_str = '';
    $spacing = floor($per_space);
    $new_str .= $words[0] . str_pad('', $spacing);
    foreach($words as $x => $word) {
        if($x == $word_count - 1 || $x == 0) continue;
        if($x < $word_count - 1) {
            $diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x))));
            $new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' ');
        }
    }
    $new_str .= $words[$x];

    return $new_str;   
}

$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 $word) {
    print $word . ' = ' . str_replace(' ', '_', justify($word, 48)) . '<br>';
}

3
2018-06-15 23:11



Ik mis mijn lijstbegrippen in Python ...

<?php
function justify ($str, $len)
{
    // split by whitespace, remove empty strings
    $words = array_diff (preg_split ('/\s+/', $str), array (""));

    // just space if no words
    if (count ($words) == 0)
        return str_repeat (" ", $len);

    // add empty strings if only one element
    if (count ($words) == 1)
        $words = array ("", $words[0], "");

    // get number of words and spaces
    $wordcount = count ($words);
    $numspaces = $wordcount - 1;

    // get number of non-space characters
    $numchars = array_sum (array_map ("strlen", $words));

    // get number of characters remaining for space
    $remaining = $len - $numchars;

    // return if too little spaces remaining
    if ($remaining <= $numspaces)
        return substr (implode (" ", $words), 0, $len);

    // get number of spaces per space
    $spaces_per_space = $remaining / $numspaces;
    $spaces_leftover = $remaining % $numspaces;

    // make array for spaces, spread out leftover spaces
    $spaces = array_fill (0, $numspaces, $spaces_per_space);
    while ($spaces_leftover--)
        $spaces[$numspaces - $spaces_leftover - 1]++;
    $spaces[] = 0; // make count ($words) == count ($spaces)

    // join it all together
    $result = array ();
    foreach ($words as $k => $v)
        array_push ($result, $v, str_repeat (" ", $spaces[$k]));
    return implode ($result);
}
?>

3
2018-06-15 22:44



Dit is mijn poging.

function justify($str_in, $desired_length)
{
    foreach ($str_in as &$line) {
        $words = explode(' ', $line);
        $word_count = count($words) - 1;
        $spaces_to_fill = $desired_length - strlen($line) + $word_count;
        if (count($words) == 1) {
            $line = str_repeat('_', ceil($spaces_to_fill/2)) . $line
                  . str_repeat('_', floor($spaces_to_fill/2));
            continue;
        }
        $next_space = floor($spaces_to_fill/$word_count);
        $leftover_space = $spaces_to_fill % $word_count;
        $line = array_shift($words);
        foreach($words as $word) {
            $extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0;
            $leftover_space -= $extra_space;
            $line .= str_repeat('_', $next_space + $extra_space) . $word;
        }
    }
    return $str_in;
}

Ik heb geprobeerd het relatief beknopt te houden, wat de leesbaarheid heeft beïnvloed. Maar hier is hoe het werkt:

Voor elk item splitsen we de woorden in een array $words. Omdat we spaties voor en na het woord willen, voegen we ook een lege reeks toe aan het begin en einde van de array.

We berekenen het resterende aantal spaties $leftover_space (dat is, de spaties die we ergens moeten invoegen), en verdeel het op aantal woorden $word_count, dus we weten het gemiddelde van het aantal spaties dat tussen elk woord moet worden geplaatst.

Telkens wanneer we een woord toevoegen, voegen we ook een paar spaties toe $extra_space, afhankelijk van hoeveel er nog zijn. Daarna verwijderen we het toegevoegde bedrag van de $leftover_space.

Voorbeelduitvoer

$data = justify($data, 48);
print_r($data);

Array
(
    [0] => 123456789012345678901234567890123456789012345678
    [1] => hello_______world_______there_______ok______then
    [2] => ______________________hello_____________________
    [3] => ok__________________________________________then
    [4] => this__string__is_almost_certainly_longer_than_48
    [5] => two________________________________________words
    [6] => three__________________ok__________________words
    [7] => 1_____2_____3_____4_____5_____6_____7_____8____9
)

2
2018-06-15 22:53



Ik denk dat dit volledig werkt: (de "_" houdt gewoon de ruimte zichtbaar)

function justify($str_in, $desired_length)
{
   $str_in = preg_replace("!\s+!"," ",$str_in);   // get rid of multiple spaces
   $words = explode(" ",$str_in);   // break words
   $num_words = sizeof($words);     // num words   
   if ($num_words==1) {   
      return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH);   
   }
   else {
      $num_chars = 0; $lenwords = array();
      for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); }
      $each_div = round(($desired_length - $num_chars) / ($num_words-1));
      for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); }
      $space_to_addcut = ($desired_length - $sum);
      for($x=0;$x<$num_words-1;$x++) {
         $words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0));
         if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); } 
      }
      return substr(implode($words),0,$desired_length);
   }
}

Bewerkt:

Functie ontdoen zich nu ook van meerdere spaties tussen woorden. Hoe het werkt (in het kort):

  • verwijdert doorlopende spaties tussen woorden
  • tel woorden dus als een (de 'Hallo' bijvoorbeeld) gewoon beide opvullen en herhalen.
  • .. anders tel de karakters van de gebruikte woorden
  • bereken de globale en gedeeltelijke ruimte om toe te voegen (de '_' bijvoorbeeld).
  • bereken de extra ruimte om toe te voegen (string len <gewenste) OF verwijder (string len> gewenste) en pas het toe op opvulling.
  • definitief, verminder de laatste reeks tot de gewenste lengte.

TESTEN:

$tests = array(
   'hello world there ok then',
   'hello',
   'ok then',
   'this string is almost certainly longer than 48 I think',
   'three ok words',
   '1 2 3 4 5 6 7 8 9',
   'Lorem Ipsum is simply dummy text'
);

$arr = array();
foreach($tests as $key=>$val) {
   $arr[$key] = justify($val,50);
   $arr[$key] .= " - (chars: ".strlen($arr[$key]).")";
}
echo "<pre>".print_r($arr,TRUE)."</pre>";

EN HET RESULTAAT:

Array
(
    [0] => hello________world_______there_______ok_______then - (chars: 50)
    [1] => ______________________hello_______________________ - (chars: 50)
    [2] => ok____________________________________________then - (chars: 50)
    [3] => this_string_is_almost_certainly_longer_than_48_I_t - (chars: 50)
    [4] => three___________________ok___________________words - (chars: 50)
    [5] => 1______2_____3_____4_____5_____6_____7_____8_____9 - (chars: 50)
    [6] => Lorem____Ipsum____is_____simply_____dummy_____text - (chars: 50)
)

DAT WAS HARD :)

EDITED 2:

Functie gaat nu over 20% sneller, omdat die benchmark me raakte :)


2
2018-06-16 02:40



De (semi-lange) oplossing

Het kostte me een tijdje om te perfectioneren (waarschijnlijk veel, veel langer dan een interviewer zou hebben toegestaan), maar ik heb een elegante OOP-oplossing met 162 regels voor dit probleem bedacht. Ik heb functionaliteit toegevoegd voor het rechtvaardigen van een enkele tekenreeks, reeks reeksen (al gescheiden in regels) of een lange tekenreeks die eerst in regels van een maximale breedte moet worden opgesplitst. Demo's volgen het codeblok.

Belangrijke notitie: Deze klasse werkt alleen in PHP 5.4. Ik besefte dit toen ik een versie op mijn eigen server PHP (5.3.6) draaide om profileringsstatistieken te krijgen met XDebug. PHP 5.3 klaagt over mijn gebruik van $this in de anonieme functie. Een snelle controle van de documenten over anonieme functies onthult dat $this kon niet worden gebruikt in de context van een anonieme functie tot 5.4. Als iemand hier een schone oplossing voor kan vinden, laat dit dan achter in de reacties.  Ondersteuning toegevoegd voor PHP 5.3!

<?php
class Justifier {
    private $text;

    public function __construct($text) {
        if(!is_string($text) && !is_array($text)) {
            throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text));
        }

        if(is_array($text)) {
            // String arrays must be converted to JustifierLine arrays
            $this->text = array_map(function($line) {
                return JustifierLine::fromText($line);
            }, $text);
        } else {
            // Single line of text input
            $this->text = $text;
        }
    }

    public function format($width = null) {
        // Strings have to be broken into an array and then jusitifed
        if(is_string($this->text)) {
            if($width == null) {
                throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided');
            }

            if($width <= 0) {
                throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width);
            }

            // Break up a JustifierLine of all text until each piece is smaller or equal to $width
            $lines = array(JustifierLine::fromText($this->text));
            $count = 0;
            $newLine = $lines[0]->breakAtColumn($width);

            while($newLine !== null) {
                $lines[] = $newLine;
                $newLine = $lines[++$count]->breakAtColumn($width);
            }
        } else {
            $lines = $this->text;

            // Allow for fluid width (uses longest line with single space)
            if($width == NULL) {
                $width = -1;

                foreach($lines as $line) {
                    // Width of line = Sum of the lengths of the words and the spaces (number of words - 1)
                    $newWidth = $line->calculateWordsLength() + $line->countWords() - 1;

                    if($newWidth > $width) { // Looking for the longest line
                        $width = $newWidth;
                    }
                }
            }
        }

        // Justify each element of array (PHP 5.4 ONLY)
        //$output = array_map(function($line) use ($width) {
        //  return $this->justify($line, $width);
        //}, $lines);

                    // Support for PHP 5.3
                    $output = array();
                    foreach($lines as $line) {
                        $output = $this->justify($line, $width);
                    }

        // If a single-line is passed in, a single line is returned
        if(count($output)) {
            return $output[0];
        }

        return $output;
    }

    private function justify(JustifierLine $line, $width) {
        // Retrieve already calculated line information
        $words     = $line->extractWords();
        $spaces    = $line->countWords() - 1;
        $wordLens  = $line->findWordLengths();
        $wordsLen  = $line->calculateWordsLength();
        $minWidth  = $wordsLen + $spaces;
        $output    = '';

        if($minWidth > $width) {
            throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead');
        }

        // No spaces means only one word (center align)
        if($spaces == 0) {
            return str_pad($words[0], $width, ' ', STR_PAD_BOTH);
        }

        for(;$spaces > 0; $spaces--) {
            // Add next word to output and subtract its length from counters
            $output   .= array_shift($words);
            $length    = array_shift($wordLens);
            $wordsLen -= $length;
            $width    -= $length;

            if($spaces == 1) { // Last Iteration
                return $output . str_repeat(' ', $width - $wordsLen) . $words[0];
            }

            // Magic padding is really just simple math
            $padding  = floor(($width - $wordsLen) / $spaces);
            $output  .= str_repeat(' ', $padding);
            $width   -= $padding;
        }
    }
}

class JustifierLine {
    private $words;
    private $numWords;
    private $wordLengths;
    private $wordsLength;

    public static function fromText($text) {
        // Split words into an array
        preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER);
        $words       = $matches[0];

        // Count words
        $numWords    = count($words);

        // Find the length of each word
        $wordLengths = array_map('strlen', $words);

        //And Finally, calculate the total length of all words
        $wordsLength = array_reduce($wordLengths, function($result, $length) {
            return $result + $length;
        }, 0);

        return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
    }

    private function __construct($words, $numWords, $wordLengths, $wordsLength) {
        $this->words       = $words;
        $this->numWords    = $numWords;
        $this->wordLengths = $wordLengths;
        $this->wordsLength = $wordsLength;
    }

    public function extractWords() { return $this->words; }
    public function countWords() { return $this->numWords; }
    public function findWordLengths() { return $this->wordLengths; }
    public function calculateWordsLength() { return $this->wordsLength; }

    public function breakAtColumn($column) {
        // Avoid extraneous processing if we can determine no breaking can be done
        if($column >= ($this->wordsLength + $this->numWords - 1)) {
            return null;
        }

        $width       = 0;
        $wordsLength = 0;

        for($i = 0; $i < $this->numWords; $i++) {
            // Add width of next word
            $width += $this->wordLengths[$i];

            // If the line is overflowing past required $width
            if($width > $column) {
                // Remove overflow at end & create a new object with the overflow
                $words             = array_splice($this->words, $i);
                $numWords          = $this->numWords - $i;
                $this->numWords    = $i;
                $wordLengths       = array_splice($this->wordLengths, $i);
                $tempWordsLength   = $wordsLength;
                $wordsLength       = $this->wordsLength - $wordsLength;
                $this->wordsLength = $tempWordsLength;

                return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
            }

            $width++; // Assuming smallest spacing to fit

            // We also have to keep track of the total $wordsLength
            $wordsLength += $this->wordLengths[$i];
        }

        return null;
    }
}

demos

Oorspronkelijke vraag (uitvullende tekstregels naar breedte = 48)

Je kunt een reeks van vele reeksen of slechts één reeks doorgeven aan Justifier. Roeping Justifier::format($desired_length) zullen altijd een reeks van gerechtvaardigde regels retourneren *als een reeks tekenreeksen of tekenreeksen die segmentatie vereisten, werd doorgegeven aan de constructor. Anders wordt een string geretourneerd. (Codepad-demo)

$jus = new Justifier(array(
    'hello world there ok then',
    'hello',
    'ok then',
    'two words',
    'three ok words',
    '1 2 3 4 5 6 7 8 9'
));

print_r( $jus->format(48) );

uitgang

Array
(
    [0] => hello      world       there       ok       then
    [1] =>                      hello                      
    [2] => ok                                          then
    [3] => two                                        words
    [4] => three                  ok                  words
    [5] => 1    2     3     4     5     6     7     8     9
)

U merkt misschien dat ik een van de testlijnen van het OP heb overgeslagen. Dit komt omdat het 54 tekens lang is en het zou overschrijden $desired_length doorgegeven aan Justifier::format(). De functie gooit een IllegalArgumentException voor breedten die niet positief zijn, niet-nulgetallen die groter of gelijk zijn aan de minimumbreedte. De minimale breedte wordt berekend door de langste regel (van alle lijnen die aan de constructor zijn doorgegeven) met enkele spatiëring te vinden.

Vloeiende breedte rechtvaardigt met een array van strings

Als u de breedte weglaat, Justifier gebruikt de breedte van de langste regel (van de lijnen die aan de constructor zijn doorgegeven) wanneer een enkele regelafstand is. Dit is dezelfde berekening als het vinden van de minimale breedte in de vorige demo. (Codepad-demo)

$jus = new Justifier(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'
));

print_r( $jus->format() );

uitgang

Array
(
    [0] => hello        world        there        ok         then
    [1] =>                         hello                         
    [2] => ok                                                then
    [3] => this string is almost certainly longer than 48 I think
    [4] => two                                              words
    [5] => three                     ok                     words
    [6] => 1     2     3     4      5      6      7      8      9
)

Een enkele reeks tekst rechtvaardigen (breedte = 48)

Ik heb ook een functie in de klasse opgenomen waarmee je een enkele, niet-verbroken reeks aan de constructor kunt doorgeven. Deze reeks kan elke lengte hebben. Wanneer je belt Justifier::format($desired_length) de string is opgedeeld in lijnen, zodat elke regel is gevuld met zoveel mogelijk tekst en gerechtvaardigd voordat een nieuwe regel wordt gestart. De klas zal klagen met een InvalidArgumentException omdat je een breedte moet geven waarin het touw kan breken. Als iemand een verstandige standaard of manier kan bedenken om programmatisch een standaard voor een string te bepalen, sta ik volledig open voor suggesties. (Codepad-demo)

$jus = new Justifier(
    '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'
);

print_r( $jus->format(48) );

uitgang

Array
(
    [0] => hello world there ok then  hello  ok  then  this
    [1] => string is almost  certainly  longer  than  48  I
    [2] => think two words three ok words 1 2 3 4 5 6 7 8 9
)

2
2018-06-16 23:11



Dit is mijn oplossing. Voor wat het waard is, kostte het me ongeveer 20 minuten om zowel de verantwoordingsfunctie als de acceptatietests ervoor uit te voeren; 5 van die minuten debuggen de functie rechtvaardigen. Ik heb ook notpad ++ gebruikt in plaats van een robuustere IDE om de interviewomgeving tot op zekere hoogte te simuleren.

Ik denk dat dit misschien een te groot probleem is voor een whiteboard-interviewvraag, tenzij de interviewer je laat schrijven in pseudocode en meer geïnteresseerd is in je denkproces dan wat je op het bord zet.

<?php


function justify($str_in, $desired_length) {
    $words = preg_split("/ +/",$str_in);
    // handle special cases
    if(count($words)==0) { return str_repeat(" ",$desired_length); }

    // turn single word case into a normal case
    if(count($words)==1) { $words = array("",$words[0],""); }

    $numwords = count($words);
    $wordlength = strlen(join("",$words));
    // handles cases where words are longer than the desired_length
    if($wordlength>($desired_length-$numwords)) { 
        return substr(join(" ",$words),0,$desired_length);
    }

    $minspace = floor(($desired_length-$wordlength)/($numwords-1));
    $extraspace = $desired_length - $wordlength - ($minspace * ($numwords-1));
    $result = $words[0];
    for($i=1;$i<$numwords;$i++) {
        if($extraspace>0) {
            $result.=" ";
            $extraspace--;
        }
        $result.=str_repeat(" ",$minspace);
        $result.=$words[$i];
    }
    return $result;
}

function acceptance_justify($orig_str, $just_str, $expected_length) {
    // should be the correct length
    if(strlen($just_str)!=$expected_length) { return false; }

    // should contain most of the words in the original string, in the right order
    if(preg_replace("/ +/","",substr($orig_str,0,$expected_length)) != preg_replace("/ +/","",substr($just_str,0,$expected_length))) { return false; }

    //spacing should be uniform (+/- 1 space)
    if(!preg_match("/( +)/",$just_str,$spaces)) { return false; }

    $space_length=strlen($spaces[0]);
    $smin=$space_length;
    $smax=$space_length;
    for($i=1;$i<count(@spaces);$i++) {
        $smin=min($smin,strlen($spaces));
        $smax=max($smax,strlen($spaces));
    }
    if(($smax-$smin)>1) { return false; }
    return true;
}

function run_test($str,$len) {
    print "<pre>";
    print "$str  ==> \n";
    $result = justify($str,$len);
    print preg_replace("/ /",".",$result) . "\n";
    print acceptance_justify($str,$result,$len)?"passed":"FAILED";
    print "\n\n</pre>";
}


run_test("hello world there ok then",48);
run_test("hello",48);
run_test("this string is almost certainly longer than 48 I think",48);
run_test("two words",48);
run_test("three ok words",48);
run_test("1 2 3 4 5 6 7 8 9",48);

1
2018-06-15 22:10