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;
}
약간 변경해서, 1^1 + 2^2 + ... + 10000^10000 의 결과 중 끝 50자리를 출력하는 형식으로 바꿔보았다.
from multiprocessing import Pool
import time
MAX_COUNT = 10**50
def mypower(num):
result = 1
for i in range(num):
result = result * num
if result < MAX_COUNT:
continue
result = result % MAX_COUNT
return result
def get_sum(num):
assert num > 0
numbers = [i for i in range(1, num+1)]
assert len(numbers) == num
pool = Pool(processes=4)
return sum(list(pool.map(mypower, numbers))) % MAX_COUNT
if __name__ == '__main__':
start_time = time.time()
print(get_sum(10000))
print(time.time() - start_time)
