Language detail: OCaml - 's unsolved challenges
Duff's deviceをinline bytecode assemblyを使って実装してください。C言語ではよくあるinline asmのほかの言語バージョンといったところです。copyのsrcとdstは呼び出し側から渡すようにしてください。（要はbytecode側で閉じていてはならない)
Duff's deviceとは、 http://ja.wikipedia.org/wiki/Duff%27s_device に説明がありますが、ループ展開したコピーのコードです。もちろんbytecodeである時点で速度の話をするのはナンセンスです。
bytecodeで速くするとかいう話よりも、ある言語で書かれたcodeの中にその言語で使用されているbytecodeが埋め込めるかどうか、どのようにできるのかが、このお題の意図です。面白い使い道があるならsiteしていただけると幸いです。
また、1言語につき1種のbytecodeとは限りません。たとえば、PythonならCPythonのbytecode, JythonのJavaVMのbytecode, IronPythonのCIL/CLRなどがあります。 もちろん特定アーキテクチャのasmを呼んでもよいです。x86を書くことができるpyasmなんてものもあるらしいです。 http://members.verizon.net/olsongt/usersGuide.pdf
LL Golf Hole 9のリリースをアナウンスしているエントリにトラックバックを打ってください(トラックバックURL)。マシンガンのようには打たないでください。ただし、このエントリにはスパムフィルタが搭載されているため、寄せることはできてもカップインできないかもしれません。その場合はtakano32が用意させていただきました打ちっ放し場にてガンガン試し打ちください(トラックバックURL)。
余力のあるものは感想を公式ブログの感想エントリにトラックバックくしてください。 余力がなくても感想をトラックバックしてくれるとスタッフがよろこびます。
see: トラックバック技術仕様書
1 2 3 4 5 6 7 8 9 10 11 12 13 | #!/usr/bin/env ruby
require 'net/http'
require 'uri'
uri = URI.parse('http://ll.jus.or.jp/2008/blog/archives/38/trackback')
Net::HTTP.start(uri.host) do |http|
ping = "title=LL+Futureに行ってきた！&" +
"excerpt=参加者としてもLL+Futureおもしろかったよ！¥n" +
"でも、司会ぐだぐだですみません。次から頑張ります！&" +
"url=http://ja.doukaku.org/207/&" +
"blog_name=LL+Golf+Hole+9"
response, = http.post(uri.path, ping)
puts response.body
end
|
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:
1 = 2^0 * 3^0 * 5^0 2 = 2^1 * 3^0 * 5^0 3 = 2^0 * 3^1 * 5^0 4 = 2^2 * 3^0 * 5^0 5 = 2^0 * 3^0 * 5^1 6 = 2^1 * 3^1 * 5^0 8 = 2^3 * 3^0 * 5^0 9 = 2^0 * 3^2 * 5^0 10 = 2^1 * 3^0 * 5^1 12 = 2^2 * 3^1 * 5^0
※解答では i, j, k の各値を示す必要はありません。
GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。
与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: open-uri - Rubyリファレンスマニュアル
1 2 3 4 5 6 7 8 9 10 | #!/usr/bin/env ruby
require 'open-uri'
lines = open('http://www.gnu.org/licenses/gpl.txt').readlines
dic = {}
lines.each_with_index do |line, index|
line.scan(/\w+/).each do |word|
dic[word] = dic[word] ? dic[word] << index + 1 : [index + 1]
end
end
p dic
|
今日から2013年12月31日までの、13日の金曜日とその総数を表示してください。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: DateTime - Rubyリファレンスマニュアル
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #!/usr/bin/env ruby
require 'date'
from = DateTime.now
to = DateTime.parse("2013-12-31")
friday = (from..to).inject(0) do |friday, date|
if date.mday == 13 and date.wday == 5 then
puts date.strftime('%Y-%m-%d')
friday + 1
else
friday
end
end
puts friday
|
'tail'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
２次元ランダムウォークをつくってみてください。
＊＊＊＊＊＊
元は3本建てにしようかと思ったけど、上の一本に絞りました。おまけとして、3本とも下に補足しておきます。作れるようでしたら作ってみてください。
1.一次元のランダムウォークを作ってください。
1.1 データファイルに残してください。 フォーマット：時間 位置
おまけ）
可視化が簡単な処理系・プログラミング言語でしたら実際に可視化してみてください。フォーマットしたファイルをスプレッドシートやplotutilitiesなどの可視化ソフトを使って、実際に動きをかくにんしてみましょう。:-)
2.同じように2次元のランダムウォークを作ってください。
2.1 1.1と同じようにしてください。
フォーマット：時間 x位置 y位置
3.凝りたければ、アニメーションにするもよし、3次元の動きをとるもよし、自分の想像力がいかせるところまでやってみてください。
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%82%A6%E3%82%A9%E3%83%BC%E3%82%AF
分からないというヒトへの分かりにくいヒント：
今の位置から次の時間の位置が決まるのですが、決まりかたが、乱数で一歩後退するか一歩先にいくか?ということをやればよいです。
tinyurl.com( http://tinyurl.com/ )のサービスを利用し、 http://ll.jus.or.jp/2008/info/xgihyo というURLを短縮しなさい。tinyurl.comのalias機能は使わないものとする。 なお、参考までに短縮したURLは http://tinyurl.com/5mngx8 となる。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてみよ。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: tinyurl.comでURLを短縮するRubyスクリプト
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #!/usr/bin/env ruby
require 'rubygems'
require 'mechanize'
def tinyurl(url, _alias = nil)
m = WWW::Mechanize.new
res = m.get('http://tinyurl.com/')
form = res.forms[1]
form['url'] = url
form['alias'] = _alias if _alias
res = m.submit(form)
regexp = Regexp.new('.*(http\:\//tinyurl.com/[a-z0-9-]+).*')
match = regexp.match(res.body)
return match[1] if match
end
if __FILE__ == $0 then
puts tinyurl('http://ll.jus.or.jp/2008/info/xgihyo')
end
|
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。 ・最低値・最大値・個数・並び替え対象の4つを引数として受け取る ・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。 ・同値が複数出現することがある。 ・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。 ・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。 ・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。 ・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ) ・昇順降順はどちらでもかまいません 以下サンプル入出力 >>入力 -1 10 10 -1 9 4 8 9 6 3 9 5 2 >>出力 -1 2 3 4 5 6 8 9 9 9
設定ファイルのイメージも載せてください。
ここで設定ファイルとは、
・項目名と値のペアが書いてあるファイル
・フォーマットはその言語で扱いやすいものでよい
・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません（テーブル、環境変数など）。
例）
----
ファイル：ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200
> showPrice()
「りんご」は210円（税込み）
----
ITEM_NAME=みかん
ITEM_COST=100
> showPrice()
「みかん」は105円（税込み）
YYYY年mm月dd日HH時MM分SS.xxx秒なら、「YYYYmmddHHMMSS.xxx」のようにミリ秒まで含んだ文字列を返すプログラムを書いてください。
プログラムコード中の文字の頻度は言語によって相当にばらつきがあると思います。ある言語はピリオドが頻出するとか、別の言語はカッコの頻出頻度が高い、とか。そこで、
- 文字の頻度解析をするプログラムを作成し、
- 適当なプログラムに対して実行し、結果を出力して、そのような頻度になっている理由を教えてください。
(その言語で書かれた「典型的な」プログラムコード、といえるようなものがあると良いのですが・・）
簡単すぎるという方は、複数文字にしてみたり単語の頻度にしてみてください。
参考；Wikipedia 頻度分析
http://ja.wikipedia.org/wiki/%E9%A0%BB%E5%BA%A6%E5%88%86%E6%9E%90
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、viな
ど貧弱なエディタを使っているときに困る
のが変数名の置換です。さすがに以下の例のよ
うなプログラムは例としてしか書きませんが、
置換しようとしている変数名と同じ綴りの他の
ものがプログラム中に出てくることはまれにあ
ります。そこで、与えられたソースコードに現
れる変数だけを指定された名前に置換してくだ
さい。
置換対象となるソースコードと使用言語は同じ
ものを使ってください。与えられるソースコー
ドは、完全なコンパイル単位、もしくはパース
して意味が通る範囲のものどちらであってもか
まいません。後者の場合、一番外側の変数だけ
置換できるようにしてください。
C言語での解答例をつけたかったのですが、と
ても難しかったためまだ作成できていません。
ご容赦ください。
例
$ cat a.c
/* a */
int foo()
{
struct a {int a;} a;
#if FOO
a.a = 1;
#endif
{ int a; }
return 0;
}
$ alpha -DFOO=1 b a < a.c
/* a */
int foo()
{
struct a {int a;} b;
#if FOO
b.a = 1;
#endif
{ int a; }
return 0;
}
予め言語内に用意されている場合は、(1)一般的な使用法と、(2)より進んだ使用方法を提示して下さい。
'ABCDEF'と'abcdef'等すべて対応する文字を書く必要があるものを、(1)基本版、'A-Z'と'a-z'のように"-"で範囲を指定できるものを(2)拡張版、2を更に発展させたものを(3)発展版とします。任意のものを選んで解答して下さい。
実行例. (与えられた文字列が、"typewriter"の場合)
tr 'qwertyuiop' 'QWERTYUIOP' "typewriter"
=> TYPEWRITER
1 2 3 4 5 6 7 8 | ;; 基本版/Arc
(def tr (orig subst str)
(tostring
(each c str
(pr (aif (pos c orig) (subst it) c)))))
(tr "qwertyuiop" "QWERTYUIOP" "typewriter")
;=>"TYPEWRITER"
|
see: Wikipedia 閏年
nを入力としてn年の年間カレンダーを返すプログラムを作ってください
少なくとも日曜日と土曜日が判別出来るようにしてください
出力は標準出力でもファイルでも構いません
デザインは各自のお好みで
出力例1:
(y-calendar 2008)=>
#=Saturday, @=Sunday
2008/1 1 2 3 4 #5 @6 7 ...
2008/2 1 #2 @3 4 5 6 7 ...
...
2008/12 1 2 3 4 5 #6 @7 ...
出力例2:
(y-calendar 2008)=>
M T W T F S S M
2008/ 1 1 2 3 4 5 6 7 ...
2008/ 2 1 2 3 4 ...
...
2008/12 1 2 3 4 5 6 7 8 ...
出力例3:
(y-calendar 2008)は2008.htmlを出力する
2008.htmlの中身
----
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>2008 calendar</title>
<style type="text/css">
* {font-family: monospace;}
span {margin: 0px 3px;}
span.sunday {color:red;font-weight:bold;}
span.saturday {color:blue;font-weight:bold;}
dd ul li{display:inline;}
</style>
</head>
<body>
<h1>2008 calendar</h1>
<dl>
<dt>2008/1</dt>
<dd><ul>
<li><span class="weekday">1</span></li>
<li><span class="weekday">2</span></li>
<li><span class="weekday">3</span></li>
<li><span class="weekday">4</span></li>
<li><span class="saturday">5</span></li>
<li><span class="sunday">6</span></li>
...
</ul></dd>
...
</dl>
</body>
</html>
----
スレッドプールに複数のワーカスレッドが待機しており、メインスレッドはいつでもワーカスレッドに仕事を渡せるような状態になっているとします。
さて、メインスレッドからスレッドプールにいくつか仕事を与え、メインスレッドは与えた仕事すべてが終了するまで待機し、次の処理に行ってはいけない、というようなコードを書いてください。 ＃現実に書く機会が多そうなコードですね…。
ここでの仕事の内容は、適当に5秒から15秒の間スレッドをスリープする、というもので結構です。 また、ワーカスレッドのスレッドプール自体の使用を終了するか、または残して再利用するかは問いません。できればコメントにスレッドプールを残したかどうかを書いてください。
HTTPでGET その２ 前回のお題 http://ja.doukaku.org/18/ HTTPで指定されたURLをGETするコードを書いてください。 URLは「http://ja.doukaku.org/feeds/comments/」とします。 ただし ・Proxyサーバを経由してGETしてください。 ・タイムアウトを1秒に設定してください。 (デフォルトが1秒でも、1秒に変更してください) ・タイムアウトを十分に小さくした場合、GETが失敗することを確認してください。 もしOSに依存する場合はそのOS名のタグを、 依存しない場合は「OS非依存」というタグをつけてください。 わからなければつけなくても構いません。
see: HTTPでGET
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
- 除算および剰余の使用禁止
- 加算や乗算から除算・剰余を単純に定義することも禁止とする
- ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
- 多倍長演算をサポートすること（各言語のライブラリ状況を見たいので）
- 引数は2つの正整数と仮定して構わない
- F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください
スラッシュで区切られた文字列の配列(以下パスリスト)がある。 このパスリストにたいして擬似的なlsを行いたい。 lsはパスリストと表示対象ディレクトリのパスを入力する。 例としては以下のようになる。 pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"] ls(pathList,"aaa/") >["bbb","ccc","ddd/"] ls(pathList,"aaa/ddd/") >["eee"] なおパスリストが大きくなったとき、速度がなるべく低下しないように実装するのが望ましい。 文字列は任意の文字コードであると仮定してかまわない。
一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください． ただし，除算や剰余算を使わないで書いてみてください． sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく" divid 4 sample => "ゆめよりもはかなき世のなかを" "なげきわびつゝあかしくらすほ" "どに四月十よひにもなりぬれ" "ば木のしたくらがりもてゆく" divid 5 sample => "ゆめよりもはかなき世の" "なかをなげきわびつゝあ" "かしくらすほどに四月十" "よひにもなりぬれば木の" "したくらがりもてゆく" divid 6 sample => "ゆめよりもはかなき" "世のなかをなげきわ" "びつゝあかしくらす" "ほどに四月十よひに" "もなりぬれば木のし" "たくらがりもてゆく"
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
無憂無風 礼 林 千 火 万水千山 知行合一 者 筆 不 勾 言語道断
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。 列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。
サンプル出力
0, 0 1, 0 0, 1 -1, 0 0, -1 1, 1 -1, 1 1, -1 -1, -1 2, 0
最低でも1000件まで列挙できることを確認してください。 また「反時計回り」の条件も満たしている場合は、1000番目の頂点が何かも併せて答えてください。
このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。
n個の整数をソートするプログラムを生成するプログラム gensort を 書いて下さい．条件は以下のとおり
- 生成するプログラム，生成されたプログラムは同じ言語にして下さい．
- 生成したプログラムはファイルに書き込んでください．
- 生成されたプログラムでは最初に n 個の整数を読み込んで， n個の変数を初期化してください．「可能なら」変数名は，アルファベット 一文字で a，b，c ... の順で使ってください．n = 5 なら 変数は a, b, c, d, e です．
- 生成されたプログラムでは，if 文あるいは if 式で2つの変数を比較して いって，変数の順が確定したら，その順で変数の値を出力するようにして 下さい．
- 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)
gensort 3 で生成した Pascal のプログラム例は以下のとおりです．
program sort(input,output);
var
a,b,c : integer;
begin
readln(a,b,c);
if a < b then
if b < c then
writeln(a,b,c)
else if a < c then
writeln(a,c,b)
else
writeln(c,a,b)
else
if a < c then
writeln(b,a,c)
else if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.
n の値を 2 〜 10 くらいまで変化させて以下の処理時間を測定してください．
1. gensort n の処理
2. 生成したプログラムの処理
2-1. コンパイル言語の場合は，コンパイル時間と実行時間
2-2. インタプリタ言語の場合，可能ならロード時間と実行時間を別測定，
分解できないなら実行時間
ごさっしのとおり，出力されたプログラムは n の値で急激に大きくなります．
n が大きいと gensort n で文法的に正しいプログラムは生成できてもコンパ イル
や実行ができないということもありえると思います．処理系ごとの限界がわか
ると面白いのではないかと思います．オリジナルの問題は Pascal のプログラム
コードを生成するプログラムを書けという問題でしたが，生成する側とされる側
の言語を同じにするほうが面白いですよね．
この問題はnobsunさんからの投稿です。ご投稿ありがとうございました。助かります。
Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。
37 199148647.999978 58 24591257752.000000 67 147197952743.999999 163 262537412640768744.000000この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。
ただし、このお題の趣旨は実数区間での探索なので、 立方根関数があっても使ってはいけません。 指数関数と対数関数も禁止します。
Pythonで表現した入出力の例：
>>> cube_root(10.0) 2.1544346900318834 >>> _ ** 3 9.9999999999999947 >>> cube_root(100.0) 4.6415888336127793 >>> _ ** 3 100.00000000000003
サンプル入力
aaa abc-hidden.png>hoge-big.jpeg ---foo-hidden-small.gif|^_^a.bmp --hiddena-hoge.png<=not hidden~~ --small.jpg<=not small(^_^) normal-small-big.hoge
サンプル出力
name:'abc', ext:'png', size: normal hidden: True name:'hoge', ext:'jpeg', size: big hidden: False name:'foo', ext:'gif', size: small hidden: True name:'a', ext:'bmp', size: normal hidden: False name:'hoge', ext:'png', size: normal hidden: False name:'small', ext:'jpg', size: normal hidden: False name:'small', ext:'hoge', size: big hidden: False
探すべき文字列は下の条件を満たします
- アルファベットと1個のピリオド、ハイフンで構成される
- 前後にはアルファベットではない文字がある(abcd.jpgがaaaabcd.jpghogeなどと書かれていることはない)
- ピリオドの後ろは拡張子で、アルファベットだけで構成されている
- ピリオドの直前に-hidden, -small, -bigがある場合には特殊な意味がある。複数個ある場合(a-hidden-big.jpgなど)も同じ
- ファイル名に-hiddenと-smallまたは-hiddenと-bigの両方が含まれる場合は-hiddenの方が先にある
- 特殊な意味の-hidden, -small, -big以外でハイフンが使われることはない
- 特殊な意味の-smallと-bigの両方が付くことはない
出力は以下の条件を満たす必要があります
- ファイル名が出現した順に表示される
- ファイル名に-hiddenが含まれるかどうかを真偽値で表示する
- ファイル名に-smallまたは-bigが含まれる場合はsmallまたはbigと、含まれない場合はnormalと表示する
- -hidden, -small, -bigを取り除いたファイル名部分と、拡張子を表示する
このお題は、正規表現のグループに名前をつけて連想配列として取得できるPythonからの挑戦状です。
詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると
- ページがn枚ある場合、n×nの2次元配列を用意する。
- ページiからページjにリンクがある場合、mat[j][i] = 1 / num_link[i]とする。ただしnum_link[i]はi番目のページから出ているリンクの総数。
- 行列計算ライブラリを使ってできあがった2次元配列の固有値、固有ベクトルを求める。
- 出力された固有ベクトルから合計が1になるようなPageRankを算出する
という流れになります。
Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。
data = {
1: [2, 3, 4, 5, 7],
2: [1],
3: [1, 2],
4: [2, 3, 5],
5: [1, 3, 4, 6],
6: [1, 5],
7: [5],
}
?????
print pagerank
# [0.303514376997, 0.166134185304, 0.140575079872,
# 0.105431309904, 0.178913738019, 0.0447284345048,
# 0.0607028753994]
このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。
アクセスログの各行の先頭にIPアドレスがあります．そのIPアドレスを逆引き結果のFQDNで置き換えてください．
逆引きが出来なかった場合は，IPアドレスのまま残します． IPアドレス以外の部分は，そのまま加工せずに残してください．
----
例）192.168.7.1 が逆引きできない場合
210.166.209.71 - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
↓
mikage.to - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
----
アクセスログは膨大な量があるため，現実的な時間で処理できるよう，以下の条件をつけます．
・メモリに入りきらないような巨大なログも処理できるようにしてください．（ファイル全体をメモリに読み込むのはNG）
・十分な速度で処理できるよう，並列化する等の工夫をしてください．
・DNSサーバに大量のリクエストが行かないよう，結果をキャッシュしてDNSサーバへのアクセスを削減してください． なお，DNSのTTLは無視して結果をキャッシュしてかまいません． （ログの記録された時間の逆引きするタイミングがずれているため，正確な逆引きは元々無理なので）
名前解決はgethostbyaddrを利用しても良いですし，再帰的に名前解決が出来るDNSサーバと直接通信してもかまいません．
ログを順次読み取り処理する部分を，データを共有しつついかに並列化するか，という部分を問うのが目的です．
このお題は沢渡みかげさんの投稿です。ご投稿ありがとうございます。
説明のために2*3のサイズで説明します。
画像1 ■■■ ■■■ 画像2 □□□ □□□ 画像3 ■■■ □□□ 指定された画像 ■■■ ■□□この場合、画像1とは4つのピクセルが同じ値なので類似度は4、 画像2との類似度は2、画像3とは上半分の3つと下半分の白2つが一致するので類似度は5、よって一番類似しているのは画像3となります。
このお題の趣旨は検索処理の実行速度にあるので、 実行してみて実用的な速度で動くことを確認することを強く推奨します。 可能であればマシンのスペックと実行にかかった時間を書いてもらえると参考になっておもしろいと思います。
なおこのお題はC言語からスクリプト言語への挑戦状です。 スクリプト言語に有利な問題が多すぎるので、この手の問題も大募集します。
ここにトランプが一組あります． 司会者がそこから二枚抜いて，その積をAさんに，その和をBさんに教えました． #トランプにジョーカーはなく、1～13までの数字が書かれたカードであると考えて構いません． #たとえば，二枚のトランプの数字が2と5なら，Aさんには10，Bさんには7を教えます． #二つの数は同じかもしれません． 司会者がAさん，Bさんに二つの数字が分かるかと質問しました． Aさん「(この情報だけでは)分かりません」 Bさん「私も分かりません．ただ，Aさんが『分かりません』というのは分かっていました」 それを聞いたAさん「それなら，分かりました」 それを聞いたBさん「それなら，私も分かりました」 元の二つの数はなんだったのでしょうか．この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。 このお題は光成さんの投稿が元になっています。ご投稿ありがとうございます。
ckbx #8053() Rating5/5=1.00
[ reply ]