Blog List View

Mathematica Crossword Puzzles Maker(转) 

2015-04-16 05:46:05
2020 次阅读
本帖最后由 小小2 于 2015-4-16 13:54 编辑

之前找OS X游戏的时候在一个忘记了什么网站上看到了“Black ink”的Crossword Puzzle游戏,中文就是纵横字谜啦,不过好贵,而且我周围基本没见过有人玩过(感觉上一次见人玩大概就是无数年前Big Bang第一季第一集的时候了。。),自己更加没有刚需,所以就没理了;
然后某天晚上躺在床上脑洞的时候突然想到。。。啊咧,Mathematica的DictionaryLookup函数不是有全部的英语单词么?WordData不是可以获得单词的各种信息,包括Definition么?那我是不是可以利用这个生成单词列表,然后设计一个算法自动构造出一个Crossword Puzzle的谜题来?然后以前玩绘制Pokemon图鉴的时候玩过Grid这个屌炸天的函数,还可以用Dynamic来做一些联动的动态操作,so,本文就是这个脑洞的实现。。
生成单词列表
其实我自己从来没玩过Crossword Puzzle。。(所以我为什么会想到做这种东西),凭直觉大概觉得单词不会太长,也不会太短。。。。吧。。。。
于是,先找出所有单词里面长度4~7的单词:
Mathematica Code
随便看了一下,发现其实有一大部分比例单词第一个字母是大写,而且不是常用词,计划把他们过滤掉,另外,用WordData的时候也发现不是所有词都可以获取到Definition的,这些词也要扔掉!
首先,WordData第一次运行需要从W|A上面下载一些云上的数据,所以可以随便搞个单词来先把数据抓回来:
Mathematica Code
上面这个运行一下,等它下载完就可以了。
而且返回来的数据我们要获取其中Definition那部分,所以需要准备一个函数来获取定义:
Mathematica Code
然后过滤掉首字母大写和没定义的:
Mathematica Code
接下来随机找出我们指定数目的单词即可:
Mathematica Code
wordlist即所谓求。
构造谜题
构造谜题这个算法其实不难想,随便脑补一下大概就可以想到了,但是我发现这个算法Mathematica实现起来实在是。。。太尼玛艰难了,当然,我模仿别的语言,用各种For,Table,If函数确实可以翻译出来,但是既然不美,就索性不要去创造!【后来我想了想,可能是我mma在使用模式匹配上面的功力不够】
so,我用python实现了一下,思路很简单,就是随便挑一个单词放棋盘上,然后再不断地找下一个单词,在合适的位置放上去,递归求解就是了;
这个算法用python实现起来很快,我写的第一个可以输出结果的代码,加上空行注释,100行都不到,后面增加了一些结果打印函数,迭代中每次随机找单词和随机找位置,把结果导出到文本以便后期Mathematica调用,代码也是150行都不到。。
但是吐个槽,虽然python实现这种东西代码量远远小于C++,但是再给我一次机会,再也不敢用python了,对于这种需要迭代求解,每次往递归函数里面传进各种标记信息变量的时候,python这种不允许指定是值传递还是引用传递的语法,你就只能用a[:]来值传递一维的list,用copy.deepcopy来值传递二维list,难受死了,不是写得难受,而是感觉代码失去了某种美感。。
代码如下:
  1. $code
import copy,sys,random # 单词列表 wordstring = "buckles,killed,rubato,collect,......." WORDPOOL = wordstring.split(',') random.shuffle(WORDPOOL) BOARD_SIZE = 33 class CRecord: def __init__(self, m_size,m_wordpool): self.indexTable = [set() for x in range(26)] self.board = [['-' for x in range(m_size)] for x in range(m_size)] self.dirFlag = [[0 for x in range(m_size)] for x in range(m_size)] self.wordpool = m_wordpool self.items = [] # 显示结果 def ShowResult(record): output = "" for i in record.board: for j in i: output += j output += "\n" print output # 设置单词 def SetBoard(record, word, i, j, IsRow): record_copy = copy.deepcopy(record) for (idx,ch) in enumerate(word): ci = i + (not IsRow)*idx cj = j + IsRow*idx record_copy.dirFlag[ci][cj] |= (0x01 if IsRow else 0x02) record_copy.board[ci][cj] = ch record_copy.indexTable[ord(ch)-ord('a')].add((ci,cj)) record_copy.items.append([word,i,j,IsRow]) # 如果结束 if 0 == len(record_copy.wordpool): ShowResult(record) sys.exit(0) return record_copy # 检查在指定位置指定方向放单词是否合法 def ValidCheck(record, word, i, j, IsRow): L = len(word) if i < 0 or j < 0: return False # 横/纵向溢出检测 if IsRow and j + L - 1 >= BOARD_SIZE: return False if not IsRow and i + L - 1 >= BOARD_SIZE: return False # 单词左边/上边不可以已经有字母 if IsRow and j-1 >= 0 and record.board[i][j-1] != '-': return False if not IsRow and i-1 >= 0 and record.board[i-1][j] != '-': return False # 单词尾部下一位置不可以有单词 if IsRow and j+L < BOARD_SIZE and record.board[i][j+L] != '-': return False if not IsRow and i+L < BOARD_SIZE and record.board[i+L][j] != '-': return False for (idx,ch) in enumerate(word): ci = i + (not IsRow)*idx cj = j + IsRow*idx # 如果和已有单词不匹配 if record.board[ci][cj] != '-' and record.board[ci][cj] != ch: return False if record.board[ci][cj] == '-':#如果位置为空 # 横向单词上下不可以有纵向单词的尾部/头部 if IsRow and ci-1 >= 0 and record.board[ci-1][cj] != '-' and record.dirFlag[ci-1][cj] & 0x02: return False if IsRow and ci+1 < BOARD_SIZE and record.board[ci+1][cj] != '-' and record.dirFlag[ci+1][cj] & 0x02: return False # 纵向单词左右不可以有横向单词的尾部/头部 if not IsRow and cj-1 >= 0 and record.board[ci][cj-1] != '-' and record.dirFlag[ci][cj-1] & 0x01: return False if not IsRow and cj+1 < BOARD_SIZE and record.board[ci][cj+1] != '-' and record.dirFlag[ci][cj+1] & 0x01: return False return True # 迭代计算 def Calculate(record, curWord, i, j, isrow): if ValidCheck(record, curWord, i, j, isrow): record_t = SetBoard(record, curWord, i, j, isrow) for word in record.wordpool: Iter(copy.deepcopy(record_t), word) # 随机排序yield返回 def RandomSort(l): random.shuffle(l) for i in l: yield i def Iter(record, curWord): global WORDPOOL global BOARD_SIZE record.wordpool.remove(curWord) # 如果是第一个单词,放在棋盘中间 if len(record.wordpool) == len(WORDPOOL)-1: for isrow in RandomSort([True,False]): Calculate(record, curWord, (BOARD_SIZE-len(curWord)*(not isrow))//2, (BOARD_SIZE-len(curWord)*isrow)//2, isrow) else:# 否则,随机挑个字母,随机挑个位置 for (idx, ch) in enumerate(curWord): for pos in RandomSort(list(record.indexTable[ord(ch)-ord('a')])): for isrow in RandomSort([True,False]): Calculate(record, curWord, pos[0]-idx*(not isrow), pos[1]-idx*isrow, isrow) if __name__ == "__main__": record = CRecord(BOARD_SIZE, WORDPOOL) for word in record.wordpool: Iter(copy.deepcopy(record), word)



本文中代码删减了几个无谓的函数,完整版请看Github
由于不少地方用了random.shuffle函数,所以每次跑出来的结果都是不一样的,结果大概如下(左图是调试的时候一个参考):
然后导出到Mathematica的文本格式大概如下:
  1. $code
finesse 17 14 - encored 17 20 | outlay 20 20 - wisp 16 15 | cankers 19 20 - bocks 13 18 | insofar 16 16 | gerunds 22 19 - flower 17 14 | galling 22 19 | clear 15 18 - honchos 14 17 - decking 22 24 |

标记好单词,起点坐标,横竖信息。
显示谜题
首先,读进来数据,然后计算出有效棋盘大小,再然后初始化一个grid变量,全部为空字符串:
然后对grid变量,在正确的位置赋值上谜题答案的字母(要分横纵两种情况赋值):
Mathematica Code
在画棋盘之前需要准备两个小函数,一个是设置格子背景颜色的,一个是线框:
Mathematica Code
好了,可以试着把棋盘画出来了,一行:
Mathematica Code
结果如下:
感觉还行。。
但是。。。这个是答案啊!!不是谜题啊摔!!!你搞错了吧。。。
好好好,画谜题就画谜题。。
和画答案的区别在于,不要把字母标上,而是在起始位置标上数字,而联动操作的时候,设置一个按钮面板,点击不同的数,首先会在界面上高亮相应的行或列(or行和列),并且会在面板下面显示行列单词的谜题(就是词典里面这个单词的全部定义啦~)
代码如下:

Mathematica Code
录了个gif:
这种方法有两个缺陷,第一,要做出自动判断输入结果是对是错这个效果很麻烦(不是不可以),因为Table内每个元素绑定Dynamic的时候会有点限制。。另外一个问题就是自己输入结果的时候第一个字母处那个数字index要手动删掉。。
所有代码放在Github,有爱自取。
本来想做一个cdf演示直接挂博客的,但是,你看我这文章版面宽度,也懒了。。
总结
总之,食用方法就是先Mathematica生成单词列表,然后把列表拷到python代码中,运行一下,表格将会导出到一个文件中,再用Mathematica读取这个文件,构造界面。。

发表评论