Compute the Hausdorff Distance
CJam, 53 52 46 38 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";
$W= "Take max";
e> "Take max of the two maximums";
Try it online here
Lua, 235 bytes
Definitely not a winner, but at least a fun challenge.
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)))
Input works like so:
lua hausdorff.lua <space-separated-sequence>
...and here's a test script:
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)
...produces...
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