마방진:1307 2일차.

오늘도 마방진문제에 대하여서 풀고 있다.

그전에 무작정 논문에 나온 알고리즘을 분석하여 적용하려 했는데, 구현이 꽤나 까다로운 것 같아 방향을 틀었다.
일단 마방진을 구현하기 위해서 시간 분석도는 차차하고, n이 홀수일때, O(N^2)안에 수행되는 

de la Loubère의 알고리즘을 이용하기로 했다.

def make_odd_magicsquare(n):
    #n^2크기 배열 생성
    arr = [[0 for _ in range(n)] for _ in range(n)]
    #초기 인덱스 첫번째 행의 가운데 위치 now를 설정
    now = [n // 2, 0]
    #주어진 규칙으로 숫자를 n^2번 배정한다.
    for i in range(1, n**2 + 1):
        x, y = now
        arr[y][x] = i
        new_x = x + 1 if x + 1 < n else 0
        new_y = y - 1 if y - 1 >= 0 else n - 1
        now = (x, y + 1) if arr[new_y][new_x] else (new_x, new_y)
    return arr

홀수마방진 알고리즘은 다음과 같이 구현할 수 있었다.

그 다음 문제는 단일 짝수 마방진 생성을 홀수마방진을 이용하여 구하는 것이었다.
여기서 짝수 마방진을 4개의 홀수 마방진으로 분할하여 처리하면 되는데, 분할하는 과정에서
배열의 값을 한번에 처리하는 함수를 생성하여 처리하려고 했는데, 그게 잘 안되어서 머리가아프다.
2중 리스트를 순회하여 map을 n번 적용시키는 방법도 있는데, 이번에 다중 리스트안의 요소를 일괄적으로 처리하는 방법에 대해 찾아보던중, 데코레이터에 대해 알게되어서 해당 방법을 적용해보기로 하였다.

https://hnanmal.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%95%A8%EC%88%98-%EB%8D%B0%EC%BD%94%EB%A0%88%EC%9D%B4%ED%84%B0%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%B4%EC%84%9C-%ED%95%A8%EC%88%98-%EB%B2%94%EC%9A%A9%EC%84%B1-%EB%86%92%EC%9D%B4%EA%B8%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EB%A0%88%EB%B2%A8%EA%B5%AC%EC%A1%B0-%EA%B8%B0%EB%8A%A5-%EC%B6%94%EA%B0%80

파이썬 함수 데코레이터를 이용해서 함수 범용성 높이기(리스트 레벨구조 기능 추가)

그런데 생각보다 적용하기가 쉽지 않았다.

magic_plus라는 함수에 데코레이터를 적용하면 쉽게 될줄 알았는데, 단순 곱하기에 데코레이터를 사용하는 것과 변수가 들어가는 것은 달랐다.

아무튼 데코레이터를 적용하는 아이디어는 괜찮은 것 같다.
오늘의 결과코드

def make_odd_magicsquare(n):
    #n^2크기 배열 생성
    arr = [[0 for _ in range(n)] for _ in range(n)]
    #초기 인덱스 첫번째 행의 가운데 위치 now를 설정
    now = [n // 2, 0]
    #주어진 규칙으로 숫자를 n^2번 배정한다.
    for i in range(1, n**2 + 1):
        x, y = now
        arr[y][x] = i
        new_x = x + 1 if x + 1 < n else 0
        new_y = y - 1 if y - 1 >= 0 else n - 1
        now = (x, y + 1) if arr[new_y][new_x] else (new_x, new_y)
    return arr


def make_double_even_magicsquare(n):
    pass

def iterize(function):
    def wrapper(args):
        if isinstance(args, list) or isinstance(args, set) or isinstance(args, tuple) or isinstance(args, dict):
            return map(wrapper, args)
        else:
            return function(args)
    return wrapper

@iterize
def magic_plus1(x):
    return x + (N // 2 ** 2) * 1

@iterize
def magic_plus2(x):
    return x + (N // 2 ** 2) * 2

@iterize
def magic_plus3(x):
    return x + (N // 2 ** 2) * 3

def strachey_algorithm(n):
    arr = [make_odd_magicsquare(n // 2) for _ in range(4)]
    arr[1] = magic_plus2(arr[1])
    arr[2] = magic_plus3(arr[2])
    arr[3] = magic_plus1(arr[3])
    arr = list(zip(arr[0],arr[1])) + list(zip(arr[2], arr[3]))
    return arr


if __name__ == "__main__":
    N = int(input())
    if N % 2 == 1:
        print(make_odd_magicsquare(N))
    elif N % 4 == 0:
        pass
    else:
        print(strachey_algorithm(N))