Combining loops in algorithm

Question

I want to perform a specific-type of search. I do not know if it has a name, but I can describe it, and have working code for its execution.

For a 2-dimensional matrix, starting at point 0,0 and working down-right, the search generation would look like:

1, 4, 9, 16, ...
2, 3, 8, 15, ...
5, 6, 7, 14, ...
10, 11, 12, 13, ...
...

So the first search loop would inspect 1, the second loop inspects 2, 3, 4, the third loop inspects 5, 6, 7, 8, 9, etc.

The code to produce this search is:

$row_search = 0;
$point_not_found = true;

while ($point_not_found && $row_search < $matrix_height/2)
{
    $current = array(0, $row_search);

    while ($current[0] < $row_search)
    {
        if (searchForPoint( $matrix, $current ) !== false)
            $point_not_found = false;

        ++$current[0];
    }

    if (!$anchor_not_found)
        break;

    while ($current[1] >= 0)
    {
        if (searchForPoint( $matrix, $current ) !== false)
            $point_not_found = false;

        --$current[1];
    }

    ++$row_search;
}

I am unhappy with how the search is broken into two loops, as the code within the loops is nearly identical. Can you suggest a way to either combine or nest the loops and eliminate redundant calls to searchForPoint?

Damp · Accepted Answer · 2011-02-02 18:35:17Z

3

What about something like this

$pointFound = false;
$row = 0;

while(!$pointFound && $row < $matrixSize)
{
    $y = $row;
    $x = 0;
    while($y >= 0)
    {
        if (searchForPoint($matrix,$x,$y) !== false)
        {
            $pointFound = true;
            break;
        }

        // If we reached the right column, start moving upwards (decreasing y)
        if($x == $row)
            $y--;
        // Else move right
        else
            $x++;
    }
    // EDIT (forgot the next line)
    $row++;
}

edited Feb 2, 2011 at 18:35

answered Feb 2, 2011 at 18:27

Damp

3,34822 silver badges19 bronze badges

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

Comments

erisco · Accepted Answer · 2011-02-02 18:51:02Z

There exists a way to nest the loops, but the way you've broken down the problem into two loops is quite intuitive and, foremost, already works.

Say we are evaluating the math expression ln(x^2 + 1) - sqrt(x^2 + 1). Wouldn't it be convenient to write it as f(x) = ln(g(x)) - sqrt(g(x)), g(x) = x^2 + 1? That seems to be the nature of your question, and the point of this analogy is that you should consider two functions.

You have a method of iterating, from top left to bottom right. Give this strategy a name and abstract it as an iterator. Use OOP if you like. Then, you have the concept of doing something with each thing the iterator gives you. Give that thing a name and have it use your iterator. Added bonus: you can abort searching immediately after you find a match, not some time after.

Pseudo-code:

$iterator = new MatrixRippleIterator($matrix);
$needle = 1337;
$found_match = false;
while ($iterator->hasNext()) {
    $current = $iterator->next();
    if ($current == $needle) {
        $found_match = true;
        break;
    }
}

Collectives™ on Stack Overflow

Combining loops in algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related