カテゴリー別アーカイブ: 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] 男性と女性の殺人被害者数の関係は? の続きを読む

【解説】「ヒストグラムと散布図を描いてみよう」

今回の問題はRの初心者向けで、まずデータ読み込み、ヒストグラムと散布図を生成する問題でした。

問題は以下の通りです。

世界193カ国の殺人被害者のデータを読み込んで2種のヒストグラムと2種の散布図をPDFファイルに出力してください。

読み込む入力ファイルはHomicides_by_sex2.csvを使ってください。

こちらからダウンロード(homicide.zip)して解凍。

データはUNODC Homicide statisticsのHomicide by sexのエクセルファイルをコンマ区切りのCSV形式に変換したものです。

入力ファイルの最後には説明文など不要な行がありますので、うまくパラメータを使って読み込んでください。

“Males rate per 100,000″のカラムは10万人当たりの男性殺人被害者数、”Females rate per 100,000″は10万人当たりの女性殺人被害者数です。

出力するファイルはPDF形式でhomicide.pdfとしてください。1ページにつき1つの図で、全部で4つの図を描画してください。

下記の図を描画してください。

男性殺人被害者数のヒストグラム

1A. 男性殺人被害者数のヒストグラム

1B. 男性殺人被害者数の対数ヒストグラム(x軸を対数化してください)

binの数は30個。等間隔になっているbinで描画してください。目盛りはlog値になっていてもOKです。

女性と男性の殺人被害者数の散布図

女性をx軸、男性をy軸にして、各国を点として散布図を描画してください。

2A. 散布図

2B. 散布図(x軸、y軸共に対数表示)

対数は自然対数logでOKです。値には0も含まれており、log化できないものありますが、今回は警告などは無視してプログラムを作成してください。

各図にはメインタイトル、x軸ラベル、y軸ラベルを日本語でつけてください。

■解答方法

解答は作成したRのプログラムをtxtに変換し、アップロードしてください。

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

### homicide.R ###
pdf('homicide.pdf')
par(family="Japan1GothicBBB")
h <- read.csv('Homicides_by_sex2.csv', nrow=193)
str(h)
f <- h$Females.rate.per.100.000
m <- h$Males.rate.per.100.000
### HISTOGRAM ###
hmain <- '男性殺人被害者のヒストグラム'
hxlab <- '10万人当たりの殺人被害者数'
hylab <- '殺人被害者の頻度'
hist(m, main=hmain, xlab=hxlab, ylab=hylab, breaks=30)
hist(log(m), main=hmain, xlab=paste(hxlab, '(対数)', sep=''), ylab=hylab, breaks=30)
### SEXUAL COMPARISION PLOT ###
pmain <- '世界各国の男女別殺人被害者'
flab <- '10万人当たりの女性殺人被害者数'
mlab <- '10万人当たりの男性殺人被害者数'
plot(f, m, main=pmain, xlab=flab, ylab=mlab)
plot(f, m, main=paste(pmain, '(対数表示)', sep=''), log='xy', xlab=flab, ylab=mlab)

ファイルはコンマ区切りなので、読み込みにはread.csv()を使います。1行目はタイトルで、データの行数は193なので、nrow=193でデータ行数を指定します。

日本語を表示させるにはフォントファミリーパラメータの設定が必要です。

par(family=”Japan1GothicBBB”)

1A. 男性殺人被害者数のヒストグラム

f:id:infoarchitect:20140408163457p:image

binの数はhist()関数のbreaksパラメータで指定することができます。

1B. 男性殺人被害者数の対数ヒストグラム

f:id:infoarchitect:20140408163456p:image

値を対数化するにはlog()関数を使えばいいですね。ただし、このやり方だと数値も対数化されているので、分かりにくいですが、今回の問題では数値が対数になっていてもOKです。

1Aのヒストグラムは左側(小さい値)に集まっていますが、1Bの方は対数かすることによって大きな二つの山が見えてきました。

2A. 散布図

f:id:infoarchitect:20140408163455p:image

2B. 散布図(x軸、y軸共に対数表示)

f:id:infoarchitect:20140408163453p:image

散布図の対数化は、hist()とは異なり、plot()関数のlogパラメータでlog=”xy”のように指定します。この場合、x軸とy軸が対数スケールとなります。

2Aでは点が扇形に広がっているように見えますが、2Bでは対角線に並んでいるように見えます。点のばらつきから推測すると、男性・女性殺人被害者数は対数スケールで扱う方がうまく行きそうだということが分かります。

データ解析の最初に行うべきことはデータの概要をつかむことです。ですから、最初にすることは、ヒストグラムや散布図を書いてみることです。データの雰囲気を捉えることが解析への重要なステップの一つなのです。

設問3:UNIXのパイプ機能を使って1行コマンド処理をしてみよう!

CodeIQに投稿した設問3の解答を説明します。

問題

データをゲノムデータベースサイトGenBankからダウンロードし、解凍します。使用するのはnames.dmpのみです。

ftp://ftp.ncbi.nih.gov/pub/taxonomy/taxdump.tar.gz

names.dmpは、生物種のデータです。

タブも含まれていますが、’|’での区切りデータとしてください。

各フィールドの説明は以下の通り。

1. 生物種ID

2. 生物種名

3. ユニークな生物種名

4. 同義語等

UNIXにはパイプ機能がありますので、キーワード検索を行い、ソートして確認するコマンドを1行で書いてください。

1. まず、大文字・小文字の区別なく’virus’という文字列を含む行を取り出します。Virus, VIRUSも含まれます。

2. 第2フィールドの生物種名のアルファベット順(昇順)でソートします。

3. 生物種名には時々、ダブルクウォーテションや大文字・小文字が混在していますが、特殊記号は無視して、大文字・小文字の区別なくソートします。

解答するもの

1. 上記の様に抽出・ソートするための1行コマンド。目で確認する為、最後にless-Sを付けてください。

2. 1の内容の行数を計算する1行コマンド。

完成したUNIXコマンドはテキストファイルに変換し、下のファイルアップロードから提出してください。

解答例

1.

$ grep -i virus names.dmp|sort -k 2 -t "|" -f -d | less -S

セパレータの設定 -t “|” は無くても結果は同じです。

2.

ソートは要らないので、

$ grep -i virus names.dmp | wc -l
111548

※ grep -i virus names.dmp | wc -l の結果の値はデータが定期的に更新されているので、結果が異なります。

設問4:コマンドを定期的に自動実行させよう!

CodeIQに投稿した設問4の解答を説明します。

問題

cron でユーザーのディスク使用量管理

管理しているサーバーの全ユーザーのディスク使用状況を知りたいと思い、毎日定時にディスク使用量をログを取ることにしました。

UNIX のcron 機能 を使って、定期的に各ユーザーのディスク使用量の情報を取得する設定をしてください。

詳細は以下の通りです。

・/home の下にある全ユーザーのディレクトリ内の使用量をdu を使って求めてください。

・毎日23:30に情報を取得してください。

・ファイルは、/var/lib/bak に保存し、名前はdu-YYYYMMDD.log のようにしてください。

 例えば、2013年4月31日ならば、/var/lib/bak/du-20130431.log となります。

 日付の生成にはdateコマンドを使ってください。

・crontab -e で編集し、設定は crontab -e 内の一行のみで実現させてください。

 他のスクリプトファイルを読みに行くようなことはしないでください。

・使用するシェルはbashです。

【解答方法】

crontab -l の表示結果をテキストファイルに貼り付けて、そのテキストファイルをアップロードしてください。

解答

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

1. cronによるコマンド自動実行の理解

2. du, dateのオプションの理解

3. シェルのコマンド展開機能の理解

解答例

30 23 * * * du -s /home/* > /var/lib/bak/du-`date +"\%Y\%m\%d"`.log

dateコマンドの展開部分が難しいです。

bashスクリプト実行では、`date +”%Y%m%d”`でコマンドの展開がうまく行きますが、cronの中ではフォーマットの%\でエスケープしないと正常に動作しないです。

下記のURLも参考にしてください。

http://maruta.be/intfloat_staff/67

/var/libは管理者権限があり、実際のコマンド実行には、/var/lib/bakにユーザーの書き込み権限を与える必要があります。

設問5:PythonでXML解析をしてみよう

CodeIQの設問5について解答します。

問題

日本人の同姓同名データのファイルをXMLパーサのElementTreeを使ってパースしてみよう。

更に、姓と名の漢字の組み合わせを集計してみます。

課題

person_name.xmlファイルを読み込み、PythonのXMLパーサモジュールElementTreeを使って苗字、名前、同姓同名の数を抜き出して、標準出力で表示してください。

同姓同名のファイルを下記からダウンロードしてください。

下記zipファイルを解凍するとperson_name.xmlが入っています。

person_name.zip

※このファイルは「同姓同名辞典」の全国ランキング1位から20000位までのHTMLファイルを修正したものです。

http://www.douseidoumei.net/00/dou01.html

ElementTreeについては以下を参照。

http://d.hatena.ne.jp/hikm/20090206/1233950923

出力するもの

・文字列の両端にある不要な空白は除いてください。

・文字コードはUTF-8にしてください。(難しければ、他の文字コードでも可です)

・ファイル形式はヘッダを一行にして、コンマ区切りで以下のようにしてください。

順位,姓,名,件数

1,田中,実,2620

2,鈴木,茂,2470

課題の提出はプログラムのみです。

完成したら、テキストファイル(.txt)に変換し、ファイルアップロードにて提出してください。

 

解答

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

1. XMLの理解

2. xml.etree.ElementTree

3. 漢字コードの扱い

解答例

#!/usr/bin/python
# -*- coding: utf-8 -*-
#
#                               element.py
#
from xml.etree import ElementTree
def main(i_file, o_file):
o_handle = open(o_file, 'w')
tree = ElementTree.parse(i_file)
elem = tree.getroot()
for tr in list(elem):
td = list(tr)
w = ''
w += '%s,' % td[0].text.encode('utf-8').strip()
w += '%s,' % ','.join(td[1].text.encode('utf-8').strip().split(" "))
w += '%s' % td[2].text.encode('utf-8').strip()
o_handle.write('%s\n' % w)
##############################################################
main('person_name.xml', 'personal_name.txt')

設問6の解説:アッカーマンの呪い

CodeIQに投稿した問題6「アッカーマンの呪い」の解答を解説します。

問題

昔、アッカーマンという人(残念ながらミカサという妙齢の女性ではありません)がいました。

その人の手帳には以下のような式が書かれていました。

A(m, n) =
m = 0 ならば n + 1
n = 0 ならば A(m - 1, 1)
他の場合は A(m - 1, A(m, n - 1))

この関数を計算してみましょう。

A(1,3)の場合は以下のようになります。

A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問1A

A(2,1)を手で計算してみましょう。

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

問1B

気力のある人はA(2,2)を手で計算してみましょう。

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

問2A

再帰関数を使ってプログラムを書いてみましょう。

プログラミング言語は問いません。

A(3,4) の値はいくつになりますか。

答えと使った言語名のみを書いて提出してください。

プログラムの提出は必要ありません。

問2B

A(4,1) をプログラムで計算してみましょう。

ただし、スタックオバーフローのエラーが出る恐れがありますので、

パラメータ値の増加には十分注意してください。

ハングアップする恐れがあるので、他の重要なプログラムが走っているときは実行するの

はやめたほうが良いです。

(もし値が計算できたら、3行目に答を書いてください)

【解答方法】

テキストファイルに以下のように解答を書いてください。

完成しましたら、ファイルアップロードより提出してください。

???   # 1 行目 問2Aの答え
???   # 2 行目 プログラミング言語名
???   # 3 行目 問2Bの答え(計算出来なかったら空欄でも構いません)

【補足】

A(4,1) は何とか計算できるかもしれませんが、

A(4,2) はあまりにも値が大きいので普通の方法では計算できないでしょう。

LISP等を使ったほうがすんなり行くかもしれません。

コンピュータを壊さないように気をつけて頑張ってください。

解説

今回の問題はWilhelm Friedrich Ackermannというドイツの数学者が考案したアッカーマン関数を問題としました。残念ながら、進撃の巨人とは何の関係もありません。(ただし、進撃の巨人の舞台がドイツらしいので関係なくはありませんが…)

手計算の結果は以下の通りです。何度も再帰的に計算しているが視覚的に分かるように省略せずに全過程を書いてみました。僅かな数なのに再帰が深くなっているのが分かるでしょうか。

問2.1

A(2,1))
=A(1,A(2,0))
=A(1,A(1,1))
=A(1,A(0,A(1,0))
=A(1,A(0,A(0,1)))
=A(1,A(0,2))
=A(1,3)
=A(0,A(1,2))
=A(0,A(0,A(1,1)))
=A(0,A(0,A(0,A(1,0))))
=A(0,A(0,A(0,A(0,1))))
=A(0,A(0,A(0,2)))
=A(0,A(0,3))
=A(0,4)
=5

問2.2

A(2,2)
=A(1,A(2,1))
=A(1,A(1,A(2,0)))
=A(1,A(1,A(1,1)))
=A(1,A(1,A(0,A(1,0)))
=A(1,A(1,A(0,A(0,1))))
=A(1,A(1,A(0,2)))
=A(1,A(1,3))
=A(1,A(0,A(1,2)))
=A(1,A(0,A(0,A(1,1))))
=A(1,A(0,A(0,A(0,A(1,0)))))
=A(1,A(0,A(0,A(0,A(0,1)))))
=A(1,A(0,A(0,A(0,2))))
=A(1,A(0,A(0,3)))
=A(1,A(0,4))
=A(1,5)
=A(0,A(1,4))
=A(0,A(0,A(1,3)))
=A(0,A(0,A(0,A(1,2))))
=A(0,A(0,A(0,A(0,A(1,1)))))
=A(0,A(0,A(0,A(0,A(0,A(1,0))))))
=A(0,A(0,A(0,A(0,A(0,A(0,1))))))
=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))
=A(0,A(0,A(0,4)))
=A(0,A(0,5))
=A(0,6)
=7

アッカーマン関数は、自分自身を値として取る再帰関数ですが、簡単な定義にも関わらず、最初の部分でさえ爆発的に大きな値が現れてしまいます。

f:id:infoarchitect:20130625120719p:image:w640

Wikipedia:アッカーマン関数より転載

私が大学の夏期特別講座でこのアッカーマン関数を知りました。当時は、コンピュータは一般的には存在せず、共有の大型コンピュータをかろうじて使うことが出来ましたが、一行書くのに一回リターンキーを押してしまうと二、三分待たなければ、レスポンスが帰ってこないと言う有様でした。年がバレてしまいますがwww。

ですから、自分でこの関数をコンピュータでプログラミングするなんてできませんから、手で計算したのです。ところが、小さな値で計算を始めたにも関わらず、なかなか答えが収束せず、大変な思いをしました。その時、友人が書きすぎて手が痛くなったので、「これはアッカーマンの呪いだ!」と叫んでいました。そこで、これを今回の問題のタイトルにしたというわけです。

Pythonでのプログラミングの例

def ack(m, n):
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
else:
return ack(m - 1, ack(m, n - 1))
###
print ack(3,4)

挑戦者のtakana32さんがいろいろな言語で書いたアッカーマン関数のプログラムを公開してくれたので、参考にしてください。

https://github.com/Rosetta-Ack

問2A

A(3,4)の答えは125。

問2B

A(4,1)の答えは65533となります。

既にA(4,1)でコンピュータがエラーを吐き出し始めるかと思います。私のUbuntuの場合、パラメータをいじったのですが、A(4,1)はスタックオーバーフローで計算できませんでした。

A(4,2)は 2^65536 – 3 になり、19729桁という膨大な数になってしまい、通常のやり方では計算不可能です。しかし、PythonやRubyではintegerに収まらない数も扱えるため、既に計算した値を保持することで、A(4,2)等も計算することができます。

スタックオーバーフローの対処方法についてはいくつかありますので、参考にしてみてください。

スタックオーバーフローの対処方法

とにかく、こんな簡単な式でこんな爆発的に大きな数が作れるなんて不思議ですね。しかも、コンピュータの普及していない時代にこんな関数を考えだすなんて数学者ってすごいなと思います。

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

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