Language detail: Groovy - 's unsolved challenges
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 の各値を示す必要はありません。
'tail'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
１：ランダムな２０文字を持つ文字列をもった３００個作ります。
２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）
５：以後３：と４：を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、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 文字で以下のデータが格納されています。デリミタはなく、固定長で格納されています。レコードとレコードのあいだも改行はありません。
- 姓 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
- 名 (12文字) 文字数が足りない場合は、後ろを空白で埋めてあります。
- 性別 (F,M,Uの3種類、1文字)
- 年齢 (3桁の数字、桁数が足りない場合は、ゼロで埋めず、頭を空白で埋めてあります。
- 年 2008 固定
- 月 03 固定
- さらに以下のデータが日付分くりかえされます。
- 日付 (01 〜 31) 2文字
- 朝食のメニュー (500文字)
- 昼食のメニュー (500文字)
- 夕食のメニュー (500文字)
以上の形式のデータ500人分を読みこんで、データを複数の値を格納できるデータ型に格納してください。データに大して何か処理を行う必要はなく、すぐに破棄してかまいません。
この問題は、このようなファイルをどのように扱うかを知りたくて作成しました。
セルオートマトンに関するお題です. 2次元タイプの'ライフゲーム'を実装して下さい. 初期値としては10行10列程度の格子上の平面に0.3程度の人口(?)密度を考え, 末端はループするようにして下さい. (例: 座標[-1, -1] = [10, 10]) それだけだと簡単すぎると思われる方は, 過密状態で間引きが発生するような機能を組み込んで下さい. 間引きは, 少なくともその後の1時間ステップにおける死亡率が, それをしなかった場合よりも小さくなれば結構です. (死亡率の最小化は複雑性が高すぎる感がありますし. ) サンプル: t = 0 [ ][*][ ][ ][ ][ ][*][*][*][ ] [ ][ ][ ][ ][*][ ][ ][*][*][ ] [ ][ ][ ][*][ ][ ][*][ ][*][ ] [*][ ][*][*][ ][ ][*][ ][ ][ ] [ ][*][ ][ ][ ][ ][ ][ ][*][ ] [*][ ][ ][ ][*][ ][*][*][ ][*] [ ][*][ ][ ][ ][ ][*][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][ ][*][ ][ ][*] [ ][ ][ ][ ][*][*][ ][ ][*][ ] t = 1 [ ][ ][ ][ ][*][ ][ ][ ][ ][*] [ ][ ][ ][ ][ ][*][ ][ ][ ][*] [ ][ ][*][ ][*][*][*][ ][*][*] [ ][*][ ][*][ ][ ][ ][ ][ ][*] [ ][ ][*][*][ ][*][*][ ][*][ ] [ ][*][ ][ ][ ][*][*][ ][*][*] [ ][ ][ ][ ][ ][*][*][*][*][*] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][*][ ][ ][*][ ] [*][ ][ ][ ][ ][ ][ ][ ][ ][ ]
see: Wikipedia:ライフゲーム
see: Wikipedia 閏年
以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。 1. 格子状の迷路であること。 2. 経路の幅は均等であること。 3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。 ループも認めません。 4. 出力の度にランダムな迷路であること。 ランダムシードが同じ時に同じ迷路になってしまうのはよいです。 たとえば、n=4, m=5の迷路の出力は以下のようになります。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ■ ―■■■■■■■■■ こう言うのは、×の部分が3のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■×■ ■ ―■■■ ■■■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■■■ ■ ４■ ■×××■ ■ ―■ ■×■■■ ■ ５■ ■×××■ ■ ―■■■■■■■■■ このようなループも2のルールに違反するのでダメです。 ｜１｜２｜３｜４｜ ―■■■■■■■■■ １■ ■ ■ ―■■■ ■ ■ ■ ２■ ■ ■ ―■ ■■■ ■ ■ ３■ ■ ■ ―■ ■■■ ■ ■ ４■ ■ ■ ■ ―■ ■ ■■■ ■ ５■ ■ ■ ―■■■■■■■■■ できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。 難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を どうやって作るのかを考えると答えが見えてくると思います。 ソースコードはJavaで150行程度になりました。
引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。
条件：
- スートは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
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
お題#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
一応、制約条件を示しておきます。
- あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります 。
- 同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
- 除算および剰余の使用禁止
- 加算や乗算から除算・剰余を単純に定義することも禁止とする
- ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
- 多倍長演算をサポートすること（各言語のライブラリ状況を見たいので）
- 引数は2つの正整数と仮定して構わない
- F_1=1, F_2=1のフィボナッチ数列で2000番目と1999番目の最大公約数を求めたときのループ回数を教えてください
与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを 書いてください。 文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを 対象とします。出力は起点"ウ"の座標と方向のリストにしてください。 サンプル入力： リオウウリウ ウオリウオリ オリリオリウ リリオオウオ サンプル出力： (2, 0), 左 (0, 1), 右 (0, 1), 下 (3, 1), 右 (4, 3), 左上 -- より一般には、任意の検索文字列への対応も考えてみてください。
正整数の分割といったとき，同じ組み合わせのもの同じ分割とみなし，
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);
}
|
これは、実例を見た方が簡単だと思います。 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)
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)?)?)
|
「どう書く?」でまだ出ていないのが不思議なお題。それがBF処理系。 ここでは、BFで書かれたソースを、同じ言語に変換するコンパイラーを募集します。
私自身、すでにPerlとJavaScriptに関しては http://blog.livedoor.jp/dankogai/archives/50545151.html でやっているのですが、他の言語バージョンも是非見たいので。
Dan the Brainf.ucker
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
無憂無風 礼 林 千 火 万水千山 知行合一 者 筆 不 勾 言語道断
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
与えられた文字列を前後反転する関数 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さんの投稿です。ご協力ありがとうございます。
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さんからの投稿です。ご投稿ありがとうございました。助かります。
n = 4の時には [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] が正解です。
問題の理解を促すために上のリストを2進数表記で表示してみます。
0000 0 1000 8 0100 4 1100 12 0010 2 1010 10 0110 6 1110 14 0001 1 1001 9 0101 5 1101 13 0011 3 1011 11 0111 7 1111 15n = 8などの場合のリストは音声のFFT演算でよく使わているそうです。 この問題は光成さんの投稿を元にしています。 ご協力ありがとうございました。
Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。
37 199148647.999978 58 24591257752.000000 67 147197952743.999999 163 262537412640768744.000000この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。
また、ユーザの入力注の<br>は<br/>に変換してください。
このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。
ただし、このお題の趣旨は実数区間での探索なので、 立方根関数があっても使ってはいけません。 指数関数と対数関数も禁止します。
Pythonで表現した入出力の例：
>>> cube_root(10.0) 2.1544346900318834 >>> _ ** 3 9.9999999999999947 >>> cube_root(100.0) 4.6415888336127793 >>> _ ** 3 100.00000000000003
- 通すタグは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>
>>> pyramid("hoge")
e
g e
o g e
h o g e
>>> pyramid("abracadabra")
a
r a
b r a
a b r a
d a b r a
a d a b r a
c a d a b r a
a c a d a b r a
r a c a d a b r a
b r a c a d a b r a
a b r a c a d a b r 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からの挑戦状です。
詳しい導出方法は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]
このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。
「重複無し乱数」で作ったbingo関数の結果を下のように「何番目の乱数か」とセットにして10個ずつ折り返して表示するコードを書いてください。
>>> bingo(30) 1 2 3 4 5 6 7 8 9 10 29 14 16 13 30 15 22 11 25 9 11 12 13 14 15 16 17 18 19 20 23 4 18 5 28 17 8 12 21 20 21 22 23 24 25 26 27 28 29 30 26 6 2 19 1 7 10 27 3 24 >>> bingo(35) 1 2 3 4 5 6 7 8 9 10 7 15 3 32 1 16 17 28 6 29 11 12 13 14 15 16 17 18 19 20 19 23 30 26 20 5 12 2 25 31 21 22 23 24 25 26 27 28 29 30 35 13 24 18 11 8 10 34 22 21 31 32 33 34 35 9 4 27 33 14
分散関数呼び出しを実装してください． 呼び出される関数は，定価を整数で，割引率(%)を整数で受け取り， 文字列で「販売価格 ○円（定価○円から○%引き）」を返すものとします． また，数字は3桁のカンマ区切りにするものとします． たとえば，pricestring(2000, 20) なら "販売価格 1,600円 (定価2,000円から20%引き)" を返します． 関数の呼び出し元と，呼び出される側は，物理的に異なる サーバに配置できることを条件とします． 呼び出し方法は問いませんが，呼び出し方法に名前がある場合， それをタグに加えてください． （XML-RPC，SOAP，CORBA，RMI，など） また，作成した関数を直列に1万回呼び出して， 実行にかかった時間を測定してください． 測定時は別サーバでなくても構いません． （なるべく別サーバが望ましいです） 測定環境として， ・サーバとクライアントのCPU・メモリ ・同一サーバ内での実行か別サーバでの実行か ・別サーバの場合，通信経路．（100Mbps Ethernet等） ・言語のバージョン ・ミドルウェアを使用している場合，その名前とバージョン も併記してください． 1つの言語で複数の分散関数呼び出しの実装方法がある場合， 複数の回答を歓迎します． 出題の意図は，様々な分散呼び出し方法の実装例と， レスポンス速度の確認にあります．このお題は沢渡 みかげさんの投稿です。 まったく手を加えないでいい完成度の投稿で本当に助かります。 ありがとうございました。
nori
#7961()
Rating-4/4=-1.00
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
[ reply ]