## Sunday, June 6, 2010

### With 3 arrays of sorted data find the tuple with the minuim distance

Question;
You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
* Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))
* Please give a solution in O(n) time complexity

Note it contains the paired as well as the tuple type solution. I didnt know how to do so i trial it with a pair type..

EDIT: Also on the web I noticed several other solutions that just move the min number I didnt click until now.. But be careful the mins movement is a property of this particular distance function if that changes then moving the min might not be the best course of action.

#include <math.h>
#include <iostream>
#include <list>
using namespace std;

#define MAX3(a,b,c) ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c))

#define DIST2(a,b) abs(a-b)
#define DIST3(a,b,c) MAX3(abs(a-b),abs(a-c),abs(b-c));

struct Tuple
{
int a;
int b;
int c;

Tuple(int _a, int _b, int _c) { a = _a; b = _b; c = _c; }
};

typedef list ListTuple;

void min_tuple(int* a, int* b, int* c, int sizea, int sizeb, int sizec)
{
ListTuple best_tuple;

//best_pairs.push_back(Pair(0,0));
int best = DIST3(a[0], b[0], c[0]);

int i, j, k;
i = j = k = 0;

while(
(i < sizea) &&
(j < sizeb) &&
(k < sizec)
)
{
//check the current for best status
int dist = DIST3(a[i], b[j], c[k]);
if(dist < best)
{
best_tuple.clear();
best_tuple.push_back(Tuple(i,j,k));
best = dist;
}
else if(dist == best)
best_tuple.push_back(Tuple(i,j,k));

//move to the next possible minium...
int dist_i = DIST3(a[i+1], b[j],   c[k]);
int dist_j = DIST3(a[i],   b[j+1], c[k]);
int dist_k = DIST3(a[i],   b[j],   c[k+1]);

if(dist_i < dist_j)
if(dist_i < dist_k)
i++;
else
k++;
else
if(dist_j < dist_k)
j++;
else
k++;
cout << i << "," << j << "," << k << " -> ";
}
cout << endl;

cout << "best tuples are: " << endl;
for(ListTuple::iterator pit = best_tuple.begin(); pit != best_tuple.end(); pit++)
{
Tuple& t = *pit;
cout  << "index: " << t.a << "," << t.b << "," << t.c
<< " values: "<< a[t.a] << "," << b[t.b] << "," << c[t.c] << endl;
}
cout << endl;
cout << "best distance was: " << best;
}

struct Pair
{
int a;
int b;

Pair(int _a, int _b) { a = _a; b = _b; }
};

typedef list ListPair;

void min_pair(int* a, int* b, int sizea, int sizeb)
{
ListPair best_pairs;

//best_pairs.push_back(Pair(0,0));
int best = DIST2(a[0], b[0]);

int i, j;
i = j = 0;

while(
(i < sizea) &&
(j < sizeb)
)
{
//check the current for best status
int dist = DIST2(a[i], b[j]);
if(dist < best)
{
best_pairs.clear();
best_pairs.push_back(Pair(i,j));
best = dist;
}
else if(dist == best)
best_pairs.push_back(Pair(i,j));

//move to the next possible minium...
if(i < sizea)
if(j < sizeb)
if(DIST2(a[i+1], b[j]) < DIST2(a[i], b[j+1]))
i++;
else
j++;
else
i++;
else
j++;
cout << i << "," << j << " -> ";
}
cout << endl;

cout << "best pairs are: ";
for(ListPair::iterator pit = best_pairs.begin(); pit != best_pairs.end(); pit++)
{
Pair& p = *pit;
cout  << "index: " << p.a << "," << p.b
<< " values: "<< a[p.a] << "," << b[p.b] << endl;
}
cout << endl;
cout << "best distance was: " << best;
}

void print(int* data, int size)
{
for(int i = 0; i < size; i++)
cout << data[i] << " ";
cout << endl;
}

void bubblesort(int data[], int size)
{
bool change = true;
int tmp;
while(change)
{
change = false;
for(int i = 0;i < size-1;i++)
if(data[i] > data[i+1])
{
tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
change = true;
}
}
}

#define COUNT 10
int main()
{
int data1[COUNT];
int data2[COUNT];
int data3[COUNT];

srand(time(NULL));
for(int i = 0; i < COUNT; i++)
{
data1[i] = rand()%200;
data2[i] = rand()%200;
data3[i] = rand()%200;
//data1[i] = -20 + i*3;
//data2[i] = i*5;
}

bubblesort(data1, COUNT);
bubblesort(data2, COUNT);
bubblesort(data3, COUNT);

print(data1, COUNT);
print(data2, COUNT);
print(data3, COUNT);

min_pair(data1, data2, COUNT, COUNT);
cout << endl;
min_tuple(data1, data2, data3, COUNT, COUNT, COUNT);

}