Oblicz odległość Hausdorffa

21

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
Zgarb
źródło
W twoim równaniu uważam, że jest on o wiele za długi, co max(max(min(d(a, b) for b in B) for a in A))powinno wystarczyć. Jest tak, ponieważ d(a,b)zwraca wartość bezwzględną, a zatem obie funkcje maksymalne zwracają tę samą liczbę za każdym razem.
Nathan Merrill,
6
@NathanMerrill Być może każdy element Ajest bardzo zbliżony do jednego B, ale istnieją elementy Bbardzo dalekie A(na przykład, jeśli Ajest podzbiorem B). W takim przypadku krótka formuła jest niepoprawna.
Zgarb

Odpowiedzi:

7

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.

Martin Ender
źródło
5

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

Optymalizator
źródło
5

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
thenumbernine
źródło
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.

Jakube
źródło
><Cabjest taki sam jak :Cba.
isaacg
Dobrze, że przypadki testowe nie zawierają dużego wkładu ...
TLW,
3

Mathematica, 88 bajtów

Max[Min/@#,Min/@Thread@#,-1]/.∞->-1&@Outer[Abs[#-#2]&,p=Position;p[#,1|3],p[#,2|3],1]&
alephalpha
źródło
1
Bardzo miła odpowiedź. Aby uzyskać bardziej ogólne ustalenie odległości Hausdorffa, można użyć tego, m=MaxValue;Max[m[RegionDistance[#[[1]],s],s\[Element]#[[2]]]/.m[__]->-1&/@{#,Reverse@c}]& który można następnie zastosować do obiektów wielowymiarowych, takich jak%@{Sphere[],Line[{{1,1,0},{3,3,3}}]}
Kelly Lowder
3

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!

nimi
źródło
mod 2Wydaje się zbędne. Możesz również skorzystać z tego, że nie definiujesz ai nie wyrażasz bwprost.
Zgarb
możesz zaoszczędzić 2 bajty za pomocą []%_= -1- ale pobiłaś moją próbę na tym :)
Alexander Brett
3

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ęć

Ton Hospel
źródło
2

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])])
feersum
źródło
1

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
marinus
źródło
@Optimizer: Jakoś udało mi się skopiować testowe wyjście z wcześniejszej wersji, która zawierała błąd. Sam kod był poprawny i nadal jest. Jeśli mi nie wierzysz, spróbuj tutaj . (Pamiętaj, że musisz wprowadzić listę jednoelementową jako ,X, aby odróżnić ją od skalara X.)
marinus
O, rozumiem. leniwy, żebym nie poszedł do kompilatora online i nie testował ..
Optymalizator
1

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

Alexander-Brett
źródło
0

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?

NikoNyrh
źródło