Checkio.org | Mono Captcha题解

昨天在checkio上做了一道挺有意思的题。这道题中同时用上了列表推导、filter、int、join、map、bin和数字异或的特性。将解题思路记下来,也算是对自己近期学习Python的一个总结吧~~

题目(译)

原题地址:Mono Captcha
让我们来教教机器人Stephan识别简单的数字。机器人使用低分辨率的等宽字体。你可以看看下面图片中的字体感受一下。这个字体具备一个像素错误的抗噪能力。

你的程序应该能够读取以二进制数字矩阵图像显示的数字。每一个数字最多只允许包含一个错误的像素。每个数字之间是一个像素的空间(例如”1”虽然比其他数字窄,但是还是具有3个像素的宽度)。

输入

一个图片,该图片用拥有取值为1或0的列表组成的列表

输出

整型数字

例子

1
2
3
4
5
6
7
8
9
10
checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394
checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394

前提条件

矩阵行数 == 5
5 ≤ 矩阵列数 < 30
∀ x ∈ 矩阵 : x == 0 or x == 1
数字宽度 == 3
每一个数字至多包含一个像素错误。
数字间宽度 == 1

题解

由于每个数字的宽度和数字间的间隔是固定的,因此可以分割输入矩阵为一个一个的数字块,然后比较该数字块与哪一个数字块最接近即可。因此,思路梳理为:分割 -> 查找 -> 拼接

分割

由于只能使用Python自带模块,因此不能考虑使用例如第三方模块numpy来进行简单快速的矩阵操作进行矩阵分割。此时,可以使用列表推导代替。
另外,由于每个数字的宽度是3, 数字间宽度为1,因此,第i个数字为矩阵的第1+i4列到第3+i4列。
此时,可以写出类似下面的代码来分割:

1
2
def slice(array, index=0):
return [item[1+index*4:4+index*4] for item in array]

查找

首先,我们需要建立一个正确的数字二进制矩阵集。这样的话,就可以将分割出来的每一个数字与标准进行对比。只要找到一个数字n,与分割出来的数字i最多存在一个位的不同,那么说明i所表示的就是数字n。
这里使用二进制异或的概念来实现。由于每个矩阵都是由0或1组成的,那么很容易就可以将每个数字转换为一个15位的二进制字符串。将二进制字符串m与分割出来的数字所转换成的二进制字符串j进行异或运算得到结果z。当z为0或者z的二进制表示中只包含一个”1”时,表明这个m对应的数字就是我们要找的数字。
根据上面分析得到的正确的数字二进制矩阵集如下:

1
2
3
digits = {0b010110010010010:'1',0b111001011100111:'2',0b111001010001111:'3',
0b101101111001001:'4',0b111100110001110:'5',0b011100111101011:'6',
0b111001010100100:'7',0b111101111101111:'8',0b011101111001110:'9',0b110101101101011:'0'}

需要修改一下分割函数,使得返回的也是编码后的数字:

1
2
def transfer(array, index=0):
return int("".join(["".join(map(lambda i:str(i),item[1+index*4:4+index*4])) for item in array]),2)

对应的判断函数如下:

1
func = lambda value, real=transfer(array,i): 1 == bin(value^real).count("1") or '0b0' == bin(value^real)

拼接

怎么根据查找到的二进制字符串找到对应的数字呢?此时我们可以用filter函数:filter(func,digits)
由于digits是字典,因此实际上func中的value取的是digits的键,这就是为什么digits长得这么怪异。另外,我们也可以利用digits的键值查找到对应的数字。

1
digits[filter(func,digits)[0]]

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def transfer(array, index=0):
return int("".join(["".join(map(lambda i:str(i),item[1+index*4:4+index*4])) for item in array]),2)

def checkio(array):
digits = {0b010110010010010:'1',0b111001011100111:'2',0b111001010001111:'3',
0b101101111001001:'4',0b111100110001110:'5',0b011100111101011:'6',
0b111001010100100:'7',0b111101111101111:'8',0b011101111001110:'9',0b110101101101011:'0'}

res = ""
#数字的个数可以用矩阵的列数len(array[0])/4得到,当然,python3k在这里需要修改一下
for i in xrange(0,len(array[0])/4):
func = lambda value, real=transfer(array,i): 1 == bin(value^real).count("1") or '0b0' == bin(value^real)
res+=digits[filter(func,digits)[0]]
return int(res)
请言小午吃个甜筒~~