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

jerryxjr1220

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

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


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

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

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



下面贴一下我的解答：

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

from pymprog import *
def p185(data1,gs1,nd1=5,ncn1=6) :
  xid1=iprod(list(range(nd1)),list(range(10)))
  m1=model('p185')
  x1=m1.var(xid1,'X1',bool)
  r1=m1.st(sum(x1[i1,j1] for j1 in range(10))==1 for i1 in range(nd1))
  r2=m1.st(sum(x1[j1,data1[i1][j1]] for j1 in range(nd1))==gs1[i1] for i1 in range(ncn1))
  m1.solve()
  s1=''
  for i1 in range(nd1) :
    for j1 in range(10) :
      if x1[i1,j1].primal>0.5 :
        s1+=str(j1)
  return s1
data2=[
(5,6,1,6,1,8,5,6,5,0,5,1,8,2,9,3),
(3,8,4,7,4,3,9,6,4,7,2,9,3,0,4,7),
(5,8,5,5,4,6,2,9,4,0,8,1,0,5,8,7),
(9,7,4,2,8,5,5,5,0,7,0,6,8,3,5,3),
(4,2,9,6,8,4,9,6,4,3,6,0,7,5,4,3),
(3,1,7,4,2,4,8,4,3,9,4,6,5,8,5,8),
(4,5,1,3,5,5,9,0,9,4,1,4,6,1,1,7),
(7,8,9,0,9,7,1,5,4,8,9,0,8,0,6,7),
(8,1,5,7,3,5,6,3,4,4,1,1,8,4,8,3),
(2,6,1,5,2,5,0,7,4,4,3,8,6,8,9,9),
(8,6,9,0,0,9,5,8,5,1,5,2,6,2,5,4),
(6,3,7,5,7,1,1,9,1,5,0,7,7,0,5,0),
(6,9,1,3,8,5,9,1,7,3,1,2,1,3,6,0),
(6,4,4,2,8,8,9,0,5,5,0,4,2,7,6,8),
(2,3,2,1,3,8,6,1,0,4,3,0,3,8,4,5),
(2,3,2,6,5,0,9,4,7,1,2,7,1,4,4,8),
(5,2,5,1,5,8,3,3,7,9,6,4,4,3,2,2),
(1,7,4,8,2,7,0,4,7,6,7,5,8,2,7,6),
(4,8,9,5,7,2,2,6,5,2,1,9,0,3,0,6),
(3,0,4,1,6,3,1,1,1,7,2,2,4,6,3,5),
(1,8,4,1,2,3,6,4,5,4,3,2,4,5,8,9),
(2,6,5,9,8,6,2,6,3,7,3,1,6,8,6,7)]
gs2=(2,1,3,3,3,2,2,3,1,2,3,1,1,2,0,2,2,3,1,3,3,2)
nd1,ncn1=16,22
n1=p185(data2,gs2,nd1,ncn1)
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

from random import randint, choice

print('Project-Euler-185 Number Mind')
guess = [
    ('5616185650518293', 2),
    ('3847439647293047', 1),
    ('5855462940810587', 3),
    ('9742855507068353', 3),
    ('4296849643607543', 3),
    ('3174248439465858', 2),
    ('4513559094146117', 2),
    ('7890971548908067', 3),
    ('8157356344118483', 1),
    ('2615250744386899', 2),
    ('8690095851526254', 3),
    ('6375711915077050', 1),
    ('6913859173121360', 1),
    ('6442889055042768', 2),
    ('2321386104303845', 0),
    ('2326509471271448', 2),
    ('5251583379644322', 2),
    ('1748270476758276', 3),
    ('4895722652190306', 1),
    ('3041631117224635', 3),
    ('1841236454324589', 3),
    ('2659862637316867', 2)
]

nlen = len(guess[0][0]) # 数字的位数
guess_set = [(set(enumerate(s)),n)for s,n in guess]

def 错误量计数(curset:set):
    errors = sum(abs(n-len(curset & st))for st,n in guess_set)
    return errors

def 随机替换(digit:str):
    digit_old = digit
    while digit_old == digit:
        digit = choice('0123456789') 
    return digit
    
MaxImprv = 20 # 最多试探次数
test_cnt = 0  # 试探次数

curnum = randint(10**(nlen-1),10**nlen-1) #随机生成 当前待测数
curset = set(enumerate(str(curnum)))
errors = errors_old = 错误量计数(curset)
while (errors != 0):
    for i in range(nlen):# 依次替换每位数字
        num_old = [x for x in curset if x[0]==i][0]
        _,digit = num_old
        num_new = (i,随机替换(digit))
        curset.remove(num_old)
        curset.add(num_new)        
        curerr = 错误量计数(curset)
        if curerr <= errors: #错误量 减少
            errors = curerr
        else:
            curset.remove(num_new)
            curset.add(num_old) #保留 原数字
            
    if errors == errors_old: #整体错误量没改善
        test_cnt += 1
        if test_cnt==MaxImprv:# 达到了 最多试探次数，则随机换一个新数
            curnum = randint(10**(nlen-1),10**nlen-1) 
            curset = set(enumerate(str(curnum)))
            errors = 错误量计数(curset)
            test_cnt = 0
    else: # 有改善，继续测试
        test_cnt = 0
        errors_old = errors       

print(''.join(d for n,d in sorted(curset,key=lambda x:x[0])))
input('ok')

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