使用Python根据成语列表生成填字的拼图
#!/usr/bin/python
# -*- coding: utf-8 -*-
# crossword_puzzle_genxword.py by jtwo
from __future__ import unicode_literals
import os, random, time, codecs
from operator import itemgetter
from functools import partial
from collections import defaultdict
class Crossword(object):
def __init__(self, rows, cols, available_words=[], empty='.'):
self.rows = rows
self.cols = cols
self.empty = empty
self.available_words = available_words
self.let_coords = defaultdict(list)
def prep_grid_words(self):
self.current_wordlist = []
self.let_coords.clear()
self.grid = [[self.empty]*self.cols for i in range(self.rows)]
self.available_words = [word[:2] for word in self.available_words]
self.first_word(self.available_words[0])
def compute_crossword(self, time_permitted=1.00):
self.best_wordlist = []
wordlist_length = len(self.available_words)
time_permitted = float(time_permitted)
start_full = float(time.time())
while (float(time.time()) - start_full) < time_permitted:
self.prep_grid_words()
[self.add_words(word) for i in range(2) for word in self.available_words if word not in self.current_wordlist]
if len(self.current_wordlist) > len(self.best_wordlist):
self.best_wordlist = list(self.current_wordlist)
self.best_grid = list(self.grid)
if len(self.best_wordlist) == wordlist_length:
break
return self.rows, self.best_grid
def get_coords(self, word):
"""Return possible coordinates for each letter."""
word_length = len(word[0])
coordlist = []
temp_list = [(l, v) for l, letter in enumerate(word[0]) for k, v in self.let_coords.items() if k == letter]
for coord in temp_list:
letc = coord[0]
for item in coord[1]:
(rowc, colc, vertc) = item
if vertc:
if colc - letc >= 0 and (colc - letc) + word_length <= self.cols:
row, col = (rowc, colc - letc)
score = self.check_score_horiz(word, row, col, word_length)
if score:
coordlist.append([rowc, colc - letc, 0, score])
else:
if rowc - letc >= 0 and (rowc - letc) + word_length <= self.rows:
row, col = (rowc - letc, colc)
score = self.check_score_vert(word, row, col, word_length)
if score:
coordlist.append([rowc - letc, colc, 1, score])
if coordlist:
return max(coordlist, key=itemgetter(3))
else:
return
def first_word(self, word):
"""Place the first word at a random position in the grid."""
vertical = random.randrange(0, 2)
if vertical:
row = random.randrange(0, self.rows - len(word[0]))
col = random.randrange(0, self.cols)
else:
row = random.randrange(0, self.rows)
col = random.randrange(0, self.cols - len(word[0]))
self.set_word(word, row, col, vertical)
def add_words(self, word):
"""Add the rest of the words to the grid."""
coordlist = self.get_coords(word)
if not coordlist:
return
row, col, vertical = coordlist[0], coordlist[1], coordlist[2]
self.set_word(word, row, col, vertical)
def check_score_horiz(self, word, row, col, word_length, score=1):
cell_occupied = self.cell_occupied
if col and cell_occupied(row, col-1) or col + word_length != self.cols and cell_occupied(row, col + word_length):
return 0
for letter in word[0]:
active_cell = self.grid[row][col]
if active_cell == self.empty:
if row + 1 != self.rows and cell_occupied(row+1, col) or row and cell_occupied(row-1, col):
return 0
elif active_cell == letter:
score += 1
else:
return 0
col += 1
return score
def check_score_vert(self, word, row, col, word_length, score=1):
cell_occupied = self.cell_occupied
if row and cell_occupied(row-1, col) or row + word_length != self.rows and cell_occupied(row + word_length, col):
return 0
for letter in word[0]:
active_cell = self.grid[row][col]
if active_cell == self.empty:
if col + 1 != self.cols and cell_occupied(row, col+1) or col and cell_occupied(row, col-1):
return 0
elif active_cell == letter:
score += 1
else:
return 0
row += 1
return score
def set_word(self, word, row, col, vertical):
"""Put words on the grid and add them to the word list."""
word.extend([row, col, vertical])
self.current_wordlist.append(word)
horizontal = not vertical
for letter in word[0]:
self.grid[row][col] = letter
if (row, col, horizontal) not in self.let_coords[letter]:
self.let_coords[letter].append((row, col, vertical))
else:
self.let_coords[letter].remove((row, col, horizontal))
if vertical:
row += 1
else:
col += 1
def cell_occupied(self, row, col):
cell = self.grid[row][col]
if cell == self.empty:
return False
else:
return True
class Genxword(object):
def __init__(self):
pass
def puzzle(self, word_table, rect_num=0):
for word_list in word_table:
if rect_num > 15:
continue
if rect_num > 0:
self.nrow = self.ncol = rect_num
elif len(word_list) in [3,4]:
self.nrow = self.ncol = 6
elif len(word_list) in [5,6]:
self.nrow = self.ncol = 7
elif len(word_list) in [7,8]:
self.nrow = self.ncol = 8
elif len(word_list) in [9,10]:
self.nrow = self.ncol = 9
else:
self.nrow = self.ncol = 10
self.wordlist = [[word] for word in word_list]
calc = Crossword(self.nrow, self.ncol, self.wordlist)
grid_size, grid_info = calc.compute_crossword()
grid_coord = [i for gi in grid_info for i in gi]
idiom_raw = list(set(sorted([w for wl in word_list for w in wl])))
idiom_use = list(set(sorted([i for gi in grid_info for i in gi if i!='.'])))
if cmp(idiom_raw, idiom_use) != 0: #成语不同则加格子，重新运算
self.puzzle([[w for wl in self.wordlist for w in wl]], self.nrow+1); continue
word_coord = []
word_string = ''.join(word_list)
for ws in word_string:
gc = [str(k+1) for k,v in enumerate(grid_coord) if v==ws]
word_coord.append('/'.join(gc)) #如果某字多个坐标，斜杠分割
print '=' * 40
print 'PLAID:', grid_size
print 'IDIOM:', ','.join(word_list)
print 'COORD:', ','.join(word_coord)
print
grid_graph = '\n'.join([''.join([u'{} '.format(c) for c in grid_info[r]]) for r in range(grid_size)]).replace('.','．')
print grid_graph; print
open = partial(codecs.open, encoding='utf-8')
with open('/tmp/crossword/idiom.txt') as wordfile:
word_table = [line.strip().split(',') for line in wordfile if line.strip()]
Genxword().puzzle(word_table)
成语列表idiom.txt文件内容：
物伤其类,其应若响,大辩若讷,大有可观
心如止水,似水流年,延年益寿,寿比南山,恩重如山
承欢膝下,赧颜汗下,靦颜人世,年谊世好,好为事端,事无大小
输出效果：
========================================
PLAID: 6
IDIOM: 物伤其类,其应若响,大辩若讷,大有可观
COORD: 7,13,19,25,19,20,21,22,9,15,21,27,9,10,11,12
． ． ． ． ． ．
物 ． 大 有 可 观
伤 ． 辩 ． ． ．
其 应 若 响 ． ．
类 ． 讷 ． ． ．
． ． ． ． ． ．
========================================
PLAID: 7
IDIOM: 心如止水,似水流年,延年益寿,寿比南山,恩重如山
COORD: 8,9/47,10,11,4,11,18,25,24,25,26,27,27,34,41,48,45,46,9/47,48
． ． ． 似 ． ． ．
心 如 止 水 ． ． ．
． ． ． 流 ． ． ．
． ． 延 年 益 寿 ．
． ． ． ． ． 比 ．
． ． ． ． ． 南 ．
． ． 恩 重 如 山 ．
========================================
PLAID: 9
IDIOM: 承欢膝下,赧颜汗下,靦颜人世,年谊世好,好为事端,事无大小
COORD: 6,15,24,33,30,31,32,33,22,31,40,49,47,48,49,50,50,59,68,77,68,69,70,71
． ． ． ． ． 承 ． ． ．
． ． ． ． ． 欢 ． ． ．
． ． ． 靦 ． 膝 ． ． ．
． ． 赧 颜 汗 下 ． ． ．
． ． ． 人 ． ． ． ． ．
． 年 谊 世 好 ． ． ． ．
． ． ． ． 为 ． ． ． ．
． ． ． ． 事 无 大 小 ．
． ． ． ． 端 ． ． ． ．
参考资料（其实就是genxword库的代码）： https://pypi.org/project/genxword/ https://github.com/riverrun/genxword