Game of master mind: you have four balls, and four different colors, as a solution. The user tries to guess the solution. If they guess the right color for the right spot, it counts as a 'hit'. If it's the right color, but the wrong spot, it counts as a pseudo-hit.

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 ?

yes
instead 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);

for i=0
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=1
1<<(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=2
1<<(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=3
1<<(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=0
guess[i]== solution[i]
'A'=='A'is equal
therefore increment hit by 1

for i=1
guess[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=2
guess[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=3
guess[i]== solution[i]
'D'=='D'is equal
therefore increment hit by 1

Hence number of hits is 2 and pseudo hits is 1

done!!

Shuffle card algorithm

One common programming question is how to randomly shuffle an array of numbers in-place.

variant of question:-

How would you write code to shuffle a deck of cards?

                                                   OR

write a program to generate a random permutation of array elements.

let's try to understand problem:

algorithm:

1. Start iterating the array from the last element.
2. If you are at ith element from the end, generate a random number say j,in range[0,i].
3. Swap A[i] and A[j].
4. Decrease j by 1
5. Continue till you reach the element at index 1 i.e A[1].

Generalize code:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>
     int a[] = {1, 2, 3, 4, 5, 6, 7, 8},temp,i, n = 8;
// A function to generate a random permutation of a[]
void randomize ( )
{

// srand()--> gives the random function a new seed, a starting point 
//(usually random numbers are calculated by taking the previous number 
//(or the seed) and then do many operations on that number to generate the next).
 
//time(0)--> gives the time in seconds since the Unix epoch, 
//which is a pretty good "unpredictable" seed 
//(you're guaranteed your seed will be the same only once, 
//unless you start your program multiple times within the same second).
    srand ( time(NULL) );
 
    //We don't need to run for the first element that's why n-1 pass
    
    for ( i = n-1; i > 0; i--) //for Shuffle card algorithm i=51
    {
        // Pick a random index from 0 to i
        int j = rand() % (i+1);
 
        // Swap a[i] with the element at random index
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
    }
}
 
int main()
{
 // shuffle the array
    randomize ();
  // print results.
     for ( i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

output:-

8 1 5 4 6 2 3 7

time complexity:-  O(n)
time complexity to traverse array is o(n) and assume rand() generates random number in O(1) time.

code for  shuffle deck of cards: 
we have to make change in input and array size of above generalize algorithm.input array consist of 52 cards

          int a[] ={  1,2,3,4,5,6,7,8,9,10,11,12,13,
                      14,15,16,17,18,18,20,21,22,23,24,25,26,
                      27,28,29,30,31,32,33,34,35,36,37,38,39,
                      40,41,42,43,44,45,46,47,48,49,50,51,52
                   };

change value of n

int n=52  // array size 

final code for  shuffle deck of cards:  :

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h>
// Clubs->1 to 13
//Diamonds->14 to 26
//Hearts->27 to 39
//Spades->40 to 52
 int a[] ={ 1,2,3,4,5,6,7,8,9,10,11,12,13,
            14,15,16,17,18,18,20,21,22,23,24,25,26,
            27,28,29,30,31,32,33,34,35,36,37,38,39,
            40,41,42,43,44,45,46,47,48,49,50,51,52
          };
 int temp,i, n = 52;
// A function to generate a random permutation of a[]
void randomize ( )
{
 
// srand()--> gives the random function a new seed, a starting point 
//(usually random numbers are calculated by taking the previous number 
//(or the seed) and then do many operations on that number to generate the next).
  
//time(0)--> gives the time in seconds since the Unix epoch, 
//which is a pretty good "unpredictable" seed 
//(you're guaranteed your seed will be the same only once, 
//unless you start your program multiple times within the same second).
    srand ( time(NULL) );
  
    //We don't need to run for the first element that's why n-1 pass
     
    for ( i = n-1; i > 0; i--) //for Shuffle card algorithm i=51
    {
        // Pick a random index from 0 to i
        int j = rand() % (i+1);
  
        // Swap a[i] with the element at random index
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
    }
}
  
int main()
{
 // shuffle the array
    randomize ();
  // print results.
     for ( i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

output:-

29 8 47 10 49 28 24 43 14 13 48 32 2 12 
36 31 30 18 50 1 25 41 40 45 39 38 6 35
23 17 9 46 20 11 51 52 4 34 42 15 22 7 
37 33 18 3 5 16 27 26 21 44