DouKaku? Language detail: なでしこ

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

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

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

# -*- 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

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秒です。

LL Golf Hole 9 - トラックバックを打つ (Nested Flatten)

LL Golf Hole 9のリリースをアナウンスしているエントリにトラックバックを打ってください(トラックバックURL)。マシンガンのようには打たないでください。ただし、このエントリにはスパムフィルタが搭載されているため、寄せることはできてもカップインできないかもしれません。その場合はtakano32が用意させていただきました打ちっ放し場にてガンガン試し打ちください(トラックバックURL)。

余力のあるものは感想を公式ブログの感想エントリにトラックバックくしてください。余力がなくても感想をトラックバックしてくれるとスタッフがよろこびます。

see: トラックバック技術仕様書

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

起動オプションの解析 (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の内容と一致するようにしてみてください。

LL Golf Hole 4 - 文章から単語の索引を作る (Nested Flatten)

GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。

与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。

余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。

※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。

see: open-uri - Rubyリファレンスマニュアル

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

tailの実装 (Nested Flatten)

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

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

最低限必要な機能は、

行数指定
「-f」パラメータの対応

です。

lessの実装 (Nested Flatten)

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

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

最低限必要な機能は、

上下スクロール
検索

です。

2次元ランダムウォーク (Nested Flatten)

２次元ランダムウォークをつくってみてください。

＊＊＊＊＊＊

元は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

分からないというヒトへの分かりにくいヒント：

今の位置から次の時間の位置が決まるのですが、決まりかたが、乱数で一歩後退するか一歩先にいくか?ということをやればよいです。

コード圧縮 (Nested Flatten)

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

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

コード中の文字の頻度分析 (Nested Flatten)

プログラムコード中の文字の頻度は言語によって相当にばらつきがあると思います。ある言語はピリオドが頻出するとか、別の言語はカッコの頻出頻度が高い、とか。そこで、

文字の頻度解析をするプログラムを作成し、
適当なプログラムに対して実行し、結果を出力して、そのような頻度になっている理由を教えてください。

(その言語で書かれた「典型的な」プログラムコード、といえるようなものがあると良いのですが・・）

簡単すぎるという方は、複数文字にしてみたり単語の頻度にしてみてください。

参考；Wikipedia 頻度分析

http://ja.wikipedia.org/wiki/%E9%A0%BB%E5%BA%A6%E5%88%86%E6%9E%90

出力の一時停止と再開 (Nested Flatten)

起動すると、標準出力に1秒毎に'a'の1文字を出力し続けるプログラムで、以下の条件を満たすものを「どう書く？」

'q'キーが押されるとプログラムは終了する
出力中に'p'キーが押されると一時停止する
一時停止中に'p'キーが押されると出力を再開する

METHINKS IT IS A WEASEL (Nested Flatten)

ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。

簡単に流れを書いてみます。

１：ランダムな２０文字を持つ文字列をもった３００個作ります。

２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。

３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。

４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）

５：以後３：と４：を繰り返す。

ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。

METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)

Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。

参考

http://home.pacbell.net/s-max/scott/weasel.html (JAVA アプレット)
http://en.wikipedia.org/wiki/Weasel_program

マルバツゲーム：賢いプレイヤー (Nested Flatten)

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

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

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

マルバツゲーム (Nested Flatten)

マルバツゲームは３×３の格子に交互に○と×を書き込み、先に縦・横・斜めに記号をそろえたほうが勝ちというおなじみのゲームです。

「毎ターン乱数を使って手を決めるランダムプレイヤー同士を対戦させる」というのが今回のお題です。１万回対戦させ、勝ち・負け・引き分けの数を表示してください。そして先手が有利であることを確かめてください。

良い手を思考するプレイヤーについては別のお題にしようと思っています。プレイヤーを簡単に差し換えることができる設計を目指してください。

α置換 (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)

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

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

姓 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。

名 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。

性別 (F,M,Uの3種類、1文字)

年齢 (3桁の数字、桁数が足りない場合は、ゼロで埋めず、頭を空白で埋めてあります。

年 2008 固定

月 03 固定

さらに以下のデータが日付分くりかえされます。

日付 (01 〜 31) 2文字

朝食のメニュー (500文字)

昼食のメニュー (500文字)

夕食のメニュー (500文字)

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

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

メソッドのフック (Nested Flatten)

例えば、あるクラスのあるメソッドを実行する前に他の処理を呼びたい(例えばログやトランザクション開始など)。また、そのメソッドの終了後にも何らかの後処理を呼びたい(トランザクション終了など)。

そのような、メソッドに対するフック処理を書いてください。ライブラリを使用してメソッドのフックを実現した場合はライブラリの名前を紹介してくれると助かります。

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

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

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

変数の初期値 (Nested Flatten)

WEB+DB 43のRecent Perl Worldを読んで知りました。

変数を初期化するに当たってPerlでは
my $var ||= 'foo';
とかきます。この不備を補うためPerlの5.10には
Defined-or演算子が実装されたそうです。
$zero //= 25;
このような変数のデフォルト設定を行う方法を各種言語ではどうかくのでしょうか。

データの整列 (Nested Flatten)

(x, y) の座標情報を以下の2種類の方法で整列する機能を実現してください。

(x, y) の辞書順(まず x で昇順に整列して、x が同じデータに対して y で昇順に整列する)
(0, 0) からの距離の昇順

データの表現方法はタプルなり構造体/オブジェクトなり各自で適当に選んで下さい。

不動点演算子 (Nested Flatten)

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

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

see: Wikipedia

総当たり戦の日程作成 (Nested Flatten)

任意の偶数Nのチームの総当たり戦を最短日数（N-1日）で行う場合の日程表を１つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、４チームであれば、

1-2 3-4
1-3 2-4
1-4 2-3

６チームであれば

1-2 3-4 5-6 
1-3 2-5 4-6 
1-4 2-6 3-5 
1-5 2-4 3-6 
1-6 2-3 4-5

が解のひとつです。

see: カークマンの組分け

指定コマンドを別プロセスで起動 (Nested Flatten)

与えられた文字列のコマンドを、別プロセスで実行してください。異なるPIDのプロセスが立ち上がり、指定したコマンドを実行することが条件です。

あわせて、実行結果のリターンコードと、別プロセスが出力した標準出力を受け取る方法も記載してください。

今回投稿する上で、別プロセスとして実行するコマンドの与え方は自由ですが、実行した結果、何らかの損害を与えるようなコマンドは埋め込まないようにお願いします。

ポーカーの役判定 (Nested Flatten)

引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。

条件：

スートはS,D,H,C、ランクはA,2～9,T,J,Q,Kのそれぞれ一文字で表します。
手札は S2D5H3CQS9 のように10文字で指定されます。特にソートはされていません。
手札にジョーカーは含まれません。
ストレートで取りうるランクの種類はA2345, 23456 ... 9TJQK, TJQKAの10種類で、JQKA2のようにK-A-2をまたぐものはストレートではありません。

実行例：

% ./poker SQSJSASKST
Royal flush

% ./poker D9D7D6D5D8
Straight flush

% ./poker C2D2S2H3H2
Four of a kind

% ./poker C2D3S2H3H2
Full house

% ./poker S9S4S8STSJ
Flush

% ./poker C4H7D5S6H3
Straight

% ./poker S6H6C5DQC6
Three of a kind

% ./poker S6HQC5DQC6
Two pair

% ./poker S6H4C5DQC6
One pair

% ./poker SJSQSKSAC2
No pair

see: ポーカー - Wikipedia

ワーカスレッドを安全に終了させるまで待機 (Nested Flatten)

スレッドプールに複数のワーカスレッドが待機しており、メインスレッドはいつでもワーカスレッドに仕事を渡せるような状態になっているとします。

さて、メインスレッドからスレッドプールにいくつか仕事を与え、メインスレッドは与えた仕事すべてが終了するまで待機し、次の処理に行ってはいけない、というようなコードを書いてください。＃現実に書く機会が多そうなコードですね…。

ここでの仕事の内容は、適当に5秒から15秒の間スレッドをスリープする、というもので結構です。また、ワーカスレッドのスレッドプール自体の使用を終了するか、または残して再利用するかは問いません。できればコメントにスレッドプールを残したかどうかを書いてください。

HTTPでGET　その2 (Nested Flatten)

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

Meertens数 (Nested Flatten)

お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．

このような数のことをMeertens数と言うそうです．

32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．

与えられた並べ替えを実現するあみだくじの生成 (Nested Flatten)

お題#4476を見て思いつきました。

0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。

与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：

 0 1 2 3 4 5
 | | |-| |-|
 | |-| |-| |
 |-| |-| | |
 | |-| |-| |
 | | |-| |-|
 | | | |-| |
 3 5 2 4 0 1

一応、制約条件を示しておきます。

あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります。
同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。

一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。

魔方分割数 (Nested Flatten)

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

最大公約数（除算禁止） (Nested Flatten)

あなたが使っている言語で除算と剰余が使えなくなりました。

以下の条件のもと最大公約数を求めるプログラムを書いてください。

条件

除算および剰余の使用禁止
加算や乗算から除算・剰余を単純に定義することも禁止とする
ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
多倍長演算をサポートすること（各言語のライブラリ状況を見たいので）
引数は2つの正整数と仮定して構わない
F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください

文字列の八方向検索 (Nested Flatten)

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。

自然数の分割（別表現） (Nested Flatten)

正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
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: ヤング図形

擬似lsの実装 (Nested Flatten)

スラッシュで区切られた文字列の配列(以下パスリスト)がある。
このパスリストにたいして擬似的なlsを行いたい。
lsはパスリストと表示対象ディレクトリのパスを入力する。

例としては以下のようになる。
pathList = ["aaa/bbb","aaa/ccc","aaa/ddd/eee","bbb/ddd/eee"]

ls(pathList,"aaa/")
>["bbb","ccc","ddd/"]

ls(pathList,"aaa/ddd/")
>["eee"]

なおパスリストが大きくなったとき、速度がなるべく低下しないように実装するのが望ましい。
文字列は任意の文字コードであると仮定してかまわない。

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);
}

正しい文(クイズ) (Nested Flatten)

「この文は0が□個，1が□個，...，9が□個あります」
が正しくなるように□を埋めてください．数値は10進数とします．
一般のn(<=16で可)進数でも解いてみてください．

たとえば2進数なら
「この文は0が11個，1が100個あります」
となります．

文字列リストを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)

与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。

出力例:

無憂無風
礼　　林
千　　火
万水千山

知行合一
者　　筆
不　　勾
言語道断

四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。

四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。

問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。

水の移し替えパズル (Nested Flatten)

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．

可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

文字列の反転(括弧の対応を保存) (Nested Flatten)

与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。

以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では

  reverseString("文字列(もじれつ)の反転(はんてん)") 
    → ")んてんは(転反の)つれじも(列字文"

のように括弧の対応は保存されませんが、reverseString2 では

  reverseString2("文字列(もじれつ)の反転(はんてん)")
    → "(んてんは)転反の(つれじも)列字文"

のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。

  reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
    → "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"

入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、

  reverseString2("これ(は(対応のとれていない)括弧がある例です。")
    → "。すで例るあが弧括(いないてれとの応対)は(れこ"

次のような場合は対応のとれている括弧はないという解釈になります。

  reverseString2("これ(も{対応の)とれていない}括弧の例です")
    → "。すで例の弧括}いないてれと)の応対{も(れこ"

日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。 

---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。

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

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

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

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

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

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

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

ファイル内の重複行削除(後優先) (Nested Flatten)

「アレイのuniq」の応用編です。

入力されたテキストデータから重複する行をとりのぞいて、その結果を標準出力へ出力するプログラムを作成してください。

重複行の排除については、以下の仕様を満たしてください。

読み込み順序は変更しないこと
重複する行があった場合、以前のデータを削除すること (後に読み込んだ方が強い)
ファイル全体を一度にメモリに読み込んで処理しないこと
比較は行全体で行うこと

#4.はおまけですがある／なしで作りが変わってくると思われるので追加しました。

この問題はraynstardさんにご投稿いただきました。ご協力ありがとうございます。ところで、素朴な実装のしかたをするとメモリ容量の数倍のサイズのすべての行が異なっているファイルを読ませたときに大変なことが起こりそうな気がしますが、そういうシビアなお題設定ではないので素朴に解いてしまって構いません。シビアなのは続編にしたいと思います。

格子点の列挙 (Nested Flatten)

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であれば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番目の頂点が何かも併せて答えてください。

このお題はかもさんの投稿を元にしています。ご協力ありがとうございました。

制限時間内のキー入力検査 (Nested Flatten)

ユーザーの入力を検査する関数 InputCheckerを作成して 3回連続実行してください。

関数 InputCheckerは、以下の仕様を満たしてください。

引数に時間(秒) Nと文字列 Sを受け取ること。
ユーザからの標準入力とあらかじめ指定された S を比較し、一致すれば「OK」、一致しなければ「NG」を標準出力へ出力すること。
ユーザーの入力がN秒以内に完了しなかった場合は、比較せず「TIME OUT」を標準出力へ出力すること。
経過時間はユーザーが入力を開始した地点から計測すること。
ENTER キーの入力によってユーザー入力が完了したと仮定すること。
ユーザの入力が完了するまでは、完了を待ち続けること

たとえば、「InputCheker(5, "ABCDEF")」と指定した場合、出力例はこんな感じです。

input(ABCDEF) =>ABCDEF<ENTER>
1. result => OK
2. result => NG
3. result => TIME OUT

1. input(ABCDEF) =>

と出力して入力待ちをし、ユーザーが「ABCDEF<ENTER>」を入力したとき、入力開始から5秒以内ならば「OK」、5秒をこえていれば「TIME OUT」を出力します。このとき、ユーザーがキーを押下しなければ1. を出力してからたとえ10秒たっていても「TIME OUT」にはならないので注意してください。時間計測はあくまでユーザーが入力を開始してからです。

このお題はraynstardさんの投稿です。ご協力ありがとうございます。

ソートするコードの生成 (Nested Flatten)

Meta-Loopless Sortsの改題です．

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

exp(pi * sqrt(n))が整数に近くなるnを探す (Nested Flatten)

1以上200未満の整数nのうち、 exp(pi * sqrt(n))がほとんど整数であるようなnを求めるコードを書いてください。なお、expは底がeである指数関数 - Wikipedia、 piは円周率、sqrtは平方根です。また「ほとんど整数である」とは整数からプラスマイナス0.0001の範囲にあることとします。

Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。

37 199148647.999978
58 24591257752.000000
67 147197952743.999999
163 262537412640768744.000000

この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。

DouKaku?

Language detail: なでしこ - 's unsolved challenges

条件