[Python/C] 휴대폰 패턴의 가지수

인터넷에서 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;
}