Algorithm simplification

Question

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!

I actually posted a clearer solution to that problem, on your original post, at around the same time that this solution was posted. — Cully
– Cully, Commented May 8, 2014 at 8:19
@CullyLarson I saw that. Is that why you downvoted this question? I'm not trying to outdo you. I'm trying to improve my programming skills and figure out a way to come up with a better solution than my first attempt. Ultimately, this question has nothing to do with the one you answered. This question is about how to simplify a redundant algorithm. — Mark Miller
– Mark Miller, Commented May 8, 2014 at 8:25
Hovering over the downgrade button, you see the text, "This question does not show research effort." The reason I downgraded it is because you have a simplified solution in a question you already asked. I would have downgraded it if I had simply seen the answers to your previous question, and had not provided one myself. — Cully
– Cully, Commented May 8, 2014 at 8:30
@CullyLarson Please pay attention to details. (1) The last question you are referring to was NOT my question. I have no interest in that solution. (2) This question is of an entirely different nature, it has nothing to do with the shortest path algorithm you provided for the other OP - which by the way is incorrect, go back and test it and read the question. I am not trying to solve some problem here for work or school, and I'm not looking for the solution you provided to the OTHER person's question - I am trying to learn and I ran into an unrelated problem which I clearly explained above. — Mark Miller
– Mark Miller, Commented May 8, 2014 at 8:41
Mark, I'm so sorry! I just now realized you weren't the guy who posted that original question. Undoing the down vote. Again, so sorry for subjecting you to my misunderstanding :) — Cully
– Cully, Commented May 9, 2014 at 0:57

Dai · Accepted Answer · 2014-05-08 08:30:48Z

2

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;

answered May 8, 2014 at 8:30

Dai

157k31 gold badges314 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mark Miller Over a year ago

Holy crap that's awesome! I was not familiar with max and min, but that is just what I was looking for - a way to cut down from 36 lines to just 1. Tested this on several combos and it seems to be working. Thanks for the help +1

Dai Over a year ago

@MarkM max is an elementary mathematical function which simply returns the largest of its arguments, and min is the opposite: it returns the smallest of its arguments, e.g. max( -5, 10 ) == 10, min( -50, 10 , 999, 21, Pi) == -50.

Collectives™ on Stack Overflow

Algorithm simplification

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related