Объединение циклов в алгоритме

Question

Я хочу выполнить поиск определенного типа. Я не знаю, есть ли у него имя, но я могу описать его и иметь рабочий код для его выполнения.

Для двумерной матрицы, начинающейся в точке 0,0 и работающей вниз справа, генерация поиска будет выглядеть следующим образом:

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

Таким образом, первый цикл поиска будет проверять 1, второй цикл проверяет 2, 3, 4, третий цикл проверяет 5, 6, 7, 8, 9 и т. Д.

Код для поиска:

$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;
}

Я недоволен тем, как поиск разбивается на два цикла, так как код внутри циклов почти идентичен. Можете ли вы предложить способ объединения или вложения циклов и исключения избыточных вызовов для searchForPoint?

Answer 1

Как насчет этого

$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++;
}

Answer 2

Существует способ вложения циклов, но способ разбивки задачи на два цикла довольно интуитивен и, прежде всего, уже работает.

Скажем, мы оцениваем математическое выражение ln(x^2 + 1) - sqrt(x^2 + 1). Не было бы удобно написать это как f(x) = ln(g(x)) - sqrt(g(x)), g(x) = x^2 + 1? Похоже, это характер вашего вопроса, и смысл этой аналогии в том, что вы должны рассмотреть две функции.

У вас есть метод итерации, слева направо и снизу. Дайте этой стратегии имя и выделите ее как итератор. Используйте ООП, если хотите. Затем у вас есть понятие, что нужно делать что-то с каждой вещью, которую вам дает итератор. Дайте этой вещи имя и пусть она использует ваш итератор. Дополнительный бонус: вы можете прервать поиск сразу после того, как найдете совпадение, а не через некоторое время.

Псевдо-код:

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