Shortening an array based on consecutive occurences.

Question

I'm in the middle of learning PHP, and the following list-related problem has come up. The language doesn't really matter, so I'll give you this in pseudo-code. Pseudo-code answers are fine, of course.

Say, there's a list of two different, repeating elements - two single characters, for instance. So my list looks roughly like this:

myList = [C, C, D, C, D, D, D, C, C, D, C, D, C, C, ...]

However, that's not the form I want. Instead, the list should look like this:

myList* = [CC, D, C, DDD, CC, D, C, D, CC, ...]
myList* = shorten(myList)

What's the most elegant way of turning the single-character list into one that contains continuous strings of subsequent characters as its elements? My solution strikes me as rather crappy, given that it involves multiply nested if-statements, various state variables and other nastiness.

Pseudo-code away! Many thanks in advance for any implementation of

shorten()

you throw at me.

Answer 1

You can do that with a single scan of the array by keeping track of the current character and the last character:

function shorten($myList) {
        $myList[] = '';                         // add a dummy char at the end of list.
        $result = array();                      // result to be returned.
        $last_char = $myList[0];                // initilize last char read.
        $combine = $last_char;                  // initilize combined string.
        for($i=1;$i<count($myList);$i++) {      // go from index 1 till end of array.
                $cur_char = $myList[$i];        // current char.
                if($cur_char != $last_char) {   
                        $result[] = $combine;   // time to push a new string into result.
                        $combine = $cur_char;   // reset combine string.
                } else {
                        $combine.=$cur_char;    // is cur char is same as prev..append it.
                }
                $last_char = $cur_char;         // for next iteration cur become last.
        }
        return $result;                         // return result.
}

Code In Action

Answer 2

$myList = array('C', 'C', 'D', 'C', 'D', 'D', 'D', 'C', 'C', 'D', 'C', 'D', 'C', 'C');

function shorten($list) {
    $newList = array();

    foreach($list as $key => $entry) {
        if ($key == 0) {
            $newList[] = $entry;
        } elseif ($entry == substr($newList[count($newList)-1],0,1)) {
            $newList[count($newList)-1] .= $entry;
        } else {
            $newList[] = $entry;
        }
    }

    return $newList;
}

$shortenedList = shorten($myList);

var_dump($myList);
echo '<br />';
var_dump($shortenedList);

Answer 3

Here you go something short

$mylist = array("a","b","b","b","c","c","d");
$shortened = array();
$prev = $item = null;
foreach($mylist as $key=>$val) {
  if($val==$prev) $item.= $val; // previous character was the same
  else { // was not the same: put it into $shortened and start creating new $item
    $shortened[] = $item;
    $item = $val;
  }
  $prev = $val; // remember previous
}
$shortened[] = $item; // append the last item
array_shift($shortened); // first item is always empty
print_r($shortened); // a, bbb, cc, d

Answer 4

$result = array();
$word = '';
$lastChar = $myList[0];
foreach($myList as $char){
    if($lastChar !== $char){
        $result[] = $word;
        $word = '';
    }
    $word .= $char
}

Answer 5

Using PHP 5.3 Closure and array_reduce:

ini_set('error_reporting', E_ALL);

function shorten(array $list) {
    return array_reduce($list, function($a, $b) {
        $lastIdx = count($a) - 1;
        if(isset($a[$lastIdx]) && strstr($a[$lastIdx], $b)) $a[$lastIdx] .= $b;
        else $a[] = $b;

        return $a;
    }, array());
}


$list = array('C', 'C', 'D', 'C', 'D', 'D', 'D', 'C', 'C', 'D', 'C', 'D', 'C', 'C');
$expected = array('CC', 'D', 'C', 'DDD', 'CC', 'D', 'C', 'D', 'CC');

$listShortened = shorten($list);
assert($expected === $listShortened);

Answer 6

Ah, I think I made your point! I believe this is exactly waht you want:

$mylist = array("a","b","b","b","c","c","d");
function shorten($array) {
  $str = implode("",$array); // step 1: make string from array of chars
  preg_match_all("/(\w)\\1*/",$str,$matches); // step 2: split into chunks
  return $matches[0]; // step 3: that's all
}
print_r(shorten($mylist));