Tetris-ing una matriz

8 minutos de lectura

avatar de usuario
Peka

Considere la siguiente matriz:

/www/htdocs/1/sites/lib/abcdedd
/www/htdocs/1/sites/conf/xyz
/www/htdocs/1/sites/conf/abc/def
/www/htdocs/1/sites/htdocs/xyz
/www/htdocs/1/sites/lib2/abcdedd

¿Cuál es la forma más corta y elegante de detectar el ruta base común – en este caso

/www/htdocs/1/sites/

y eliminarlo de todos los elementos de la matriz?

lib/abcdedd
conf/xyz
conf/abc/def
htdocs/xyz
lib2/abcdedd

  • Esto podría valer la pena intentarlo: en.wikibooks.org/wiki/Algorithm_implementation/Strings/… (Lo probé y funciona).

    – Richard Knop

    19 de julio de 2010 a las 9:05

  • ¡Awww! Una gran cantidad de aportes brillantes. Tomaré uno para resolver mi problema en cuestión, pero creo que para elegir realmente una respuesta aceptada justificada, tendré que comparar las soluciones. Puede tomar un tiempo hasta que lo haga, pero ciertamente lo haré.

    – Peka

    19 de julio de 2010 a las 12:39


  • título entretenido 😀 por cierto: ¿por qué no puedo encontrarte en la lista de moderadores nominados? @Pekka

    – El Surricano

    19 de enero de 2011 a las 16:38

  • ninguna respuesta aceptada durante dos años?

    – Gordon

    18 de junio de 2012 a las 19:44

  • @Pekka Acercándonos a los tres años desde que esto no tiene una respuesta aceptada 🙁 Y es un título tan increíble que lo recordé hace un momento y busqué en Google “tetrising an array”.

    – Camilo Martín

    19 de abril de 2013 a las 13:26

escribir una función longest_common_prefix que toma dos cadenas como entrada. Luego aplíquelo a las cadenas en cualquier orden para reducirlas a su prefijo común. Como es asociativo y conmutativo, el orden no importa para el resultado.

Esto es lo mismo que para otras operaciones binarias como, por ejemplo, la suma o el máximo común divisor.

  • +1. Después de comparar las 2 primeras cadenas, utilice el resultado (ruta común) para comparar con la 3.ª cadena y así sucesivamente.

    – Milan Babuškov

    18 de julio de 2010 a las 15:20


avatar de usuario
fanfarrón

Cárguelos en una estructura de datos trie. Comenzando desde el nodo principal, vea cuál tiene un hijo que cuenta más que uno. Una vez que encuentre ese nodo mágico, simplemente desmantele la estructura del nodo principal y tenga el nodo actual como raíz.

  • ¿La operación que carga los datos en la estructura de árbol trie que describe no incluiría un poco el algoritmo para encontrar el prefijo común más largo, haciendo así innecesario el uso de una estructura de árbol? Es decir, ¿por qué revisar el árbol en busca de varios niños cuando podría detectarlo mientras construye el árbol? ¿Por qué entonces un árbol en absoluto? Quiero decir, si ya comienzas con una matriz. Si puede cambiar el almacenamiento para usar solo un trie en lugar de matrices, supongo que tiene sentido.

    – Ben Schwehn

    18 de julio de 2010 a las 15:21


  • Creo que si tiene cuidado, mi solución es más eficiente que construir un trie.

    – estrella azul

    24 de julio de 2010 a las 19:50

  • Esta respuesta es incorrecta. Hay soluciones triviales publicadas en my y otras respuestas que son O (n).

    – Ari Ronen

    8 de agosto de 2010 a las 6:06


  • @el.pescado: Los intentos son de tamaño cuadrático con la longitud de la cadena de origen en el peor de los casos.

    – Billy ONeal

    8 mayo 2012 a las 17:06

avatar de usuario
Sjoerd

$common = PHP_INT_MAX;
foreach ($a as $item) {
        $common = min($common, str_common($a[0], $item, $common));
}

$result = array();
foreach ($a as $item) {
        $result[] = substr($item, $common);
}
print_r($result);

function str_common($a, $b, $max)
{
        $pos = 0;
        $last_slash = 0;
        $len = min(strlen($a), strlen($b), $max + 1);
        while ($pos < $len) {
                if ($a{$pos} != $b{$pos}) return $last_slash;
                if ($a{$pos} == "https://stackoverflow.com/") $last_slash = $pos;
                $pos++;
        }
        return $last_slash;
}

  • Esta es, con mucho, la mejor solución publicada, pero necesitaba mejoras. No tomó en cuenta la ruta común más larga anterior (posiblemente iterando sobre más de la cadena de lo necesario) y no tomó en cuenta las rutas (así que para /usr/lib y /usr/lib2 lo dio /usr/lib como el camino común más largo, en lugar de /usr/). Yo (con suerte) arreglé ambos.

    – Gabo

    18 de julio de 2010 a las 15:41


avatar de usuario
ircmaxell

Bueno, considerando que puedes usar XOR en esta situación para encontrar las partes comunes de la cadena. Cada vez que xor dos bytes que son iguales, obtiene un byte nulo como salida. Entonces podemos usar eso a nuestro favor:

$first = $array[0];
$length = strlen($first);
$count = count($array);
for ($i = 1; $i < $count; $i++) {
    $length = min($length, strspn($array[$i] ^ $first, chr(0)));
}

Después de ese bucle único, el $length variable será igual a la parte base común más larga entre la matriz de cadenas. Entonces, podemos extraer la parte común del primer elemento:

$common = substr($array[0], 0, $length);

Y ahí lo tienes. Como una función:

function commonPrefix(array $strings) {
    $first = $strings[0];
    $length = strlen($first);
    $count = count($strings);
    for ($i = 1; $i < $count; $i++) {
        $length = min($length, strspn($strings[$i] ^ $first, chr(0)));
    }
    return substr($first, 0, $length);
}

Tenga en cuenta que usa más de una iteración, pero esas iteraciones se realizan en bibliotecas, por lo que en lenguajes interpretados esto tendrá una gran ganancia de eficiencia…

Ahora, si solo desea rutas completas, debemos truncar hasta el último / personaje. Asi que:

$prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths));

Ahora, puede cortar demasiado dos hilos como /foo/bar y /foo/bar/baz será cortado a /foo. Pero antes de agregar otra ronda de iteración para determinar si el siguiente carácter es / o final de cadena, no puedo ver una forma de evitar eso …

avatar de usuario
Félix Kling

Un enfoque ingenuo sería explotar los caminos en el / y comparar sucesivamente cada elemento en las matrices. Entonces, por ejemplo, el primer elemento estaría vacío en todas las matrices, por lo que se eliminará, el siguiente elemento será wwwes el mismo en todas las matrices, por lo que se elimina, etc.

Algo como (no probado)

$exploded_paths = array();

foreach($paths as $path) {
    $exploded_paths[] = explode("https://stackoverflow.com/", $path);
}

$equal = true;
$ref = &$exploded_paths[0]; // compare against the first path for simplicity

while($equal) {   
    foreach($exploded_paths as $path_parts) {
        if($path_parts[0] !== $ref[0]) {
            $equal = false;
            break;
        }
    }
    if($equal) {
        foreach($exploded_paths as &$path_parts) {
            array_shift($path_parts); // remove the first element
        }
    }
}

Después solo tienes que implosionar los elementos en $exploded_paths otra vez:

function impl($arr) {
    return "https://stackoverflow.com/" . implode("https://stackoverflow.com/", $arr);
}
$paths = array_map('impl', $exploded_paths);

Lo que me da:

Array
(
    [0] => /lib/abcdedd
    [1] => /conf/xyz
    [2] => /conf/abc/def
    [3] => /htdocs/xyz
    [4] => /conf/xyz
)

Esto podría no escalar bien;)

Ok, no estoy seguro de que esto sea a prueba de balas, pero creo que funciona:

echo array_reduce($array, function($reducedValue, $arrayValue) {
    if($reducedValue === NULL) return $arrayValue;
    for($i = 0; $i < strlen($reducedValue); $i++) {
        if(!isset($arrayValue[$i]) || $arrayValue[$i] !== $reducedValue[$i]) {
            return substr($reducedValue, 0, $i);
        }
    }
    return $reducedValue;
});

Esto tomará el primer valor en la matriz como cadena de referencia. Luego iterará sobre la cadena de referencia y comparará cada carácter con el carácter de la segunda cadena en la misma posición. Si un carácter no coincide, la cadena de referencia se acortará a la posición del carácter y se comparará la siguiente cadena. La función devolverá la cadena coincidente más corta entonces.

El rendimiento depende de las cadenas dadas. Cuanto antes se acorte la cadena de referencia, más rápido terminará el código. Sin embargo, realmente no tengo ni idea de cómo poner eso en una fórmula.

Descubrí que el enfoque de Artefacto para ordenar las cadenas aumenta el rendimiento. agregando

asort($array);
$array = array(array_shift($array), array_pop($array));

antes de array_reduce aumentará significativamente el rendimiento.

También tenga en cuenta que esto devolverá el subcadena inicial coincidente más largaque es más versátil pero no te dará la camino común. tienes que correr

substr($result, 0, strrpos($result, "https://stackoverflow.com/"));

sobre el resultado Y luego puedes usar el resultado para eliminar los valores.

print_r(array_map(function($v) use ($path){
    return str_replace($path, '', $v);
}, $array));

que debe dar:

[0] => /lib/abcdedd
[1] => /conf/xyz/
[2] => /conf/abc/def
[3] => /htdocs/xyz
[4] => /lib2/abcdedd

Comentarios bienvenidos.

avatar de usuario
Día del Juicio Final

Puede eliminar el prefijo de la manera más rápida, leyendo cada carácter solo una vez:

function findLongestWord($lines, $delim = "https://stackoverflow.com/")
{
    $max = 0;
    $len = strlen($lines[0]); 

    // read first string once
    for($i = 0; $i < $len; $i++) {
        for($n = 1; $n < count($lines); $n++) {
            if($lines[0][$i] != $lines[$n][$i]) {
                // we've found a difference between current token
                // stop search:
                return $max;
            }
        }
        if($lines[0][$i] == $delim) {
            // we've found a complete token:
            $max = $i + 1;
        }
    }
    return $max;
}

$max = findLongestWord($lines);
// cut prefix of len "max"
for($n = 0; $n < count($lines); $n++) {
    $lines[$n] = substr(lines[$n], $max, $len);
}

  • De hecho, una comparación basada en caracteres será la más rápida. Todas las demás soluciones usan operadores “caros” que al final también harán (múltiples) comparaciones de caracteres. Incluso fue mencionado en las escrituras del Santo Joel.!

    – Jan Fabry

    9 de agosto de 2010 a las 7:03

¿Ha sido útil esta solución?