DouKaku?

m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例：
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例：
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ

n×nの2次元配列を引数にとり、 これを行列とみなして行列式を返す 関数を作成してください。

行列・線形代数のライブラリ等を 使用しないことが条件です。

参考：http://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E5%BC%8F

 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
26
27
28

# -*- coding: utf-8 -*-

#   定義に基づく実装例


#   対称群
def symmetric_group(n):
    #   配列 [0, 1, .., (n-1)] を並び替えてできる
    #   すべての配列の組み合わせを返します。

#  置換の符号
def signature(sym):
    #   配列 [0, 1, .., (n-1)] の符号を +1とします。
    #   互換（2つの要素を交換）すると符合が変わります。
    #   配列 [0, 1, .., (n-1)] から
    #   奇数回の互換で得られる配列の符号は -1、
    #   偶数回の互換で得られる配列の符号は +1 になります。

#  行列式
def determinant(mat):
    det = 0;
    deg = len(mat)
    for s in symmetric_group(deg):
        term = signature(s)
        for i in range(deg):
            term *= mat[i][s[i]]
        det += term
    return det

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
2
3
4

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

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

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

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

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

コマンドライン引数の取得がありましたが、今回は環境変数の取得をお願いします。

取得した内容を表示できればよいですが、可能でしたらキーから値を得る手段の実装もお願いします。

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

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

設定ファイルから項目名をキーとして値を取得するコードを書いてください。
設定ファイルのイメージも載せてください。

ここで設定ファイルとは、
　・項目名と値のペアが書いてあるファイル
　・フォーマットはその言語で扱いやすいものでよい
　・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません（テーブル、環境変数など）。

例）
----
ファイル：ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200

> showPrice()
「りんご」は210円（税込み）
----
ITEM_NAME=みかん
ITEM_COST=100

> showPrice()
「みかん」は105円（税込み）

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

整数nを与えると　範囲lowからhigh内での位置を返すmodular関数を作ってください。
(
  low <high かつ　n=0のとき low　を返す

    n = 1 のとき low + 1　を返す。
    n = high　－ lowのときhighを返す。
    n = high　－ low  + 1 のときlowを返す。
       （循環　：　例＊　を参考にしてください） 
    n = high　－ low  + 2 のときlow+1を返す。


    n = 整数 * （high　－ low）  + 1 のときlowを返す。
    n = 整数 * （high　－ low） のときhighを返す。
    n = 整数 * （high　－ low）  + 2 のときlow+1を返す。
....循環の繰り返し
)


例
  modular(n,low,high) -> 出力

  modular(0,100,200)    -> 100

  modular(50,100,200)   -> 150
  modular(100,100,200)  -> 200

  ＊例
  modular(101,100,200)  -> 100
  
  modular(-1,100,200)   -> 200
  modular(1,-5,200)     ->  -4
  modular(-500,-5,-1)   ->  -5

#6190 の続編です。
マルバツゲームで、賢いプレイヤーの思考ルーチンを実装してください。

賢いといってもいろいろありますが、
１．負けない
２．できるだけ勝つ
という条件でいってみたいと思います。

ランダムプレイヤーと１万回バトルした結果（勝ち・負け・分け）を表示してください。
先攻になっても後攻になっても無敗！となれば言うことなしです。

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

固定長のデータが記載されたファイルを読み込むプログラムを作成してください。読み込んだデータは、複数の値を格納できるデータ型に格納してください。

ファイルには、すべて ascii 文字で以下のデータが格納されています。デリミタはなく、固定長で格納されています。レコードとレコードのあいだも改行はありません。

1. 姓 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
2. 名 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
3. 性別 (F,M,Uの3種類、1文字)
4. 年齢 (3桁の数字、桁数が足りない場合は、ゼロで埋めず、頭を空白で埋めてあります。
5. 年 2008 固定
6. 月 03 固定
7. さらに以下のデータが日付分くりかえされます。
   1. 日付 (01 〜 31) 2文字
   2. 朝食のメニュー (500文字)
   3. 昼食のメニュー (500文字)
   4. 夕食のメニュー (500文字)

以上の形式のデータ500人分を読みこんで、データを複数の値を格納できるデータ型に格納してください。データに大して何か処理を行う必要はなく、すぐに破棄してかまいません。

この問題は、このようなファイルをどのように扱うかを知りたくて作成しました。

不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。 つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。

お題は不動点演算子を実装することです。（Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします）

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、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 }は同じもの
とすることに注意してください。

これは、実例を見た方が簡単だと思います。 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

 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
26
27

#!/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)?)?)

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

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

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

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

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

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

Meta-Loopless Sortsの改題です．

n個の整数をソートするプログラムを生成するプログラム gensort を 書いて下さい．条件は以下のとおり

1. 生成するプログラム，生成されたプログラムは同じ言語にして下さい．
2. 生成したプログラムはファイルに書き込んでください．
3. 生成されたプログラムでは最初に n 個の整数を読み込んで， n個の変数を初期化してください．「可能なら」変数名は，アルファベット 一文字で a，b，c ... の順で使ってください．n = 5 なら 変数は a, b, c, d, e です．
4. 生成されたプログラムでは，if 文あるいは if 式で2つの変数を比較して いって，変数の順が確定したら，その順で変数の値を出力するようにして 下さい．
5. 生成される側のプログラムでのアルゴリズムやデータ構造を工夫する問題では ありません :)

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さんからの投稿です。ご投稿ありがとうございました。助かります。