An odd assignment about adding dashes to strings. PHP

2012-10-13

An answer to this question on Stack Overflow.

Question

I have a need for a function that will do the following thing:

If I have a string like this "2 1 3 6 5 4 8 7" I have to insert dashes between pairs of numbers following some rules.

The rules are simple.

Put a dash between two numbers if the first one of the pair is smaller then the one that follows it. Do all possible combinations of this and if a pair already has a dash then the space next to it can't have a dash.

Basically my results for above string would be

2 1-3 6 5 4 8 7
2 1-3 6 5 4-8 7
2 1 3-6 5 4 8 7
2 1 3-6 5 4-8 7
2 1 3 6 5 4-8 7

I did create a function that does this but I am thinking it is pretty sluggish and I don't want to taint your ideas with it. If possible I would like to know how you guys are thinking about this and even some pseudo code or code would be great.

EDIT 1: here is the code I have so far

$string = "2 1 3 6 5 4 8 7";
function dasher($string){
   global $dasherarray;
   $lockcodes = explode(' ', $string);
   for($i = 0; $i < count($lockcodes) - 1; $i++){
      if(strlen($string) > 2){
         $left = $lockcodes[$i];
         $right = $lockcodes[$i+1];
         $x = $left . ' ' . $right;
         $y = $left . '-' . $right;
         if (strlen($left) == 1 && strlen($right) == 1 && (int)$left < (int)$right) {
            $dashercombination = str_replace($x, $y, $string); 
            $dasherarray[] = $dashercombination;
            dasher($dashercombination);
         }
      }
   }
   return array_unique($dasherarray);
}
foreach(dasher($string) as $combination) {
   echo $combination. '<br>';
}

Answer

Perhaps this will be helpful in terms of offering different methods to parse the string.

$str="2 1 3 6 5 4 8 7";
$sar=explode(' ',$str);
for($i=1;$i<count($sar);$i++)
  if($sar[$i-1]<$sar[$i])
    print substr_replace($str,'-',2*($i-1)+1,1) . "\n";

Note that the code expects only single digits numbers in the string.

Note that the code expects that the string is formatted as per your example. It would be good to add some sanity checks (collapse multiple spaces, strip/trim blanks at the beginning/end).

We can improve upon this by finding all the spaces in the string and using them to index substrings for comparison, still assuming that only a single spaces separates adjacent numbers.

<?php
$str="21 11 31 61 51 41 81 71";
$letter=' ';
#This finds the locations of all the spaces in the strings
$spaces = array_keys(array_intersect(str_split($str),array($letter)));
#This function takes a start-space and an end-space and finds the number between them.
#It also takes into account the special cases that we are considering the first or 
#last space in the string
function ssubstr($str,$spaces,$start,$end){
	if($start<0)
		return substr($str,0,$spaces[$end]);
	if($end==count($spaces))
		return substr($str,$spaces[$start],strlen($str)-$spaces[$start]);
	return substr($str,$spaces[$start],$spaces[$end]-$spaces[$start]);
}
#This loops through all the spaces in the string, extracting the numbers on either side for comparison
for($i=0;$i<count($spaces);$i++){
	$firstnum=ssubstr($str,$spaces,$i-1,$i);
	$secondnum=ssubstr($str,$spaces,$i,$i+1) . "\n";
	if(intval($firstnum)<intval($secondnum))
		print substr_replace($str,'-',$spaces[$i],1) . "\n";
}
?>

Note the explicit conversion to integers in order to avoid lexicographic comparison.