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.
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.
Comments
Post a Comment