CODEWITHSUNDEEP
phpalgorithmoptimization
Mark Miller
Mark Miller

Reputation: 7447

Algorithm simplification

This question is in regard to another question that was posted earlier by someone else:

PHP: Determining Grid Count Between 2 Grids.

Note: Understanding the above problem is not necessary for this question; I just wanted to provide it for reference and additional context.

I was able to solve the problem, but I don't like my solution - it is obviously repetitive and I know it can be simplified, but my brain is just too fried right now to see it. I just can't give in and go to bed until I get some resolution.

Here is my current, working solution (at least the part that is relative to my question):

// Note: $col_diff and $row_diff will always be integers between 0 and 4

if ($col_diff==4) {
    $d = 5;
}
elseif ($col_diff==3) {
    if ($row_diff==4) 
        $d = 5;
    else
        $d = 4;
}
elseif ($col_diff==2) {
    if ($row_diff==4)
        $d = 5;
    elseif ($row_diff==3)
        $d = 4;
    else
        $d = 3;
}
elseif ($col_diff==1) {
    if ($row_diff==4)
        $d = 5;
    elseif ($row_diff==3)
        $d = 4;
    elseif ($row_diff==2)
        $d = 3;
    else
        $d = 2;
}
elseif ($col_diff==0) {
    if ($row_diff==4)
        $d = 5;
    elseif ($row_diff==3)
        $d = 4;
    elseif ($row_diff==2)
        $d = 3;
    elseif ($row_diff==1)
        $d = 2;
    else
        $d = 1;
}

echo $d; // Correct!

How can I simplify this and remove the redundancy?

This is what I envision the optimized structure to look like, but it is obviously flawed:

for ($i=4;$i>=0;$i--) 
    if ($col_diff==$i) 
        for ($j=$i;$j>=0;$j--)
            if ($row_diff==$j)
                $d = $j+1;

echo $d; // NOT Correct!

Upvotes: 1

Views: 84

Answers (1)

Dai
Dai

Reputation: 155055

I made a table from your code:

    col 4   3   2   1   0
row                     
4       5   5   5   5   5
3       5   4   4   4   4
2       5   4   3   3   3
1       5   4   3   2   2
0       5   4   3   2   1

There's a pattern here: the value of a cell is equal to its distance from 0,0 (see how like-numbers form 'squares' centered around the bottom-right corner).

Or:

cell = Max( x, y ) + 1

...kinda simple, eh?

Consider this as proof:

cell4,4 = Max( 4, 4 ) + 1 == 5
cell2,3 = Max( 2, 3 ) + 1 == 4

For your PHP, this is:

$d = max( $col_diff, $row_diff ) + 1;

It's that simple!

If your domain is limited to the range 4-0, then add a clamp:

$d = max( max( min( $col_diff, 4 ), 0 ), max( min( $row_diff, 4 ), 0 ) + 1;

Upvotes: 2

Related Questions