苦海

学海无涯苦做舟

0%

Python Challenge (Level 32)

发表于 更新于 Valine：

第32关

这一关卡了好几天，现在还没解决好。为了能在过年前写完所有的关卡，打算先把解题思路弄下来，春节后再完善。

这一关是关于一个叫Nonogram的游戏。大概就是根据每一行每一列的数字来填格子，行列都符合的图案就是要求的答案。改变格子图案，再看看相应的行列的数字变换，大概就能知道这种游戏的玩法了。

根据Page Source里的提示，得到一个warmup.txt.根据这个warmup.txt解出来的的图案是一个向上的箭头。因此我们找到这个页面。

接着，我们得到一个更复杂的up.txt.根据这个攻略，up.txt解得的图像是一条蛇，python.html.

新页面上有以下内容

Congrats! You made it through to the smiling python.
“Free” as in “Free speech”, not as in “free…

Bing搜一下，找到这个页面，通关密码是beer. http://www.pythonchallenge.com/pc/rock/beer.html

下面是我用backtracking做的一个解。可以解出较小的图案，比如warmup.txt(LEN=8)。对于较大的，比如up.txt(LEN=32)，就无能为力了。我看了下，主要问题应该是产生candidates并把它们入栈是一次性完成的，会比较慢，占的内存又多。解决方法是入栈一个迭代器而不是所有candidates，每次next得到一个candidate.这个过完年再做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# -*- coding:utf-8 -*-
__author__ = 'chen'

from pprint import pprint
import numpy as np
import itertools

def readClue(loc_file):
    with open(loc_file, 'rb') as handle:
        data = list(handle)
    data = filter(lambda l: l[0] != '#' and l.strip(), data)
    data.pop(0)
    data = [i.strip().split() for i in data]
    for i in range(len(data)):
        data[i] = [int(item) for item in data[i]]
    clues = {}
    clues['row'] = data[ : len(data) / 2 ]
    clues['col'] = data[len(data) / 2 :]
    return clues

def getClue(clues, idx):
    if idx % 2 == 0:
        return clues['col'][idx // 2]
    else:
        return clues['row'][(idx - 1) // 2]

def getMask(picMat, idx):
    if idx % 2 == 0:
        ret = picMat[:, idx // 2]
    else:
        ret = picMat[(idx - 1) //2, :]
    ret = [str(i) for i in ret]
    return ''.join(ret)

def candidate(picMat, clue, idx, LEN):
    freeNum = LEN - (sum(clue) + len(clue) - 1)
    if freeNum < 0:
        return -1
    p = freeNum * ['0'] + len(clue) * ['#']
    options = set(list(itertools.permutations(p, len(p))))
    options = [''.join(i).split('#') for i in options]
    patterns = []
    for op in options:
        patt = ''
        for i in range(len(clue)):
            patt += op[i] + '1'*clue[i] + '0'
        patt = patt[:-1]  #除去最后一个0
        patt += op[-1]
        if check(idx, patt, picMat):
            patterns.append(patt)
    return patterns

def check(idx, patt, picMat):
    if idx % 2 == 0:
        idx = idx // 2
        restrict = picMat[:idx, idx]
    else:
        idx = (idx - 1) // 2
        restrict = picMat[idx, :idx+1]
    restrict = [str(i) for i in restrict]
    restrict = ''.join(restrict)
    return patt[:len(restrict)] == restrict

def resetMat(picMat, idx):
    if idx % 2 == 0:
        picMat[:, idx // 2] = 0
    else:
        picMat[(idx - 1) // 2, :] = 0

def fillMat(picMat, idx, patt):
    patt = [int(i) for i in patt]
    if idx % 2 == 0:
        picMat[:, idx // 2] = patt
    else:
        picMat[(idx - 1) // 2, :] = patt

def solve():
    LEN = 9
    clues = readClue('data/warmup.txt')
    picMat = np.zeros((LEN, LEN), dtype=np.int8)
    patt_l = []
    patt_l.append(candidate(picMat, getClue(clues, 0), 0, LEN))
    while patt_l and len(patt_l) != 2*LEN:
        curIdx = len(patt_l) - 1
        print curIdx
        if len(patt_l[curIdx]) <= 0:
            # resetMat(picMat, curIdx)
            # print picMat
            patt_l.pop(curIdx)
            continue
        else:
            patt = patt_l[curIdx].pop(0)
            fillMat(picMat, curIdx, patt)
            # print picMat
            nextCandidates = candidate(picMat, getClue(clues, curIdx+1), curIdx+1, LEN)
            if nextCandidates != -1 and nextCandidates:
                patt_l.append(nextCandidates)
    return picMat

if __name__ == "__main__" : print(solve())