For example: if the solution is 'RGGB' and the user guesses 'YRGB' they have 2 hits and one pseudo hit. Write a program to, given a solution and a guess, calculate the number of hits and pseudo hits.
Solution 1:Algorithm:1.Take an temp array of length ascii chars(256), although we need array of length of 4 here
taking above array will give advantage so that we set/reset the 1 or 0 at particular character
position according to their ascii value.
2.scan solution & guess string & set value to 1 in temp array for each matching character of
solution & guess string also increment the hits counter.else increment temp array location of
corresponding character location.
3.in 2nd pass over temp array check for each location if that location value is not equal to 1 &
also temp[location]>0 if yes then increment pseudo-counter & decrement corresponding character
count in temp array.
code:#include <stdio.h>
int main()
{
char solution[]={'A','B','C','D'};
char guess[] ={'A','E','D','D'};
int arr[256],i,hits=0,pseudoHits=0;
for ( i = 0; i < 4; i++) // initialize all char in solution to set
arr[solution[i]]=1;
//arr[i]=00..111100... till 256
for ( i = 0; i < 4; i++)
{
if (guess[i]== solution[i]) // if match then increment hit
hits++;
else
arr[guess[i]]++; //no match increment guess array index by 1
}
//now array will look like arr[i]=00..111210... till 256
//because in this example E and D does not mach hence we increment them
//but D was present in sol hence it value was 1 and after increment it become 2
//and E was initially 0 and after increment it become 1
//note:all index having value 2 means they are already present in solution
//but guess does not match
//hence to find pseudoHits we have to search for index value equal to 2
for ( i = 0; i < 4; i++)
{
if (arr[solution[i]]> 1)
{
pseudoHits++;
arr[solution[i]]--;
}
}
printf("number of hits is %d\n",hits);
printf("number of pseudo hits is %d",pseudoHits);
return 0;
}
output:-number of hits is 2
number of pseudo hits is 1
but can we do better than this ?
yesinstead of using char array of length 256 we can take help of bits to make set/reset the 1 or 0 to keep track of particular character.
Solution 2:
code:#include <stdio.h>
int main()
{
char solution[]={'A','B','C','D'};
char guess[] ={'A','E','D','D'};
int solution_mask = 0,i,hits=0,pseudoHits=0;
for ( i = 0; i < 4; ++i)
solution_mask =solution_mask | 1 << (solution[i] - 64);
for ( i = 0; i < 4; ++i)
{
if (guess[i]== solution[i])
{
hits++;
}
else if ((solution_mask & (1 << (guess[i] - 64))) >= 1)
{
pseudoHits++;
}
}
printf("number of hits is %d\n",hits);
printf("number of pseudo hits is %d",pseudoHits);
return 0;
}
output:-number of hits is 2
number of pseudo hits is 1
time complexity:- O(n)space complexity:- O(1)
Step By Step Execution:initialize solution_mask to 0
Step 1:-for ( i = 0; i < 4; ++i)
solution_mask =solution_mask | 1 << (solution[i] - 64);
let's break the things first,
1<<(solution[i] - 64)
1<<(A-64)
1<<1
0000 0001
after 1<<1
0000 0010
now
solution_mask = solution_mask | 1 << (solution[i] - 64)
00000000 | 00000010 =00000010
decimal of 00000010 is 2.
Therefore new value of solution_mask is 2.
for i=11<<(solution[i] - 64)
1<<(B-64)
1<<2
0000 0001
after 1<<2
0000 0100
Value of solution_mask is 2 and binary of 2 is 00000010
solution_mask = solution_mask | 1 << (solution[i] - 64)
00000010 | 00000100 =00000110
decimal of 00000110 is 6.
Therefore new value of solution_mask is 2.
for i=21<<(solution[i] - 64)
1<<(C-64)
1<<3
0000 0001
after 1<<3
0000 1000
Value of solution_mask is 6 and binary of 6 is 00000110
solution_mask = solution_mask | 1 << (solution[i] - 64)
00001000 | 00000110 =00001110
decimal of 00001110 is 14.
Therefore new value of solution_mask is 14.
for i=31<<(solution[i] - 64)
1<<(D-64)
1<<4
0000 0001
after 1<<3
0001 0000
Value of solution_mask is 6 and binary of 6 is 00000110
solution_mask = solution_mask | 1 << (solution[i] - 64)
00010000 | =00001110 =00011110
decimal of 00011110 is 30.
Therefore new value of solution_mask is 30.
Step 2:- for ( i = 0; i < 4; ++i)
{
if (guess[i]== solution[i])
{
hits++;
}
else if ((solution_mask & (1 << (guess[i] - 64))) >= 1)
{
pseudoHits++;
}
}
for i=0guess[i]== solution[i]
'A'=='A'is equal
therefore increment hit by 1
for i=1guess[i] != solution[i]
hence control move to else part
now,let's break the things again
1<<(guess[i] - 64)
1<<(E-64)
1<<5
0000 0001
after 1<<5
0010 0000
now
solution_mask & (1 << (guess[i] - 64))
00011110 & 00100000 =00000000
decimal of 00000000 is 0.
((solution_mask & (1 << (guess[i] - 64))) >= 1)
0>=1 condition become false hence control goes to for loop
for i=2guess[i] != solution[i]
hence control move to else part
now,let's break the things again
1<<(guess[i] - 64)
1<<(D-64)
1<<4
0000 0001
after 1<<5
0001 0000
now
solution_mask & (1 << (guess[i] - 64))
00011110 & 00010000 =00010000
decimal of 00000000 is 16.
((solution_mask & (1 << (guess[i] - 64))) >= 1)
16>=1 condition is true
hence pseudoHits will increment by 1
for i=3guess[i]== solution[i]
'D'=='D'is equal
therefore increment hit by 1
Hence number of hits is 2 and pseudo hits is 1
done!!
.jpg)
.jpg)
.jpg)
.jpg)
