replace in an array

[miguelna]

I have an array like this:

Code: Select all

$ddd = array(2,3,a,a,a,5,78,a,a,99,0,a,a,a,a,45,a,56)

and I want replace the groups of consecutive letters greater than 2.
So, my array will be

Code: Select all

$ddd = array(2,3,””,””,””,5,78,a,a,99,0,””,””,””,””,45,a,56)

Can someone help me, please?

M

[/code]

[ednark]

Code: Select all

$ddd = array(2,3,a,a,a,5,78,a,a,99,0,c,c,c,c,45);

$result = obliterateDuplicates( $ddd, $obliterate_with );

echo "<pre>";
print_r($ddd);
print_r($result);
echo "</pre>";

function obliterateDuplicates( $from, $obliterate_with )
{
    $array_size = count($from);

    /// must have at least three items to have a possible match
    if ( $array_size >= 3 ) {

        $current_item   = 0;
        $possible_match = 1;
   
        $match_count = 0;
   
        /// while we are not searching past the end of the array
        while ( $possible_match < $array_size  ) {
   
            /// while we are looking at numbers    (use the ctype_alpha() if you have it compiled in)
            while ( !preg_match("/[a-zA-Z]/",$from[$current_item]) ) {
                /// we do not try to match this
                /// move the current_item to the one that we found which does not match
                $current_item = $possible_match;
                /// move the possible_match to the next item
                $possible_match++;
   
                if ( $possible_match >= $array_size ) {
                    /// we are done
                    return $from;
                }
            } /// while not a matchable item
   
            /// while we found a match
            while ( $from[$current_item] == $from[$possible_match] ) {
                /// tell our program we found a match
                $match_count++;
                /// if we have matched three items, two in a row
                if ( $match_count == 2 ) {
                    /// obliterate this and previous item
                    $from[$possible_match-1] = $obliterate_with;
                    $from[$possible_match]   = $obliterate_with;
                /// if we are matching more than two in a row
                } else if ( $match_count > 2 ) {
                    /// obliterate only the one we are on
                    $from[$possible_match]   = $obliterate_with;
                }
                /// move on to check the next item
                $possible_match++;
                /// if the next possible match takes us past the end of the array
                if ( $possible_match >= $array_size ) {
                    /// we are done
                    return $from;
                }
            } /// while match
   
            /// we are done matching this item
            /// set match_count back to 0
            $match_count = 0;
            /// move the current_item to the one that we found which does not match
            $current_item = $possible_match;
            /// move the possible_match to the next item
            $possible_match++;
       
        } /// while there is any array left

    } /// if the array is big enough for at least one match

    /// return our finished array
    return $from;
}


[Jay]

That's a lot of code for such a simple task. I'm sure you can make it 10 times smaller!

[ednark]

ok try this:

makes one pass, but backtracks to obliterate sequences. loops through and uses three variables to hold state, chooses action dependant on state

min execution, no replacements : n
max execution, one big replacement, min_sequence=array_size: 2n
avg execution : 1.5 n

so this function is O(n)

this is functionally equiv to my last, but this just looks cleaner

and i can't see a way to make it smaller, without using a different algorithm altogether;

30 lines of code without comments and spacing:
if you really just wanted it smaller i could get rid of some end brackets, but it won't make it run faster

and if you know a better way, please post it., i'd love to see how someone else tackles this

Code: Select all

$ddd = array(2,3,a,a,a,5,78,a,a,99,0,a,a,a,a,45);

$result = obliterateDuplicates( $ddd );

echo "<pre>";
print_r($ddd);
print_r($result);
echo "</pre>";

function obliterateDuplicates( $from, $obliterate_with='', $min_sequence=3 )
{

    $array_size = count($from);
    if ( $array_size >= $min_sequence ) {

        $current        = 0;
        $match_to       = NULL;
        $match_count    = 0;

        /// we need only 1 pass through the array
        for ( $current = 0; $current < $array_size; $current++ ) {
            /// if we are looking for the next alpha character to match
            if ( $match_to === NULL ) {
                /// if we we have found something to try and match
                if ( preg_match("/[a-zA-Z]/",$from[$current]) ) {
                    /// set out program to attempt to match next items to this item
                    $match_to = $current;
                }

            /// if we are trying to match this item to a previously found one
            } else {
                /// if this item matches, we are in a sequence of like items
                if ( $from[$current] == $from[$match_to] ) {
                    /// update our match count
                    $match_count++;
                    /// if the match_count is < $min_sequence do nothing, we need more matches, move on
                    /// if the match_count is $min_sequence
                    if ( $match_count == 2 ) {
                        /// we skipped over the first few matches, so go back and obliterate them, as well as the current one
                        for ( $i = $current; $i >= $match_to; $i-- ) {
                            $from[$i]= $obliterate_with;
                        }

                    /// if the match_count is > $min_sequence
                    } else if ( $match_count > $min_sequence ) {
                        /// obliterate this match
                        $from[$current]= $obliterate_with;
                    }
                   
                /// if this item is not in our sequence
                } else {
                    /// reset our state variables to reflect this
                    $match_to = NULL;
                    $match_count = 0;
                }
            }
       }
    }
    return $from;
}


[ednark]

oops

Code: Select all

if ( $match_count == 2 ) {


should read

Code: Select all

if ( $match_count == $min_sequence ) {


[Jay]

Still far too long in my opinion. I would have used a for loop, and got it to check the $i variable, and then $i+1, and if it's the same, then $i+2, and if they're all the same, to unset $i+1 and $i+2 and move swiftly on

[ednark]

all talk and no code are we... lets see you fancy-schmancy tawlkin up on the board

[Jay]

I don't write my code for free ;)

But I'll help for free!