Tetris-ment un tableau

Question

Considérons le tableau suivant :

Quel est le moyen le plus court et le plus élégant de détecter le chemin d’accès de base commun - dans ce cas

et le retirer de tous les éléments dans le tableau ?

Answer 1

Écrire une fonction `` qui prend deux chaînes comme entrée. Puis l’appliquer aux cordes afin de les réduire à leur préfixe commun. Puisqu’il est associative et commutative l’ordre n’importe pas pour le résultat.

C’est le même que pour d’autres opérations binaires comme par exemple l’ajout ou plus grand commun diviseur.

Answer 2

Charger dans une structure de données trie. À partir du nœud parent, voir qui est d’avoir un grand nombre d’enfants qu’un. Lorsque vous avez trouvé ce nœud magique, il suffit de démanteler la structure de nœuds parents et ont le nœud actuel en tant que root.

Answer 3

$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} == '/') $last_slash = $pos;
                $pos++;
        }
        return $last_slash;
}

Answer 4

Ainsi, en considérant que vous pouvez utiliser XOR dans cette situation pour trouver les parties communes de la chaîne. Tout moment vous xor de deux octets qui sont les mêmes, vous obtenez un nullbyte que la sortie. De sorte que nous pouvons l'utiliser à notre avantage:

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

Après cette boucle unique, l' $length variable sera égale à la plus longue de la commune basepart entre le tableau de chaînes de caractères. Ensuite, nous pouvons extraire la partie commune à partir du premier élément:

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

Et là vous l'avez. Comme une fonction:

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

Notez qu'il n'utilisez plus d'une itération, mais ces itérations sont effectuées dans les bibliothèques, donc dans des langages interprétés cela aura un énorme gain d'efficacité...

Maintenant, si vous voulez seulement les chemins d'accès complets, nous avons besoin de tronquer au dernier / de caractère. Donc:

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

Maintenant, il peut trop couper deux chaînes de caractères comme /foo/bar et /foo/bar/baz sera réduit à /foo. Mais à court de l'ajout d'une autre itération cycle pour déterminer si le caractère suivant est soit / ou en fin de chaîne, je ne peux pas voir un moyen de contourner ça...

Answer 5

Une approche naïve serait de faire exploser les chemins d'accès à l' / successifs et de comparer chaque élément dans les tableaux. Donc, par exemple, le premier élément serait vide dans tous les tableaux, de sorte qu'il sera supprimé, l'élément suivant sera www, il est le même dans tous les tableaux, donc il s'est retiré, etc.

Quelque chose comme (non testé)

$exploded_paths = array();

foreach($paths as $path) {
    $exploded_paths[] = explode('/', $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
        }
    }
}

Ensuite vous avez juste à faire imploser les éléments en $exploded_paths nouveau:

function impl($arr) {
    return '/' . implode('/', $arr);
}
$paths = array_map('impl', $exploded_paths);

Ce qui me donne:

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

Cela pourrait ne pas bien ;)