Coding/Python 삽질기2023. 3. 17. 00:51

ChatGPT의 도움을 받아서,  Python으로  간단한 Stack 기반의  virtual machine을 만들어 보기로 했다.

1. 명령어 정의 하기

Q: stack 기반 simple vm 용 어셈블리 명령어 리스트를 만들어줘

A:
아래는 스택 기반의 간단한 가상 머신 (VM)을 위한 어셈블리 명령어 리스트입니다. 
이러한 기본 명령어를 통해 작은 프로그램을 구현하고 실행할 수 있습니다.

PUSH <value>: 스택에 값을 푸시합니다. 예: PUSH 10
POP: 스택의 맨 위 값을 제거하고 반환합니다.
ADD: 스택의 맨 위 두 개의 값을 제거하고 합계를 계산한 후, 스택에 결과를 푸시합니다.
SUB: 스택의 맨 위 두 개의 값을 제거하고 차이를 계산한 후, 스택에 결과를 푸시합니다.
MUL: 스택의 맨 위 두 개의 값을 제거하고 곱을 계산한 후, 스택에 결과를 푸시합니다.
DIV: 스택의 맨 위 두 개의 값을 제거하고 나눗셈을 계산한 후, 스택에 결과를 푸시합니다. 
(0으로 나누는 경우에 대한 오류 처리를 고려하세요.)
MOD: 스택의 맨 위 두 개의 값을 제거하고 나머지를 계산한 후, 스택에 결과를 푸시합니다.
DUP: 스택의 맨 위 값을 복사하여 스택에 푸시합니다.
SWAP: 스택의 맨 위 두 개의 값을 교환합니다.
JMP <label>: 주어진 레이블로 프로그램 실행을 이동합니다. 예: JMP LOOP
JZ <label>: 스택의 맨 위 값이 0이면 주어진 레이블로 프로그램 실행을 이동합니다.
JNZ <label>: 스택의 맨 위 값이 0이 아니면 주어진 레이블로 프로그램 실행을 이동합니다.
CMP: 스택의 맨 위 두 개의 값을 비교하고 결과를 스택에 푸시합니다. 
(-1: 첫 번째 값이 작음, 0: 두 값이 같음, 1: 첫 번째 값이 큼)
CALL <label>: 현재 위치를 저장하고 주어진 레이블로 프로그램 실행을 이동합니다.
RET: 이전에 저장된 위치로 돌아가 프로그램 실행을 계속합니다.
NOP: 아무 작업도 수행하지 않습니다. 이 명령은 프로그램에서 무시됩니다.
HALT: 프로그램 실행을 중지합니다.
이 명령어들은 가장 기본적인 스택 기반 VM을 위한 것이며, 
필요에 따라 추가 명령어를 구현하여 더 복잡한 기능을 수행할 수 있습니다.

 

2. 명령어를 실행 할 수 있는 VM 만들기

위 명령어로 1부터 10까지 곱하는 어셈블리 프로그램을 짜줘

1부터 10까지 곱하는 스택 기반 가상 머신의 어셈블리 프로그램을 작성해 보겠습니다. 
이 프로그램은 10! (10 팩토리얼)을 계산하는 것과 동일합니다. 결과는 스택의 맨 위에 있게 됩니다.

vbnet
Copy code
; 팩토리얼 계산 시작
  PUSH 1         ; 스택에 초기 결과 (1)을 푸시
  PUSH 1         ; 스택에 초기 반복 횟수 (1)을 푸시

; 루프 시작
LOOP:
  DUP           ; 반복 횟수를 복사
  PUSH 10       ; 10을 스택에 푸시
  CMP           ; 반복 횟수와 10을 비교
  JG END_LOOP   ; 반복 횟수가 10보다 크면 루프 종료
  DUP           ; 반복 횟수를 복사
  MUL           ; 현재 결과와 반복 횟수를 곱하기
  PUSH 1        ; 1을 스택에 푸시
  ADD           ; 반복 횟수 증가
  JMP LOOP      ; 루프로 돌아가기

; 루프 종료
END_LOOP:
  NOP           ; 여기서 프로그램이 끝납니다. 필요한 경우 HALT 명령어를 사용할 수 있습니다.
이 프로그램을 실행하면 스택의 맨 위에 10! (3,628,800)이라는 결과가 남게 됩니다.

이렇게 버그가 포함된 코드를 짜주셨다. 이걸 실행 하면, 26이 나온다.

왜냐면 아래 코드가 잘못되었기 때문이다. 

  DUP           ; 반복 횟수를 복사
  MUL           ; 현재 결과와 반복 횟수를 곱하기

야간의 삽질 끝에 고친 실제 동작하는 코드는 아래와 같다. (ChatGPT 의 코드를 디버깅 하고 있었다;;;)

; 팩토리얼 계산 시작
  PUSH 1         ; 스택에 초기 결과 (1)을 푸시
  PUSH 1         ; 스택에 초기 반복 횟수 (1)을 푸시

; 루프 시작
LOOP:
  DUP           ; 반복 횟수를 복사
  PUSH 10       ; 10을 스택에 푸시
  CMP           ; 반복 횟수와 10을 비교
  JG END_LOOP   ; 반복 횟수가 10보다 크면 루프 종료
  MOV AX        ; 반복 횟수를 AX 레지스터에 복사
  MUL           ; 현재 결과와 반복 횟수를 곱하기
  PUSH AX       ; AX 레지스터의 값을 스택에 푸시
  PUSH 1        ; 1을 스택에 푸시
  ADD           ; 반복 횟수 증가
  JMP LOOP      ; 루프로 돌아가기

; 루프 종료
END_LOOP:
  NOP           ; 여기서 프로그램이 끝납니다. 필요한 경우 HALT 명령어를 사용할 수 있습니다.
이 프로그램을 실행하면 스택의 맨 위에 10! (3,628,800)이라는 결과가 남게 됩니다.

 

3. 위  코드를 실행 할 수 있는 VM 코드 생성

Q: 위 스택머신을 이용해서 파이썬으로 gwbasic 인터프리터 만들어줘

A:
GW-BASIC 인터프리터를 파이썬으로 만드는 것은 복잡한 작업입니다. 
그러나 여기 간단한 스택 기반 가상 머신 인터프리터를 제공합니다. 
이 인터프리터는 위에서 제공한 어셈블리 명령어를 사용할 수 있습니다.

python
Copy code
class StackMachine:
    def __init__(self):
        self.stack = []
        self.program = []
        self.labels = {}
        self.ip = 0

    def load_program(self, program):
        self.program = program
        for i, line in enumerate(program):
            if line.endswith(':'):
                self.labels[line[:-1]] = i

    def run(self):
        while self.ip < len(self.program):
            cmd = self.program[self.ip].split()
            op = cmd[0].upper()

            if op == 'PUSH':
                self.stack.append(int(cmd[1]))
            elif op == 'POP':
                self.stack.pop()
            elif op == 'ADD':
                self.stack.append(self.stack.pop() + self.stack.pop())
            elif op == 'SUB':
                b, a = self.stack.pop(), self.stack.pop()
                self.stack.append(a - b)
            elif op == 'MUL':
                self.stack.append(self.stack.pop() * self.stack.pop())
            elif op == 'DIV':
                b, a = self.stack.pop(), self.stack.pop()
                self.stack.append(a // b)
            elif op == 'MOD':
                b, a = self.stack.pop(), self.stack.pop()
                self.stack.append(a % b)
            elif op == 'DUP':
                self.stack.append(self.stack[-1])
            elif op == 'SWAP':
                self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]
            elif op == 'JMP':
                self.ip = self.labels[cmd[1]]
                continue
            elif op == 'JZ':
                if self.stack.pop() == 0:
                    self.ip = self.labels[cmd[1]]
                    continue
            elif op == 'JNZ':
                if self.stack.pop() != 0:
                    self.ip = self.labels[cmd[1]]
                    continue
            elif op == 'CMP':
                b, a = self.stack.pop(), self.stack.pop()
                self.stack.append((a > b) - (a < b))
            elif op == 'NOP':
                pass
            elif op == 'HALT':
                break

            self.ip += 1

# 예제 프로그램
program = [
    'PUSH 1',
    'PUSH 1',
    'LOOP:',
    'DUP',
    'PUSH 10',
    'CMP',
    'JG END_LOOP',
    'DUP',
    'MUL',
    'PUSH 1',
    'ADD',
    'JMP LOOP',
    'END_LOOP:',
    'NOP',
]

# 스택 머신 인스턴스 생성
stack_machine = StackMachine()

# 프로그램 로드 및 실행
stack_machine.load_program(program)
stack_machine.run()

# 결과 출력
print("계산 결과:", stack_machine.stack[-1])
이 코드는 간단한 스택 기반 가상 머신 인터프리터를 구현합니다. 
이것은 GW-BASIC 인터프리터가 아니지만, 이 인터프리터를 확장하여 
GW-BASIC 인터프리터를 구현하는 데 사용할 수 있습니다. 
GW-BASIC 인터프리터를 구현하려면 다음 단계를 수행하세요:

GW-BASIC 문법 정의: GW-BASIC의 문법을 정의하고 토큰화합니다. 
키워드, 상수, 변수, 연산자, 함수 등을 인식하도록 토크나이저를 작성해야 합니다.

파서 작성: 토크나이저에서 생성된 토큰을 사용하여 문법 트리를 작성하는 파서를 구현합니다. 
이 파서는 GW-BASIC 프로그램을 읽고 실행 가능한 중간 표현으로 변환합니다.

실행 엔진 확장: 현재 스택 기반 가상 머신을 확장하여 GW-BASIC의 
기능에 맞게 사용자 정의 변수, 프로시저, 함수, 조건문, 반복문 등을 처리할 수 있도록 해야 합니다.

입출력 및 에러 처리: GW-BASIC 인터프리터는 사용자 입력을 처리하고 출력을 표시해야 합니다. 
또한 실행 중 발생할 수 있는 에러를 적절하게 처리해야 합니다.

테스트: 다양한 GW-BASIC 프로그램을 사용하여 인터프리터를 테스트하고 버그를 수정합니다.

위 단계를 따르면 파이썬으로 GW-BASIC 인터프리터를 만드는 데 도움이 됩니다. 
그러나 이 작업은 상당한 시간과 노력이 필요합니다. 
이미 만들어진 BASIC 인터프리터가 여러 개 있으므로, 
이러한 프로젝트 중 하나를 참조하거나 사용하는 것도 좋은 방법입니다. 
이러한 프로젝트 중 하나는 pcbasic이며, 
다음 링크에서 확인할 수 있습니다: https://github.com/robhagemans/pcbasic

일단 위와 같이 대충 돌아가는 것 처럼 보이는 코드를 작성해 주신다. (물론 안돌아 간다)

그리고 ChatGPT 님 께서도, 오픈소스 가져다 쓰라고 추천 하신다.

2부에서 계속...

 

Posted by chobocho
Coding/Python 삽질기2023. 3. 14. 22:23

요즘 핫 한 ChatGPT를 유료 결제 하고, 이것 저것 질문을 해보았습니다.

Q:  python api 작명법

A: Python API 작명법은 일반적으로 PEP 8 스타일 가이드에 따라 작성됩니다. PEP 8은 파이썬의 공식 스타일 가이드로, 코드를 읽기 쉽고 이해하기 쉽게 만들어줍니다. API 작성에도 적용할 수 있는 일반적인 규칙은 다음과 같습니다.

  1. 함수와 메서드의 이름은 소문자와 밑줄을 사용하여 작성합니다.
  2. 변수와 함수 매개변수의 이름도 소문자와 밑줄을 사용하여 작성합니다.
  3. 클래스의 이름은 대문자로 시작하는 카멜 케이스(CamelCase)로 작성합니다.
  4. 모듈의 이름도 소문자와 밑줄을 사용하여 작성합니다.

예를 들어, 다음은 PEP 8에 따른 예시입니다.

# 함수와 메서드의 이름
def calculate_average(numbers_list):
    ...

class MyClass:
    def __init__(self):
        ...

# 변수와 함수 매개변수의 이름
my_variable = 42

def print_message(message):
    ...

# 모듈의 이름
import my_module

API 작성에는 더욱 구체적인 규칙이 존재할 수 있습니다. 따라서 해당 API의 문서를 참조하여 작명법을 따르는 것이 좋습니다.

  1. 상수의 이름은 모두 대문자와 밑줄을 사용하여 작성합니다.
  2. 함수나 메서드의 이름은 가능한 명사 또는 동사로 작성합니다. 함수나 메서드의 이름에서 명사와 동사는 함께 사용하여 기능을 명확하게 설명해야 합니다.
  3. 클래스의 이름은 명사로 작성하며, 클래스 이름이 여러 단어로 이루어진 경우 각 단어의 첫 글자를 대문자로 작성합니다. 이 스타일을 카멜 케이스(CamelCase)라고 합니다.
  4. 모듈의 이름은 짧고 명확해야 하며, 가능한 단일 단어로 작성하는 것이 좋습니다. 모듈의 이름도 카멜 케이스를 사용할 수 있지만, 보통은 소문자와 밑줄을 사용하여 작성합니다.

예를 들어, 다음은 PEP 8에 따른 예시입니다.

# 상수의 이름
MAXIMUM_NUMBER = 100

# 함수나 메서드의 이름
def calculate_average(numbers_list):
    ...

class MyClass:
    def __init__(self):
        ...

    def perform_action(self):
        ...

# 클래스의 이름
class MyClassName:
    ...

# 모듈의 이름
import my_module

API 작성 시에는 일관성이 매우 중요합니다. 같은 기능을 수행하는 함수나 메서드의 이름이 다른 경우, 사용자가 API를 이해하는 데 어려움을 겪을 수 있습니다. 따라서 API 작성 시에는 팀의 스타일 가이드를 따르거나, 기존 코드와 일관성 있게 작성하는 것이 좋습니다.

  1. 함수나 메서드의 이름에는 가능한한 매개변수의 자료형을 포함하지 않습니다. 함수나 메서드의 매개변수는 일반적으로 자료형에 대한 힌트(hint)를 포함할 수 있지만, 함수나 메서드의 이름에는 자료형에 대한 정보가 포함되어 있지 않아야 합니다.
  2. 함수나 메서드의 이름은 가능한한 짧게 작성하지 않습니다. 함수나 메서드의 이름은 가능한한 짧게 작성하는 것이 좋습니다. 그러나, 이름이 너무 짧으면 기능을 명확하게 설명하지 못할 수 있습니다. 따라서 이름은 가능한한 기능을 명확하게 설명할 수 있도록 작성하는 것이 좋습니다.

예를 들어, 다음은 PEP 8에 따른 예시입니다.

# 함수나 메서드의 이름에 자료형을 포함하지 않기
def calculate_average(numbers):
    ...

def add_numbers(x: int, y: int) -> int:
    ...

# 함수나 메서드의 이름이 너무 짧지 않게 작성하기
def calculate_average_of_numbers_in_list(numbers_list):
    ...

def add_two_numbers_and_return_result(first_number, second_number):
    ...

API 작성 시에는 사용자가 쉽게 이해할 수 있도록 기능을 명확하게 설명하는 것이 중요합니다. 또한, 코드의 가독성을 높이기 위해 이름을 가능한한 명확하게 작성하는 것이 좋습니다.

Posted by chobocho
Coding/Python 삽질기2023. 3. 9. 01:03

문명과 수학을 읽는 중 문득 Cycloid 곡선을 그리는 코드가 궁금해서, ChatGPT에게 물어보았다

Cycloid 곡선

 

import numpy as np
import matplotlib.pyplot as plt

# 파라미터 정의
r = 1  # 원의 반지름
a = 1  # 원주와 돌기의 간격

# 각도 범위 설정
t = np.linspace(0, 4*np.pi, 1000)

# 싸이클로이드의 수식
x = r * (t - np.sin(t))
y = r * (1 - np.cos(t)) - a

# 그래프 그리기
fig, ax = plt.subplots(figsize=(8, 8))

ax.plot(x, y, color='blue', linewidth=2)
ax.set_aspect('equal', adjustable='box')
ax.set_title('Cycloid')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.grid(True)

plt.show()

 

위 코드를 실행하면 아래 그림 같이 이쁘게 코드를 그려준다.

 

'Coding > Python 삽질기' 카테고리의 다른 글

[ChatGPT에게 묻다] python api 작명법  (0) 2023.03.14
[Python] Python 소소한 기능들  (0) 2023.02.04
[Design Pattern] Singleton pattern  (0) 2022.07.12
Posted by chobocho
Coding/Python 삽질기2023. 2. 4. 01:33

1.  f-string 예제

def f_string_test():
    rate = int(100_000_000 * 0.05 / 12)
    print(f'[{rate}]')
    # 3자리 마다 , 표시
    print(f'[{rate:,}]')
    # < : 좌측 정렬
    print(f'[{rate:<11}]')
    # < : 좌측 정렬, 빈칸은 _로 채우기
    print(f'[{rate:_<11,}]')
    # ^ : 가운데 정렬, 빈칸은 _로 채우기, 3자리 마다 , 표시
    print(f'[{rate:_^11,}]')
    # > : 우측 정렬, 빈칸은 _로 채우기, 3자리 마다 , 표시
    print(f'[{rate:_>11,}]')


if __name__ == '__main__':
    f_string_test()

2. ... 

def f_string_test():
    ...


if __name__ == '__main__':
    f_string_test()

'Coding > Python 삽질기' 카테고리의 다른 글

[Python] Cycloid 곡선 그리기  (0) 2023.03.09
[Design Pattern] Singleton pattern  (0) 2022.07.12
About Pyscript  (0) 2022.06.10
Posted by chobocho
Coding/Python 삽질기2022. 7. 12. 21:26

파이썬 싱글톤 패턴

class SingletonMeta(type):
    _instance = {}

    def __call__(cls, *args, **kwargs):
        if cls not in cls._instance:
            cls._instance[cls] = super().__call__(*args, **kwargs)
            print("make first object")
        else:
            print("return a exist object")

        return cls._instance[cls]


class Singleton(metaclass=SingletonMeta):
    def __init__(self):
        print("\nSingleton Init!")


def test_singleton():
    singletone1 = Singleton()
    singletone2 = Singleton()

    print(f'{id(singletone1)} == {id(singletone2)} -> {id(singletone1) == id(singletone2)}')

 

Singleton Init!
make first object
return a exist object
2608647861000 == 2608647861000 -> True

참고

https://refactoring.guru/design-patterns/singleton/python/example

 

Design Patterns: Singleton in Python

Usage examples: A lot of developers consider the Singleton pattern an antipattern. That’s why its usage is on the decline in Python code. Identification: Singleton can be recognized by a static creation method, which returns the same cached object. Naïv

refactoring.guru

https://dojang.io/mod/page/view.php?id=2468 

 

파이썬 코딩 도장: 47.9 메타클래스 사용하기

메타클래스(metaclass)는 클래스를 만드는 클래스인데, 이 메타클래스를 구현하는 방법은 두 가지가 있습니다. type을 사용하여 동적으로 클래스를 생성하는 방식 type을 상속받아서 메타클래스를

dojang.io

 

'Coding > Python 삽질기' 카테고리의 다른 글

[Python] Python 소소한 기능들  (0) 2023.02.04
About Pyscript  (0) 2022.06.10
[Python] C 함수 호출 하기  (0) 2022.04.23
Posted by chobocho
Coding/Python 삽질기2022. 6. 10. 00:05

'Coding > Python 삽질기' 카테고리의 다른 글

[Design Pattern] Singleton pattern  (0) 2022.07.12
[Python] C 함수 호출 하기  (0) 2022.04.23
[PyTorch] CUDA 설치기  (0) 2022.02.21
Posted by chobocho
Coding/Python 삽질기2022. 4. 23. 00:49

C library 작성

#include <stdio.h>
int add(int left, int right) {
    return left+right;
}
 
C library 빌드
gcc -shared -o libaddnumber.so add_number.c
 

Python Code 작성

from ctypes import CDLL
 
def main():
    c_func = CDLL('./libaddnumber.so')
    print(c_func.add(10, 20))
 
if __name__ == '__main__':
    main()
 
 
실행결과
chobocho@Chobocho-Mint:~/github/python/sharedlib$ python3 add_number.py 
30

'Coding > Python 삽질기' 카테고리의 다른 글

About Pyscript  (0) 2022.06.10
[PyTorch] CUDA 설치기  (0) 2022.02.21
생일 문제  (0) 2021.06.21
Posted by chobocho
Coding/Python 삽질기2022. 2. 21. 23:37

PyTorch에서 GPU를 사용해보기로 하고, 삽질한 기록을

미래의 나를 위하여, 기록하였습니다.

1. 노트북 그래픽 카드 확인

 

2. Pytorch 사이트에서 CUDA 버전을 확인한다.

https://pytorch.org/get-started/locally/

 

PyTorch

An open source machine learning framework that accelerates the path from research prototyping to production deployment.

pytorch.org

 PyTorch 1.10.2에 Pip로 CUDA 10.2를 선택하면, 아래에 pip3 명령어가 보인다.  이를 사용하여 pytorch를 설치한다.

 

3. CUDA library 설치

PyTorch 사이트에서 확인한 CUDA 10.2 버전을 설치한다.

 

* 간혹 NVIDIA experience가 동작을 안하는 경우에는 아래와 같이

NVIDIA LocalSystem Controller 에서 로컬 시스템 계정 항목을 체크해 준다.

4. 파이썬을 실행해서 확인 해 본다.

 

'Coding > Python 삽질기' 카테고리의 다른 글

[Python] C 함수 호출 하기  (0) 2022.04.23
생일 문제  (0) 2021.06.21
[Python/C] 휴대폰 패턴의 가지수  (0) 2021.02.21
Posted by chobocho
Coding/Python 삽질기2021. 6. 21. 23:46

기차표 예매를 위하여 줄을 섰을 때, 이들 중 생일이 같은 사람이 존재 할 확률은 얼마일까?

계산을 해보면, 23명 이상 일 때 부터 50%가 넘어가고, 57명이 넘어가면 99%가 넘어간다.

 

 

파이썬으로 짜보면 아래와 같다.

import matplotlib.pyplot as plt

prev = 1
result = [0]
for m in range(57):
    prev = prev * (365-m)/365
    result.append(1-prev)

x = [ n for n in range(len(result))]

plt.scatter(x, result)
plt.axvline(x=23, color='RED', linestyle='-', linewidth=0.2)
plt.axhline(y=0.5, color='RED', linestyle='-', linewidth=0.2)
plt.show()

Posted by chobocho
Coding/Python 삽질기2021. 2. 21. 23:27

인터넷에서 4개의 점 이상을 지나는 휴대폰 패턴의 가지수는 모두 몇 가지인가 라는 문제롤 보고 파이썬으로 풀어 보았다.

0: 9
1: 56
2: 320
3: 1624
4: 7152
5: 26016
6: 72912
7: 140704
8: 140704

4-9 patterns count: 389112

 

작성코드는 아래와 같다

 

import time
import math

def is_valid(used_pattern, stack, max_point):
    if len(stack) < max_point:
        return 0
                
    checked_point = [False] * 9
    checked_point[stack[0]] = True   

    for i in range(1, len(stack)):
        prev_x = stack[i-1] % 3
        prev_y = math.floor(stack[i-1] / 3)
        cur_x = stack[i] % 3
        cur_y = math.floor(stack[i] / 3)
        
        """
        0 1 2
        3 4 5
        6 7 8
        
        아래와 같은 이동한 경우,
        이동시 가운데 점이 기존 패턴에 포함 되지 않은 경우
        유효 하지 않다.
        
        0 <-> 2 | 0 <-> 6 | 0 <-> 8
        2 <-> 8 | 6 <-> 8 | 2 <-> 6
        1 <-> 7 | 3 <-> 5 

        예)
        0 -> 1 -> 0 -> 2 : OK
        0 -> 2 : Not OK
        
        유효하지 않은 경우를 판단하기 위하여
        각 버튼의 위치를 (y, x)로 나타내면 (0,0) ... (2,2) 까지이다.
         
        0 -> 2  =>  (0,0) -> (0, 2)
        0 -> 6  =>  (0,0) -> (2, 0)

        여기서 문제 경우의 
        두 좌표의 합을 구하면 x, y가 모두 2의 배수가 된다.
        그래서 아래와 같이 이동 전후의 좌표의 합이 모두 2의 배수가 되는 경우에서
        Not OK 경우만 걸러 주면 된다.
        
        0 -> 1 -> 0 -> 2 : OK
        0 -> 2 : Not OK

        """
        if ((prev_x + cur_x) % 2 == 0) and ((prev_y + cur_y) % 2 == 0):
            mid_x = math.floor((prev_x + cur_x) / 2)
            mid_y = math.floor((prev_y + cur_y) / 2)
            if checked_point[mid_y * 3 + mid_x] == False:
                return 0
                
        checked_point[stack[i]] = True
        
    return 1


def check_pattern(used_pattern, stack, max_point):
    if len(stack) > max_point:
       return 0
    
    result = is_valid(used_pattern, stack, max_point)
    
    for p in range(0, 9):
        if used_pattern[p]:
            continue
        used_pattern[p] = True
        stack.append(p)
        result = result + check_pattern(used_pattern, stack, max_point)
        stack.pop()
        used_pattern[p] = False
        
    return result

    
def main():
    used_pattern = [False] * 9
    stack = []
    result = []
  
    
    for max_point in range(1, 10):
        result.append(check_pattern(used_pattern, stack, max_point))
        
   
    for c in range(0, len(result)):
        print ("{0}: {1}".format(c, result[c]))
        
    print("4-9 patterns count:", sum(result[3:]))

if __name__ == '__main__':
    start_time = time.time() 
    main()
    print('\n', time.time() - start_time)
    

 


위 코드를 C로 바꾸면 아래와 같다.

#include <stdio.h>


int stack_idx;
int stack[9] = {0, };


int is_valid(int used) {
    int checked = 0;
    
    if (stack_idx < 4) {
        return 0;
    }

    checked |= 1 << stack[0];

    for (int i = 1; i < stack_idx; i++) {
        int prev_x = stack[i-1] % 3;
        int prev_y = stack[i-1] / 3;
        int cur_x = stack[i] % 3;
        int cur_y = stack[i] / 3;

        if (((prev_x + cur_x) % 2 == 0) &&
            ((prev_y + cur_y) % 2 == 0)) {

                 int mid_x = (prev_x + cur_x) / 2;
                 int mid_y = (prev_y + cur_y) / 2;
                 int pos = mid_y*3 + mid_x; 

                 if (!(checked & (1 << pos))) {
                     return 0;
                 }
        }
        checked |= (1 << stack[i]);
    }

    return 1;
}


int check_pattern(int used) {
    int result = 0;

    if (stack_idx == 10) {
        return 0;
    }

    result = is_valid(used);

    for (int i = 0; i < 9; i++) {
        if (used & (1 << i)) {
            continue;
        }

        stack[stack_idx++] = i;
        result += check_pattern(used | (1 << i));
        --stack_idx;
    }
    return result;
}


int main(int argc, char **argv) {
    printf("%d\n", check_pattern(0));
    return 0;
}
Posted by chobocho