I'm really having a hard time devising an algorithm to solve the following problem :
I will be accepting an array of inputs like below :
$input = array('100', '101', '102', '110', '111', '112');
and the output should be a string containing :
"100-102, 110-112".
Basically what I need to do is to group numbers in sequence, like 100 to 102 and form them in a string "100-102" since all numbers form a sequence. But since the value 110 is not next to 102, values 110 to 112 should be grouped and the string "110-112" will be formed.
Input is not limited to numbers however, they are strings. So I will be expecting inputs like:
$input = array('N1', 'N2', 'N3', 'GX1', 'GX2', 'Z-3');
Following the same pattern, the output should be:
"N1-N3, GX1-GX3, Z-3"
My pseudo-code (i'm a newbie) to attack the problem for the numbers atleast is:
$sequenceArr = [];
$string = '';
foreach(...){
if(nextValue == prevValue+1){
$sequenceArr[] = nextValue;
}else{
//form the string from the sequenceArr
//if the preceeding string doesn't conform to the pattern anymore.
}
}
The problem I think I will be facing above is if the inputs are not sorted.. I could "sort" them, but how about for strings with character values in them? I'm kinda lost, and I don't think I'm going anywhere with this solution.
*UPDATED FURTHER DESCRIPTION :
This will just be a simple grouping algorithm, only the last number will indicate grouping,
AB-1-DF AB-2-DF and AB-3-DF will NOT be grouped to AB-1-DF - AB-3-DF. That simplifies the problem, also the 0 prefix doesn't matter, 001 and 002 can be grouped as 1-2.
The simple rule is basically this :
(character) - (number)
ABC - 1
A difference in character means an entirely different thing.
Here's something that ought to work if sequential items are next to one another. And you'd probably want to write your own are_sequential function:
$input = ["1","2","4","6","7","8"];
$len = count($input);
$result = [];
function are_sequential($a,$b){
return $a + 1 == $b;
}
$i = 0;
while ($i < $len - 1){
$first = $input[$i];
$last = $input[$i];
$i++;
$sequenceLength = 1;
while (are_sequential($last, $input[$i])){
$last = $input[$i];
$sequenceLength++;
if ($i < $len - 1){
$i++;
}
}
if ($sequenceLength > 1){
$result[] = $first . "-" . $last;
} else {
$result[] = $first;
}
}
var_dump($result);
Output:
array(3) {
[0]=>
string(3) "1-2"
[1]=>
string(1) "4"
[2]=>
string(3) "6-8"
}
Sort the array increasingly using the standard string comparison predicate (alphabetical order).
Then compare the strings in pairs.
Isolate the string prefix (all characters but the last), and compare for equality.
If you accept numerical suffixes consisting of more than one digit, you will need to isolate the suffix, convert it to integer, and do the comparison on the remaining prefix. (Regular expressions can help you.)