Language detail: D - '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
入力の'('と')'の対応をとってください。
ただし、コード中に'('と')'を含まないでください。
漢字の九九にinspireされました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | import sys
start = sys.argv[1]
end = sys.argv[2]
to_test = sys.argv[3]
print start
print end
print to_test
stack = []
while to_test:
print stack
head = to_test[0]
to_test = to_test[1:]
if head == start:
stack += [head]
if head == end:
if stack:
stack = stack[:-1]
else:
stack = [True]
break
if stack:
print False
else:
print True
|
タブ区切りのデータを読み込んで操作をし書き出す方法を教えてください。 読み込み・書き出しの方法は任意とします。
与えられるデータは:
- レコードの区切りは改行、カラムの区切りはタブです。
- 最初のレコードはヘッダで、カラムの名前が書いてあります。
- それ以降はデータで、第1,4カラムは整数値、第2,3カラムは文字列値です。
この入力データに対して以下の操作をしたものを書き出してください:
- 第1カラムの値でデータを昇順にソートする。
- 第2カラムと第3カラムをヘッダを含めて入れ替える。
- 第4カラムの値にそれぞれ1を加える。
入力の例:
ID Surname Forename Age 1 Sato Hanako 17 0 Suzuki Taro 18 ...
出力の例:
ID Forename Surname Age 0 Taro Suzuki 19 1 Hanako Sato 18 ...
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
|
いわゆる、コマンドライン引数の取得(http://ja.doukaku.org/118/)からの派生です。
やっぱ、自分のコマンドってオプションつけたいですよね(笑
タグに「クックブック」なんてつけてみました
長文なのはご容赦ください^^;;
-----
次の起動インタフェースを持つコマンドを作成してください。
書式：cmdopt -o [-q] -d{0|1|2} 文字列 [文字列 ...]
書式を説明すると
- オプション「o」
必須オプションです。指定されていない場合、異常終了してください。
- オプション「q」
選択オプションです。
省略されていても問題有りません。
- オプション「d」
引数付きオプションです。
「0」「1」「2」のいずかが続いて指定されます。
- 文字列
パラメータです。
1つ以上であればいくつでも指定できます。
指定されていなかった場合、異常終了してください。
オプションの開始が「-」になっていますが
「+」や「/」でもかまいません。
余力があればロングオプションに対応してもよいです。
起動例：(すべて許容されるのが望ましいです)
1. cmdopt -o AAA
2. cmdopt -o AAA BBB CCC
3. cmdopt -oq AAA
4. cmdopt -o -q AAA
5. cmdopt -o -s1 AAA
6. cmdopt -o -s 1 AAA
7. cmdopt -q -s2 -o AAA
出力例：
[オプション情報]
o(output)： ON|OFF
q(quote)： ON|OFF
d(debug)： 0|1|2
[パラメータ情報]
指定数： N
1： 文字列1
2： 文字列2
...
N： 文字列N
TCPのechoクライアントを書いてください。
- サーバのホスト名ないしIPアドレス、およびポートはコマンドライン引数で指定します。
- 標準入力からユーザの入力を受け取り、echoサーバに送信します。
- echoサーバから受信したデータを標準出力に出力します。
Windowsなら、Simple TCP/IP Servicesを起動してやれば、ローカルの確認用echo サーバとして使えます。
my_program localhost 7 < input_file > result_file
のようにしてリダイレクトを行った場合にも、result_fileがinput_fileの内容と一致するようにしてみてください。
'tail'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
設定ファイルのイメージも載せてください。
ここで設定ファイルとは、
・項目名と値のペアが書いてあるファイル
・フォーマットはその言語で扱いやすいものでよい
・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません（テーブル、環境変数など）。
例）
----
ファイル：ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200
> showPrice()
「りんご」は210円（税込み）
----
ITEM_NAME=みかん
ITEM_COST=100
> showPrice()
「みかん」は105円（税込み）
プログラムコード中の文字の頻度は言語によって相当にばらつきがあると思います。ある言語はピリオドが頻出するとか、別の言語はカッコの頻出頻度が高い、とか。そこで、
- 文字の頻度解析をするプログラムを作成し、
- 適当なプログラムに対して実行し、結果を出力して、そのような頻度になっている理由を教えてください。
(その言語で書かれた「典型的な」プログラムコード、といえるようなものがあると良いのですが・・）
簡単すぎるという方は、複数文字にしてみたり単語の頻度にしてみてください。
参考；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;
}
以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。 1. 格子状の迷路であること。 2. 経路の幅は均等であること。 3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。 ループも認めません。 4. 出力の度にランダムな迷路であること。 ランダムシードが同じ時に同じ迷路になってしまうのはよいです。 たとえば、n=4, m=5の迷路の出力は以下のようになります。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ■ ―■■■■■■■■■ こう言うのは、×の部分が3のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■×■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■■■ ■ ４■ ■×××■ ■ ―■ ■×■■■ ■ ５■ ■×××■ ■ ―■■■■■■■■■ このようなループも2のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■ ■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ―■■■■■■■■■ できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。 難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を どうやって作るのかを考えると答えが見えてくると思います。 ソースコードはJavaで150行程度になりました。
スレッドプールに複数のワーカスレッドが待機しており、メインスレッドはいつでもワーカスレッドに仕事を渡せるような状態になっているとします。
さて、メインスレッドからスレッドプールにいくつか仕事を与え、メインスレッドは与えた仕事すべてが終了するまで待機し、次の処理に行ってはいけない、というようなコードを書いてください。 ＃現実に書く機会が多そうなコードですね…。
ここでの仕事の内容は、適当に5秒から15秒の間スレッドをスリープする、というもので結構です。 また、ワーカスレッドのスレッドプール自体の使用を終了するか、または残して再利用するかは問いません。できればコメントにスレッドプールを残したかどうかを書いてください。
ここでいう法演算とは，与えられた数(ここでは「法」と言います)で剰余をとりながら行う計算のことです．たとえば，法が10である場合，以下のように計算します．
- 足し算
- 1 + 2 = 3
- 7 + 3 = 0 (10を10で割った余りは0)
- 11 + 12 = 1 + 2 = 3
- 引き算
- 3 - 2 = 1
- 2 - 3 = 9
- 掛け算
- 2 * 3 = 6
- 11 * 12 = 1 * 2 = 2
- 18 * 39 = 8 * 9 = 2
式と法を与えたときに，このような法演算を行い，計算結果を表示するプログラムを作成してください．
注意点
- プログラムの入力には，式と法が与えられます．
- 式に現れる数は，整数のみと仮定してかまいません．しかし，法より大きな数が与えられるかもしれませんし，負の数が与えられるかもしれません．
- 法は2以上の正整数のみが与えられます．
- 式と法は，プログラムにとって都合のよい形式で与えられると仮定してかまいません．ソースコード中に埋め込んでしまってもかまいません．
- 足し算，引き算，掛け算に対応してください．
- 法10の世界においては，1 - 2 と 1 + 8 は同じ意味です．引き算の計算においては，この性質を使い，足し算に変換してから計算してもかまいません．
プログラムの出力として，計算結果を表示して下さい．
- 与えられた式の中に，範囲外の数(負の数や，法の数以上の数)が現れた時には，必ず一度，式全体を正規化し，その結果を表示してから計算を行って下さい．
- ここでいう「正規化」とは，式の中のすべての項をいったん法で剰余をとり，0以上，法-1以下の範囲になるようにする，ということです
- 正規化をする際に，引き算を足し算へ変換する処理を一緒に行ってもかまいません．
- 計算過程で範囲外の数が現れたときには，正規化を行うことが望ましいですが，必ずしも行う必要はありません．(最終的な計算結果が正しければよしとします)
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。
ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。
なお、数え上げるときの注意として、
・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの
・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
- 除算および剰余の使用禁止
- 加算や乗算から除算・剰余を単純に定義することも禁止とする
- ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
- 多倍長演算をサポートすること（各言語のライブラリ状況を見たいので）
- 引数は2つの正整数と仮定して構わない
- F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください
古典的なパズルである小町算を解くプログラムを作成してください。
小町算とは：
1□2□3□4□5□6□7□8□9＝100
四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。
解答例：
1－2－3＋4×56÷7＋8×9＝100
1＋234×5÷6－7－89＝100
参考： http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97
- evalやそれに類するものを使うか否かは自由です。
-
割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
- 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
- 余裕があれば括弧を含むようにしてもいいかもしれません。
手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。
正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
0 を除いて降順に並べたものを指すことも多いのではないかと思います．
たとえば，
partitions 1 ⇒ [[1]]
partitions 2 ⇒ [[2],[1,1]]
partitions 3 ⇒ [[3],[2,1],[1,1,1]]
partitions 4 ⇒ [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
partitions 5 ⇒ [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
partitions 6 ⇒ [[6],[5,1],[4,2],[3,3],[4,1,1],[3,2,1],[2,2,2],[3,1,1,1]
,[2,2,1,1],[2,1,1,1,1],[1,1,1,1,1,1]]
すなわち，
- 1つの分割は非増加列
- 分割は長さが短いものが先
- 同じ長さの分割では辞書順で大きいものが先
という規則でならべたものです．一つの分割に一つのヤング図形が対応します．
たとえば、5 の分割に対応するヤング図形を列挙すると以下 7 つのようになります．
□□□□□
□□□□
□
□□□
□□
□□□
□
□
□□
□□
□
□□
□
□
□
□
□
□
□
□
お題：
正整数を与えられたとき上の意味での分割に対応するヤング図形をすべて
標準出力に印字する関数 young を定義してください．ヤング図形の出力は
上の例のように文字'□'を並べてください．
young 50 の出力をファイルにリダイレクトしたときの処理時間はどの程度
かかったかもCPUスペックとあわせt教えてください．
see: ヤング図形
- 標準でついているprintf系関数の使用禁止
- 標準でついているライブラリ以外の使用禁止
- 引数・返り値等の仕様はできるだけ似せればよい
1 2 3 4 5 6 7 | #include <string.h>
// なにもフォーマットしてない
int mysprintf(char *str, const char *format, ... ){
strcpy(str, format);
return strlen(str);
}
|
与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。
以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では
reverseString("文字列(もじれつ)の反転(はんてん)")
→ ")んてんは(転反の)つれじも(列字文"
のように括弧の対応は保存されませんが、reverseString2 では
reverseString2("文字列(もじれつ)の反転(はんてん)")
→ "(んてんは)転反の(つれじも)列字文"
のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。
reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
→ "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"
入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、
reverseString2("これ(は(対応のとれていない)括弧がある例です。")
→ "。すで例るあが弧括(いないてれとの応対)は(れこ"
次のような場合は対応のとれている括弧はないという解釈になります。
reverseString2("これ(も{対応の)とれていない}括弧の例です")
→ "。すで例の弧括}いないてれと)の応対{も(れこ"
日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。
---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。
こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。
追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。
入力されたテキストデータから重複する行をとりのぞいて、その結果を標準出力へ出力するプログラムを作成してください。
重複行の排除については、以下の仕様を満たしてください。
- 読み込み順序は変更しないこと
- 重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い)
- ファイル全体を一度にメモリに読み込んで処理しないこと
- 比較は行全体で行うこと
#4.はおまけですがある／なしで作りが変わってくると思われるので追加しました。
この問題はraynstardさんにご投稿いただきました。ご協力ありがとうございます。 ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズのすべての行が異なっているファイルを読ませたときに大変なことが起こりそうな気がしますが、そういうシビアなお題設定ではないので素朴に解いてしまって構いません。シビアなのは続編にしたいと思います。
関数 InputCheckerは、以下の仕様を満たしてください。
- 引数に 時間(秒) Nと文字列 Sを受け取ること。
- ユーザからの標準入力とあらかじめ指定された S を比較し、 一致すれば「OK」、一致しなければ「NG」を標準出力へ出力すること。
- ユーザーの入力がN秒以内に完了しなかった場合は、比較せず 「TIME OUT」を標準出力へ出力すること。
- 経過時間はユーザーが入力を開始した地点から計測すること。
- ENTER キーの入力によってユーザー入力が完了したと仮定すること。
- ユーザの入力が完了するまでは、完了を待ち続けること
たとえば、「InputCheker(5, "ABCDEF")」と指定した場合、 出力例はこんな感じです。
- input(ABCDEF) =>ABCDEF<ENTER>
- result => OK
- result => NG
- result => TIME OUT
1. input(ABCDEF) =>
と出力して入力待ちをし、ユーザーが「ABCDEF<ENTER>」を入力したとき、 入力開始から5秒以内ならば「OK」、5秒をこえていれば「TIME OUT」を出力します。 このとき、ユーザーがキーを押下しなければ1. を出力してから たとえ10秒たっていても「TIME OUT」にはならないので注意してください。 時間計測はあくまでユーザーが入力を開始してからです。
このお題はraynstardさんの投稿です。ご協力ありがとうございます。
また、ユーザの入力注の<br>は<br/>に変換してください。
このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。
- 通すタグはAとBRとSTRONGのみ。大文字小文字は区別しない。
- それ以外のタグとして意味を持ちうる文字列は<を<に変換することで無効化する(削除するのではない。>は変換してもしなくてもよい)
- Aタグのhrefとname以外の属性は削除する。BRやSTRONGの属性はすべて削除する。
このお題はperezvonさんの提案を元にしています。ありがとうございました。 ただ、いきなりだと難しいかと思ったので、肝の部分以外を先に出題しました。このお題は続編で徐々に難しくなっていきます。
追記：属性に<や>が含まれてしまうケースに漏れのある解答が多いようなのでテストケースを追加します。
これは「この出力なら十分」という意味です。この出力の通りでなければいけないという意味ではありません。
<script foo="<script>alert('bar')</script>">alert('foo')</script>
<script foo="<script>alert('bar')</script>">alert('foo')</script>
<script foo="<a href='link'>link</a>">alert('foo')</script>
<script foo="<a href='link'>link</a>">alert('foo')</script>
<a href='www.g>oogle.com'>link</a>
<a href="./www.g%3Eoogle.com">link</a>
サンプル入力
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からの挑戦状です。
分散関数呼び出しを実装してください． 呼び出される関数は，定価を整数で，割引率(%)を整数で受け取り， 文字列で「販売価格 ○円（定価○円から○%引き）」を返すものとします． また，数字は3桁のカンマ区切りにするものとします． たとえば，pricestring(2000, 20) なら "販売価格 1,600円 (定価2,000円から20%引き)" を返します． 関数の呼び出し元と，呼び出される側は，物理的に異なる サーバに配置できることを条件とします． 呼び出し方法は問いませんが，呼び出し方法に名前がある場合， それをタグに加えてください． （XML-RPC，SOAP，CORBA，RMI，など） また，作成した関数を直列に1万回呼び出して， 実行にかかった時間を測定してください． 測定時は別サーバでなくても構いません． （なるべく別サーバが望ましいです） 測定環境として， ・サーバとクライアントのCPU・メモリ ・同一サーバ内での実行か別サーバでの実行か ・別サーバの場合，通信経路．（100Mbps Ethernet等） ・言語のバージョン ・ミドルウェアを使用している場合，その名前とバージョン も併記してください． 1つの言語で複数の分散関数呼び出しの実装方法がある場合， 複数の回答を歓迎します． 出題の意図は，様々な分散呼び出し方法の実装例と， レスポンス速度の確認にあります．このお題は沢渡 みかげさんの投稿です。 まったく手を加えないでいい完成度の投稿で本当に助かります。 ありがとうございました。
アクセスログの各行の先頭に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サーバと直接通信してもかまいません．
ログを順次読み取り処理する部分を，データを共有しつついかに並列化するか，という部分を問うのが目的です．
このお題は沢渡みかげさんの投稿です。ご投稿ありがとうございます。
「組み合わせ型の最小完全ハッシュ関数」とは 下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)
>>> for xs in make_perm(5, 2): print xs, "=>", hash(xs, 5, 2) [1, 1, 0, 0, 0] => 9 [1, 0, 1, 0, 0] => 8 [1, 0, 0, 1, 0] => 7 [1, 0, 0, 0, 1] => 6 [0, 1, 1, 0, 0] => 5 [0, 1, 0, 1, 0] => 4 [0, 1, 0, 0, 1] => 3 [0, 0, 1, 1, 0] => 2 [0, 0, 1, 0, 1] => 1 [0, 0, 0, 1, 1] => 0
「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、 ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)
さて、ここからが本題です。 組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。 この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。
このお題はshuyoさんの提案を元に作成しました。ありがとうございました。
ここにトランプが一組あります． 司会者がそこから二枚抜いて，その積を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 ]