Sunday, June 19, 2011

Game of Master Mind !!!!!!!!!!!!!!

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 psuedo-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.

Data Structure Used: Array

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.

Above algorithm will take O(N) time & constant space with two passes over three arrays.1 pass over solution & guess string
2nd pas over temp string



Time Complexity O(N)
Space Complexity O(1)
Run Here

No comments :