php - strip_tags - Justificar el algoritmo de cadena
strip_tags wordpress (12)
Acabo de enviar una entrevista de trabajo en la que me pidieron que implementara una función con esta firma:
function justify($str_in, $desired_length)
Debe imitar lo que haría HTML con el texto: justify haría, aquí hay algunos ejemplos (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
(Reemplazo los espacios con puntos para ilustrar)
La longitud de los espacios entre las palabras nunca puede diferir en más de uno.
He escrito una solución PHP, pero estoy más interesado en los algoritmos que la gente puede encontrar para resolver el problema. Fue mi primera pregunta de pizarra en una entrevista de trabajo, y me temo que una combinación de factores me hizo tomar mucho más tiempo del que debería.
La solución (semi-larga)
Me ha llevado un tiempo perfeccionarlo (probablemente mucho, mucho más tiempo de lo que hubiera permitido un entrevistador), pero se me ocurrió una solución OOP de 162 líneas elegante para este problema. Incluí funcionalidad para permitir la justificación de una sola cadena, una matriz de cadenas (ya separadas en líneas) o una cadena larga que debe dividirse primero en líneas de un ancho máximo. Las demostraciones siguen el bloque de código.
Nota importante: Esta clase solo funcionará en PHP 5.4. Me di cuenta de esto cuando ejecutaba una versión en mi propio servidor PHP (5.3.6) para obtener estadísticas de perfiles con XDebug. PHP 5.3 se queja sobre mi uso de Añadido soporte para PHP 5.3! $thisla función anónima. Una revisión rápida de los documentos sobre funciones anónimas revela que $thisno se pudo usar en el contexto de una función anónima hasta 5.4. Si alguien puede encontrar una solución limpia a esto, por favor déjelo en los comentarios.
<?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;
}
}
Población
Pregunta original (Justificar líneas de texto a ancho = 48)
Puede pasar una serie de muchas cadenas o solo una cadena a Justifier. Llamando Justifier::format($desired_length)será siempre devuelva una matriz de líneas justificadas * si una matriz de cadenas o cadena que requirió la segmentación se pasó al constructor. De lo contrario, se devolverá una cadena. ( Demostración del teclado )
$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) );
Salida
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
)
Puede notar que omití una de las líneas de prueba del OP. Esto se debe a que tenía 54 caracteres y superaría los $desired_lengthpasados Justifier::format(). La función arrojará un IllegalArgumentExceptionpara anchos que no son positivos, números distintos de cero que superan o son iguales al ancho mínimo. El ancho mínimo se calcula al encontrar la línea más larga (de todas las líneas pasadas al constructor) con un espaciado sencillo.
Ancho de fluido que justifica con una serie de cuerdas
Si omite el ancho, Justifierutilizará el ancho de la línea más larga (de las que se pasaron al constructor) cuando haya espacio simple. Este es el mismo cálculo que para encontrar el ancho mínimo en la demostración anterior. ( Demostración del teclado )
$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() );
Salida
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
)
Justificando una sola cadena de texto (ancho = 48)
También he incluido una característica en la clase que le permite pasar una cadena única, no rota al constructor. Esta cadena puede ser de cualquier longitud. Cuando llama, Justifier::format($desired_length)la cadena se divide en líneas, de modo que cada línea se rellena con la mayor cantidad de texto posible y se justifica antes de comenzar una nueva línea. La clase se quejará con un InvalidArgumentExceptionporque debe proporcionar un ancho en el que pueda romper la cadena. Si alguien puede pensar en un valor predeterminado razonable o una manera de determinar mediante programación un valor predeterminado para una cadena, estoy completamente abierto a las sugerencias. ( Demostración del teclado )
$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) );
Salida
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
)
Aquí está mi intento.
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;
}
He intentado mantenerlo relativamente conciso, lo que ha afectado la legibilidad. Pero así es como funciona:
Para cada entrada, dividimos las palabras en una matriz $words . Como es posible que queramos espacios antes y después de la palabra, también agregamos una cadena vacía al principio y al final de la matriz.
Calculamos la cantidad de espacios $leftover_spaceque sobran (es decir, los espacios que necesitamos insertar en algún lugar), y la dividimos por el número de palabras $word_count, de modo que sepamos el promedio de cuántos espacios hay entre cada palabra.
Cada vez que agregamos una palabra, también agregamos algunos espacios $extra_space, dependiendo de cuántos queden. Después de eso, eliminamos la cantidad añadida de la $leftover_space.
Salida de muestra
$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
)
Aquí está mi solución sin bucles molestos
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
);
}
Comentarios y salida ...
https://gist.github.com/2939068
- Descubre cuantos espacios hay
- Averigua cuántos espacios se necesitan.
- Reemplace los espacios existentes con la cantidad de espacios (distribuidos uniformemente) necesarios para cumplir o simplemente superar la longitud de línea deseada
- Use preg_replace_callback para reemplazar la cantidad de
/s{spaces_inserted}con/s{spaces_inserted-1}necesaria para cumplir con la longitud de línea deseada
Esta es mi solución. No molestos expresiones regulares :)
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);
}
Esto es impulsado por las funciones de matriz PHP .
Aquí está el ejemplo de trabajo .
Esto es lo que se me ocurrió. $char parámetro $char opcional para que pueda ver lo que está generando. Por supuesto, puede colocarlo dentro de la función para que el prototipo cumpla con el requisito.
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;
}
Y los casos de prueba:
$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";
}
Y la salida:
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)
Edición: Limpié el código, y todavía funciona :) .
Extraño mi lista de comprensión en 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);
}
?>
Quería ver qué algoritmo era el más eficiente, así que ejecuté algunos puntos de referencia. Hice 100k iteraciones de los 7 casos de prueba. (Se ejecutó en una máquina virtual de Ubuntu de un solo núcleo)
Los resultados de @ppsreejith y el código de @Kristian Antonsen se omiten, porque su código se bloqueó cuando intenté ejecutarlo. El código de @PhpMyCoder se ejecutó mientras no hice el formateo a 48 de longitud después de la construcción del objeto. Por lo tanto el resultado de la prueba es incompleto. (Fijo)
Resultados de referencia
$ 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 (Fixed!)
justificar.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;
}
}
Se convirtió en un desafío personal no usar ningún bucle / recursión o expresión regular con devoluciones de llamada. Utilicé un solo explode() y un solo implode() para lograr esto. ¡Gran éxito!
El código
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;
}
Corto (348 caracteres)
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);}
Algoritmo / explicación del código
- Maneja las dos excepciones (cadena más larga que la longitud máxima o solo una palabra).
- Encuentre el espacio promedio necesario entre cada palabra (
$space_string_avg_length). - Cree una cadena de relleno larga y corta para usar entre las palabras, en función de
ceil()yfloor()de$space_string_avg_length, respectivamente. - Averigua cuántas cadenas largas de relleno necesitamos. (
$limit+1). - Divida el texto según la cantidad de cadenas de relleno que necesitemos.
- Reemplace los espacios en la última parte de la matriz, hechos por la división, con las cadenas de relleno cortas.
- Unir el texto dividido de nuevo junto con las cadenas de relleno largo.
Pruebas
$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";
}
Resultados
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
¡Véalo correr!
Solo para que nadie piense que estoy tratando de que me hagan mi tarea, esta es mi solución (de trabajo, creo).
Sin embargo, no estoy seguro de que pudiera haber esperado que escribiera todo este código en una pizarra, por lo que, por lo general, siento curiosidad por ver cómo otros lo abordarían sin mirar mi código. (Logré llegar al foreach en la entrevista antes de que me llamaran "tiempo", por así decirlo)
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>'';
}
Aquí hay una implementación un poco diferente solo hacia el final.
<?php
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 = 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;
?>
No estoy seguro sobre el regexp, solo quise decir $spacesy no el próximo espacio.
Creo que esto está funcionando completamente: (la "_" solo mantiene el espacio visible)
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);
}
}
EDITADO:
Función ahora deshacerse de múltiples espacios entre palabras también. Cómo funciona ( en definitiva ):
- elimina espacios continuos entre palabras
- cuente las palabras de modo que si uno (el ejemplo ''hola'' ) simplemente rellene ambos y haga eco.
- .. De lo contrario, cuente los caracteres de las palabras utilizadas.
- calcule el espacio global y parcial para agregar (la ''_'' en el ejemplo).
- calcule el espacio adicional para agregar (string len <deseado) O quite (string len> deseado) y aplíquelo al relleno.
- final, reduzca la cuerda final a la longitud deseada.
PRUEBAS:
$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>";
Y EL RESULTADO:
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)
)
ESO FUE DURO :)
EDITADO 2:
La función es ahora un 20% más rápida , porque me tocó ese punto de referencia :)
Aquí está mi solución. Para lo que vale la pena, me tomó cerca de 20 minutos hacer las pruebas de justificación de función y aceptación; 5 de esos minutos depurando la función justificar. Además, utilicé notpad ++ en lugar de un IDE más robusto para intentar simular en cierta medida el entorno de la entrevista.
Creo que esto puede ser un problema demasiado grande para una pregunta de entrevista de pizarra, a menos que el entrevistador le permita escribir en pseudocódigo y esté más interesado en su proceso de pensamiento que en lo que está poniendo en la pizarra.
<?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);