Aug 31
天下一プログラマー実行委員の inada-n です。
今回は、本戦１日目の２問目にあたる「ナンクロ」を紹介します。
まずは問題です。
ナンクロとは、ナンバークロスワードの略称で、ヒントとなるカギ （補足説明）のないクロスワードパズルです。 文字の並びから単語を推理し、マスに文字を埋め、解いていく パズルになります。 通常のクロスワードとは異なり、すべてのマスに番号がついています。 同じ番号には同じ文字が入るので、他のマスでも単語の一部として 使えるようにマスに文字を埋めなくてはなりません。 なお、1つの番号に2つの文字が当てはまったり、逆に2つの番号に同じ 文字が当てはまることはありません。 また、同じ単語が2度出てくることもありません。 このルールを踏まえ、下記のナンクロ問題を解くプログラムを作成 し、ナンクロを解いてください。 なお、この問題を解く際には、下記に指定された辞書ファイルを 使用してください。 問題：numbercross.PNG <http://tenka1.klab.jp/resources/numbercross.PNG> 辞書：english.dic <http://tenka1.klab.jp/resources/english.dic>
補足すると、
(1)左から右、もしくは上から下に向かって、2文字以上連続している部分が単語になります。
(2)アルファベットの大文字小文字は区別しません。
この問題を解くためには、
(1) 2次元の問題データから、単語に対応する数列を抽出する
(2) すべての数列を辞書にある単語に変換するような、数値からアルファベットへの単射を探す
という作業が必要になります。ただし、問題データを画像で出題してしまっていたので、(1)に関しては手作業で行った方が早いかもしれません。
数値からアルファベットへの単射ですが、何も考えずにすべての組み合わせで上手くいくか試していこうとすると、アルファベットが２６種類、ナンクロに登場する数値が１～１９まで１９種類あるので、
>>> import math
>>> math.factorial(26) / math.factorial(26-19)
80018147048929689600000Lこれだけたくさんの試行が必要になってしまいます。そこで、数値とアルファベットの関係よりも数列と単語の関係に注目して、
(1) ある数列を選び、同じ形をした単語を選び、その数列と単語に出てきた数値とアルファベットから単射を構成する。
(2) 次の数列を選び、同じ形をした単語のうちすでに構成されている単射と矛盾が出ないものを選ぶ。構成済みの単射に含まれていない数値・アルファベットがあれば単射にそれを追加する。 (1,2,1 と aba のような場合に同じ形だとする)
(3) すべての数列を選ぶまで (2) を繰り返す。
といったプログラムで解くのが妥当でしょう。
次に、試行で数列を選ぶ順序ですが、長い数列や同じ数値が複数回出てくる単語を優先して選ぶと、早い段階で選択肢を絞り込むことができて効率がよさそうです。
たとえば数列を「同じ形をした単語の数」が少ない順に並べて試行すれば良いのですが、今回はもっと簡単に単語の長さの降順で試行するだけでもすぐに解がみつかりました。
次のプログラムは私の用意した解答プログラムです。
from pprint import pprint
from time import time
Q = """\
1 2 3 4 5 0 6 7 8 9 10
2 8 11 0 2 12 13 0 1 5 12
12 14 0 7 2 6 5 2 0 12 11
15 10 5 16 0 4 0 13 12 2 6
17 0 2 5 17 3 2 5 6 0 16
3 15 5 0 5 2 12 0 7 8 2
15 0 15 2 5 12 17 7 2 0 3
12 11 17 3 0 18 0 2 5 14 17
18 5 0 18 8 19 9 5 0 10 3
19 12 6 0 14 5 5 0 9 8 11
5 2 7 6 5 0 17 10 7 11 9"""
Q = [x.split() for x in Q.splitlines()]
for l in Q:
for i in range(len(l)):
l[i] = int(l[i])
for l in Q:
for c in l:
print "%2s" % (c,),
print
def make_dict():
words = [x.strip().lower() for x in open('english.dic').readlines() if x.strip() != '']
max_length = 0
for w in words:
max_length = max(len(w), max_length)
dic = [set() for x in xrange(max_length+1)]
for w in words:
dic[len(w)].add(w)
return dic
def make_slots(q):
W = len(q[0])
H = len(q)
slots = []
for y in range(H):
t = []
for x in range(W):
a = q[y][x]
if a == 0:
if len(t) > 1:
slots.append(tuple(t))
t = []
else:
t.append(a)
if len(t) > 1:
slots.append(tuple(t))
for x in range(W):
t = []
for y in range(H):
a = q[y][x]
if a == 0:
if len(t) > 1:
slots.append(tuple(t))
t = []
else:
t.append(a)
if len(t) > 1:
slots.append(tuple(t))
slots.sort(key=len, reverse=True)
return slots
def solve(slots, mapping, dictionary, used=set(), mapped=set()):
if len(slots) == 0:
return mapping
slot = list(slots[0])
L = len(slot)
for w in dictionary[L]:
if w in used:
continue
map = dict(mapping)
mapd = set(mapped)
u = used.copy()
u.add(w)
for i in xrange(L):
n = slot[i]
if n in map:
if w[i] != map[n]:
break
else:
if w[i] in mapd:
break
map[n] = w[i]
mapd.add(w[i])
else:
ret = solve(slots[1:], map, dictionary, u, mapd)
if ret:
return ret
start = time()
dictionary = make_dict()
slots = make_slots(Q)
pprint(slots)
map = solve(slots, {}, dictionary)
end = time()
pprint(map)
print '-----'
import sys
for l in Q:
for c in l:
if c == 0:
sys.stdout.write('#')
else:
sys.stdout.write(map[c])
sys.stdout.write('\n')
print '-----'
print (end-start), '[ms]'
solve() がメイン部分になっています。この関数は再帰でバックトラックするようになっており、引数の slots は数列のリスト、mapping は数値からアルファベットへのマッピング(単射)、dictionary は辞書を文字数毎に分けたもの、used はすでに利用されて選ぶことの出来ない英単語、mappedはアルファベットのうちmappingによって数値からマッピングされているものになっています。
短いし複雑なことも行っていないので、特に解説は要りませんね。
さて、今回の問題での一番の反省点は、問題データを画像形式で提供してしまったことです。
しかし、二日目の天下一プレゼン大会で、この点を突いて「問題データの画像を解析して解く」というプログラムを用意してくださった方がいました。そのプログラムも紹介しておきます。
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <map>
using namespace std;
typedef unsigned char ubyte;
typedef unsigned int uint;
struct RGB {
ubyte r;
ubyte g;
ubyte b;
uint toInt() const { return ((r<<16)|(r<<8)|(b)); }
};
struct BITMAPFILEHEADER {
unsigned short bfType;
unsigned long bfSize;
unsigned short bfReserved1;
unsigned short bfReserved2;
unsigned long bfOffBits;
};
struct BITMAPINFOHEADER {
unsigned long biSize;
long biWidth;
long biHeight;
unsigned short biPlanes;
unsigned short biBitCount;
unsigned long biCompression;
unsigned long biSizeImage;
long biXPixPerMeter;
long biYPixPerMeter;
unsigned long biClrUsed;
unsigned long biClrImporant;
};
class Bitmap
{
public:
Bitmap(const string fname)
{
FILE *fp = fopen(fname.c_str(), "rb");
// header_
header_.bfType = getShort(fp);
header_.bfSize = getInt(fp);
header_.bfReserved1 = getShort(fp);
header_.bfReserved2 = getShort(fp);
header_.bfOffBits = getInt(fp);
info_.biSize = getInt(fp);
assert(info_.biSize==40);
// info_
info_.biWidth = getInt(fp);
info_.biHeight = getInt(fp);
info_.biPlanes = getShort(fp);
info_.biBitCount = getShort(fp);
info_.biCompression = getInt(fp);
info_.biSizeImage = getInt(fp);
info_.biXPixPerMeter = getInt(fp);
info_.biYPixPerMeter = getInt(fp);
info_.biClrUsed = getInt(fp);
info_.biClrImporant = getInt(fp);
assert(info_.biBitCount==24);
cout << info_.biWidth << " x " << info_.biHeight << endl;
assert(header_.bfOffBits == ftell(fp)); //読み込み位置確認
const int h = info_.biHeight;
const int w = info_.biWidth;
const int pad = w % 4; // Bitmap は横幅が4バイトの倍数になるようにパディングされる
color_ = new RGB*[h];
for (int i=h-1; i >= 0; --i) {
color_[i] = new RGB[w];
for (int j=0; j < w; ++j) {
color_[i][j].r = getByte(fp);
color_[i][j].g = getByte(fp);
color_[i][j].b = getByte(fp);
}
for (int j=0; j < pad; ++j) {
getByte(fp);
}
}
fclose(fp);
}
int width() const { return info_.biWidth; }
int height() const { return info_.biHeight; }
~Bitmap()
{
for (int i=0; i < height(); ++i) {
delete[] color_[i];
}
delete[] color_;
}
RGB getColor(const int x, const int y) const { return color_[y][x]; }
private:
ubyte getByte(FILE *fp)
{
ubyte res;
fread(&res, 1, 1, fp);
return res;
}
int getInt(FILE* fp)
{
unsigned int t;
fread(&t, 4, 1, fp);
return t;
}
short getShort(FILE* fp)
{
return (getByte(fp) | (getByte(fp)<<8));
}
private:
RGB** color_;
BITMAPFILEHEADER header_;
BITMAPINFOHEADER info_;
};
const int HN = 30;
struct Histgram
{
int h[HN];
int len;
bool operator<(const Histgram &other) const
{
for (int i=0; i < HN; ++i) {
if (h[i] != other.h[i]) return h[i] < other.h[i];
}
return false;
}
Histgram operator+(const Histgram &other) const
{
Histgram res;
for (int i=0; i < HN; ++i) {
res.h[i] = h[i] + other.h[i];
}
return res;
}
};
Histgram getHist(const Bitmap &img, const int px, const int py, const int w)
{
Histgram res;
for (int i=0; i < HN; ++i) {
res.h[i] = 0;
for (int j=0; j < w; ++j) {
res.h[i] += (img.getColor(j+px, i+py).toInt()==0);
}
}
// 正規化
res.len = HN;
for (int i=0; i < HN; ++i) {
if (res.h[0]!=0) break;
rotate(res.h, res.h+1, res.h+res.len);
--res.len;
}
return res;
}
const int W = 11;
int field[W][W];
const int BLOCK = 0;
Histgram hist[20];
// 一番似ているものを探す
int findNo(const Histgram& h)
{
const int MAX_VAL = 100000;
// DP
int res = -1;
int minVal = MAX_VAL;
for (int k=0; k < 20; ++k) {
int g[HN][HN];
for (int i = 0; i < HN; ++i) {
for (int j = 0; j < HN; ++j) {
if (i == 0) g[i][j] = 0;
else g[i][j] = MAX_VAL;
}
}
for (int i=1; i < HN; ++i) {
for (int j=0; j < HN; ++j) {
int minPrev = g[i][j];
if (0 <= j - 1) minPrev = min(minPrev, g[i-1][j-1]);
if (0 <= j - 2) minPrev = min(minPrev, g[i-1][j-2]);
const int d = abs(hist[k].h[i]-h.h[j]);
g[i][j] = minPrev + d;
}
}
const int val = g[HN-1][HN-1];
if (val < minVal) {
res = k;
minVal = val;
}
}
return res;
}
void makeField()
{
// mspaint で numbercross.PNG を
// 24ビットマップ画像として保存したもの
Bitmap img("numbercross.bmp");
const int pw = img.width()/W;
const int ph = img.height()/W;
map<Histgram, int> histToInt;
const int num[W] = { 1, 2, 3, 4, 5, BLOCK, 6, 7, 8, 9, 10 };
// 1～10までをサンプルとしてとる
for (int ni=0; ni < 11; ++ni) {
Histgram h = getHist(img, ni*pw+1, 1, pw-2);
histToInt[h] = num[ni];
hist[num[ni]] = h;
}
// 組み合わせて11～を生成
for (int i=1; i <= 9; ++i) {
Histgram h = hist[1] + hist[i];
histToInt[h] = 10+i;
hist[10+i] = h;
}
for (int py=0; py < W; ++py) {
for (int px=0; px < W; ++px) {
Histgram h = getHist(img, px*pw+1, py*ph+1, pw-2);
field[py][px] = findNo(h);
printf("%2d ", field[py][px]);
}
cout << endl;
}
}
struct Form {
vector<int> num;
bool operator<(const Form &f) const {
return num.size() < f.num.size();
}
};
const int MAX_LEN = 30;
vector<Form> form;
vector<string> word[MAX_LEN];
bool isSafe(const int x, const int y)
{
return (0<=x&&x<W && 0<=y&&y<W && field[y][x]!=BLOCK);
}
void makeForm(const int dx, const int dy)
{
for (int y=0; y < W; ++y) {
for (int x=0; x < W; ++x) {
if (field[y][x] == BLOCK) continue;
if (isSafe(x-dx, y-dy)==false && isSafe(x+dx, y+dy)) {
Form t;
int tx=x;
int ty=y;
while (isSafe(tx, ty)) {
t.num.push_back(field[ty][tx]);
tx += dx;
ty += dy;
}
/*
cout << "Add:" << x << "," << y << " : ";
for (int i=0; i < t.num.size(); ++i) {
cout << t.num[i] << " ";
}
cout << endl;
*/
form.push_back(t);
}
}
}
}
void toUpper(string &s)
{
for (int i=0; i < s.length(); ++i) {
s[i] = toupper(s[i]);
assert(isalpha(s[i]));
}
}
vector<int> validWord(const Form &f, const char bindChar[], const bool used[])
{
vector<int> res;
const int len = f.num.size();
for (int i=0; i < word[len].size(); ++i) {
bool valid = true;
bool usedTmp[50]={0}; copy(used, used+50, usedTmp);
char bindTmp[20]={0}; copy(bindChar, bindChar+20, bindTmp);
for (int j=0; j < word[len][i].length(); ++j) {
const char c = word[len][i][j];
if ((usedTmp[c-'A'] && bindTmp[f.num[j]]!=c)
|| (!usedTmp[c-'A'] && (bindTmp[f.num[j]]!=0 && bindTmp[f.num[j]]!=c))
) {
valid = false;
break;
}
usedTmp[c-'A'] = true;
bindTmp[f.num[j]] = c;
}
if (valid) {
res.push_back(i);
}
}
return res;
}
void dfs(const int formPos, char* bindChar, bool* used, bool &isEnd)
{
if (isEnd) return;
static int mt = 0;
if (mt < formPos) {
mt = formPos;
cout << mt << endl;
if (formPos >=1) {
for (int i=1; i <= 19; ++i) {
cout << i << " = " << bindChar[i] << endl;
}
for (int i=0; i < W; ++i) {
for (int j=0; j < W; ++j) {
printf("%2c ", bindChar[field[i][j]]);
}
cout << endl;
}
//isEnd = true;
//return;
}
}
//cout << formPos << endl;
//if (formPos == form.size()) {
if (formPos==form.size()) {
isEnd = true;
return;
}
const Form &f = form[formPos];
const vector<int> wn = validWord(f, bindChar, used);
const int len = f.num.size();
for (int i=0; i < wn.size(); ++i) {
const string w = word[len][wn[i]];
assert(w.length()==f.num.size());
for (int j=0; j < w.length(); ++j) {
bindChar[f.num[j]] = w[j];
used[w[j]-'A'] = true;
}
dfs(formPos+1, bindChar, used, isEnd);
for (int j=0; j < w.length(); ++j) {
bindChar[f.num[j]] = 0;
used[w[j]-'A'] = false;
}
}
}
int main()
{
makeField();
makeForm(1, 0);
makeForm(0, 1);
sort(form.rbegin(), form.rend());
ifstream fin("english.dic");
int maxLen = 0;
string w;
while (fin>>w) {
toUpper(w);
maxLen = max(maxLen, (int)w.length());
word[w.length()].push_back(w);
}
fin.close();
char bindChar[20] = { 0 };
bool used[50] = { 0 };
bool isEnd = false;
dfs(0, bindChar, used, isEnd);
return 0;
}
なんという技術の無駄遣い！！