Алгоритмы неформально. Инструкция для начинающих питонистов - [16]

Все вместе

Все, о чем говорилось выше, можно объединить в функцию, которая получает начальный квадрат со значениями nan и перемещается по нему, применяя три правила для заполнения. Все функция приведена в листинге 2.2.

Листинг 2.2. Функция, лежащая в основе реализации алгоритма Курусимы

import random

def fillsquare(square,entry_i,entry_j,howfull):

     while(sum(math.isnan(i) for row in square for i in row) > howfull):

        where_we_can_go = []

        if(entry_i < (n - 1) and entry_j < (n - 1)):

            where_we_can_go.append('down_right')

        if(entry_i < (n - 1) and entry_j > 0):

            where_we_can_go.append('down_left')

        if(entry_i > 0 and entry_j < (n - 1)):

            where_we_can_go.append('up_right')

        if(entry_i > 0 and entry_j > 0):

            where_we_can_go.append('up_left')

        where_to_go = random.choice(where_we_can_go)

        if(where_to_go == 'up_right'):

            new_entry_i = entry_i - 1

            new_entry_j = entry_j + 1

            square[new_entry_i][new_entry_j] =

                   rule1(square[entry_i][entry_j],n,True)

        if(where_to_go == 'down_left'):

            new_entry_i = entry_i + 1

            new_entry_j = entry_j - 1

            square[new_entry_i][new_entry_j] =

                   rule1(square[entry_i][entry_j],n,False)

        if(where_to_go == 'up_left' and (entry_i + entry_j) != (n)):

            new_entry_i = entry_i - 1

            new_entry_j = entry_j - 1

            square[new_entry_i][new_entry_j] =

                   rule2(square[entry_i][entry_j],n,True)

        if(where_to_go == 'down_right' and (entry_i + entry_j) != (n-2)):

            new_entry_i = entry_i + 1

            new_entry_j = entry_j + 1

            square[new_entry_i][new_entry_j] =

                   rule2(square[entry_i][entry_j],n,False)

        if(where_to_go == 'up_left' and (entry_i + entry_j) == (n)):

            new_entry_i = entry_i - 1

            new_entry_j = entry_j - 1

            square[new_entry_i][new_entry_j] =

                   rule3(square[entry_i][entry_j],n,True)

        if(where_to_go == 'down_right' and (entry_i + entry_j) == (n-2)):

            new_entry_i = entry_i + 1

            new_entry_j = entry_j + 1

            square[new_entry_i][new_entry_j] =

                   rule3(square[entry_i][entry_j],n,False)

   ❶  entry_i = new_entry_i

        entry_j = new_entry_j

    return(square)

Эта функция получает четыре аргумента: первый — исходный квадрат, содержащий значения nan; второй и третий — индексы ячейки, с которой начинается обход; четвертый — степень заполнения квадрата (количество допустимых значений nan). Функция состоит из цикла while, который при каждой итерации записывает число в квадрат по одному из трех правил. Цикл продолжается, пока не остается количество значений nan, заданное четвертым аргументом. После записи значения в ячейку цикл «переходит» в эту ячейку, изменяя индексы (❶), после чего все повторяется.

После того как функция будет написана, остается только правильно вызвать ее.

Использование правильных аргументов

Начнем заполнять магический квадрат с центральной ячейки. В аргументе howfull будет передаваться значение (n**2)/2-4. Причина для использования такого значения howfull станет понятной, когда мы увидим результаты:

entry_i = math.floor(n/2)

entry_j = math.floor(n/2)

square = fillsquare(square,entry_i,entry_j,(n**2)/2 - 4)

В данном случае функция fillsquare() вызывается с передачей существующей переменной square, определенной ранее. Напомню, что мы определили переменную square и заполнили ее значениями nan, кроме пяти центральных элементов. После того как функция fillsquare() с этим значением square на входе будет выполнена, она заполняет многие оставшиеся незаполненные значения.

Выведем полученный квадрат и посмотрим, как он выглядит после заполнения:

printsquare(square)

Результат выглядит так:

         [0]   [1]   [2]   [3]   [4]   [5]   [6]

   [0]    22   nan    16   nan    10   nan     4

   [1]   nan    23   nan    17   nan    11   nan

   [2]    30   nan    24    49    18   nan    12

   [3]   nan    31     7    25    43    19   nan

   [4]    38   nan    32     1    26   nan    20

   [5]   nan    39   nan    33   nan    27   nan

   [6]    46   nan    40   nan    34   nan    28

Обратите внимание: nan занимают чередующиеся ячейки, образуя шахматный узор. Это объясняется тем, что выбранные нами правила диагонального перемещения дают нам доступ приблизительно к половине ячеек в зависимости от того, какая ячейка была выбрана как начальная.

Допустимы те же перемещения, что и при игре в шашки: фигура, начинающая на черном квадрате, может перемещаться по диагонали на другие черные квадраты, но диагональные движения никогда не позволят ей встать на белую клетку. Если обход начинается с центральной ячейки, то оставшиеся значения nan недоступны. В алгоритме howfull передается значение (n**2)/2-4 вместо 0, поскольку мы знаем, что однократный вызов функции не позволит заполнить всю матрицу. Но если начать с одного из соседей центральной ячейки, то можно получить доступ к остальным значениям nan «шахматной доски». Снова вызовем функцию fillsquare(), однако на этот раз с другой исходной ячейкой и четвертым аргументом, равным 0 (он означает, что в квадрате не должно остаться пустых ячеек):