使用Python根据成语列表生成填字的拼图

Published: Tags: 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