2015年5月31日日曜日

「ソフトウェアエンジニアならば1時間以内に解けなければいけない5つの問題」にPythonで挑んでみた

売られたケンカは買わずにいられない性分の人間です。こんにちは。
ダメ人間の鑑みたいな感じですね。

さてタイトルの通り、遅まきながら微妙に話題になっている感のある以下の問題に挑戦してみました。



Problem1〜4は昼休みに会社で20分くらい、Problem5は帰宅してから40〜50分くらいで終わったので失格かどうかギリギリのラインですね。

ということで、解答したソースコードは以下の通り。
（力業ゴリ押し感があるのはご愛嬌）
view raw _readme.md hosted with ❤ by GitHub
#!/usr/bin/env python
# -*- coding: utf-8-unix -*-
# this is the very simple impl :)
def do_for_loop(data):
sum = 0
for v in data:
sum += v
return sum
def do_while_loop(data):
sum = 0
i = 0
while i < len(data):
sum += data[i]
i += 1
return sum
def do_recursion(data):
if len(data) == 0:
return 0
return data[0] + do_recursion(data[1:])
def main(data, answer):
result = do_for_loop(data)
print(result)
assert answer == result
result = do_while_loop(data)
print(result)
assert answer == result
result = do_recursion(data)
print(result)
assert answer == result
if __name__ == '__main__':
main([1,2,3,4,5,6,7,8,9], 45)
view raw answer01.py hosted with ❤ by GitHub
#!/usr/bin/env python
# -*- coding: utf-8-unix -*-
import itertools
def concat_alternatively(former, latter):
return list(itertools.chain.from_iterable(zip(former, latter)))
def main(sources, answer):
result = concat_alternatively(sources[0], sources[1])
print(result)
assert answer == result
if __name__ == '__main__':
main((['a', 'b', 'c'], [1, 2, 3]),
['a', 1, 'b', 2, 'c', 3])
view raw answer02.py hosted with ❤ by GitHub
#!/usr/bin/env python
# -*- coding: utf-8-unix -*-
def calc_fibonacci(size):
result = [0,1]
while len(result) < size:
result.append(result[-1] + result[-2])
return result
def main(size, answer):
result = calc_fibonacci(size)
print(result)
assert answer == result
if __name__ == '__main__':
main(101, [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,
6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,
102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,
2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,
86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,
27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,
308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,
3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,
37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,
420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,
2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,
19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,
135301852344706746049,218922995834555169026,354224848179261915075])
view raw answer03.py hosted with ❤ by GitHub
#!/usr/bin/env python
# -*- coding: utf-8-unix -*-
import itertools
def calc_possible_maxvalue(data):
# brute-force and black-magic :)
return int(sorted(map(lambda l: ''.join(map(str, l)),
itertools.permutations(data)))[-1])
def main(data, answer):
result = calc_possible_maxvalue(data)
print(result)
assert answer == result
if __name__ == '__main__':
main([50,2,1,9], 95021)
main([50,2,12,9,13], 95021312)
view raw answer04.py hosted with ❤ by GitHub
#!/usr/bin/env python
# -*- coding: utf-8-unix -*-
operator_add = lambda t, p: t + p
operator_sub = lambda t, p: t - p
def calc_all_pattern(data):
state_list = [(0, data[0], data[1:], operator_add, '{}'.format(data[0]))]
result = []
while len(state_list) > 0:
# dirty...:(
total_value, previous_value, remain_values, previous_op, expression = state_list.pop(0)
if len(remain_values) > 0:
state_list.append((total_value,
(previous_value * 10 + remain_values[0]), remain_values[1:],
previous_op,
'{}{}'.format(expression, remain_values[0])))
state_list.append((previous_op(total_value, previous_value),
remain_values[0], remain_values[1:],
operator_add,
'{} + {}'.format(expression, remain_values[0])))
state_list.append((previous_op(total_value, previous_value),
remain_values[0], remain_values[1:],
operator_sub,
'{} - {}'.format(expression, remain_values[0])))
continue
applied_value = previous_op(total_value, previous_value)
if applied_value == 100:
result.append(expression)
return result
def main(data, answer):
result = calc_all_pattern(data)
for ex in result:
print(ex)
assert answer == eval(ex)
if __name__ == '__main__':
main([1,2,3,4,5,6,7,8,9], 100)
view raw answer05.py hosted with ❤ by GitHub
投稿者 時刻: 0 件のコメント:
ラベル:

2015年5月27日水曜日

mecab-ipadic-neologd試してみた

ちまちま手を動かしてましたが、どうも心折れると進みが悪くなりますね。おはようございます。

先日の記事（オープンソース版SiriのSirius試してみた）で、質問応答をいろいろ試していたのですが、どうやら日本語対応（というか英語以外の言語への対応を）していない*1ようでした。
てことで、せっかくなので勉強がてらNLPにも手を出してみることにします。
直近の目標は「簡単な質問応答ができる」にしようと思います。

んで、なんにせよ日本語を扱うのだから分かち書きできないとお話にならんのですが、MeCabの辞書としてよく使われるipadicをそのまま使うと、結果が今ひとつな感じになる印象です。（特に口語や新語の取り扱い）
辞書を自前で整備しようとするとどうもコストの調整が容易ではなさそうなので、また心折れそうになってました。

が、神はネットにいました。
MeCab 用の新語辞書 mecab-ipadic-neologd を公開しました [Overlasting::Life]
mecab-ipadic-neologd は、多数のWeb上の言語資源から得た新語を追加することでカスタマイズした MeCab 用のシステム辞書です。
まさに必要としていたものが公開されていたことに感動を覚えます。
ということで今回はこちらのご紹介です。

インストール（ソースインストールのMeCabを添えて）

基本的な手順はgithubに記載のとおりですが、MeCabをソースビルドしてかつ、root権が必要なところへインストールしている場合、neologdのインストールでsudoする際にMeCabへのパスを渡す必要があるので注意が必要*2です。
例えば以下の通り。
$ sudo PATH=$PATH:/usr/local/mecab/mecab-0.996/bin ./bin/install-mecab-ipadic-neologd -n
（/usr/local/mecab/mecab-0.996 にインストールしていた場合）

使ってみる

インストールが済んだら早速使ってみます。
システム辞書として指定するので、-d オプションでインストール先のディレクトリを指定して動かします。
$ echo "備忘録とかそんな感じの" | mecab -d /usr/local/mecab/mecab-0.996/lib/mecab/dic/mecab-ipadic-neologd
備忘録 名詞,一般,*,*,*,*,備忘録,ビボウロク,ビボーロク
とか 助詞,並立助詞,*,*,*,*,とか,トカ,トカ
そんな 連体詞,*,*,*,*,*,そんな,ソンナ,ソンナ
感じ 名詞,一般,*,*,*,*,感じ,カンジ,カンジ
の 助詞,連体化,*,*,*,*,の,ノ,ノ
EOS
ひとまずエラーなく動いているようです。
ただこのままだと、毎回長々とディレクトリ指定を書く必要があり面倒なのでエイリアスを追加しておきます。
.bashrcに以下の記述を追加しておくことで、少しでも楽をしたいと思います。
alias mecab-with-neolog='mecab -d /usr/local/mecab/mecab-0.996/lib/mecab/dic/mecab-ipadic-neologd'
一応ちゃんと設定できているか確認します。
$ mecab-with-neolog -D
filename: /usr/local/mecab/mecab-0.996/lib/mecab/dic/mecab-ipadic-neologd/sys.dic
version: 102
charset: UTF8
type: 0
size: 2068937
left size: 1316
right size: 1316
どうやら大丈夫そうです。
ということで、いろいろ試してみましょう。

手始めに最近購入して積ん読している某書籍のタイトルから。
$ echo "続・わかりやすいパターン認識　教師なし学習入門" | mecab
続 接頭詞,名詞接続,*,*,*,*,続,ゾク,ゾク
・ 記号,一般,*,*,*,*,・,・,・
わかり 動詞,自立,*,*,五段・ラ行,連用形,わかる,ワカリ,ワカリ
やすい 形容詞,非自立,*,*,形容詞・アウオ段,基本形,やすい,ヤスイ,ヤスイ
パターン 名詞,一般,*,*,*,*,パターン,パターン,パターン
認識 名詞,サ変接続,*,*,*,*,認識,ニンシキ,ニンシキ
　 記号,空白,*,*,*,*,　,　,　
教師 名詞,一般,*,*,*,*,教師,キョウシ,キョーシ
なし 形容詞,自立,*,*,形容詞・アウオ段,文語基本形,ない,ナシ,ナシ
学習 名詞,サ変接続,*,*,*,*,学習,ガクシュウ,ガクシュー
入門 名詞,サ変接続,*,*,*,*,入門,ニュウモン,ニューモン

$ echo "続・わかりやすいパターン認識　教師なし学習入門" | mecab-with-neolog 
続 接頭詞,名詞接続,*,*,*,*,続,ゾク,ゾク
・ 記号,一般,*,*,*,*,・,・,・
わかり 動詞,自立,*,*,五段・ラ行,連用形,わかる,ワカリ,ワカリ
やすい 形容詞,非自立,*,*,形容詞・アウオ段,基本形,やすい,ヤスイ,ヤスイ
パターン認識 名詞,固有名詞,一般,*,*,*,パターン認識,パターンニンシキ,パターンニンシキ
　 記号,空白,*,*,*,*,　,　,　
教師 名詞,一般,*,*,*,*,教師,キョウシ,キョーシ
なし 形容詞,自立,*,*,形容詞・アウオ段,文語基本形,ない,ナシ,ナシ
学習 名詞,サ変接続,*,*,*,*,学習,ガクシュウ,ガクシュー
入門 名詞,サ変接続,*,*,*,*,入門,ニュウモン,ニューモン
EOS
「パターン認識」が1語として分割されるようになっています。
「教師なし学習」も1語にしてほしい気もしますが、どこまでつなげるべきかについては詳しくないのでよくわかりません。

続いて某ラノベのタイトル。 
 echo "とある魔術の禁書目録" | mecab
とある 連体詞,*,*,*,*,*,とある,トアル,トアル
魔術 名詞,一般,*,*,*,*,魔術,マジュツ,マジュツ
の 助詞,連体化,*,*,*,*,の,ノ,ノ
禁書 名詞,一般,*,*,*,*,禁書,キンショ,キンショ
目録 名詞,一般,*,*,*,*,目録,モクロク,モクロク
EOS

$ echo "とある魔術の禁書目録" | mecab-with-neolog 
とある魔術の禁書目録 名詞,固有名詞,一般,*,*,*,とある魔術の禁書目録,トアルマジュツノインデックス,トアルマジュツノインデックス
EOS
1語にまとまっているのもさることながら、読みまで変わるのは素晴らしいです。

次。 
$ echo "リア充やリア充爆発しろとはどういう意味なのでしょうか。" | mecab
リア 名詞,固有名詞,人名,名,*,*,リア,リア,リア
充 名詞,固有名詞,人名,名,*,*,充,タカシ,タカシ
や 助詞,並立助詞,*,*,*,*,や,ヤ,ヤ
リア 名詞,一般,*,*,*,*,リア,リア,リア
充 名詞,固有名詞,人名,名,*,*,充,タカシ,タカシ
爆発 名詞,サ変接続,*,*,*,*,爆発,バクハツ,バクハツ
しろ 動詞,自立,*,*,サ変・スル,命令ｒｏ,する,シロ,シロ
と 助詞,格助詞,引用,*,*,*,と,ト,ト
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
どういう 連体詞,*,*,*,*,*,どういう,ドウイウ,ドーユウ
意味 名詞,サ変接続,*,*,*,*,意味,イミ,イミ
な 助動詞,*,*,*,特殊・ダ,体言接続,だ,ナ,ナ
の 名詞,非自立,一般,*,*,*,の,ノ,ノ
でしょ 助動詞,*,*,*,特殊・デス,未然形,です,デショ,デショ
う 助動詞,*,*,*,不変化型,基本形,う,ウ,ウ
か 助詞,副助詞／並立助詞／終助詞,*,*,*,*,か,カ,カ
。 記号,句点,*,*,*,*,。,。,。
EOS

$ echo "リア充やリア充爆発しろとはどういう意味なのでしょうか。" | mecab-with-neolog 
リア充 名詞,固有名詞,一般,*,*,*,リア充,リアジュウ,リアジュー
や 助詞,並立助詞,*,*,*,*,や,ヤ,ヤ
リア充爆発しろ 名詞,固有名詞,一般,*,*,*,リア充爆発しろ,リアジュウバクハツシロ,リアジュウバクハツシロ
と 助詞,格助詞,引用,*,*,*,と,ト,ト
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
どういう 連体詞,*,*,*,*,*,どういう,ドウイウ,ドーユウ
意味 名詞,サ変接続,*,*,*,*,意味,イミ,イミ
な 助動詞,*,*,*,特殊・ダ,体言接続,だ,ナ,ナ
の 名詞,非自立,一般,*,*,*,の,ノ,ノ
でしょ 助動詞,*,*,*,特殊・デス,未然形,です,デショ,デショ
う 助動詞,*,*,*,不変化型,基本形,う,ウ,ウ
か 助詞,副助詞／並立助詞／終助詞,*,*,*,*,か,カ,カ
。 記号,句点,*,*,*,*,。,。,。
EOS
「リア充」が1語にまとまっているのも、いろいろな用途を感じられてよいですね。
が、「リア充爆発しろ」が1語にまとまり、かつ名詞なのはどういうことでしょう？
と思って調べたら、どうやら少し前に「リア充爆発しろ」というアプリが話題になっていたようなのでその影響かもしれません。

ということで、非常に有用なMeCab用辞書 mecab-ipadic-neologd のご紹介でした。
これで日本語の解析がはかどりますね！！

*1：「システム構成上、自由に入れ替えられるから勝手にやってね！」って話のようですが。。。
*2：ハマったというか、そらそうよね感ある話。

投稿者 時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)