겹치지 않는 숫자 문제(1/3)

http://blog.readiz.com/112

에서 문제를 봤다. 나름 재밌는 문제 같아 나도 풀어봤다.

핵심 아이디어는 코멘트로 적었다. 세가지 방법으로 했다.

두번째는 그냥 가능한 전체 리스트를 만들어서 검사.

두번째를 하고 나니 코드가 나에게 외치고 있었다.

'재귀함수로 바꿔주세요. 재귀함수로 바꿔주세요...'

코드의 목소리를 외면할 수 없었다...ㅠ.ㅠ

재귀함수를 잘 설계하면 리스트를 넣으면 가능한 조합의 리스트를 출력하는 것도 가능할 거 같다.

quiz.py

 1 # -*- coding: cp949 -*-
 2 '''
 3 [a...i] == [1...9]
 4 
 5     a b
 6   x   c
 7  -------
 8     d e
 9   + f g
10  -------
11     h i
12 
13 1. [a, b, c, f, g] 5번 루프를 돈다.
14 2. c, b는 1이 될 수 없다. e값이 겹치게 된다.
15 3. 2의 이유로 c는 2이상이다. a가 4보다 크면 100을 넘어가게 된다.
16 4. d는 1이상이다. f는 9보다 작아야 100이 안넘는다.
17 5. e나 i는 0이 되면 안된다.
18 '''
19 
20 import string
21 
22 def prettyPrint(l, prettyShow=True):
23     (a, b, c, d, e, f, g, h, i) = l
24     if prettyShow:
25         print '='*10
26         print '    %d %d' % (a, b)
27         print '  X   %d' % c
28         print '-'*10
29         print '    %d %d' % (d, e)
30         print '  + %d %d' % (f, g)
31         print '-'*10
32         print '    %d %d' % (h, i)
33         print '\n'*1
34     else:
35         for num, val in enumerate(l):
36             print '%s=%d ' % (string.lowercase[num], val)
37 
38 def quizSolver(prettyShow=True):
39     iGotIt = False
40     for a in range(1, 5):
41         sublist = filter(lambda x: x!=a, range(1, 10))
42 
43         for b in filter(lambda x: x!=1, sublist):
44             subsublist = filter(lambda x: x!=b, sublist)
45 
46             for c in filter(lambda x: x!=1, subsublist):
47                 subsubsublist = filter(lambda x: x!=c, subsublist)
48 
49                 tmp = (a*10+b)*c
50                 d = tmp / 10
51                 e = tmp % 10
52 
53                 if tmp>98 or e==0 or len(set([a, b, c, d, e]))!=5:
54                     continue
55 
56                 subsubsubsublist = filter(lambda x: x!=d and x!=e, subsubsublist)
57                 for f in filter(lambda x: x<9, subsubsubsublist):
58                     for g in filter(lambda x: x!=f, subsubsubsublist):
59                         tmp2 = tmp + f*10 + g
60                         h = tmp2 / 10
61                         i = tmp2 % 10
62 
63                         if tmp2<99 and i!=0:
64                             l = [a, b, c, d, e, f, g, h, i]
65                             #if len(set(l)) == 9:
66                             if set(l) == set(range(1,10)):
67                                 iGotIt = True
68                                 prettyPrint(l, prettyShow=prettyShow)
69     return iGotIt
70 
71 if __name__ == '__main__':
72     if not quizSolver(prettyShow=False):
73         print "Cannot find numbers set(s)."