Hatena::Grouppython

Pythonで遊ぶよ

2011-01-20

リスト内包表記で数独

11:18

前回のような方法でリスト内包表記を使って数独を解くことができないかと思って試してみた。

数独の問題はだいぶ前にやったやつ。

    table = [
            [1,0,0,0,0,7,0,9,0],
            [0,3,0,0,2,0,0,0,8],
            [0,0,9,6,0,0,5,0,0],
            [0,0,5,3,0,0,9,0,0],
            [0,1,0,0,8,0,0,0,2],
            [6,0,0,0,0,4,0,0,0],
            [3,0,0,0,0,0,0,1,0],
            [0,4,0,0,0,0,0,0,7],
            [0,0,7,0,0,0,3,0,0]]

こんな感じ。

nums = set(range(1,10))
ans = [
        [
        [_00,_01,_02,_03,_04,_05,_06,_07,_08],
        [_10,_11,_12,_13,_14,_15,_16,_17,_18],
        [_20,_21,_22,_23,_24,_25,_26,_27,_28],
        [_30,_31,_32,_33,_34,_35,_36,_37,_38],
        [_40,_41,_42,_43,_44,_45,_46,_47,_48],
        [_50,_51,_52,_53,_54,_55,_56,_57,_58],
        [_60,_61,_62,_63,_64,_65,_66,_67,_68],
        [_70,_71,_72,_73,_74,_75,_76,_77,_78],
        [_80,_81,_82,_83,_84,_85,_86,_87,_88]
        ]
        for _00 in [1]
        for _05 in [7]
        for _07 in [9]
        for _11 in [3]
        for _14 in [2]
        for _18 in [8]
        for _22 in [9]
        for _23 in [6]
        for _26 in [5]
        for _32 in [5]
        for _33 in [3]
        for _36 in [9]
        for _41 in [1]
        for _44 in [8]
        for _48 in [2]
        for _50 in [6]
        for _55 in [4]
        for _60 in [3]
        for _67 in [1]
        for _71 in [4]
        for _78 in [7]
        for _82 in [7]
        for _86 in [3]
        for _01 in nums - set([_41,_71,_05,_07,_00,_11,_22])
        for _02 in nums - set([_05,_07,_00,_01,_11,_32,_22,_82])
        for _03 in nums - set([_05,_07,_00,_01,_02,_33,_23,_14])
        for _04 in nums - set([_44,_05,_07,_00,_01,_02,_03,_23,_14])
        for _06 in nums - set([_04,_05,_07,_00,_01,_02,_03,_26,_86,_18,_36])
        for _08 in nums - set([_48,_78,_04,_05,_06,_07,_00,_01,_02,_03,_26,_18])
        for _10 in nums - set([_02,_50,_60,_14,_00,_01,_11,_22,_18])
        for _12 in nums - set([_02,_14,_00,_01,_11,_10,_32,_22,_82,_18])
        for _13 in nums - set([_10,_04,_05,_14,_12,_11,_03,_33,_23,_18])
        for _15 in nums - set([_10,_55,_04,_05,_14,_13,_12,_11,_03,_23,_18])
        for _16 in nums - set([_06,_15,_07,_13,_12,_11,_10,_26,_86,_18,_08,_14,_36])
        for _17 in nums - set([_06,_16,_15,_07,_13,_12,_11,_10,_26,_18,_08,_14,_67])
        for _20 in nums - set([_02,_50,_60,_00,_12,_11,_10,_26,_22,_23,_01])
        for _21 in nums - set([_02,_41,_71,_00,_12,_11,_10,_26,_22,_23,_20,_01])
        for _24 in nums - set([_44,_04,_05,_15,_14,_13,_03,_26,_22,_23,_20,_21])
        for _25 in nums - set([_55,_04,_05,_15,_14,_13,_03,_26,_24,_22,_23,_20,_21])
        for _27 in nums - set([_18,_08,_17,_16,_06,_07,_67,_26,_24,_25,_22,_23,_20,_21])
        for _28 in nums - set([_48,_78,_18,_08,_17,_16,_06,_07,_26,_27,_24,_25,_22,_23,_20,_21])
        for _30 in nums - set([_41,_50,_60,_00,_10,_33,_32,_20,_36])
        for _31 in nums - set([_41,_50,_71,_21,_01,_11,_30,_33,_32,_36])
        for _34 in nums - set([_44,_55,_04,_14,_31,_30,_33,_32,_24,_36])
        for _35 in nums - set([_32,_44,_55,_05,_15,_31,_30,_33,_25,_34,_36])
        for _37 in nums - set([_48,_17,_07,_67,_27,_31,_30,_33,_32,_35,_34,_36])
        for _38 in nums - set([_48,_78,_18,_08,_28,_31,_30,_33,_32,_35,_34,_37,_36])
        for _40 in nums - set([_48,_41,_50,_44,_60,_00,_10,_31,_30,_32,_20])
        for _42 in nums - set([_48,_40,_41,_50,_44,_12,_02,_31,_30,_32,_22,_82])
        for _43 in nums - set([_48,_40,_41,_42,_44,_55,_23,_13,_03,_33,_35,_34])
        for _45 in nums - set([_48,_40,_41,_42,_43,_44,_55,_05,_15,_33,_25,_35,_34])
        for _46 in nums - set([_48,_38,_40,_41,_42,_43,_44,_45,_16,_06,_26,_86,_37,_36])
        for _47 in nums - set([_48,_40,_41,_42,_43,_44,_45,_46,_17,_38,_07,_67,_27,_37,_36])
        for _51 in nums - set([_40,_41,_42,_50,_71,_55,_01,_11,_31,_30,_32,_21])
        for _52 in nums - set([_40,_41,_51,_50,_55,_12,_02,_31,_30,_32,_22,_42,_82])
        for _53 in nums - set([_43,_52,_51,_50,_44,_45,_55,_23,_13,_03,_33,_35,_34])
        for _54 in nums - set([_43,_53,_52,_51,_50,_44,_45,_55,_04,_14,_33,_24,_35,_34])
        for _56 in nums - set([_48,_38,_53,_52,_51,_50,_55,_54,_16,_06,_46,_26,_86,_47,_37,_36])
        for _57 in nums - set([_48,_46,_53,_52,_51,_50,_56,_55,_54,_17,_38,_07,_67,_27,_47,_37,_36])
        for _58 in nums - set([_48,_78,_18,_53,_52,_51,_50,_57,_56,_55,_54,_38,_46,_28,_47,_08,_37,_36])
        for _61 in nums - set([_01,_41,_51,_71,_60,_67,_11,_31,_82,_21])
        for _62 in nums - set([_52,_42,_71,_60,_61,_12,_02,_32,_22,_82,_67])
        for _63 in nums - set([_53,_43,_62,_60,_61,_13,_67,_03,_33,_23])
        for _64 in nums - set([_61,_62,_44,_54,_04,_63,_60,_14,_67,_24,_34])
        for _65 in nums - set([_60,_05,_45,_55,_62,_63,_15,_61,_67,_64,_25,_35])
        for _66 in nums - set([_06,_78,_63,_56,_46,_62,_16,_60,_61,_67,_64,_65,_26,_86,_36])
        for _68 in nums - set([_48,_58,_64,_38,_78,_62,_63,_60,_61,_66,_67,_28,_65,_86,_08,_18])
        for _70 in nums - set([_78,_40,_50,_71,_62,_60,_61,_00,_82,_10,_30,_20])
        for _72 in nums - set([_78,_52,_42,_71,_70,_62,_60,_61,_12,_02,_32,_22,_82])
        for _73 in nums - set([_43,_78,_53,_65,_71,_70,_72,_63,_13,_64,_03,_33,_23])
        for _74 in nums - set([_78,_44,_71,_70,_73,_72,_04,_63,_14,_64,_65,_24,_54,_34])
        for _75 in nums - set([_78,_05,_74,_71,_45,_73,_72,_63,_15,_55,_64,_65,_70,_25,_35])
        for _76 in nums - set([_46,_78,_75,_74,_71,_56,_73,_72,_16,_06,_66,_67,_70,_26,_86,_68,_36])
        for _77 in nums - set([_78,_75,_74,_76,_71,_70,_73,_47,_17,_07,_66,_67,_57,_27,_86,_72,_68,_37])
        for _80 in nums - set([_40,_50,_71,_70,_72,_62,_60,_61,_00,_82,_10,_30,_86,_20])
        for _81 in nums - set([_41,_51,_71,_70,_72,_62,_60,_61,_01,_11,_31,_86,_80,_82,_21])
        for _83 in nums - set([_43,_86,_75,_74,_65,_73,_23,_63,_53,_13,_64,_03,_33,_80,_81,_82])
        for _84 in nums - set([_34,_75,_74,_44,_73,_54,_04,_63,_14,_64,_65,_86,_24,_80,_81,_82,_83])
        for _85 in nums - set([_35,_05,_75,_74,_45,_73,_63,_15,_55,_64,_65,_84,_86,_25,_80,_81,_82,_83])
        for _87 in nums - set([_81,_78,_77,_76,_57,_68,_47,_17,_07,_66,_82,_27,_84,_85,_86,_80,_67,_37,_83])
        for _88 in nums - set([_48,_58,_78,_18,_08,_77,_76,_38,_68,_66,_67,_28,_84,_85,_86,_87,_80,_81,_82,_83])
]
print(ans)

↑を出力するために書いたプログラム

#!/usr/bin/env python

'''
[
[_00,_01,_02,_03,_04,_05,_06,_07,_08],
[_10,_11,_12,_13,_14,_15,_16,_17,_18],
[_20,_21,_22,_23,_24,_25,_26,_27,_28],
...
]
'''

indices = range(9)
val = lambda row,col: '_' + str(row) + str(col)

table_rows = []

for row in indices:
    table_rows.append(
            '[' + ','.join(val(row,col) for col in indices) + ']')

table = '[\n' + ',\n'.join(table_rows) + '\n]'

program = table


fields = []
#problem set
problem = [
        [1,0,0,0,0,7,0,9,0],
        [0,3,0,0,2,0,0,0,8],
        [0,0,9,6,0,0,5,0,0],
        [0,0,5,3,0,0,9,0,0],
        [0,1,0,0,8,0,0,0,2],
        [6,0,0,0,0,4,0,0,0],
        [3,0,0,0,0,0,0,1,0],
        [0,4,0,0,0,0,0,0,7],
        [0,0,7,0,0,0,3,0,0]]

for row,rows in enumerate(problem):
    for col,num in enumerate(rows):
        if num: # != 0
            program += '\nfor ' + val(row,col) + ' in [' + str(num) + ']'
            fields.append((row,col))


# other conditions
for row in indices:
    for col in indices:
        if (row,col) not in fields:
            visited = set(fields)
            visited.update((r,c) for r in range(row) for c in indices)
            visited.update((row,c) for c in range(col))
            excl = set([val(r,c) for (r,c) in visited
                    if (r == row)
                    or (c == col)
                    or ((row / 3) * 3 <= r < (row / 3 + 1) * 3
                    and (col / 3) * 3 <= c < (col / 3 + 1) * 3)])
            program += '\nfor ' + val(row,col) + ' in nums - set([' + ','.join(excl) + '])'

program = '\t' + program.replace('\n', '\n\t')

program = 'nums = set(range(1,10))\nans = [\n' + program + '\n]\nprint(ans)'

print(program)


import profile
profile.run(program)

profile とったけど、リスト内包表記の中までは見てくれないらしくて参考にならなかった。0.7秒ぐらいで終わったらしい。

Haskell (GHC) だとコンパイルに0.6秒、実行に0.05秒ぐらいだった。そんなもんか。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20110120

2010-12-25

SEND+MORE=MONEY

04:31

おもしろかった。リストの内包表記みたいだと思った。

digits = set(range(0,10))

def dig(*args):
  return reduce(lambda x,y: x*10 + y, args)

ans = [(dig(s,e,n,d), dig(m,o,r,e), dig(m,o,n,e,y))
    for s in digits
    for e in digits - set([s])
    for n in digits - set([s,e])
    for d in digits - set([s,e,n])
    for m in digits - set([s,e,n,d])
    for o in digits - set([s,e,n,d,m])
    for r in digits - set([s,e,n,d,m,o])
    for y in digits - set([s,e,n,d,m,o,r])
    if  s != 0
    and m != 0
    and dig(s,e,n,d) + dig(m,o,r,e) == dig(m,o,n,e,y)]

print(ans)

深さ優先探索。ただし全部列挙なのでオーダーは O(N!) かな?

何度も同じ計算をやってる部分をちょっと直すと実行時間40%オフになるけど。

digits = set(range(0,10))

def dig(*args):
  return reduce(lambda x,y: x*10 + y, args)

ans = [(send, more, dig(m,o,n,e,y))
    for s in digits - set([0])
    for e in digits - set([s])
    for n in digits - set([s,e])
    for d in digits - set([s,e,n])
    for send in [dig(s,e,n,d)]
    for m in digits - set([0,s,e,n,d])
    for o in digits - set([s,e,n,d,m])
    for r in digits - set([s,e,n,d,m,o])
    for more in [dig(m,o,r,e)]
    for y in digits - set([s,e,n,d,m,o,r])
    if send + more == dig(m,o,n,e,y)]

print(ans)
トラックバック - http://python.g.hatena.ne.jp/edvakf/20101225

2010-11-24

fontTools

03:43

Charis SIL という IPA 記号(発音記号)がとても綺麗なフリーのフォントがある。

改変 OK だしウェブフォントにも使えるんだけど、いかんせん Unicode をかなり網羅的にカバーしていて1.5MB もあるので、発音記号のあたりだけ抜き出したい。

そこで、project_the_tower2 さんが紹介してた fontTools というライブラリを使おうとしたんだけど、途中でエラーが出てしまった。

% ~/c/Python26/python foo.py
Dumping 'GlyphOrder' table...
Dumping 'head' table...
Dumping 'hhea' table...
Dumping 'maxp' table...
Dumping 'OS/2' table...
Dumping 'hmtx' table...
Dumping 'cmap' table...
Dumping 'fpgm' table...
Dumping 'prep' table...
Dumping 'cvt ' table...
Dumping 'loca' table...
Dumping 'glyf' table...
Traceback (most recent call last):
  File "foo.py", line 4, in <module>
    tt.saveXML("CharisSIL-regular.xml");
  File "C:\Users\atsushi\My Dropbox\Programming\Sites\webfont\py\fonttools-2.3\Lib\fontTools\ttLib\__init__.py", line 268, in saveXML
    self._tableToXML(tableWriter, tag, progress)
  File "C:\Users\atsushi\My Dropbox\Programming\Sites\webfont\py\fonttools-2.3\Lib\fontTools\ttLib\__init__.py", line 283, in _tableToXML
    table = self[tag]
  File "C:\Users\atsushi\My Dropbox\Programming\Sites\webfont\py\fonttools-2.3\Lib\fontTools\ttLib\__init__.py", line 373, in __getitem__
    table.decompile(data, self)
  File "C:\Users\atsushi\My Dropbox\Programming\Sites\webfont\py\fonttools-2.3\Lib\fontTools\ttLib\tables\_k_e_r_n.py", line 40, in decompile
    subtable.decompile(data[:length], ttFont)
  File "C:\Users\atsushi\My Dropbox\Programming\Sites\webfont\py\fonttools-2.3\Lib\fontTools\ttLib\tables\_k_e_r_n.py", line 103, in decompile
    assert len(data) == 0, len(data)
AssertionError: 21154

残念。regular でも italic でも同じところ(グリフを抜き出すところ?)で止まってしまう。何かいい方法ないかな…。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20101124

2010-11-17

collections.Counter

10:05

SQLite で300万行ぐらいのテキストの転置インデックスを作っているのだが、そもそも大量に出てくるトークンを保存してもあまり意味が無いので、それらは省きたい。

そこで、

{
  "this": 100,
  "is": 200,
  "a": 500,
  "pen": 10
}

のように各トークンを数えて、一番カウントが多かったものから順に取り出したい。

まさにそういう目的のために用意されてるのが collections.Counter 。

collections は大量のデータを扱うための dict のようなものらしい。Counter は Python 3.1以上と 2.7 にある。(3.0 にはない)

SQLite ファイルを開いて、転置インデックスのテーブルを全部見ていき、トークンを Counter に格納する。最後は most_common で取り出す。

#!/usr/bin/python
import sqlite3
import collections

path = "C:\\Users\\atsushi\\AppData\\Local\\Google\\Chrome\\User Data\\Default\\databases\\chrome-extension_igchbgllbcppipoalfnjoepildadhkll_0\\4"

conn = sqlite3.connect(path)
tokens = collections.Counter()

c = conn.cursor()
c.execute('SELECT token FROM invindex ;')
for row in c:
  token = row[0]
  tokens[token] += 1

f = open('output.txt', 'w', encoding='utf-8')
for token, times in tokens.most_common(10000):
  f.write(token + '\t' + str(times) + '\n')

f.close()

簡単ですな。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20101117

2010-10-02

urllib.urlencode に unicode を渡すとエラー

02:33

Python 2.x の話。3.x は知らない。

args = {"foo": "bar", "hoge": "fuga", "piyo": 123}

foo=bar&hoge=fuga&piyo=123 にしたい。

そういうときは urllib.urlencode を使って

import urllib
print urllib.urlencode(args)

とするみたいなのだが、unicode が混じってると使えない。

>>> args = {"foo": "bar", "hoge": u"ほげ", "piyo": 123}
>>> urllib.urlencode(args)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Library/Frameworks/Python.framework/Versions/6.0.0/lib/python2.6/urllib.py", line 1268, in urlencode
    v = quote_plus(str(v))
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: ordinal not in range(128)

エラーメッセージで検索すると、

urllib.urlencode(dict([k, v.encode('utf-8')] for k, v in args.items()))

でいいと書いてあった。

unicodestr だけだったらこれでいいんだけど、今回のように数字とかが混じってると .encode メソッドが無いよと怒られるので、

urllib.urlencode(dict([k, v.encode('utf-8') if isinstance(v, unicode) else v] for k, v in args.items()))

とした。

>>> urllib.urlencode(dict([k, v.encode('utf-8') if isinstance(v, unicode) else v] for k, v in args.items()))
'foo=bar&piyo=123&hoge=%E3%81%BB%E3%81%92'

面倒だな。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20101002