You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
This problem is based on graphs , weights and strings:
- Map the strings to ids and create a disjoint set
- weights should be maintained for each pair of strings
I have used disjoint sets approach here.
Creating a disjoint set for strings:
This problem is designed with the strings. Disjoint sets use a root array and connected elements will point one element. For more info on disjoint sets please go through graphs section in explore area.
In C language if we need to use disjoint set for strings, we should give an id for each string. So using an array of char * pointers strs and num_strs to save strings pointers and map each string to one id (starts from 0). Basically mapping the strings to ids.
While going through equations, if it is a new string, we specify the an id else returned mapped id.
Once strings are mapped to ids, disjoint sets can be created using find and union functions.
Weights:
Main issue which we need to understand here is how to maintain weights (values[]) and how to calculate them. I have used 2D array to maintain these weights and initialised to 1s. If (s1, s2, w1) is given, get the mapped s1 and s2 ids and set wt[s1][s2] to w1 and wt[s2][s1] to 1/w1 .
When we do union of (s1, s2) , we update root, rnk and wt arrays. While linking x, y through rx and ry , weights should be caluculated for wt[rx][ry] as wt[rx][ry] = wt[rx][x] wt[y][ry] wt[x][y];
Queries:
These queries consists of pair of strings. These strings may or may not exist in disjoint set. If not there in map set, just set the result as -1 and go for the next pair.
If both the strings are matching with the map set, check if there is calculated weight value, else get the root values for these string mapped ids and calculate the weight.
#define MAX_ELEMENTS 40
int map_str(char* strs[MAX_ELEMENTS], char *s, int num){
int ii;
for (ii=0; ii<num; ii++){
if (!strcmp(strs[ii],s))
return ii+1;
}
return 0;
}
int findDJ (int *rt, double wt[][MAX_ELEMENTS], int x){
int rx = rt[x];
if (rx == x){
return x;
}
rt[x] = findDJ(rt, wt, rx);
if (rt[x] != rx) {
wt[x][rt[x]] = wt[x][rx] * wt[rx][rt[x]];
wt[rt[x]][x] = 1/(wt[x][rt[x]]);
// printf("x %d rx %d, rt[x] %d, wt[x][rt[x]] %f, wt[x][rx] %f wt[rx][rt[x]] %f \n", x, rx, rt[x], wt[x][rt[x]], wt[x][rx], wt[rx][rt[x]]);
}
return (rt[x]);
}void unionDJ(int *rt, int *rnk, double wt[][MAX_ELEMENTS], double w, int x, int y){
int rx, ry;
rx = findDJ(rt, wt, x);
ry = findDJ(rt, wt, y);
wt[x][y] = w;
wt[y][x] = 1/w;
if (rx == ry) return;
/* calculate the weight of wt[rx][ry] */
wt[rx][ry] = wt[rx][x] * wt[y][ry] *wt[x][y];
wt[ry][rx] = 1/(wt[rx][ry]);
if (rnk[rx] > rnk[ry]){
rt[ry] = rx;
}else if (rnk[ry] > rnk[rx]){
rt[rx] = ry;
}else{
rt[ry] = rx;
rnk[rx] += 1;
}
// printf("x %d y %d rx %d, ry %d rt[rx] %d rt[ry] %d ", x, y, rx, ry, rt[rx], rt[ry]);
// printf("wt[%d][%d] %f wt[%d][%d] %f wt[rx][x] %f , w %f\n", rx, ry, wt[rx][ry], ry, rx,wt[ry][rx], wt[rx][x], w);
return;
}double* calcEquation(char *** equations, int equationsSize, int* equationsColSize, double* values, int valuesSize, char *** queries, int queriesSize, int* queriesColSize, int* returnSize){
int num_strs=0;
char *strs[MAX_ELEMENTS];
int rt[MAX_ELEMENTS];
char *s;
int map_id1, map_id2;
double wt[MAX_ELEMENTS][MAX_ELEMENTS];
{
int rnk[MAX_ELEMENTS];
for (int ii=0; ii< MAX_ELEMENTS; ii++){
for (int jj=0; jj< MAX_ELEMENTS; jj++)
wt[ii][jj] = 1.0;
rt[ii] =ii;
rnk[ii] = 1;
}
for (int ii=0; ii< equationsSize; ii++){
/* get each string and mapped id of string*/
s = equations[ii][0];
if (!(map_id1 = map_str(strs, s, num_strs))){
strs[num_strs] = s;
map_id1 = num_strs;
num_strs++;
}else map_id1--;
s = equations[ii][1];
if (!(map_id2 = map_str(strs, s, num_strs))){
strs[num_strs] = s;
map_id2 = num_strs;
num_strs++;
}else map_id2--;
// printf(" id1 %d, y %s snum %d id2 %d num_strs %d\n", map_id1, s, snum,map_id2, num_strs);
/* link these vertices and calculate the corresponding weights */
unionDJ(rt, rnk, wt, values[ii], map_id1, map_id2);
}
}
/* allocation for output */
double *res = (double *) malloc(sizeof(double) * queriesSize); for (int ii=0; ii<queriesSize; ii++){
/* get the mapped id strings, if not there set result as -1 */
s = queries[ii][0];
if (!(map_id1 = map_str(strs, s, num_strs))){
res[ii] = -1;
continue;
}else map_id1--;
s = queries[ii][1];
if (!(map_id2 = map_str(strs, s, num_strs))){
res[ii] = -1;
continue;
}else map_id2--;
/* if query has same strings as "a"/"a", set to 1 */
if (map_id1 == map_id2){
res[ii] = 1;
}
// printf("qii %d , x %s id1 %d, y %s, id2 %d, wt %f\n",ii,queries[ii][0], map_id1, queries[ii][1], map_id2, wt[map_id1][map_id2] );
/* While doing union some weights gets calculated ,
eg, (a, b, w1), (b, c, w2), (c, d, w3) ==>
weigths corresponding to a,b ; b,c; a,c; c,d;a,d gets calculated in unionDJ func */
else if (wt[map_id1][map_id2] != 1.0)
res[ii] = wt[map_id1][map_id2];
else {
/* there are cases where some weights will not be calculated
eg, (a, b, w1), (b, c, w2), (c, d, w3) ==>
weigths corresponding to b,d will not get caluculated.
so check if these are linked and update weights*/
int rx = findDJ(rt, wt, map_id1);
int ry = findDJ (rt, wt, map_id2);
if (rx == ry){
res[ii] = wt[map_id1][rx] * wt[rx][map_id2];
} else
res[ii] = -1.0;
}
}
*returnSize = queriesSize;
return res;
}
Tried another approach of converting string to numbers and then do mapping:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#define MAX_ELEMENTS 40
int srch_el(long *ar, long ele, int num){
int ii;
for (ii=0; ii<num; ii++){
if (ar[ii] == ele)
return ii+1;
}
return 0;
}/* considering the max length of string is 6 chars */
long conv_str_to_num(char *str){
int ii;
long num=0;
for (ii=0; str[ii]!='\0'; ii++){
/* shift the existing number to 5 bits */
num <<=6;
if (isdigit(str[ii]))
num |= (28 + str[ii] - '0');
else
num |= (1 + str[ii] - 'a'); /* add the char value */
}
return num;
}int find (int *rt, double wt[][40], int x){
int rx = rt[x];
if (rx == x){
return x;
}
rt[x] = find(rt, wt, rx);
if (rt[x] != rx) {
wt[x][rt[x]] = wt[x][rx] * wt[rx][rt[x]];
wt[rt[x]][x] = 1/(wt[x][rt[x]]);
// printf("x %d rx %d, rt[x] %d, wt[x][rt[x]] %f, wt[x][rx] %f wt[rx][rt[x]] %f \n", x, rx, rt[x], wt[x][rt[x]], wt[x][rx], wt[rx][rt[x]]);
}
return (rt[x]);
}void ulink(int *rt, int *rnk, double wt[][40], double w, int x, int y){
int rx, ry;
rx = find(rt, wt, x);
ry = find(rt, wt, y);
wt[x][y] = w;
wt[y][x] = 1/w;
if (rx == ry) return;
wt[rx][ry] = wt[rx][x] * wt[y][ry] *wt[x][y];
wt[ry][rx] = 1/(wt[rx][ry]);
if (rnk[rx] > rnk[ry]){
rt[ry] = rx;
}else if (rnk[ry] > rnk[rx]){
rt[rx] = ry;
}else{
rt[ry] = rx;
rnk[rx] += 1;
}
// printf("x %d y %d rx %d, ry %d rt[rx] %d rt[ry] %d ", x, y, rx, ry, rt[rx], rt[ry]);
// printf("wt[%d][%d] %f wt[%d][%d] %f wt[rx][x] %f , w %f\n", rx, ry, wt[rx][ry], ry, rx,wt[ry][rx], wt[rx][x], w);
return;
}double* calcEquation(char *** equations, int equationsSize, int* equationsColSize, double* values, int valuesSize, char *** queries, int queriesSize, int* queriesColSize, int* returnSize){
int num_strs=0;
char *strs[MAX_ELEMENTS]; long ele[MAX_ELEMENTS],snum;
int rt[MAX_ELEMENTS], rnk[MAX_ELEMENTS];
char *s;
int id1, id2;
double wt[MAX_ELEMENTS][MAX_ELEMENTS];
for (int ii=0; ii< MAX_ELEMENTS; ii++){
for (int jj=0; jj< MAX_ELEMENTS; jj++)
wt[ii][jj] = 1.0;
rt[ii] =ii;
rnk[ii] = 1;
}
for (int ii=0; ii< equationsSize; ii++){
/* get each string */
s = equations[ii][0];
snum = conv_str_to_num(s);
if (!(id1 = srch_el(ele, snum, num_strs))){
strs[num_strs] = s;
ele[num_strs] = snum;
id1 = num_strs;
num_strs++;
}else id1--;
s = equations[ii][1];
snum = conv_str_to_num(s);
if (!(id2 = srch_el(ele, snum, num_strs))){
strs[num_strs] = s;
ele[num_strs] = snum;
id2 = num_strs;
num_strs++;
}else id2--;
// printf(" id1 %d, y %s snum %d id2 %d num_strs %d\n", id1, s, snum,id2, num_strs);
ulink(rt, rnk, wt, values[ii], id1, id2);
}
double *res = (double *) malloc(sizeof(double) * queriesSize); for (int ii=0; ii<queriesSize; ii++){
s = queries[ii][0];
snum = conv_str_to_num(s);
if (!(id1 = srch_el(ele, snum, num_strs))){
res[ii] = -1;
continue;
}else id1--;
s = queries[ii][1];
snum = conv_str_to_num(s);
if (!(id2 = srch_el(ele, snum, num_strs))){
res[ii] = -1;
continue;
}else id2--;
if (id1 == id2){
res[ii] = 1;
}
// printf("qii %d , x %s id1 %d, y %s, id2 %d, wt %f\n",ii,queries[ii][0], id1, queries[ii][1], id2, wt[id1][id2] );
else if (wt[id1][id2] != 1.0)
res[ii] = wt[id1][id2];
else {
int rx = find(rt, wt, id1);
int ry = find (rt, wt, id2);
if (rx == ry){
res[ii] = wt[id1][rx] * wt[rx][id2];
} else
res[ii] = -1.0;
}
}
*returnSize = queriesSize;
return res;
}
