Sunday, August 20, 2006

Pass code Problem

/*
Problem Description
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.The main input, contains fifty successful login attempts.Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Sample Input
Assuming 2 successful attempts (NOTE: Input would have 50)123142

Sample Output
1423
*/
int INPUT_ROW_SIZE;
int INPUT_COL_SIZE;
typedef enum
{
FALSE = -1,
TRUE = 1
}BOOLEAN;
typedef enum
{
OFF = 0,
ON = 1
}STATUS;
char **inputArray;
int **relationshipMatrix;
char *passCode;
char *uniqueArray;
unsigned int uniqueArrayIndex;
unsigned int rowSize,colSize;
unsigned int passCodeIndex;
void printInputArray(void)
{
int i,j;
printf("\n");
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("%2c",inputArray[i][j]);
}
printf("\n");
}
}
void printUniqueArray()
{
int i =0;
printf("Unique Array:\n");
for(i=0;i lessThan uniqueArrayIndex;i++)
{
printf("%2c",uniqueArray[i]);
}
printf("\n");
}
void printRelationshipArray()
{
int i,j;
printf("RelationshipArray\n");
for(i=0;i lessThan rowSize;i++)
{
for(j=0;j lessThan colSize;j++)
{
printf("%2d",relationshipMatrix[i][j]);
}
printf("\n");
}
}

void setUniqueArray()
{
BOOLEAN foundMatch = FALSE;
int i=0,j=0,k=0;
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
foundMatch = FALSE;
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
foundMatch = TRUE;
}
}
if(foundMatch == TRUE)
{
continue;
}
else
{
uniqueArray[uniqueArrayIndex] = inputArray[i][j];
uniqueArrayIndex++;
}
}
}
}
void setRelationshipArray()
{
int i=0,j=0,k=0;
int rowIndex,colIndex;
relationshipMatrix = (int **)malloc(uniqueArrayIndex*sizeof(int *));
for(i=0;i lessThan uniqueArrayIndex;i++)
{
relationshipMatrix[i]= (int *)malloc(uniqueArrayIndex*sizeof(int));
}
for(i=0;i lessThan uniqueArrayIndex;i++)
{
for(j=0;j lessThan uniqueArrayIndex;j++)
relationshipMatrix[i][j]= OFF;
}

for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE - 1;j++)
{
/*locate inputArray[i][j] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
rowIndex = k;
/*locate inputArray[i][j+1] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j+1] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
colIndex = k;
relationshipMatrix[rowIndex][colIndex] = ON;
}
}
}
BOOLEAN matrixCorrectnessCheck()
{
int i , j=0;
for(i=0;i lessThan rowSize; i++)
{
for(j=0;j lessThan colSize;j++)
{
if((i != j )&& relationshipMatrix[i][j] == ON && relationshipMatrix[j][i] == ON)
{
printf("Invalid relation between %c and %c",uniqueArray[i],uniqueArray[j]);
return FALSE;
}
}
}
return TRUE;
}
int whichColHasAllZeros()
{
int i,j=0;
int sum = 0;
if(colSize == 0 || rowSize == 0)
{
printf("Reached the end of the input with row=%d col=%d\n",rowSize,colSize);
return FALSE;
}
for(j=0;j lessThan colSize;j++)
{
sum = 0;
for(i=0;i lessThan rowSize;i++)
{
sum= sum+relationshipMatrix[i][j];
}
if(sum == 0)
{
return j;
}
}
return FALSE;
}
void exchangeRowCol(int index)
{
char temp1=0;
int temp = 0;
int i,j;
/*exhange row of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[index][i];
relationshipMatrix[index][i] = relationshipMatrix[rowSize-1][i];
relationshipMatrix[rowSize-1][i] = temp;
}
rowSize--;
/*exhange col of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[i][index];
relationshipMatrix[i][index] = relationshipMatrix[i][colSize -1];
relationshipMatrix[i][colSize -1] = temp;
}
colSize--;
/*exhange elem for uniqueArray*/
temp1 = uniqueArray[index];
uniqueArray[index] = uniqueArray[uniqueArrayIndex - 1];
uniqueArray[uniqueArrayIndex - 1] = temp1;
uniqueArrayIndex--;
}
void setPasscodeArray(void)
{
int colIndex = 0;
passCode = (char *)malloc(sizeof(char)*uniqueArrayIndex);

while(colIndex != FALSE)
{
colIndex = whichColHasAllZeros();
if(colIndex != FALSE)
{
passCode[passCodeIndex] = uniqueArray[colIndex];
passCodeIndex++;
exchangeRowCol(colIndex);
}
}

}
void printPasscodeArray(void)
{
int i=0;
printf("Passcode Array\n");
for(i=0;i lessThan passCodeIndex;i++)
{
printf("%2c",passCode[i]);
}
printf("\n");
return;
}

void makeSmallestPasscode(void)
{
int i , j=0;
BOOLEAN retVal = FALSE;

setUniqueArray();
printUniqueArray();

rowSize = uniqueArrayIndex;
colSize = uniqueArrayIndex;

setRelationshipArray();
printRelationshipArray();
retVal = matrixCorrectnessCheck();

setPasscodeArray();
printPasscodeArray();
}
main()
{
int i = 0,j=0;
printf("Enter Row size of INPUT: ");
scanf(" %d",&INPUT_ROW_SIZE);
printf("Enter Col size of INPUT:");
scanf(" %d",&INPUT_COL_SIZE);
printf("Enter Input:\n");
inputArray = (char **)malloc(INPUT_ROW_SIZE*sizeof(char*));
uniqueArray = (char *)malloc(INPUT_ROW_SIZE*INPUT_COL_SIZE*sizeof(char));
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
inputArray[i] = (char *)malloc(INPUT_COL_SIZE*sizeof(char));
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("Enterarr[%d][%d]\n",i,j);
scanf(" %c",&inputArray[i][j]);
}
}
printInputArray();
makeSmallestPasscode();
}

No comments: