DouKaku? Language detail: Scala - 's unsolved challenges

inline/embeded bytecode assembly (Nested Flatten)

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

世界時計 (Nested Flatten)

プログラムを実行した端末のロケールと、グリニッジ標準時と、ロサンゼルスの現在時刻をそれぞれ表示してください。時刻の表示はリアルタイムでなく、一回限りで構いません。時刻のフォーマットは自由とします。

出力例
現在の時刻は、2008年10月29日 11時36分21秒です。
グリニッジ標準時刻は、2008年10月29日 2時36分21秒です。
アメリカ・ロサンゼルスの時刻は、2008年10月28日 19時36分21秒です。

π (Nested Flatten)

円周率を計算してください。

積分を計算するも、素朴な方法も、速さを目指すも、LLで計算する意味を問うもあるでしょう。

http://ja.wikipedia.org/wiki/%E5%86%86%E5%91%A8%E7%8E%87

起動オプションの解析 (Nested Flatten)

いわゆる、コマンドライン引数の取得(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

echoクライアント (Nested Flatten)

TCPのechoクライアントを書いてください。

サーバのホスト名ないしIPアドレス、およびポートはコマンドライン引数で指定します。
標準入力からユーザの入力を受け取り、echoサーバに送信します。
echoサーバから受信したデータを標準出力に出力します。

Windowsなら、Simple TCP/IP Servicesを起動してやれば、ローカルの確認用echo サーバとして使えます。

my_program localhost 7 < input_file > result_file

のようにしてリダイレクトを行った場合にも、result_fileがinput_fileの内容と一致するようにしてみてください。

lessの実装 (Nested Flatten)

'less'を実装してください。

巨大なファイルでも効率的に動作するようにしてください。

最低限必要な機能は、

上下スクロール
検索

です。

コード圧縮 (Nested Flatten)

スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、
それらを可能な限り減らし、コードを短くするコード書いてください。
また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。

以下詳細
・全てを行う必要はありません、どこまで行うかは任意です。
・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。
・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。
・コンパイラや実行環境に依存する圧縮は避けてください。

コメントの削除 (Nested Flatten)

ソースコードからコメント部分を削除するプログラム decomment を書いてください．
すくなくとも，decomment を記述したのと同じ言語で書かれているソースコードが
扱えるようにしてください．

α置換 (Nested Flatten)

標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、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;
}

ポリゴンを表示するプログラム (Nested Flatten)

適当なポリゴンを表示させて、描画するプログラムを書いてください。
ポリゴンは回転させてください。

2D処理だけなら、標準ライブラリで大体いけますが、
3D処理は追加でライブラリを利用すると思うので、
何のライブラリを利用したのか書いてください。

自分自身のファイル名を知る方法 (Nested Flatten)

自分自身のファイル名を知る方法を示してください。

ビルド後のファイルが、hogehoge.exeであれば、
”hogehoge.exe”が表示されるようなプログラムを書いてください。
スクリプト言語でも同様です。

ファイル名が変更されたらそれに追従するようにしてください。

see: #3301

printfの自作 (Nested Flatten)

printf関数を自作してください。
printfの説明は不要だと思います。とりあえずWikiPediaのリンクをはっておきます。
http://ja.wikipedia.org/wiki/Printf

実際にはsprintf関数を作ってください。
注意事項

標準でついているprintf系関数の使用禁止
標準でついているライブラリ以外の使用禁止
引数・返り値等の仕様はできるだけ似せればよい

可変長引数など、言語によっては難しい/不可能な仕様もありますが、いろいろ工夫して本物に近づくようにしてみてください。

#include <string.h>

// なにもフォーマットしてない
int mysprintf(char *str, const char *format, ... ){
    strcpy(str, format);
    return strlen(str);
}

文字列リストをTRIE Optimizeされた正規表現に (Nested Flatten)

これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。

ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。

なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。

とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。

Dan the Regexp Assembler

see: Trie (en.wikipedia)

#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
while(<>){
    chomp;
    next unless $_;
    $ra->add($_);
}
print $ra->re, "\n"
__END__

% grep program /usr/share/dict/words 
program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer

% grep program /usr/share/dict/words | perl sample.pl 
(?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)

続・ファイル内の重複行削除 (Nested Flatten)

「ファイル内の重複行削除(後優先) 」の続編です。

1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。

このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。

しかし、与えられたファイルが運悪く「一致する部分のないファイル」である可能性を考えてみましょう。たとえ1行ずつ読んで処理をしたとしても、「重複するかどうかの判定」のために前の行をまるごとメモリに取っておいたのでは、最終的にファイルを丸ごとメモリに乗せることになってしまいます。

こういうデータが入力されうる状況の場合にどう書くか、というお題です。前回のお題の条件3「ファイル全体を一度にメモリに読み込んで処理しないこと」を「たとえすべての行が異なるようなデータであっても、メモリの消費量をファイルサイズのおよそ10%程度に抑えること」と読み替えてください。

追記：「メモリの10倍」はさすがに条件として厳しすぎました。「ファイルのサイズは4ギガバイト未満であり、メモリの消費量をファイルサイズの半分以下に抑えること」と読み替えてください。半分以下に抑えられているのならば題意は満たすものとします。もちろん、頑張ってもっと少ないメモリで動くようにするのもアリです。

DouKaku?

Language detail: Scala - 's unsolved challenges

Index

Feed

Other

Link

Pathtraq