Wprowadzenie

Odległość Hausdorffa mierzy różnicę między dwóch podzbiorów przestrzeni metrycznej. Intuicyjnie przestrzeń metryczna to tylko pewien zestaw z wbudowaną funkcją odległości; w tym wyzwaniu wykorzystamy liczby naturalne ze zwykłym dystansem d(a, b) := abs(a - b). Odległość pomiędzy dwoma Hausdorff niepusty zestawów ograniczonych Ai Bjest przez

max(max(min(d(a, b) for b in B) for a in A),
    max(min(d(a, b) for a in A) for b in B))

w notacji podobnej do Pythona. Odległość Hausdorffa można obliczyć, znajdując element, Adla którego odległość do najbliższego elementu Bjest maksymalna, i element, Bdla którego odległość do najbliższego elementu Ajest maksymalna, a następnie biorąc maksimum tych odległości. Innymi słowy, jeśli odległość Hausdorffa jest d, to każdy element Ajest w odległości djakiegoś elementu Bi odwrotnie.

Wkład

Twoje dane wejściowe to pojedyncza lista liczb całkowitych. Zawiera tylko elementy 0,1,2,3, które wskazują, czy dany indeks listy nie jest elementem ani, Aani Btylko A, ani też Bi jednocześnie Aoraz B. Na przykład dane wejściowe [0,1,1,0,2,3]oznaczają, że A = {1,2,5}i B = {4,5}jeśli korzystamy z indeksowania opartego na 0 (co nie ma znaczenia, ponieważ nasze wskaźniki są niezmienne w tłumaczeniu).

Wydajność

Twój wynik to odległość Hausdorffa między Ai B; w powyższym przykładzie jest to 3. Jeśli któryś z zestawów jest pusty, odległość nie jest zdefiniowana i powrócisz -1.

Zasady

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

[] -> -1
[0] -> -1
[0,1,0] -> -1
[2,0,0,2] -> -1
[0,1,2,3] -> 1
[0,3,3,0,0,0,0,3] -> 0
[1,0,0,1,0,0,1,3,1] -> 7
[1,0,0,0,0,3,0,0,0,0,2] -> 5
[0,1,1,3,1,3,2,1,1,3,0,3] -> 2
[2,2,2,1,2,0,3,1,3,1,0,3] -> 3
[1,3,0,2,0,2,2,1,0,3,2,1,1,2,2] -> 2
[1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0] -> 4

CJam, 53 52 46 38 37 bajtów

3,q~f{f&:L,{L=},}$~ff{-z}_z+::e<W+:e>

Pobiera dane wejściowe STDIN jako tablicę stylu CJam:

[0 1 2 3]

Oto uprząż testowa, która konwertuje wszystkie przypadki testowe na ten format i uruchamia na nich kod. Chociaż wyniki znajdują się w polu wejściowym, nie są używane przez kod (usuń je, jeśli mi nie ufasz :)).

Wyjaśnienie

Najpierw analizujemy dane wejściowe, aby uzyskać dwa zestawy A i B:

3,q~f{f&:L,{L=},}$~
3,                  "Push [0 1 2]. 1 is for A, 2 is for B, and 0 we can luckily ignore
                     as we'll see later.";
  q~                "Read and evaluate the input.";
    f{          }   "Map this block onto the [0 1 2] array, copying in the input for
                     each iteration.";
      f&:L          "Take the bitwise AND with each element of the input and store the
                     result in L.";
          ,{  },    "Get the length N, and filter the range [0 .. N-1] by evaluating
                     the block for each element.";
            L=      "Check if the bitwise AND at that index yielded something non-zero.
                     This gives an empty array for 0, A for 1 and B for 2.";
                 $  "Sort the three arrays. This has two important effects: a) it moves
                     the empty array resulting from 0 to the front, and b) if only one
                     of A and B is empty, it moves the non-empty one to the end.";
                  ~ "Unwrap the array, dumping all three sets on the stack.";

A teraz znajdujemy absolutne różnice i wybieramy maksimum minut:

ff{-z}_z+::e<W+:e>
ff{-z}             "Turn A and B into a matrix of absolute differences.";
      _z           "Duplicate and transpose.";
        +          "Add the two together, so I've got one row of distances for
                    each element in either A or B.";
         ::e<      "Find the minimum of each row.";
             W+    "Add a -1 in case one set was empty.";
               :e> "Get the overall maximum.";

Zauważ, że przez cały czas trzymaliśmy pustą tablicę wynikającą z początkowej wartości 0na dole stosu, ale puste tablice nie wnoszą nic do wyniku.

CJam, 57 56 52 bajtów

Myślę, że można to trochę pograć w golfa, ale oto:

q~ee_{W=2%},\{W=1>},]0ff=_W%]{~ff-{:z$1<~}%W+$W=}/e>

Dane wejściowe są wyświetlane jak lista w stylu CJam, np.

[1 0 0 0 0 3 0 0 0 0 2]

5

Jak to działa :

Kod jest podzielony na dwie części:

Przetwarzanie danych wejściowych na listy Ai B:

q~ee_{W=2%},\{W=1>},]0ff=_W%]
q~                               "Eval the input array";
  ee                             "Enumerate and prepend index with each element. For ex:
                                  [5 3 6]ee gives [[0 5] [1 3] [2 6]]";
    _{W=2%},                     "Make a copy and filter out elements with value 1 or 3";
            \{W=1>},             "On the original, filter elements with value 2 or 3";
                    ]            "Wrap stack in an array. Stack right now contains
                                  enumerated A and B in an array";
                     0ff=        "Get the index of the enumerated arrays. Stack is [A B]";
                         _W%     "Make a copy and swap order. Stack is now [A B] [B A]";
                            ]    "Wrap this in an array";

Wykonanie wymaganych działań na dwóch parach Ai B:

{~ff-{:z$1<~}%W+$W=}/e>
{                  }/            "Run this loop for both the pairs, [A B] and [B A]"
 ~ff-                            "Unwrap [A B] and take difference of every pair";
     {      }%                   "For each row in the matrix difference";
      :z$                        "abs each term and then sort";
         1<~                     "Take only the first element of the array";
              W+                 "Add -1 to compensate for an empty array";
                $W=              "Take max";
                     e>          "Take max of the two maximums";

Wypróbuj online tutaj

Lua, 235 bajtów

Zdecydowanie nie zwycięzca, ale przynajmniej zabawne wyzwanie.

A={}B={}c={}d={}m=math p=m.min q=m.max u=unpack for k=1,#arg do for h=0,1 do if
arg[k]/2^h%2>=1 then A[#A+1]=k for i=1,#B do l=m.abs(B[i]-k)d[i]=p(d[i]or
l,l)c[#A]=p(c[#A]or l,l)end end A,B=B,A c,d=d,c end end
print(q(q(-1,u(c)),u(d)))

Wejście działa tak:

lua hausdorff.lua <space-separated-sequence>

... a oto skrypt testowy:

local testcase = arg[1] or 'hausdorff.lua'
print('testing '..testcase)
local function run(args) 
    return function(expected)
        local result = tonumber(
            io.popen('lua.exe '..testcase..' '..args):read'*a':match'%S+')
        print(args..' -> '..expected..' :: '..result)
        assert(result == expected,
            ("for input %q expected %s but got %s"):format(
                args, expected, result))
    end
end
run''(-1)
run'0'(-1)
run'0 1 0'(-1)
run'2 0 0 2'(-1)
run'0 1 2 3'(1)
run'0 3 3 0 0 0 0 3'(0)
run'1 0 0 1 0 0 1 3 1'(7)
run'1 0 0 0 0 3 0 0 0 0 2'(5)
run'0 1 1 3 1 3 2 1 1 3 0 3'(2)
run'2 2 2 1 2 0 3 1 3 1 0 3'(3)
run'1 3 0 2 0 2 2 1 0 3 2 1 1 2 2'(2)
run'1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0'(4)

... produkuje ...

testing hausdorff.lua
 -> -1 :: -1
0 -> -1 :: -1
0 1 0 -> -1 :: -1
2 0 0 2 -> -1 :: -1
0 1 2 3 -> 1 :: 1
0 3 3 0 0 0 0 3 -> 0 :: 0
1 0 0 1 0 0 1 3 1 -> 7 :: 7
1 0 0 0 0 3 0 0 0 0 2 -> 5 :: 5
0 1 1 3 1 3 2 1 1 3 0 3 -> 2 :: 2
2 2 2 1 2 0 3 1 3 1 0 3 -> 3 :: 3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2 -> 2 :: 2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0 -> 4 :: 4

Pyth, 43 40 39 38 bajtów

J+m0yQQLq3.|Fb?eS.e&Yfy:J-kT+hkT0JyJ_1

Mój algorytm działa bezpośrednio na ciągu wejściowym i nigdy nie konwertuje tych liczb. Oblicza się tylko raz maksimum, a nigdy minimum.

Dzięki @isaacg za zapisanie jednego bajtu.

Wypróbuj online: Pyth Compiler / Executor

Objaśnienia:

Najpierw wstawię dużo zer przed wejściem.

          implicit: Q = input()
    yQ    powerset(Q)
  m0yQ    map each element of the powerset to 0 (creates 2^Q zeros, I said lots)
 +    Q   zeros + Q
J         assign to J

Następnie definiuję funkcję pomocnika y, która mówi, czy indeksy listy (takie jak wejściowa) pojawiają się w obu zestawach A i BEg y([0, 1, 0, 0, 1, 1]) = False, ale y([0, 1, 0, 2]) = y([3]) = True.

Lq3.|Fb
L          define a function y(b), which returns _
   .|Fb       fold b by bitwise or
 q3            == 3

Następnie najpierw sprawdzam, czy wynik jest -1.

?...yJ_1   print ... if numbers appear in both sets (`yJ`) else -1   

Teraz do ciekawych rzeczy:

  .e              J    map each pair k,Y in enumerate(J) to:
    &Y                   Y and ... (acts as 0 if Y == 0 else ...)
      f          0       find the first number T >= 0, where:
       y                    indices appear in both sets in the substring
        :J-kT+hkT           J[k-T:k+T+1]
eS                     sort and take last element (maximum)

Zauważ, że zawsze znajdę liczbę T, ponieważ już wiem, że wskaźniki pojawiają się w obu zestawach na liście J. Liczba jest maksymalna length(Q). Jest to również powód wstawiania zer. Jeśli length(Q)wstawiono co najmniej zera, k-Tzawsze >= 0jest to konieczne, co jest potrzebne do podziału listy. Dlaczego więc wstawiam 2^length(Q)zera zamiast length(Q)zera? W przypadku testowym []potrzebuję co najmniej 1 zero, w przeciwnym razie yJzwróci błąd.

Mathematica, 88 bajtów

Max[Min/@#,Min/@Thread@#,-1]/.∞->-1&@Outer[Abs[#-#2]&,p=Position;p[#,1|3],p[#,2|3],1]&

Haskell, 145 126 124 bajtów

s t x=[e|(e,i)<-zip[0..]x,t i]
d#e=maximum[minimum[abs$i-j|j<-e]|i<-d]
[]%_= -1
_%[]= -1
d%e=max(d#e)$e#d
f x=s(>1)x%s odd x

Testowe uruchomienie:

*Main> map f [[], [0], [0,1,0], [2,0,0,2], [0,1,2,3],
              [0,3,3,0,0,0,0,3], [1,0,0,1,0,0,1,3,1],
              [1,0,0,0,0,3,0,0,0,0,2], [0,1,1,3,1,3,2,1,1,3,0,3],
              [2,2,2,1,2,0,3,1,3,1,0,3],
              [1,3,0,2,0,2,2,1,0,3,2,1,1,2,2],
              [1,0,1,1,2,0,1,2,3,1,0,0,0,1,2,0]]

[-1,-1,-1,-1,1,0,7,5,2,3,2,4]

sfiltruje liczby naturalne według predykatu ti listy danych wejściowych x. #oblicza maksymalną odległość jego parametrów di e. %łapie puste zestawy A lub B lub przyjmuje końcowe maksimum d#ei e#d. fto główna funkcja, która wywołuje %zestaw A i B.

Edycja: @Zgarb znalazł wiele bajtów do zapisania; @ ali0sha inny 2. Dzięki!

Perl, 56 55

Dodano +2 do -lp.

Lista wejściowa powinna być podana na stdin bez spacji, np .:

echo 1011201231000120 | perl -lp hausdorf.pl

hausdorf.pl:

s%%$z=$_&=$p|=$'|P.$p;$q+=!!y/12/3/%eg;$_=$z=~3?$q:-1

Aby wesprzeć spacje między elementami listy wejściowej, wystarczy podzielić finał $qprzez 2 za koszt 2 pociągnięć

Python 2, 124

To zdecydowanie wydaje się nieoptymalne. No cóż.

lambda a,E=enumerate:-min([1]+[~l*(n<3)for i,n in E(a)for l,_ in E(a)if{0}|set(n*a+n/3*[5])>{0,n}>=set(a[max(i-l,0):i-~l])])

APL (49)

{(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆}

Przypadki testowe:

      ({(⊂⍬)∊∆←(↓2 2⊤⍵)/¨⊂⍳⍴⍵:¯1⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆} ¨ testcases) ,⍨ '→',⍨ ↑ ⍕¨testcases
                               → ¯1
0                              → ¯1
0 1 0                          → ¯1
2 0 0 2                        → ¯1
0 1 2 3                        →  1
0 3 3 0 0 0 0 3                →  0
1 0 0 1 0 0 1 3 1              →  7
1 0 0 0 0 3 0 0 0 0 2          →  5
0 1 1 3 1 3 2 1 1 3 0 3        →  2
2 2 2 1 2 0 3 1 3 1 0 3        →  3
1 3 0 2 0 2 2 1 0 3 2 1 1 2 2  →  2
1 0 1 1 2 0 1 2 3 1 0 0 0 1 2 0→  4

Wyjaśnienie:

• ⍳⍴⍵: uzyskaj listę liczb od 1 do długości listy danych wejściowych
• ↓2 2⊤⍵: dla każdej wartości na liście wejściowej pobierz pierwszy bajt i drugi bajt
• ∆←(... )/⊂⍳⍴⍵: dla obu list bajtów wybierz odpowiednie wartości z ⍳⍴⍵. Przechowuj je w ∆.

• (⊂⍬)∊∆... :¯1: jeśli ta lista zawiera pustą listę, wróć -1. Inaczej:

• |∘.-/∆: uzyskaj absolutną różnicę między każdą parą wartości, podając macierz

• (+,⍉¨): uzyskaj obróconą i nieobróconą kopię tej matrycy
• {⌈/⌊/⍵}: dla obu macierzy uzyskaj maksimum minimum wierszy
• ⌈/: a następnie uzyskaj maksimum tego

Perl, 189 176 157B

Teraz z 500% większym stanem.

use List::Util qw'max min';@I=<>;sub f{$n=($n%2)+1;map{$I[$_]&$n?$_:()}0..$#I}sub i{@t=f;max map{$b=$_;min map{abs$_-$b}@t}f}$r=max i,i;print defined$r?$r:-1

Czytelny:

use List::Util qw'max min';
@I=<>;
sub f {
    $n = ($n%2) + 1;
    map { $I[$_] & $n ? $_ : () } 0..$#I
}
sub i {
    @t = f;
    max map {
        $b = $_;
        min map { abs $_ - $b } @t
    } f
}
$r = max i,i;
print defined $r ? $r : -1

Przykładowe użycie:

wkład

0
1
2
3

perl golf.pl < input

Clojure, 167 bajtów

#(let[P apply F(fn[I](filter(fn[i](I(% i)))(range(count %))))A(F #{1 3})B(F #{2 3})d(fn[X Y](P min(for[x X](P max(for[y Y](P -(sort[x y])))))))](-(min(d A B)(d B A))))

Powinna być krótsza droga ... Czy istnieje?