Friday, September 4, 2015

Jolly Jumper Sequence Challenge Solved in PHP

Description
You are a spy and you need to frequently send the order in which various numbered bids for a contracts are currently ranked without it being obvious that you are sending out the official ranks. You choose to disguise the actual ranking by creating a new candidate set of numbers. The real rank will be the absolute difference between successive elements. A sequence of n > 0 integers is a candidate if the absolute values of the differences between successive elements take on all possible ranks 1 through n – 1. The definition implies that any sequence of a single integer is a candidate. Another program has generated many possible number sequences, so your goal is to process that file to determine if a sequences is a candidate or not. Examples: 1 2 6 3 5 is a candidate, because the absolute differences are 1, 4, 3, and 2, respectively. 1 2 6 3 6 is NOT a candidate because the absolute differences are 1, 4 3, and 3.

Input
Your program should read lines of text from standard input. Each line will contain an integer n < 100 followed by a list of n space separated integers.

Output
For each line of input, print to standard output 'Candidate' or 'Not a Candidate' using the criteria in this challenge.

Solution
What I understood by reading above description is the absolute differences between every two consecutive numbers should be a permutation (every number from 1 to N-1 appears exactly one time in it) of the numbers from 1 to N-1.
To be considered a 'Candidate', given array must contain atleast one value and should be greater than 0. Otherwise it will considered as 'Not a Candidate'.
Absolute values of differences will fail to cover the range of 1 to n-1 if any of the difference value is repeated or any of the difference will fall out side the range of 1 to n-1 and there will be no need to check for the numbers further.
/* Complete Sourcecode */
function isCandidate($given_array)
{ 
 if(empty($given_array))
 {
  return 'Not a Candidate';
 }
 
 
 $length_of_array = count($given_array);

 /* given array must contain at least one element and should contain value greater than 0 to be considered as valid candidate */
 if($length_of_array == 1)
 {
  if($given_array[0] > 0)
  {
   return 'Candidate';
  }
  else
  {
   return 'Not a Candidate';
  }
  
 }
 
 $diff = array();

 for($i = 0; $i < $length_of_array - 1; $i++)
 {
  $diff[] = abs($given_array[$i] - $given_array[$i+1]);
 }
 
 
 if(min($diff) <  1 || max($diff) >= $length_of_array)
 {
  return 'Not a Candidate';
 }
 
 
 if(!empty(array_has_duplicate($diff)))
 {
  return 'Not a Candidate';  
 }
  
  
 
 return 'Candidate';  
 
 
}

/* returns 1 if it has duplicate values in the array*/
function array_has_duplicate($array) {
     return count($array) !== count(array_unique($array));
}

print(isCandidate($given_array));

I have tested againt below provided arrays. It have passed all the input scenarios.
/* Assumed format of sample input are integers with space seprated i.e 1 2 6 3 5 */
//Reading input from STDIN
$handle = fopen("php://stdin","r");
$t = fgets($handle);
$given_array = explode(" ", trim($t));
fclose($handle);

        //$given_array  = array(1);
 //$given_array  = array();
        //$given_array  = array(2,5,1,3,4);
 //$given_array  = array(1,2,6,3,5);
 //$given_array  = array(1,2,6,3,6);
 $given_array  = array(5,1,4,2,-1,6);

Am I missing any thing? Please do let me know, if there is any flaw or suggestion to make it more better.

No comments:

Post a Comment