To zadanie polega na wyświetleniu najkrótszej ścieżki do pliku po rozszerzeniu globalnym.

Co to jest globbing powłoki? W większości pocisków możesz użyć *znaku na ścieżce, aby reprezentować dowolne znaki na danej pozycji. Na przykład, jeśli katalog foozawiera pliki bar bazi asdf, a następnie foo/b*wzrośnie do foo/bar foo/baz.

Załóżmy teraz, że bieżący katalog zawiera plik o nazwie ihavealongnamei nic więcej. Jeśli chcę odwołać się do tego pliku, mógłbym wpisać *, co będzie reprezentowało tylko ten jeden plik, zamiast wpisywać pełną nazwę.

Jeśli katalog zawiera również plik o nazwie ialsohavealongname, nie mogę tego zrobić *, ponieważ będzie pasował do obu plików. Musiałbym przynajmniej zrobić ih*.

*Wzór działa również na dopasowanie katalogów powyżej pliku szukam. Jeśli istnieją tylko dwa katalogi fooi bar, ale foozawiera tylko plik bazi barzawiera plik asdf, mogę dopasować foo/bazsię */baz. Lub jeszcze bardziej zwięźle */b*. Gdyby barbył pusty, */*działałby.

Twoje zadanie: Biorąc pod uwagę tablicę łańcuchów ścieżek reprezentujących „bieżący katalog” i jedną ścieżkę docelową, wypisz możliwie najkrótszy ciąg, który rozwinąłby się tylko do tej ścieżki docelowej po rozwinięciu * s.

Ścieżkę docelową można traktować jako własny ciąg znaków, jako indeks do tablicy ścieżek, jako pierwszy element w przekazanej tablicy ścieżek lub w inny wygodny sposób, który nie jest sztywno kodowany. Zapytaj w komentarzach, jeśli nie jesteś pewien.

Gwarantowana ścieżka docelowa znajduje się w „bieżącym katalogu”.

Możesz założyć, że wszystkie ścieżki zawierają tylko alfanumeryczne znaki ASCII (i /). Możesz przyjąć jako ścieżki wejściowe, które są zrootowane (zacznij od /) lub względne (nie zaczynaj od /).

Jeśli istnieje wiele równie krótkich możliwości, zwróć jedną lub wszystkie z nich.

To jest golf-golf, najmniej bajtów wygrywa!

Przypadki testowe , dzięki Kevin Cruijssen .

Perl 5 , 136 107 102 bajtów

Obejmuje +2dlan0

Podaj listę plików na STDIN. Zakłada się, że pierwszy jest plikiem docelowym

perl -n0E '@a="";for$a(@a){s%%s/(?=$a
)/;/g;$$_//=push@a,map$_.$a,/./g,"\\w*";/^;/>/
;/&&1/!say$a=~s/\\w//gr%e}'
foo/barber/test
foo/barber/testing
foo/barber/coding
foo/test
foo/bar/test
^D

Tylko kod bez dosłowności nowego wiersza:

@a="";for$a(@a){s%%s/(?=$a\n)/;/g;$$_//=push@a,map$_.$a,/./g,"\\w*";/^;/>/\n;/&&1/!say$a=~s/\\w//gr%e}

Celowo ulega awarii po wydrukowaniu rozwiązania.

Nadal wydaje się zbyt długi (użycie $ai 1/0jest bardzo niewygodny), ale jest to początek i powinien być dość wydajny.

Wypróbuj online!

Jak to działa

Program buduje globusy kandydujące, rozwijając je od tyłu do przodu, zaczynając od pustego łańcucha. Czyni to w szerokości pierwszej okazji, więc najpierw globs o długości 0 są sprawdzane (tylko ``), a następnie długość 1 (jak t, i, *), obok długość 2 (jak fb, i*, *g, **), obok długość 3 i tak dalej, aż do znaleziono glob, który pasuje tylko do pierwszej ścieżki. Będzie to wtedy najkrótsza kula ziemska, która rozwiązuje problem (mogą istnieć inne o tej samej długości).

Globs długości n+1są generowane z nglobusów długości , poprzedzając każdy znak z listy ścieżek, a także *przed każdym globusem długości n. Tak np długość 3 glob *i*przyczyni Length 4 globs f*i*, o*i*, o*i*, /*i*, b*i*... s*i*, t*i*a na końcu **i*. Zauważ, że każdy znak z listy ścieżek wejściowych jest poprzedzany, nawet jeśli pojawia się wiele razy lub nie ma żadnego sensu, ponieważ prowadzi do czegoś, co nigdy nie może się równać.

Robienie tego naiwnie prowadziłoby do eksplozji kombinatorycznej. Dlatego każda kandydująca glob jest oceniana pod kątem przydatności, określając, w których punktach ścieżek mogłaby pasować, gdyby glob był używany na końcu pełnego globu. Robię to, wstawiając znak ;w każdym miejscu, w którym możliwe jest dopasowanie. Na przykład dla globu t*otrzymam ciąg:

foo/barber/;tes;t
foo/barber/;tes;ting
foo/barber/coding
foo/;tes;t
foo/bar/;tes;t

To reprezentuje „siłę odróżniającą” globu. Każdy glob, który ma dokładnie taką samą moc odróżniającą, jest równie dobry. Jeśli je zastąpisz na końcu pełnego globu, wszystkie będą pasować dokładnie tymi samymi ścieżkami. Możesz więc równie dobrze użyć najkrótszego.

Rozważając nglobusy długości , najpierw spoglądam na jego siłę odróżniającą. Jeśli było to widziane wcześniej, istniała kolejna kula długości nlub krótsza, która była już rozważana i rozszerzana, więc ta kula jest bezcelowa i zostaje przycięta. Pozwoli to na przykład pozbyć się kandydatów, **i*ponieważ ta sama siła wyróżniająca będzie już postrzegana jako *i*. Przycina również niemożliwych kandydatów, f*i*ponieważ ciąg wyróżniający nie będzie miał;i po prostu być oryginalną listą ścieżek. Tylko pierwszy niemożliwy glob zostanie zaakceptowany, wszystkie pozostałe będą miały tę samą moc odróżniającą i zostaną przycięte. I nawet ten pierwszy tak naprawdę nie zostanie rozszerzony, ponieważ wszystkie rozszerzenia są nadal niemożliwe i zostaną uwzględnione, jeśli zostaną wzięte pod uwagę. Jednocześnie in*będzie przycinany przez i*itp.

Powyższe prowadzi do bardzo agresywnego przycinania, dlatego program jest w stanie obsłużyć złożone przypadki w bardzo krótkim czasie. Główną nieefektywnością jest jednak to, że poprzedza globusy kandydujące wszystkimi możliwymi znakami, nie tylko tymi znajdującymi się tuż przed ;częścią ścieżki docelowej łańcucha wyróżniającego. Wszystkie dodane postacie, które nie znajdują się przed, ;nie stanowią problemu, ponieważ prowadzą do niemożliwego globu, który zostanie przycięty, gdy zostanie rozpatrzony, ale nadal pozostawia postacie tuż przed ;innymi ścieżkami. Na koniec program buduje globusy, które będą w stanie dopasować dowolną kombinację podanych ścieżek. Nie ma pojęcia, że ​​powinien koncentrować się na pierwszej ścieżce.

Teraz rozważ rozwiązanie problemu. W podanym przykładzie może to być */*er/t. Daje to następujący ciąg wyróżniający:

;f;o;o;/barber/test
foo/barber/testing
foo/barber/coding
foo/test
foo/bar/test

Rozpoznaję rozwiązanie, mając pozycję ;na pierwszej pozycji (więc pasuje do pierwszej ścieżki) i nie mając ;na początku żadnej innej ścieżki (więc inne nie pasują)

Po wyjaśnieniu algorytmu przechodzę teraz do właściwego programu:

Kandydujące globusy będą w tablicy, @aktórą zapętlę, używając zmiennej $azawierającej aktualnie rozpatrywaną glob. Zamiast *globu użyję jednak, \w*więc $ajest to regex zamiast globu. Mam zamiar nadużyć dziwnego charakteru perla dla pętli, że można dodawać elementy do tablicy zapętlonej podczas działania pętli, a te nowe elementy zostaną przechwycone w pętli. Ponieważ podczas generowania n+1globów długości wszystkie globusy długości nsą już w tablicy, @ajest to szerokość pierwsza.

Ze względu na -n0opcję (niejawna pętla nad całym wejściem) lista ścieżek jest w $_postaci jednego dużego łańcucha z każdą ścieżką zakończoną znakiem nowej linii

@a="";                    Start everything with the length 0 glob
for$a(@a){    }           Loop over candidates in a breadth first way

Wewnątrz { }mamy:

s/(?=$a\n)/;/g            Loop over the paths and insert a ; at every
                          position that the suffix glob can match by
                          looking ahead and checking that the regex
                          under consideration can match up to the end of
                          the path we are in. The distinguishing sting is
                          now in `$_`.

Ups, właśnie zniszczyłem $_i będę go potrzebował do następnej pętli. Więc zawiń rzeczywisty działający kod

s%%  ...code.. %e

Odpowiada to pustemu ciągowi na początku $_i umożliwia uruchomienie kodu w celu ustalenia, co zostanie zastąpione. Jeśli upewnię się, że kod oceniany na pusty ciąg znaków $_na końcu pozostanie niezmieniony, nawet jeśli zmienię $_podczas code.

Wracając do zaraz po tym, jak zastąpiłem $_ciąg wyróżniający:

$$_//= expression

To jest jak:

$seen{$_} //= expression

//w perlu jest 'defined or. To jest jak zwarcie, w orktórym drugi argument jest oceniany tylko wtedy, gdy jest pierwszy undef. I można to połączyć z zadaniem, tak jak +=w niektórych innych językach. Więc jeśli klucz $_w hash %seenjest undef(co jest to co masz przy dostępie do nieistniejącego elementu) dopiero wtedy wykonać ekspresję i przypisać ją jako wartość dla klucza $_. Więc jeśli upewnię się, expressionże nie zwróci undef, oznacza to w zasadzie „oceń wyrażenie wtedy i tylko wtedy, gdy po raz pierwszy zobaczymy ten szczególny ciąg wyróżniający”. A ponieważ $_gwarantuje się, że zawiera \non, to w rzeczywistości bezpieczne jest nadużywanie globalnego skrótu perla do przechowywania ciągów wyróżniających, więc $$_zamiast$seen{$_}

Do expressionużywam:

push@a,map$_.$a,/./g,"\\w*"

Zasadniczo „Dla każdego znaku (z wyjątkiem nowej linii) w łańcuchu wyróżniającym, a także *dołącz go do bieżącej globu i wrzuć na tablicę globów kandydujących”. Execpt używam \w*dla *uzyskać poprawny regex (można używać ''zamiast ""pozbyć się jednego backslashem ale wtedy nie mogłem uruchomić mój kod z linii poleceń). Zauważ, że to również pobiera ;i dodaje je do globów kandydujących, ale później testuje je na przywrócone, $_które nie ma, ;że ponownie będzie niemożliwym globem i zostanie przycięte.

/^;/>/\n;/ &&      If the distinguishing string corresponds to a solution

say$a=~s/\\w//gr   Then replace all \w* back to * and print the solution

1/!                Say returns 1 so this becomes a division by 0.
                   The program exits by crashing after solving it

Zauważ, że /^;/>/\n;/ma wartość równoważną pustemu ciągowi w przypadku, gdy rozwiązanie nie zostało jeszcze znalezione, więc będzie to działać jako pusty ciąg zastępczy i $_zostanie przywrócony

Java 10, 854 824 796 738 728 703 688 655 652 647 624 bajtów

import java.util.*;a->f->{var L=new Stack();List<String>s;int i=999,j,k;for(var t:f.split("/")){s=new java.util.concurrent.CopyOnWriteArrayList();s.add(t);for(k=1;k>0;){k=0;for(var x:s)for(j=0;j<x.length();)if(!s.contains(f=x.substring(0,j)+"~"+x.substring(++j))){s.add(f);k=1;}}for(var x:s)s.add(x.replaceAll("~+","\\*"));L.add(s);}p(L,s=new Stack(),0,f="");for(var y:s){k=0;for(var x:a)if(x.matches(y.replace("*",".*"))&x.split("/").length==y.split("/").length)k++;if(k==1&(j=y.length())<i){f=y;i=j;}}return f;};void p(List L,List r,int d,String c){if(d==L.size())r.add(c);else for(var o:(List)L.get(d))p(L,r,d+1,c+"/"+o);}

Co za bałagan. Z pewnością nie jest to łatwe wyzwanie w Javie. Zdecydowanie można go pograć w golfa o kilkaset bajtów, ale cieszę się, że w końcu teraz działa. Mówiłem ci. :)
-5 bajtów dzięki @ceilingcat .
-23 bajty przełącza się z Java 8 na Java 10

Dane wejściowe jako tablica ciągów ścieżek do plików (z katalogami jako oddzielne elementy i wszystkie elementy zawierające wiodące /) oraz ciąg znaków z wejściową ścieżką do pliku do odszukania.

Wyjaśnienie:

Wypróbuj online. (Przypadki testowe z ialsohavealongname/ ihavealongnameaswellmają nieco krótszą długość i s.add(x.replaceAll("~+","\\*"));zostały zastąpione, {s.remove(x);s.add(x.replaceAll("~+","\\*"));}aby działały w TIO za 5-10 sekund, zamiast przekroczenia limitu czasu po ponad 60 sekundach.)

import java.util.*;   // Required import for List and Stack

// Method with String-array and String parameters and String return-type
a->f->{
  var L=new Stack();  //  Create a List of Lists
  List<String>s;      //  List of Strings (uninitialized)
  int i=999,j,k;      //  Three integers (`i` starting at 999,
                      //   because 260 is the maximum file-path length in Windows)
  for(var t:f.split("/")){
                      //  Loop over the input file-path split by "/":
    s=new java.util.concurrent.CopyOnWriteArrayList();
                      //  Create a List (which we can modify while iterating it)
    s.add(t);         //  Add the input to this List
    for(k=1;k>0;){    //  Loop as long as there are new items added to the List
      k=0;            //   Reset the newAdded-flag to false
      for(var x:s)    //   And inner loop over the List
        for(j=0;j<t.length();)
                      //    Inner loop `j` in range [0,length-of-item):
          if(!s.contains(f=x.substring(0,j)+"~"+x.substring(++j))){
                      //     Replace the character at index `j` with a '~'
                      //     And if it's a new item:
            s.add(f); //      Add it to the List
            k=1;}}    //      And set the newAdded-flag to true
    for(var x:s)      //  Loop over the List again
      s.add(x.replaceAll("~+","\\*")));
                      //   And replace all 1 or more '~' with a single asterisk
                      //   (NOTE: To reduce bytes it doesn't remove the existing items)
    L.add(s);}        //   Add this List to the List of Lists
  p(L,s=new Stack(),0,"");
                      //  Generate all permutations of the groppings
                      //  (List `s` now contains all groppings of the given file-path)
  for(var y:s){       //  Loop over the groppings in the String-List:
    k=0;              //   Reset integer `k` to 0
    for(var x:a)      //   Inner loop over the input file-paths:
      if(x.matches(y.replace("*",".*"))
                      //    If the current file-path matches the current gropping
         x.split("/").length==y.split("/").length)
                      //    and the amount of slashes are the same:
         k++;         //     Increase integer `k` by 1
    if(k==1           //   If only one of the file-paths matched,
       &(j=y.length())<i){
                      //   and the length is shorter than `i`:
      f=y;            //    Replace the result with this gropping file-path
      i=j;}}          //    And also replace `i` with this shorter `j`
  return f;}          //  Finally return this shortest gropping file-path

// Separated method to generate gropping file-path permutations given a List of Lists
void p(List L,List r,int d,String c){
  if(d==L.size())     //  If we've reached the final depth
    r.add(c);         //   Add the current gropping-file path to the result-List
  else                //  Else:
    for(var o:(List)L.get(d))
                      //   Loop over the List of the current depth:
      p(L,r,d+1,      //    Recursive call with depth+1,
        c+"/"+o);}    //    and current + "/" + item of loop

Dodatkowe ogólne wyjaśnienie:

Przykład: Weźmy /foo, /foo/bar, /foo/barber, /foo/bar/test, /foo/barber/test, /foo/barber/testing, /foo/barber/coding, /foo/testjako podane ścieżki do pliku i foo/bar/testjako wejściową ścieżkę do pliku.

1) Zaczynam od podzielenia danych wejściowych ścieżki /pliku i generuję wszystkie fragmenty tych oddzielonych słów:

foo: [foo, *oo, f*o, fo*, *o, *o*, f*, *]
bar: [bar, *ar, b*r, ba*, *r, *a*, b*, *]
test: [test, *est, t*st, te*t, tes*, *st, *e*t, *es*, t*t, t*s*, te*, *t, *s*, *e*, t*, *]

2) Następnie generuję wszystkie permutacje z tymi słowami w tej samej kolejności (stosując ponownie /pomiędzy i z przodu):

[/foo/bar/test, /foo/bar/*est, /foo/bar/t*st, /foo/bar/te*t, /foo/bar/tes*, /foo/bar/*st, /foo/bar/*e*t, /foo/bar/*es*, /foo/bar/t*t, /foo/bar/t*s*, /foo/bar/te*, /foo/bar/*t, /foo/bar/*s*, /foo/bar/*e*, /foo/bar/t*, /foo/bar/*, /foo/*ar/test, /foo/*ar/*est, /foo/*ar/t*st, /foo/*ar/te*t, /foo/*ar/tes*, /foo/*ar/*st, /foo/*ar/*e*t, /foo/*ar/*es*, /foo/*ar/t*t, /foo/*ar/t*s*, /foo/*ar/te*, /foo/*ar/*t, /foo/*ar/*s*, /foo/*ar/*e*, /foo/*ar/t*, /foo/*ar/*, /foo/b*r/test, /foo/b*r/*est, /foo/b*r/t*st, /foo/b*r/te*t, /foo/b*r/tes*, /foo/b*r/*st, /foo/b*r/*e*t, /foo/b*r/*es*, /foo/b*r/t*t, /foo/b*r/t*s*, /foo/b*r/te*, /foo/b*r/*t, /foo/b*r/*s*, /foo/b*r/*e*, /foo/b*r/t*, /foo/b*r/*, /foo/ba*/test, /foo/ba*/*est, /foo/ba*/t*st, /foo/ba*/te*t, /foo/ba*/tes*, /foo/ba*/*st, /foo/ba*/*e*t, /foo/ba*/*es*, /foo/ba*/t*t, /foo/ba*/t*s*, /foo/ba*/te*, /foo/ba*/*t, /foo/ba*/*s*, /foo/ba*/*e*, /foo/ba*/t*, /foo/ba*/*, /foo/*r/test, /foo/*r/*est, /foo/*r/t*st, /foo/*r/te*t, /foo/*r/tes*, /foo/*r/*st, /foo/*r/*e*t, /foo/*r/*es*, /foo/*r/t*t, /foo/*r/t*s*, /foo/*r/te*, /foo/*r/*t, /foo/*r/*s*, /foo/*r/*e*, /foo/*r/t*, /foo/*r/*, /foo/*a*/test, /foo/*a*/*est, /foo/*a*/t*st, /foo/*a*/te*t, /foo/*a*/tes*, /foo/*a*/*st, /foo/*a*/*e*t, /foo/*a*/*es*, /foo/*a*/t*t, /foo/*a*/t*s*, /foo/*a*/te*, /foo/*a*/*t, /foo/*a*/*s*, /foo/*a*/*e*, /foo/*a*/t*, /foo/*a*/*, /foo/b*/test, /foo/b*/*est, /foo/b*/t*st, /foo/b*/te*t, /foo/b*/tes*, /foo/b*/*st, /foo/b*/*e*t, /foo/b*/*es*, /foo/b*/t*t, /foo/b*/t*s*, /foo/b*/te*, /foo/b*/*t, /foo/b*/*s*, /foo/b*/*e*, /foo/b*/t*, /foo/b*/*, /foo/*/test, /foo/*/*est, /foo/*/t*st, /foo/*/te*t, /foo/*/tes*, /foo/*/*st, /foo/*/*e*t, /foo/*/*es*, /foo/*/t*t, /foo/*/t*s*, /foo/*/te*, /foo/*/*t, /foo/*/*s*, /foo/*/*e*, /foo/*/t*, /foo/*/*, /*oo/bar/test, /*oo/bar/*est, /*oo/bar/t*st, /*oo/bar/te*t, /*oo/bar/tes*, /*oo/bar/*st, /*oo/bar/*e*t, /*oo/bar/*es*, /*oo/bar/t*t, /*oo/bar/t*s*, /*oo/bar/te*, /*oo/bar/*t, /*oo/bar/*s*, /*oo/bar/*e*, /*oo/bar/t*, /*oo/bar/*, /*oo/*ar/test, /*oo/*ar/*est, /*oo/*ar/t*st, /*oo/*ar/te*t, /*oo/*ar/tes*, /*oo/*ar/*st, /*oo/*ar/*e*t, /*oo/*ar/*es*, /*oo/*ar/t*t, /*oo/*ar/t*s*, /*oo/*ar/te*, /*oo/*ar/*t, /*oo/*ar/*s*, /*oo/*ar/*e*, /*oo/*ar/t*, /*oo/*ar/*, /*oo/b*r/test, /*oo/b*r/*est, /*oo/b*r/t*st, /*oo/b*r/te*t, /*oo/b*r/tes*, /*oo/b*r/*st, /*oo/b*r/*e*t, /*oo/b*r/*es*, /*oo/b*r/t*t, /*oo/b*r/t*s*, /*oo/b*r/te*, /*oo/b*r/*t, /*oo/b*r/*s*, /*oo/b*r/*e*, /*oo/b*r/t*, /*oo/b*r/*, /*oo/ba*/test, /*oo/ba*/*est, /*oo/ba*/t*st, /*oo/ba*/te*t, /*oo/ba*/tes*, /*oo/ba*/*st, /*oo/ba*/*e*t, /*oo/ba*/*es*, /*oo/ba*/t*t, /*oo/ba*/t*s*, /*oo/ba*/te*, /*oo/ba*/*t, /*oo/ba*/*s*, /*oo/ba*/*e*, /*oo/ba*/t*, /*oo/ba*/*, /*oo/*r/test, /*oo/*r/*est, /*oo/*r/t*st, /*oo/*r/te*t, /*oo/*r/tes*, /*oo/*r/*st, /*oo/*r/*e*t, /*oo/*r/*es*, /*oo/*r/t*t, /*oo/*r/t*s*, /*oo/*r/te*, /*oo/*r/*t, /*oo/*r/*s*, /*oo/*r/*e*, /*oo/*r/t*, /*oo/*r/*, /*oo/*a*/test, /*oo/*a*/*est, /*oo/*a*/t*st, /*oo/*a*/te*t, /*oo/*a*/tes*, /*oo/*a*/*st, /*oo/*a*/*e*t, /*oo/*a*/*es*, /*oo/*a*/t*t, /*oo/*a*/t*s*, /*oo/*a*/te*, /*oo/*a*/*t, /*oo/*a*/*s*, /*oo/*a*/*e*, /*oo/*a*/t*, /*oo/*a*/*, /*oo/b*/test, /*oo/b*/*est, /*oo/b*/t*st, /*oo/b*/te*t, /*oo/b*/tes*, /*oo/b*/*st, /*oo/b*/*e*t, /*oo/b*/*es*, /*oo/b*/t*t, /*oo/b*/t*s*, /*oo/b*/te*, /*oo/b*/*t, /*oo/b*/*s*, /*oo/b*/*e*, /*oo/b*/t*, /*oo/b*/*, /*oo/*/test, /*oo/*/*est, /*oo/*/t*st, /*oo/*/te*t, /*oo/*/tes*, /*oo/*/*st, /*oo/*/*e*t, /*oo/*/*es*, /*oo/*/t*t, /*oo/*/t*s*, /*oo/*/te*, /*oo/*/*t, /*oo/*/*s*, /*oo/*/*e*, /*oo/*/t*, /*oo/*/*, /f*o/bar/test, /f*o/bar/*est, /f*o/bar/t*st, /f*o/bar/te*t, /f*o/bar/tes*, /f*o/bar/*st, /f*o/bar/*e*t, /f*o/bar/*es*, /f*o/bar/t*t, /f*o/bar/t*s*, /f*o/bar/te*, /f*o/bar/*t, /f*o/bar/*s*, /f*o/bar/*e*, /f*o/bar/t*, /f*o/bar/*, /f*o/*ar/test, /f*o/*ar/*est, /f*o/*ar/t*st, /f*o/*ar/te*t, /f*o/*ar/tes*, /f*o/*ar/*st, /f*o/*ar/*e*t, /f*o/*ar/*es*, /f*o/*ar/t*t, /f*o/*ar/t*s*, /f*o/*ar/te*, /f*o/*ar/*t, /f*o/*ar/*s*, /f*o/*ar/*e*, /f*o/*ar/t*, /f*o/*ar/*, /f*o/b*r/test, /f*o/b*r/*est, /f*o/b*r/t*st, /f*o/b*r/te*t, /f*o/b*r/tes*, /f*o/b*r/*st, /f*o/b*r/*e*t, /f*o/b*r/*es*, /f*o/b*r/t*t, /f*o/b*r/t*s*, /f*o/b*r/te*, /f*o/b*r/*t, /f*o/b*r/*s*, /f*o/b*r/*e*, /f*o/b*r/t*, /f*o/b*r/*, /f*o/ba*/test, /f*o/ba*/*est, /f*o/ba*/t*st, /f*o/ba*/te*t, /f*o/ba*/tes*, /f*o/ba*/*st, /f*o/ba*/*e*t, /f*o/ba*/*es*, /f*o/ba*/t*t, /f*o/ba*/t*s*, /f*o/ba*/te*, /f*o/ba*/*t, /f*o/ba*/*s*, /f*o/ba*/*e*, /f*o/ba*/t*, /f*o/ba*/*, /f*o/*r/test, /f*o/*r/*est, /f*o/*r/t*st, /f*o/*r/te*t, /f*o/*r/tes*, /f*o/*r/*st, /f*o/*r/*e*t, /f*o/*r/*es*, /f*o/*r/t*t, /f*o/*r/t*s*, /f*o/*r/te*, /f*o/*r/*t, /f*o/*r/*s*, /f*o/*r/*e*, /f*o/*r/t*, /f*o/*r/*, /f*o/*a*/test, /f*o/*a*/*est, /f*o/*a*/t*st, /f*o/*a*/te*t, /f*o/*a*/tes*, /f*o/*a*/*st, /f*o/*a*/*e*t, /f*o/*a*/*es*, /f*o/*a*/t*t, /f*o/*a*/t*s*, /f*o/*a*/te*, /f*o/*a*/*t, /f*o/*a*/*s*, /f*o/*a*/*e*, /f*o/*a*/t*, /f*o/*a*/*, /f*o/b*/test, /f*o/b*/*est, /f*o/b*/t*st, /f*o/b*/te*t, /f*o/b*/tes*, /f*o/b*/*st, /f*o/b*/*e*t, /f*o/b*/*es*, /f*o/b*/t*t, /f*o/b*/t*s*, /f*o/b*/te*, /f*o/b*/*t, /f*o/b*/*s*, /f*o/b*/*e*, /f*o/b*/t*, /f*o/b*/*, /f*o/*/test, /f*o/*/*est, /f*o/*/t*st, /f*o/*/te*t, /f*o/*/tes*, /f*o/*/*st, /f*o/*/*e*t, /f*o/*/*es*, /f*o/*/t*t, /f*o/*/t*s*, /f*o/*/te*, /f*o/*/*t, /f*o/*/*s*, /f*o/*/*e*, /f*o/*/t*, /f*o/*/*, /fo*/bar/test, /fo*/bar/*est, /fo*/bar/t*st, /fo*/bar/te*t, /fo*/bar/tes*, /fo*/bar/*st, /fo*/bar/*e*t, /fo*/bar/*es*, /fo*/bar/t*t, /fo*/bar/t*s*, /fo*/bar/te*, /fo*/bar/*t, /fo*/bar/*s*, /fo*/bar/*e*, /fo*/bar/t*, /fo*/bar/*, /fo*/*ar/test, /fo*/*ar/*est, /fo*/*ar/t*st, /fo*/*ar/te*t, /fo*/*ar/tes*, /fo*/*ar/*st, /fo*/*ar/*e*t, /fo*/*ar/*es*, /fo*/*ar/t*t, /fo*/*ar/t*s*, /fo*/*ar/te*, /fo*/*ar/*t, /fo*/*ar/*s*, /fo*/*ar/*e*, /fo*/*ar/t*, /fo*/*ar/*, /fo*/b*r/test, /fo*/b*r/*est, /fo*/b*r/t*st, /fo*/b*r/te*t, /fo*/b*r/tes*, /fo*/b*r/*st, /fo*/b*r/*e*t, /fo*/b*r/*es*, /fo*/b*r/t*t, /fo*/b*r/t*s*, /fo*/b*r/te*, /fo*/b*r/*t, /fo*/b*r/*s*, /fo*/b*r/*e*, /fo*/b*r/t*, /fo*/b*r/*, /fo*/ba*/test, /fo*/ba*/*est, /fo*/ba*/t*st, /fo*/ba*/te*t, /fo*/ba*/tes*, /fo*/ba*/*st, /fo*/ba*/*e*t, /fo*/ba*/*es*, /fo*/ba*/t*t, /fo*/ba*/t*s*, /fo*/ba*/te*, /fo*/ba*/*t, /fo*/ba*/*s*, /fo*/ba*/*e*, /fo*/ba*/t*, /fo*/ba*/*, /fo*/*r/test, /fo*/*r/*est, /fo*/*r/t*st, /fo*/*r/te*t, /fo*/*r/tes*, /fo*/*r/*st, /fo*/*r/*e*t, /fo*/*r/*es*, /fo*/*r/t*t, /fo*/*r/t*s*, /fo*/*r/te*, /fo*/*r/*t, /fo*/*r/*s*, /fo*/*r/*e*, /fo*/*r/t*, /fo*/*r/*, /fo*/*a*/test, /fo*/*a*/*est, /fo*/*a*/t*st, /fo*/*a*/te*t, /fo*/*a*/tes*, /fo*/*a*/*st, /fo*/*a*/*e*t, /fo*/*a*/*es*, /fo*/*a*/t*t, /fo*/*a*/t*s*, /fo*/*a*/te*, /fo*/*a*/*t, /fo*/*a*/*s*, /fo*/*a*/*e*, /fo*/*a*/t*, /fo*/*a*/*, /fo*/b*/test, /fo*/b*/*est, /fo*/b*/t*st, /fo*/b*/te*t, /fo*/b*/tes*, /fo*/b*/*st, /fo*/b*/*e*t, /fo*/b*/*es*, /fo*/b*/t*t, /fo*/b*/t*s*, /fo*/b*/te*, /fo*/b*/*t, /fo*/b*/*s*, /fo*/b*/*e*, /fo*/b*/t*, /fo*/b*/*, /fo*/*/test, /fo*/*/*est, /fo*/*/t*st, /fo*/*/te*t, /fo*/*/tes*, /fo*/*/*st, /fo*/*/*e*t, /fo*/*/*es*, /fo*/*/t*t, /fo*/*/t*s*, /fo*/*/te*, /fo*/*/*t, /fo*/*/*s*, /fo*/*/*e*, /fo*/*/t*, /fo*/*/*, /*o/bar/test, /*o/bar/*est, /*o/bar/t*st, /*o/bar/te*t, /*o/bar/tes*, /*o/bar/*st, /*o/bar/*e*t, /*o/bar/*es*, /*o/bar/t*t, /*o/bar/t*s*, /*o/bar/te*, /*o/bar/*t, /*o/bar/*s*, /*o/bar/*e*, /*o/bar/t*, /*o/bar/*, /*o/*ar/test, /*o/*ar/*est, /*o/*ar/t*st, /*o/*ar/te*t, /*o/*ar/tes*, /*o/*ar/*st, /*o/*ar/*e*t, /*o/*ar/*es*, /*o/*ar/t*t, /*o/*ar/t*s*, /*o/*ar/te*, /*o/*ar/*t, /*o/*ar/*s*, /*o/*ar/*e*, /*o/*ar/t*, /*o/*ar/*, /*o/b*r/test, /*o/b*r/*est, /*o/b*r/t*st, /*o/b*r/te*t, /*o/b*r/tes*, /*o/b*r/*st, /*o/b*r/*e*t, /*o/b*r/*es*, /*o/b*r/t*t, /*o/b*r/t*s*, /*o/b*r/te*, /*o/b*r/*t, /*o/b*r/*s*, /*o/b*r/*e*, /*o/b*r/t*, /*o/b*r/*, /*o/ba*/test, /*o/ba*/*est, /*o/ba*/t*st, /*o/ba*/te*t, /*o/ba*/tes*, /*o/ba*/*st, /*o/ba*/*e*t, /*o/ba*/*es*, /*o/ba*/t*t, /*o/ba*/t*s*, /*o/ba*/te*, /*o/ba*/*t, /*o/ba*/*s*, /*o/ba*/*e*, /*o/ba*/t*, /*o/ba*/*, /*o/*r/test, /*o/*r/*est, /*o/*r/t*st, /*o/*r/te*t, /*o/*r/tes*, /*o/*r/*st, /*o/*r/*e*t, /*o/*r/*es*, /*o/*r/t*t, /*o/*r/t*s*, /*o/*r/te*, /*o/*r/*t, /*o/*r/*s*, /*o/*r/*e*, /*o/*r/t*, /*o/*r/*, /*o/*a*/test, /*o/*a*/*est, /*o/*a*/t*st, /*o/*a*/te*t, /*o/*a*/tes*, /*o/*a*/*st, /*o/*a*/*e*t, /*o/*a*/*es*, /*o/*a*/t*t, /*o/*a*/t*s*, /*o/*a*/te*, /*o/*a*/*t, /*o/*a*/*s*, /*o/*a*/*e*, /*o/*a*/t*, /*o/*a*/*, /*o/b*/test, /*o/b*/*est, /*o/b*/t*st, /*o/b*/te*t, /*o/b*/tes*, /*o/b*/*st, /*o/b*/*e*t, /*o/b*/*es*, /*o/b*/t*t, /*o/b*/t*s*, /*o/b*/te*, /*o/b*/*t, /*o/b*/*s*, /*o/b*/*e*, /*o/b*/t*, /*o/b*/*, /*o/*/test, /*o/*/*est, /*o/*/t*st, /*o/*/te*t, /*o/*/tes*, /*o/*/*st, /*o/*/*e*t, /*o/*/*es*, /*o/*/t*t, /*o/*/t*s*, /*o/*/te*, /*o/*/*t, /*o/*/*s*, /*o/*/*e*, /*o/*/t*, /*o/*/*, /*o*/bar/test, /*o*/bar/*est, /*o*/bar/t*st, /*o*/bar/te*t, /*o*/bar/tes*, /*o*/bar/*st, /*o*/bar/*e*t, /*o*/bar/*es*, /*o*/bar/t*t, /*o*/bar/t*s*, /*o*/bar/te*, /*o*/bar/*t, /*o*/bar/*s*, /*o*/bar/*e*, /*o*/bar/t*, /*o*/bar/*, /*o*/*ar/test, /*o*/*ar/*est, /*o*/*ar/t*st, /*o*/*ar/te*t, /*o*/*ar/tes*, /*o*/*ar/*st, /*o*/*ar/*e*t, /*o*/*ar/*es*, /*o*/*ar/t*t, /*o*/*ar/t*s*, /*o*/*ar/te*, /*o*/*ar/*t, /*o*/*ar/*s*, /*o*/*ar/*e*, /*o*/*ar/t*, /*o*/*ar/*, /*o*/b*r/test, /*o*/b*r/*est, /*o*/b*r/t*st, /*o*/b*r/te*t, /*o*/b*r/tes*, /*o*/b*r/*st, /*o*/b*r/*e*t, /*o*/b*r/*es*, /*o*/b*r/t*t, /*o*/b*r/t*s*, /*o*/b*r/te*, /*o*/b*r/*t, /*o*/b*r/*s*, /*o*/b*r/*e*, /*o*/b*r/t*, /*o*/b*r/*, /*o*/ba*/test, /*o*/ba*/*est, /*o*/ba*/t*st, /*o*/ba*/te*t, /*o*/ba*/tes*, /*o*/ba*/*st, /*o*/ba*/*e*t, /*o*/ba*/*es*, /*o*/ba*/t*t, /*o*/ba*/t*s*, /*o*/ba*/te*, /*o*/ba*/*t, /*o*/ba*/*s*, /*o*/ba*/*e*, /*o*/ba*/t*, /*o*/ba*/*, /*o*/*r/test, /*o*/*r/*est, /*o*/*r/t*st, /*o*/*r/te*t, /*o*/*r/tes*, /*o*/*r/*st, /*o*/*r/*e*t, /*o*/*r/*es*, /*o*/*r/t*t, /*o*/*r/t*s*, /*o*/*r/te*, /*o*/*r/*t, /*o*/*r/*s*, /*o*/*r/*e*, /*o*/*r/t*, /*o*/*r/*, /*o*/*a*/test, /*o*/*a*/*est, /*o*/*a*/t*st, /*o*/*a*/te*t, /*o*/*a*/tes*, /*o*/*a*/*st, /*o*/*a*/*e*t, /*o*/*a*/*es*, /*o*/*a*/t*t, /*o*/*a*/t*s*, /*o*/*a*/te*, /*o*/*a*/*t, /*o*/*a*/*s*, /*o*/*a*/*e*, /*o*/*a*/t*, /*o*/*a*/*, /*o*/b*/test, /*o*/b*/*est, /*o*/b*/t*st, /*o*/b*/te*t, /*o*/b*/tes*, /*o*/b*/*st, /*o*/b*/*e*t, /*o*/b*/*es*, /*o*/b*/t*t, /*o*/b*/t*s*, /*o*/b*/te*, /*o*/b*/*t, /*o*/b*/*s*, /*o*/b*/*e*, /*o*/b*/t*, /*o*/b*/*, /*o*/*/test, /*o*/*/*est, /*o*/*/t*st, /*o*/*/te*t, /*o*/*/tes*, /*o*/*/*st, /*o*/*/*e*t, /*o*/*/*es*, /*o*/*/t*t, /*o*/*/t*s*, /*o*/*/te*, /*o*/*/*t, /*o*/*/*s*, /*o*/*/*e*, /*o*/*/t*, /*o*/*/*, /f*/bar/test, /f*/bar/*est, /f*/bar/t*st, /f*/bar/te*t, /f*/bar/tes*, /f*/bar/*st, /f*/bar/*e*t, /f*/bar/*es*, /f*/bar/t*t, /f*/bar/t*s*, /f*/bar/te*, /f*/bar/*t, /f*/bar/*s*, /f*/bar/*e*, /f*/bar/t*, /f*/bar/*, /f*/*ar/test, /f*/*ar/*est, /f*/*ar/t*st, /f*/*ar/te*t, /f*/*ar/tes*, /f*/*ar/*st, /f*/*ar/*e*t, /f*/*ar/*es*, /f*/*ar/t*t, /f*/*ar/t*s*, /f*/*ar/te*, /f*/*ar/*t, /f*/*ar/*s*, /f*/*ar/*e*, /f*/*ar/t*, /f*/*ar/*, /f*/b*r/test, /f*/b*r/*est, /f*/b*r/t*st, /f*/b*r/te*t, /f*/b*r/tes*, /f*/b*r/*st, /f*/b*r/*e*t, /f*/b*r/*es*, /f*/b*r/t*t, /f*/b*r/t*s*, /f*/b*r/te*, /f*/b*r/*t, /f*/b*r/*s*, /f*/b*r/*e*, /f*/b*r/t*, /f*/b*r/*, /f*/ba*/test, /f*/ba*/*est, /f*/ba*/t*st, /f*/ba*/te*t, /f*/ba*/tes*, /f*/ba*/*st, /f*/ba*/*e*t, /f*/ba*/*es*, /f*/ba*/t*t, /f*/ba*/t*s*, /f*/ba*/te*, /f*/ba*/*t, /f*/ba*/*s*, /f*/ba*/*e*, /f*/ba*/t*, /f*/ba*/*, /f*/*r/test, /f*/*r/*est, /f*/*r/t*st, /f*/*r/te*t, /f*/*r/tes*, /f*/*r/*st, /f*/*r/*e*t, /f*/*r/*es*, /f*/*r/t*t, /f*/*r/t*s*, /f*/*r/te*, /f*/*r/*t, /f*/*r/*s*, /f*/*r/*e*, /f*/*r/t*, /f*/*r/*, /f*/*a*/test, /f*/*a*/*est, /f*/*a*/t*st, /f*/*a*/te*t, /f*/*a*/tes*, /f*/*a*/*st, /f*/*a*/*e*t, /f*/*a*/*es*, /f*/*a*/t*t, /f*/*a*/t*s*, /f*/*a*/te*, /f*/*a*/*t, /f*/*a*/*s*, /f*/*a*/*e*, /f*/*a*/t*, /f*/*a*/*, /f*/b*/test, /f*/b*/*est, /f*/b*/t*st, /f*/b*/te*t, /f*/b*/tes*, /f*/b*/*st, /f*/b*/*e*t, /f*/b*/*es*, /f*/b*/t*t, /f*/b*/t*s*, /f*/b*/te*, /f*/b*/*t, /f*/b*/*s*, /f*/b*/*e*, /f*/b*/t*, /f*/b*/*, /f*/*/test, /f*/*/*est, /f*/*/t*st, /f*/*/te*t, /f*/*/tes*, /f*/*/*st, /f*/*/*e*t, /f*/*/*es*, /f*/*/t*t, /f*/*/t*s*, /f*/*/te*, /f*/*/*t, /f*/*/*s*, /f*/*/*e*, /f*/*/t*, /f*/*/*, /*/bar/test, /*/bar/*est, /*/bar/t*st, /*/bar/te*t, /*/bar/tes*, /*/bar/*st, /*/bar/*e*t, /*/bar/*es*, /*/bar/t*t, /*/bar/t*s*, /*/bar/te*, /*/bar/*t, /*/bar/*s*, /*/bar/*e*, /*/bar/t*, /*/bar/*, /*/*ar/test, /*/*ar/*est, /*/*ar/t*st, /*/*ar/te*t, /*/*ar/tes*, /*/*ar/*st, /*/*ar/*e*t, /*/*ar/*es*, /*/*ar/t*t, /*/*ar/t*s*, /*/*ar/te*, /*/*ar/*t, /*/*ar/*s*, /*/*ar/*e*, /*/*ar/t*, /*/*ar/*, /*/b*r/test, /*/b*r/*est, /*/b*r/t*st, /*/b*r/te*t, /*/b*r/tes*, /*/b*r/*st, /*/b*r/*e*t, /*/b*r/*es*, /*/b*r/t*t, /*/b*r/t*s*, /*/b*r/te*, /*/b*r/*t, /*/b*r/*s*, /*/b*r/*e*, /*/b*r/t*, /*/b*r/*, /*/ba*/test, /*/ba*/*est, /*/ba*/t*st, /*/ba*/te*t, /*/ba*/tes*, /*/ba*/*st, /*/ba*/*e*t, /*/ba*/*es*, /*/ba*/t*t, /*/ba*/t*s*, /*/ba*/te*, /*/ba*/*t, /*/ba*/*s*, /*/ba*/*e*, /*/ba*/t*, /*/ba*/*, /*/*r/test, /*/*r/*est, /*/*r/t*st, /*/*r/te*t, /*/*r/tes*, /*/*r/*st, /*/*r/*e*t, /*/*r/*es*, /*/*r/t*t, /*/*r/t*s*, /*/*r/te*, /*/*r/*t, /*/*r/*s*, /*/*r/*e*, /*/*r/t*, /*/*r/*, /*/*a*/test, /*/*a*/*est, /*/*a*/t*st, /*/*a*/te*t, /*/*a*/tes*, /*/*a*/*st, /*/*a*/*e*t, /*/*a*/*es*, /*/*a*/t*t, /*/*a*/t*s*, /*/*a*/te*, /*/*a*/*t, /*/*a*/*s*, /*/*a*/*e*, /*/*a*/t*, /*/*a*/*, /*/b*/test, /*/b*/*est, /*/b*/t*st, /*/b*/te*t, /*/b*/tes*, /*/b*/*st, /*/b*/*e*t, /*/b*/*es*, /*/b*/t*t, /*/b*/t*s*, /*/b*/te*, /*/b*/*t, /*/b*/*s*, /*/b*/*e*, /*/b*/t*, /*/b*/*, /*/*/test, /*/*/*est, /*/*/t*st, /*/*/te*t, /*/*/tes*, /*/*/*st, /*/*/*e*t, /*/*/*es*, /*/*/t*t, /*/*/t*s*, /*/*/te*, /*/*/*t, /*/*/*s*, /*/*/*e*, /*/*/t*, /*/*/*]

3) Następnie przeglądam elementy z powyższej listy i sprawdzam, czy pasuje ona tylko do pojedynczej ścieżki pliku w tablicy wejściowej ścieżek plików. (Robię to, sprawdzając dwie rzeczy: czy liczba ukośników jest taka sama i czy pasuje do wyrażenia regularnego, w którym każdy *jest zamieniany .*.)
Jeśli tak: zachowaj (pierwsze) najkrótsze, które zwracamy na końcu.