鱼C论坛Python精英挑战赛（第三季04期）评比结果

jerryxjr1220

本期挑战赛共有SixPy，由于版主不参与评比。所以本期无优胜者。

可能本期的题目难度有些大，所以没找的好的方法或者工具的话，确实非常困难！


本次挑战赛竞猜获胜的是：
新手·ing

请在本帖回复，领取奖励5鱼币。

本期押宝没有获胜者，奖金10鱼币将累积到下一次押宝竞猜中。



下面贴一下我的解答：

其实本题也是一道线性规划的题目，本质上和“数独”类型的题目没有什么两样，利用线性规划库pymprog可以很轻松的解决。

1. from pymprog import *
   
2. def p185(data1,gs1,nd1=5,ncn1=6) :
   
3.   xid1=iprod(list(range(nd1)),list(range(10)))
   
4.   m1=model('p185')
   
5.   x1=m1.var(xid1,'X1',bool)
   
6.   r1=m1.st(sum(x1[i1,j1] for j1 in range(10))==1 for i1 in range(nd1))
   
7.   r2=m1.st(sum(x1[j1,data1[i1][j1]] for j1 in range(nd1))==gs1[i1] for i1 in range(ncn1))
   
8.   m1.solve()
   
9.   s1=''
   
10.   for i1 in range(nd1) :
    
11.     for j1 in range(10) :
    
12.       if x1[i1,j1].primal>0.5 :
    
13.         s1+=str(j1)
    
14.   return s1
    
15. data2=[
    
16. (5,6,1,6,1,8,5,6,5,0,5,1,8,2,9,3),
    
17. (3,8,4,7,4,3,9,6,4,7,2,9,3,0,4,7),
    
18. (5,8,5,5,4,6,2,9,4,0,8,1,0,5,8,7),
    
19. (9,7,4,2,8,5,5,5,0,7,0,6,8,3,5,3),
    
20. (4,2,9,6,8,4,9,6,4,3,6,0,7,5,4,3),
    
21. (3,1,7,4,2,4,8,4,3,9,4,6,5,8,5,8),
    
22. (4,5,1,3,5,5,9,0,9,4,1,4,6,1,1,7),
    
23. (7,8,9,0,9,7,1,5,4,8,9,0,8,0,6,7),
    
24. (8,1,5,7,3,5,6,3,4,4,1,1,8,4,8,3),
    
25. (2,6,1,5,2,5,0,7,4,4,3,8,6,8,9,9),
    
26. (8,6,9,0,0,9,5,8,5,1,5,2,6,2,5,4),
    
27. (6,3,7,5,7,1,1,9,1,5,0,7,7,0,5,0),
    
28. (6,9,1,3,8,5,9,1,7,3,1,2,1,3,6,0),
    
29. (6,4,4,2,8,8,9,0,5,5,0,4,2,7,6,8),
    
30. (2,3,2,1,3,8,6,1,0,4,3,0,3,8,4,5),
    
31. (2,3,2,6,5,0,9,4,7,1,2,7,1,4,4,8),
    
32. (5,2,5,1,5,8,3,3,7,9,6,4,4,3,2,2),
    
33. (1,7,4,8,2,7,0,4,7,6,7,5,8,2,7,6),
    
34. (4,8,9,5,7,2,2,6,5,2,1,9,0,3,0,6),
    
35. (3,0,4,1,6,3,1,1,1,7,2,2,4,6,3,5),
    
36. (1,8,4,1,2,3,6,4,5,4,3,2,4,5,8,9),
    
37. (2,6,5,9,8,6,2,6,3,7,3,1,6,8,6,7)]
    
38. gs2=(2,1,3,3,3,2,2,3,1,2,3,1,1,2,0,2,2,3,1,3,3,2)
    
39. nd1,ncn1=16,22
    
40. n1=p185(data2,gs2,nd1,ncn1)
    
41. print('The answer is ',n1)

复制代码

Deprecated call to var(.): name should be the first argument.
GLPK Simplex Optimizer, v4.60
38 rows, 160 columns, 512 non-zeros
      0: obj =   0.000000000e+00 inf =   6.100e+01 (37)
     55: obj =   0.000000000e+00 inf =   8.549e-15 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.60
38 rows, 160 columns, 512 non-zeros
160 integer variables, all of which are binary
Integer optimization begins...
+    55: mip =     not found yet >=              -inf        (1; 0)
+  1103: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (14; 79)
+  1103: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 123)
INTEGER OPTIMAL SOLUTION FOUND
The answer is  4640261571845533
[Finished in 0.3s]

gunjang

啊啊啊，还没找到思路，果然大神多

SixPy

gunjang 发表于 2017-9-30 20:49
啊啊啊，还没找到思路，果然大神多

由于是线性空间搜索，有唯一解。可以用蒙特卡罗、退火等随机模拟算法求解~

新手·ing

SixPy

1. from random import randint, choice
   
2. 
   
3. print('Project-Euler-185 Number Mind')
   
4. guess = [
   
5.     ('5616185650518293', 2),
   
6.     ('3847439647293047', 1),
   
7.     ('5855462940810587', 3),
   
8.     ('9742855507068353', 3),
   
9.     ('4296849643607543', 3),
   
10.     ('3174248439465858', 2),
    
11.     ('4513559094146117', 2),
    
12.     ('7890971548908067', 3),
    
13.     ('8157356344118483', 1),
    
14.     ('2615250744386899', 2),
    
15.     ('8690095851526254', 3),
    
16.     ('6375711915077050', 1),
    
17.     ('6913859173121360', 1),
    
18.     ('6442889055042768', 2),
    
19.     ('2321386104303845', 0),
    
20.     ('2326509471271448', 2),
    
21.     ('5251583379644322', 2),
    
22.     ('1748270476758276', 3),
    
23.     ('4895722652190306', 1),
    
24.     ('3041631117224635', 3),
    
25.     ('1841236454324589', 3),
    
26.     ('2659862637316867', 2)
    
27. ]
    
28. 
    
29. nlen = len(guess[0][0]) # 数字的位数
    
30. guess_set = [(set(enumerate(s)),n)for s,n in guess]
    
31. 
    
32. def 错误量计数(curset:set):
    
33.     errors = sum(abs(n-len(curset & st))for st,n in guess_set)
    
34.     return errors
    
35. 
    
36. def 随机替换(digit:str):
    
37.     digit_old = digit
    
38.     while digit_old == digit:
    
39.         digit = choice('0123456789')
    
40.     return digit
    
41.    
    
42. MaxImprv = 20 # 最多试探次数
    
43. test_cnt = 0  # 试探次数
    
44. 
    
45. curnum = randint(10**(nlen-1),10**nlen-1) #随机生成 当前待测数
    
46. curset = set(enumerate(str(curnum)))
    
47. errors = errors_old = 错误量计数(curset)
    
48. while (errors != 0):
    
49.     for i in range(nlen):# 依次替换每位数字
    
50.         num_old = [x for x in curset if x[0]==i][0]
    
51.         _,digit = num_old
    
52.         num_new = (i,随机替换(digit))
    
53.         curset.remove(num_old)
    
54.         curset.add(num_new)        
    
55.         curerr = 错误量计数(curset)
    
56.         if curerr <= errors: #错误量 减少
    
57.             errors = curerr
    
58.         else:
    
59.             curset.remove(num_new)
    
60.             curset.add(num_old) #保留 原数字
    
61.             
    
62.     if errors == errors_old: #整体错误量没改善
    
63.         test_cnt += 1
    
64.         if test_cnt==MaxImprv:# 达到了 最多试探次数，则随机换一个新数
    
65.             curnum = randint(10**(nlen-1),10**nlen-1)
    
66.             curset = set(enumerate(str(curnum)))
    
67.             errors = 错误量计数(curset)
    
68.             test_cnt = 0
    
69.     else: # 有改善，继续测试
    
70.         test_cnt = 0
    
71.         errors_old = errors      
    
72. 
    
73. print(''.join(d for n,d in sorted(curset,key=lambda x:x[0])))
    
74. input('ok')
    

复制代码

随机测试算法，效率不算高，运气好的话，10分钟就找到正确答案。
可以多开，cpu有几个核，你就运行几次这个程序，总有一个能先找到。