Introduction

The Hausdorff distance measures the difference between two subsets of a metric space. Intuitively, a metric space is just some set with a built-in distance function; in this challenge, we will use natural numbers with the ordinary distance d(a, b) := abs(a - b). The Hausdorff distance between two non-empty finite sets A and B is given by

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

in Python-like notation. The Hausdorff distance can be computed by finding the element of A for which the distance to the nearest element of B is maximal, and the element of B for which the distance to the nearest element of A is maximal, and then taking the maximum of these distances. In other words, if the Hausdorff distance is d, then every element of A is within distance d of some element of B, and vice versa.

Input

Your input is a single list of integers. It only contains the elements 0,1,2,3, which signify whether the given index of the list is an element of neither A nor B, only A, only B, or both A and B. For example, the input [0,1,1,0,2,3] means that A = {1,2,5} and B = {4,5}, if we use 0-based indexing (which makes no difference, as our metrics are translation invariant).

Output

Your output is the Hausdorff distance between A and B; in the above example, it is 3. If either set is empty, then the distance is not defined, and you shall return -1.

Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

[] -> -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
• In your equation, I believe that it is much too long, as max(max(min(d(a, b) for b in B) for a in A)) should be sufficient. This is because d(a,b) returns the absolute value, and therefore both max functions will return the same number every time. – Nathan Merrill Apr 21 '15 at 13:34
• @NathanMerrill It may be that every element of A is very close to one of B, but there are elements of B very far from A (for example, if A is a subset of B). In that case, the short formula is incorrect. – Zgarb Apr 21 '15 at 13:36

CJam, 53524638 37 bytes

3,q~f{f&:L,{L=},}$~ff{-z}_z+::e<W+:e> Takes input on STDIN as a CJam style array: [0 1 2 3] Here is a test harness which converts all the test cases to this format and runs the code on them. Although the results are in the input field, they are not used by the code (remove them if you don't trust me :)). Explanation First, we parse the input to get the two sets A and 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."; And now we find the absolute differences and select the max of the mins: 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."; Note that we've kept the empty array resulting from the initial 0 at the bottom of the stack all the time, but empty arrays don't contribute anything to the output. CJam, 57 56 52 bytes I think this can be golfed a bit, but here goes: q~ee_{W=2%},\{W=1>},]0ff=_W%]{~ff-{:z$1<~}%W+$W=}/e> Input goes in like a CJam styled list, eg. [1 0 0 0 0 3 0 0 0 0 2] 5 How it works: The code is split in two parts: Parsing the input into the lists A and 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"; Performing the required actions on the two pairs of A and 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";
[]%_= -1
_%[]= -1

To support spaces between the elements of the input list just divide the final $q by 2 for a cost of 2 strokes Python 2, 124 This definitely feels suboptimal. Oh well. 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⋄⌈/{⌈/⌊/⍵}¨(+,⍉¨)|∘.-/∆} Testcases: ({(⊂⍬)∊∆←(↓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 Explanation: • ⍳⍴⍵: get a list of numbers from 1 to the length of the input list • ↓2 2⊤⍵: for each value in the input list, get the first byte and the second byte • ∆←(...)/⊂⍳⍴⍵: for both lists of bytes, select the corresponding values from ⍳⍴⍵. Store these in . • (⊂⍬)∊∆...:¯1: if this list contains the empty list, return -1. Otherwise: • |∘.-/∆: get the absolute difference between every pair of values, giving a matrix • (+,⍉¨): get a rotated and a non-rotated copy of that matrix • {⌈/⌊/⍵}: for both matrices, get the maximum of the minimums of the rows • ⌈/: then get the maximum of that • @Optimizer: I somehow managed to copy the test output from an earlier version which had a bug. The code itself was correct and still is. If you don't believe me, try here. (Note that you have to enter a one-element list as ,X, to distinguish it from the scalar X.) – marinus Apr 21 '15 at 15:46 • Ah I see. lazy of me to not go to an online compiler and test.. – Optimizer Apr 21 '15 at 15:50 Perl, 189176 157B Now with 500% more state. 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 Legible: 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

Example usage:

input

0
1
2
3

perl golf.pl < input

Clojure, 167 bytes

#(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))))

There should be a shorter way... Is there?