カテゴリー別アーカイブ: CodeIQ

CodeIQの問題と解説

[解説]「再帰関数で逆順並べ替え」

問題文

再帰関数で逆順並べ替え
基本関数だけで逆順アルゴリズムを実現してみよう!
今回の問題は基本的な関数のみを使って、リスト項目を逆順にするアルゴリズムを考えてみます。

問題
4つの関数car, cdr, cons, nullpのみを使って、リストの項目を逆順にする関数reverse_auxとreverse2をつくってください。

例えば、reverse2は['A','B','C','D']を、逆順の['D','C','B','A']に並べ替えます。

reverse2()は1変数、reverse_aux()は2変数のリストを取ります。
最終的には、reverse2が必要なのですが、その前段階としてreverse_auxを作ってください。


reverse_aux(x, y)の性質は以下の通りです。

reverse_auxは、リストx, yを取ります。
例えば、

reverse_aux( [‘A’, ‘B’, ‘C’, ‘D’], [‘E’, ‘F’, ‘G’] )

= [‘D’, ‘C’, ‘B’, ‘A’, ‘E’, ‘F’, ‘G’]

 のように、リストxを逆順にして、リストyはそのままで連結します。 まず、reverse_auxを作ってください。 
●基本関数 使って良い関数はcar, cdr, cons, nullpのみです。
・carは先頭の項目を返す関数です。
例えば、

car([‘A’, ‘B’, ‘C’]) = ‘A’

・cdrは先頭項目を除いたリストを返す関数です。   例えば、

cdr([‘A’, ‘B’, ‘C’]) = [‘B’, ‘C’]

 ・consは一つの項目とリストを引数する関数です。consは項目xをリストyの最初に付け足したリストを返す関数です。
例えば、

cons(‘X’, [‘A’, ‘B’, ‘C’]) = [‘X’, ‘A’, ‘B’, ‘C’]

 ・nullp()は1変数の関数で、true <- nullp([]) となり、それ以外の時(アトムあるいは有限要素数のリストの場合)はfalseを返します。
reverse_auxを定義する前に、予め自分の処理系でcar, cdr, cons, nullpを定義してください。 その時は、どんな組み込み関数を使っても構いませんが、reverse_auxだけは、上記の基本関数のみを使ってください。ただし、ifなどの条件文やreturnなどはOKです。
最後に、reverse_auxを使って、reverse2を作ってください。 名前がreverse2なのは、built-in関数との競合を防ぐためです。問題なければ、reverseでも結構です。 作成したコードは、ファイル名を reverse.txt として、アップロードしてください。

その他注意事項 今回の問題は、純LISP に関する問題です。 LISPで解くと簡単にできますが、他の言語処理系だと基本関数定義の所で手間取るかもしれません。 結構大変かと思いますが、頑張ってください。 言語はPythonを希望しますが、解答の論理構造がわかるものであれば、どの言語処理系でも解答可能です。

解説

今回は純LISPに関する問題です。純LISPとはatom, eq, car, cdr, consとう5つの基本関数でプログラミング言語です。実際には、cond, quote, lambda, defineという関数も必要となりますが、必要最小限のもので、プログラミング言語を作ることができるというのは非常に面白い考えだと思います。まるで、数学の有限の公理で色々な証明を行うのに似ています。

Pythonでの解答例


#!/usr/bin/python

#
# reverse.py
#

def car(x): return x[0]

def cdr(x): return x[1:]

def cons(x, y): return [x] + y

def nullp(x): return len(x) == 0

def reverse_aux(x, y):

print x, y # Show variables
if nullp(x):
return y
else:
return reverse_aux(cdr(x), cons(car(x), y))

def reverse2(x):

return reverse_aux(x, [])

####
print reverse_aux([‘A’,’B’,’C’,’D’], [‘E’,’F’,’G’])


reverse_aux(X, Y) の解説をします。

diagram

X=[‘A’,’B’,’C’,’D’], Y=[‘E’,’F’,’G’] とすると、cdr(X)=[‘B,’C’,’D’]を次のreverse_auxのX’に引き継ぎます。更に、car(X)=’A’とY=[‘E’,’F’,’G’] をcons()で結合したものを次のreverse_auxのY’に引き継ぎます。処理がreverse_auxで再帰的に行われ、X部分の要素が逆順になります。

うまく、再帰関数で定義できたでしょうか。再帰関数を使うと、whileやfor文などを使わずに、繰返し処理が表現できますね。

広告

[問題解説12] 男性と女性の殺人被害者数の関係は?

かなり遅くなってしまいましたが、「男性と女性の殺人被害者数の関係は?」の問題解説をします。

今回の問題は、前回の問題「ヒストグラムと散布図を描いてみよう」の発展問題です。

データとプログラムは下記のGitHubリポジトリーにおいてあります。

問題

世界各国の殺人被害者データを用いて女性被害者数から男性被害者数を予測してみましょう。

UNODC(United Nations Office on Drugs and Crime : 国連薬物犯罪事務所)から公開されている世界176ヶ国の殺人被害者の男女別のデータがあります。女性被害者数から男性被害者数を予測してみましょう。

homicide_log.zipをダウンロードしてください。解凍して、homicide_log.csvを読み込んでください。
男性・女性の殺人被害者数のデータは10を底とする対数化してあります。
元データは下記のページから入手しました。
Global Study on Homicide(殺人に関するグローバル調査)

■課題

1.回帰分析を行ってください。

Rの回帰分析関数 lm() を使用して予測式を求める計算をしてください。

2.予測式の値を答えてください。

男性被害者数をM、女性被害者数をFとすると、以下の予測式が成り立ちます。
M = a * F + b
a, b を小数点3桁まで答えてください。解答方法はプログラムの最終行に以下のように記述してください。
# a = x.xxx
# b = y.yyy
3.散布図を作成し、予測式の直線を表示してください。 X軸は女性被害者、Y軸は男性被害者。2Dの散布図を作成してください。表示範囲はX軸、Y軸ともに[-1,3]とする。 その散布図に重ねて、予測式の直線を青色で表示してください。

■解答方法 R言語のプログラムを作成し、上記1~3の課題に答えてください。プログラムファイル名は predict.txt として、アップロードしてください。 散布図は predict.pdf というファイル名でPDFとして出力するプログラムにしてください。

[問題解説12] 男性と女性の殺人被害者数の関係は? の続きを読む

08解説:SQLでエレガントにベクトル内積計算

CodeIQの設問「SQLでエレガントにベクトル内積計算」の解説を行います。

問題文

問1

下記のような要素4の縦ベクトルが2つあります。

U    V
[1   [1
3    2
5    3
7]   4]

例えば、ベクトルUはリレーショナルデータベースの表として以下のように表現されます。

Uも同様に表現されます。

row_id val_nr
1      1
2      3
3      5
4      7

2つのベクトルUとVの内積はどのようにSQLクエリーで表現できるかを考え、内積U・Vを表すSQLクエリーをselect文で答えてください。

UとVの内積はUとVの表の結合として表せます。ただし、JOIN文は使いません。

内積の計算は以下の図式になります。

U.row_id=V.row_id=1の要素同士をかけて、次のU.row_id=V.row_id=2の要素同士をかけたものを順次足していくと行くという操作になります。

U.row_id
[1 3 5 7] [1  V.row_id
2
3
4]
= 1×1 + 3×2 + 5×3 + 7×4

SQLでの表の結合は表内のすべての要素の組み合わせを試して、結果を出力するので、何らかの条件統制が必要となります。

要素mの表と要素nの表の結合を行うとm×n個の要素が結果として出てしまいます。

答えのSQLは以下のような形式になります。

select sum( ... )
from U, V
where ... = ... ;

計算結果は50となります。

答えのSQLを書き加えたvector.txtを送ってください。

問2 ステップ問題

以下のような行列Wがあります。

W =
1  2  3  4]
[5  6  7  8]
[9 10 11 12

この行列は表で以下のように表現できます。

row_id col_id val_nr
1      1      1
1      2      2
1      3      3
1      4      4
2      1      5
2      2      6
2      3      7
2      4      8
3      1      9
3      2      10
3      3      11
3      4      12

この行列Wと前問のVの積を計算してください。その計算を実現するSQLを考えてください。

W               V
1  2  3  4]  [1
[5  6  7  8]   2
[9 10 11 12  3
4]

答えは各row_id毎の結果を求めてください。

計算結果は以下のような表になります。

row_id sum
1      30
2      70
3      110

Wの行列要素は(W.row_id, W.col_id)のように行と列に分かれてしまっているので、

何らかの条件統制が必要となります。

答えのrow_id=1の場合について考えてみましょう。

W.row_id=1という条件で絞れば、以下のようにベクトルの内積となります。

W.col_id=
1 2 3 4
W.row_id=1 [1 2 3 4] [1  V.row_id=1
2           2
3           3
4]          4

row_id=1の計算結果はW.col_idとV.row_idが一致する各W, Vの要素のかけたものの和となっています。計算結果のrow_idとW.row_idは同じものです。

各row_idについて計算結果が欲しいので、W.row_idでグルーピングすれば、各row_idについて計算することができます。

解答のSQL文は以下の形式になります。

select W.row_id, sum( ... )
from W, V
where ... = ...
group by ... ;

解答方法

計算結果の数値は必要ありません。データは確認用に使ってください。

添付ファイルはこちらからダウンロードしてください。

vector.txtはpostgreSQLのスクリプトになっていますので、下記のように実行してください。

$ psql yourdb < vector.txt

前半部分は表作成とデータのロードとなっています。

MySQLやOracle等他のデータベースをお使いの場合は適宜修正して、データを読み込んでください。

発展問題

この問題ができた方は、次のレベルの問題がありますので、挑戦してみてください。

「SQLで行列積の計算???」

https://codeiq.jp/ace/kawagashira_nobuyuki/q379

解説

問1

答えは以下の通り。

select sum(U.val_nr * V.val_nr)
from U, V
where U.row_id = V.row_id;

Uの各要素をU(i)(iはrow_id)、Vの各要素をV(i)(iはrow_id)とすると、UとVのベクトル積は以下の式になる。要素数はnとする。

U・V = U(1) V(1) + U(2) V(2) + U(3) V(3) + … + U(n) V(n)

つまり、Uの各要素とVの各要素の和の形になっているので、求めるものはsum(U.val_nr * V.val_nr)となる。

ここで、ベクトル積の各項の添字iはrow_idで、UとVのrow_idが常に同じだから、U.row_id = V.row_idという制約条件をつける必要があります。

もし、ここで制約条件を付けないと、UとVの全要素の組み合わせが集計されてしまい、以下のような計算結果となってしまいます。

U(1) V(1) + U(1) V(2) + U(1) V(3) + … + U(1) V(n) +

U(2) V(1) + U(2) V(2) + U(2) V(3) + … + U(2) V(n) +

U(3) V(1) + U(3) V(2) + U(3) V(3) + … + U(3) V(n) +

U(n) V(1) + U(n) V(2) + U(n) V(3) + … + U(n) V(n)

問2 ステップ問題

答えは以下の通り。

select W.row_id, sum(W.val_nr * V.val_nr)
from W, V
where W.col_id = V.row_id
group by W.row_id;

計算結果の表をZとすると、計算結果の要素はZ(1), Z(2), Z(3),…,Z(m)となります。

mは計算結果の要素数で、W.row_idの列数です。

問題文にも書きましたが、計算結果Zの要素 row_id=k は、W(row_id=k)とVのベクトル積になるので、Z(row_id=k)についてSQL文を作成します。

Z(row_id=k) = W(k,1) V(1) + W(k,2) V(2) + W(k,3) V(3) + … + W(k,n) V(n)

計算の値はベクトル積なので、問1と同様に、sum(W.val_nr * V.val_n)となります。計算結果の要素番号、つまりrow_idを表示する必要があるので、W.row_idを要素番号としてselectの項目に付け足します。

Z(row_id=k)の和の各項はWのcol_idとVのrow_idが同じとなっているので、W.col_id = V.row_idという制約条件を付け加えます。

更に、row_id毎に掲載結果を集計する必要があるので、group by W.row_idというグループ句を付け加えます。

答えのSQLはシンプルですが、論理は結構複雑ですね。正しいSQL文が出来ましたでしょうか。

この問題ができた方は、行列積の計算にも挑戦してみてください。

SQLで行列積の計算???

06「アッカーマンの呪い」の使用言語ランキング

CodeIQの出題「アッカーマンの呪い」の挑戦者の使用言語ランキングを発表します。

f:id:infoarchitect:20130903104143p:image:w640

Ruby(18)がトップです。

意外なのが、Haskell(13)がJavaと共に3位でした。

再帰関数の問題はHaskellが得意なのでしょうか。

意外に伸び悩んだのがPython(6)とPerl(2)。

Google検索で答えを探したという挑戦者もいましたが、これはルール違反ですね。

09再帰の海に棲むドラゴンを描いてみよう【問題と解説】

CodeIQの再帰の海に棲むドラゴンを描いてみように挑戦ありがとうございます。

今回は再帰関数に潜む美しい数学的図形を堪能してもらいたいと思って、出題しました。

問題文

再帰の海に棲むドラゴンを描いてみよう

今回の問題は再帰関数を使ってC曲線とドラゴン曲線という再帰曲線を描く問題です。

準備問題 (解答を提出する必要はありません)

この問題はタートルグラフィックスという描画方法を使って作図をします。

タートルグラフィックスとは、描画の際に描画ポイントをダイレクトに示すのではなく、

ペンの場所 (x0, y0) から右に10ピクセル、90度回転、左に10ピクセル進む等のコマンドで描画する方法です。

描画のためのクラスTurtleを定義してください。

Turtleクラスには現在の描画座標 (x0, y0) をプロパティとして持っています。

Turtleクラスには下記のメソッド(関数)を定義してください。

1)new(width, height)

  描画するキャンバスのサイズを指定して、Turtleオブジェクトを生成する。

  ここでは、width=1200, height=800としてください。

2)set_initial_point(x, y)

  描画開始の座標を指定します。

3)plot_line(length, theta)

  角度 theta でlengthピクセル描画します。

  角度 theta の単位はラジアンです。つまり、90度はπ/2。

4)save(o_file)

  ファイル名 o_file にpngまたはjpeg形式でイメージを出力する。

f:id:infoarchitect:20131210135929p:image:w360:right

Turtleと同じ機能を示す関数やライブラリがある場合はTurtleを作成する必要はありません。

C曲線 (解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません)

再帰関数を利用して、C曲線を描いてみましょう。

Turtleに対して、メソッドccurve(length, theta) を再帰的に定義して曲線を描きましょう。

与えられた線の上側にπ/2ラジアン(45度)回転した線分を2つ描きます。これを何度も繰り返し行います。lengthの値が4px以下になった場合に描画するようにしてください。

描画の開始座標はset_initial_point(800, 300)。

ccurve(400, 0) で描画を開始します。

f:id:infoarchitect:20131210140636p:image:w360:right

ドラゴン曲線(解答は図のみをPDF形式にして送ってください。プログラムは送る必要はありません)

C曲線を描くことができたら、次はいよいよドラゴン曲線に挑戦してみます。

メソッドdragon(length, theta, flip)を再帰的に定義してドラゴン曲線を描いてみましょう。

C曲線の場合は、新しい線は元の線の同じ側に作っていましたが、ドラゴン曲線は新しい線を作る側が交互に変わっていきます。ドラゴン曲線のステップ2では、最初の線(左)は上側に、次の線(右)は下側に作られています。同じ手順が繰り替えされ、曲線が作られていきます。

lengthの値が5px以下になった時に描画を行います。

f:id:infoarchitect:20131210140634p:image:w360:right

ヒント

変数flipは+1, -1の値を取り、線を上側に描くか、下側に書くかの情報を表しています。ステップ1以降、flipの値は以下のように+1, -1が交替で現れます。

+1,-1,+1,-1,…,+1,-1,+1,-1

描画は下記の値で試してください。

set_initial_point(300, 300)

dragon(600, 0, +1)

ここでは数学の座標系を使って説明しましたが、計算機の座標系ではy軸が反転していますので、注意してください。

描画下限値lengthの値を変えてみて、綺麗に描画される値を探してみてください。

【解説】再帰の海に住むドラゴンを描いてみよう 

今回は再帰関数を用いてC曲線とドラゴン曲線を描く問題です。

準備問題は言語やOS等によって異なりますので、個々に対応してください。

タートルグラフィックスは直前の描画終了点を記憶し、描画の長さlengthと描画の方向角度thetaを入力変数として描画を行うシステムです。

C曲線

アルゴリズムが正しければ、以下のような綺麗な図形が現れます。

まるで、宮殿のようですね。

ここでは開口部が上を向いていますが、右に立てて描画することも可能です。形がCの形に似ているので、C曲線と名付けられました。

f:id:infoarchitect:20131210141257p:image:w640

PythonによるC曲線とドラゴン曲線のプログラム例

#!/usr/bin/python
#
#                                dragon.py
#
from PIL import Image, ImageDraw
from math import cos, sin, pi, sqrt
class Turtle:
def __init__(self, width=1200, height=800):
mode = "RGB"        # Black and White
bg = "#ffffff"
self.window = Image.new(mode, (width,height), bg)
self.dr = ImageDraw.Draw(self.window)
def set_initial_point(self, x, y):
self.x0, self.y0 = x, y
def plot_line(self, length, theta):
x1 = self.x0 + length*cos(theta)
y1 = self.y0 + length*sin(theta) ###        #self.dr.line*1
### here is a bug for Hatena Diary display        self.dr.line*2
self.x0, self.y0 = x1, y1
def save(self, o_file, form="PNG"):
self.window.show()
self.window.save(o_file, form)
def ccurve(self, length, theta):
if length <= 4:
self.plot_line(length, theta)
else:
self.ccurve(length/sqrt(2), theta + pi/4)
self.ccurve(length/sqrt(2), theta - pi/4)
def dragon(self, length, theta, flip):
if length <= 5:
self.plot_line(length, theta)
else:
self.dragon(length/sqrt(2), theta + flip*pi/4, 1)
self.dragon(length/sqrt(2), theta - flip*pi/4, -1)
if __name__ == '__main__':
d = Turtle(1200, 800)
d.set_initial_point(400, 300)    # C-CURVE
d.ccurve(400, 0)
d.save("ccurve.png")
d = Turtle(1200, 800)
d.set_initial_point(300, 300)    # DRAGON CURVE
d.dragon(600, 0, +1)
d.save("dragon.png")

C曲線の解説

C曲線を描くには元の親関数から次々に子供関数を再帰的に定義していく必要があります。

例えば、最初のステップ0では長さlength=1, 角度theta=0 (0度)とすると、次のステップ1では2つの子供関数に引き継がれます。

最初の子供関数では次のようになります。

length = length ÷ √2 = 1/√2

theta = theta + π/4 = π/4 = 45度

もうひとつの子供関数では次のようになります。

length = length ÷ √2 = 1/√2

theta = theta – π/4 = -π/4 = -45度

この操作が繰り返され、長さlengthはどんどん短くなっていきます。

length = 1, 1/√2, 1/(√2)^2, 1/(√2)^3,1/(√2)^4,…

繰り返していくと、最後に綺麗なC曲線ができます。

停止条件がないと無限に計算して止まらなくなるので、lengthがある値以下になったら終了するように設定しておきます。

ドラゴン曲線

アルゴリズムが正しければ、以下のような得体の知れない生き物のような図になります。

解答者の中にはグラデーションをつけて、より神秘的なドラゴンを描いてくれた人もいました。

f:id:infoarchitect:20131210141442p:image:w640

ドラゴン(竜)に見えますか。ドラゴンと言うよりリーフィーシードラゴンですね。

f:id:infoarchitect:20131210141920j:image:w360

(ウィキペディアより転載)

ドラゴン曲線の解説

ドラゴン曲線の手順は少し面倒です。C曲線と似ていますが、規則的に線の上側(正の角度)と下側(負の角度)に入れ替わるように描画していきます。

親関数は2つの子供関数に引き継がれます。ここで、最初の子供関数を長男関数、二番目の子供関数を次男関数と名づけます。

flipの値を次のように決めます。

上側ならば、flip = +1

下側ならば、flip = -1

長男関数も次男関数も親関数から上側に描くか下側に描くかの情報を引き継ぎますが、必ず長男関数は上側を、次男関数は下側としてflip値を引き継ぎます。

親関数は自分が受け取ったflip値に基づいて、長男及び次男関数を上側ならば、/\の形に、下側ならば\/の形で描画するように指示します。

つまり、

上側(flip = +1) →子供関数それぞれのthetaの増減値を+π/4, -π/4

下側(flip = -1)→子供関数それぞれのthetaの増減値を-π/4, +π/4

各パラメーターをいじってみて、綺麗に描画できる値を探してみてください。

*1:self.x0, self.y0, x1, y1), (0,0,255

*2:self.x0, self.y0, x1, y1), (0,0,255

設問1:トークンの出現頻度を集計してみよう!

CodeIQで作成した設問1

Pythonの自然言語処理パッケージNLTKをインストールすること。以下のURLを参照して下さい。

http://www.nltk.org/

NLTKにはフリーの電子書籍を有する「グーテンベルク電子出版アーカイブ」プロジェクト

のデータが含まれています。nltkによるgutenbergのデータのダウンロードが必要です。

http://www.gutenberg.org/

gutenbergに収録されているジェーン・オースティンの「分別と多感」のテキストausten-sense.txtを読み込んで、テキスト内のトークン(単語)の出現頻度の一覧を作成してください。

トークンには、カンマ「,」、ピリオド「.」などの記号が含まれているため、アルファベット文字でのみ構成されるトークンだけを出力対象とします。アルファベットは全て小文字に置き換えて、NLTKのFreqDist関数を使って、トークンの頻度を集計してください。

出力ファイルはカンマ区切りのCSV形式で以下の通り。

頻度順(降順)で出力すること。

1カラム目 トークン

2カラム目 頻度

3カラム目 全体に占めるパーセンテージ(出力形式は%f)

to,4116,3.40918

the,4105,3.40006

of,3572,2.95859

(以下省略)

参考文献

・Steven Bird 「入門 自然言語処理」オライリー・ジャパン

 http://www.amazon.co.jp/gp/product/4873114705

・上記の書籍の英語版はオンラインで読めます。

 Natural Language Processing with Python — Analyzing Text with the Natural Language Toolkit

 Steven Bird, Ewan Klein, and Edward Loper

 O’Reilly Media, 2009.

 http://nltk.org/book/

 Kindle版

 http://www.amazon.co.jp/gp/product/B0043D2E22

解答例1

[プログラム]

問題のプログラムのポイントは以下の3点です。

1. NLTKのインストールとデータのダウンロード

2. トークンの条件による絞り込み

3. DistFreqオブジェクトの使い方

NLTKからausten-sense.txtをダウンロードできたでしょうか。

トークンのリストを取得できたら、以下の様にアルファベットのみを含むトークンに

絞り、小文字化します。

text = [w.lower() for w in text0 if w.isalpha()]

Pythonでは、集合の数学記号 {x|x in A}

等のように1行でデータの抜き出しと変換を行う事できます。私も何年もPythonをやってきましたが、こんなにエレガントに書けるなんて長い間知りませんでした。

この書記法に慣れていきましょう。

トークンリストからFreqDistオブジェクトを生成し、ループを回して頻度を出力すれば終わりです。

問題では頻度順ソートについては書きませんでしたが、FreqDistオブジェクトの keys() メソッドは頻度の降順でキーのリストを出してくれるので、わざわざソートする必要はあ

りません。便利ですね。

プログラムの解答例は以下の通りです。

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
#                           gutenberg.py
#
import nltk
i_file, o_file = 'austen-sense.txt', 'austen-sense.out'
### データのダウンロード ###
text0 = nltk.corpus.gutenberg.words(i_file)
### アルファベットのみを含むトークンを小文字化する ###
text = [w.lower() for w in text0 if w.isalpha()]
### FreqDistオブジェクト ###
fdist1 = nltk.FreqDist(text)
o_handle = open(o_file, 'w')
words = len(text)
for k in fdist1.keys():
w = '%s,%d,%f\n' % (k, fdist1[k], 100.0*float(fdist1[k])/words)
o_handle.write(w)

[出力結果で気づいた点]

出力結果は以下の通りです。

to,4116,3.40918
the,4105,3.40006
of,3572,2.95859
and,3491,2.89150
her,2551,2.11293
a,2092,1.73275
i,2004,1.65986
in,1979,1.63915
was,1861,1.54142
it,1757,1.45528
she,1613,1.33601
that,1385,1.14716
be,1305,1.08090
for,1262,1.04528
not,1248,1.03369
as,1221,1.01132
you,1191,0.98647
he,1108,0.91773
his,1021,0.84567
had,998,0.82662
with,992,0.82165
but,886,0.73385
at,839,0.69492
have,819,0.67836
is,760,0.62949
by,750,0.62121
s,701,0.58062
on,696,0.57648
elinor,685,0.56737
all,656,0.54335
so,644,0.53341
him,642,0.53175
my,628,0.52016
which,593,0.49117
could,578,0.47874
no,568,0.47046
marianne,566,0.46880
from,541,0.44810
mrs,530,0.43899
they,521,0.43153

目で見てみると、ほとんど英語ではto, the, and等の高頻度のトークンは意味を担う語ではなく、文法的な語が多い事に気づきます。。ElinorとMarianneはこの小説にでてくる登場人物の名前です。呼びかけや説明文で、人名がでてくるは当然かもしれません。

人名以外に、この小説の特徴を表すトークンを見つけるのにはもう少し解析が必要なようですね。

トップ50の累積頻度をfdist1.plot(50, cumulative=True)で表示してみると、以下の様に

なります。

f:id:infoarchitect:20130201114813p:image:w360

テキストの全語数が120733なので60000/120733=50.0%となり、たった50の語が半数を占めている事になります。

10「ローマ数字変換器を作ってみよう」の問題と解説

今回はローマ数字を(通常の)アラビア数字に変換するプログラムです。

99名もの方が挑戦してくれました。本当にありがとうございます。

問題文

ローマ数字変換器を作ってみよう!

ローマ数字をアラビア(通常の)数字に変換するプログラムをPythonで作ってみましょう。

■ローマ数字について

ローマ数字はラテン文字の一部を使って、I, II, III, IV, X, XVなどのように数を表す方法です。I, V, X, L, C, D, Mがそれぞれ1, 5, 10, 50, 100, 500, 1000を表します。

通常は大きい数字から左から順に加算していきます。しかし例外的な減算則があり、4や9などはそれより小さい数の文字を左においてIVやIXと書きます。つまり、

IV = – I + V 4 = – 1 + 5

IX = – I + X 9 = – 1 + 10

のように表します。XIVは14となります。

XIV = X + (= I + V) 14 = 10 + (- 1 + 5)

詳しくは下記を参考。

http://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%83%9E%E6%95%B0%E5%AD%97

■プログラムについて

あまり複雑になりすぎない簡単なPythonプログラムにしてください。

使われるローマ文字はI, V, X, L, C, D, Mでこれらの組み合わせとなります。

4, 9, 40, 90 ,400, 900等の減算則に注意してローマ数字からアラビア(通常の)数字へのプログラムを作成してください。

実行関数はmain()として、main(‘XIV’)の結果は以下のようにprintで表示されるようにしてください。

XIV = 14

下記の結果を出力するプログラムを送ってください。

main(‘XLIX’)

main(‘MDCCCLXXXVIII’)

main(‘MCMXLV’)

main(‘MMMCMXCIX’)

構文解析ツールついては適切なフィードバックはできませんので、それを使わずに解答してください。私の回答不要の場合は使ってもOKです(評点は付けます)。

■解答方法

作成したPythonプログラムをテキストファイル(roman.txt)に変換しアップロードしてください。

ローマ数字は簡単な規則でできていると思っていましたが、実際に解答者のやり方を見ると、いろいろなやり方(まとめ方)があるので、びっくりしました。

半分ぐらいがアルファベット文字列を他の文字列に置き換えてしまうという方法でした。まず例外(減算)処理のIV(4)やIX(9)をIIIIやVIIII等に変換し、その後、通常の(加算)処理として他の文字をI(1)やX(10)に置き換えるやり方です。

IV → IIII

IX → VIIII 等

私が考えたのは、文字を逐一変換していく方法です。この方法で重要なのは文字の評価を左からするのではなく、右から評価していくという事です。

通常の評価では隣り合った文字は、後の文字 ≧ 前の文字 となります。例えば、VIではV(5) > I(1) となるのでVの評価値は+5となります。

…XVII… ← 評価方向

一方、例外となる減算処理では、後の文字 < 前の文字 となります。例えば、CXでは X(10) < C(100) となるので、Xの評価値は-10はとなります。

…MXCXX… ← 評価の方向

このやり方では、IIX(8)やXXC(80)等のイレギュラーな文字列は扱えませんが、同じ文字(例えばIII)をひとまとまりとしてグルーピングすれば、そのようなイレギュラーな文字列も扱えます。

解答例

#!/usr/bin/python
#
#                               roman2.py
#
class Parser:
def __init__(self):
self.value = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1, '$':0}
def compute(self, w):
num = 0
prev = '$'
for x in w[::-1]:
if self.value[x] >= self.value[prev]:
factor = +1     # ADDITION
else:
factor = -1     # SUBTRACTION
#print x, '%+d' % (factor * self.value[x])
num += factor * self.value[x]
prev = x            # STORE THE PREVIOUS CHARACTER
return num
def main(s):
p = Parser()
print s, '=', p.compute(s)
#####
main('XLIX')
main('MDCCCLXXXVIII')
main('MCMXLV')
main('MMMCMXCIX')

どうでしょうか。皆さんはどんなローマ数字変換器ができたでしょうか。

CodeIQで問題作成してますので、他の問題も挑戦してみてください。

https://codeiq.jp/ace/kawagashira_nobuyuki/