Language detail: Erlang - '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 2 3 4 | 出力例
現在の時刻は、2008年10月29日 11時36分21秒です。
グリニッジ標準時刻は、2008年10月29日 2時36分21秒です。
アメリカ・ロサンゼルスの時刻は、2008年10月28日 19時36分21秒です。
|
ただし以下の条件をつけます。
条件
一.アラビア数字(0~9)禁止。
プログラムにも出力結果にもアラビア数字を含んではいけない。(全角・半角とも)
二.結果の数字は、「七」とか「一○」(=10)とか「六四」(=64)のような形式とする。
三.九九の結果をそのままプログラム中に書き込んではいけない。
1 2 3 4 5 6 7 8 | 出力例
一 二 三 ・・・・
二 四 六 ・・・・
三 六 九 ・・・・
四 八 一二
・
・
|
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
日時を表す文字列と時間(秒)を受け取り
指定された日時からN秒となる日時を出力する関数 DateEx() を作成してください。
関数の仕様は次の通りです。
1. 入力となる日時の書式は任意である。
→ プログラムの都合に合わせてよい。
2. 入力となる時間(秒)は、負の値も許容すること。
また、負の値が指定された場合、指定の日時よりも前の日時を出力すること
3. 出力する日時は入力の日時と同じ書式をとる文字列であること
4. 出力する日時は正規化されていること
5. 出力先は標準出力、または、バッファのいずれでもよい。
たとえば、DateEx("20080827235925",40)ならば
出力は
「20080828000005」です。
余力があれば時間を省略可能とし、
省略された場合は「現在時刻」を利用するようにしてみてください。
GNU GENERAL PUBLIC LICENSE Version 3に登場する単語について、単語が登場する行を示した索引を作成してください。
与えられる文章についてはリテラルで表記する、標準入力で与えられる、引数でファイル名が与えられるなどは自由とします。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてください。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: open-uri - Rubyリファレンスマニュアル
1 2 3 4 5 6 7 8 9 10 | #!/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'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
2次元ランダムウォークをつくってみてください。
******
元は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
分からないというヒトへの分かりにくいヒント:
今の位置から次の時間の位置が決まるのですが、決まりかたが、乱数で一歩後退するか一歩先にいくか?ということをやればよいです。
tinyurl.com( http://tinyurl.com/ )のサービスを利用し、 http://ll.jus.or.jp/2008/info/xgihyo というURLを短縮しなさい。tinyurl.comのalias機能は使わないものとする。 なお、参考までに短縮したURLは http://tinyurl.com/5mngx8 となる。
余力のあるものはこのプログラムを短くしてみたり、短くしてみたり、短くしてみよ。
※LL Future実行委員の高野光弘です。この出題は LL Future公式の出題であり、優れたものについてはLL Golfのセッションでご紹介させていただくかもしれません。ご理解の上、ご投稿ください。また、LL Futureのチケットは現在も発売中です。よろしければ、メインイベントの方にもぜひご参加ください。
see: tinyurl.comでURLを短縮するRubyスクリプト
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #!/usr/bin/env ruby
require 'rubygems'
require 'mechanize'
def tinyurl(url, _alias = nil)
m = WWW::Mechanize.new
res = m.get('http://tinyurl.com/')
form = res.forms[1]
form['url'] = url
form['alias'] = _alias if _alias
res = m.submit(form)
regexp = Regexp.new('.*(http\:\//tinyurl.com/[a-z0-9-]+).*')
match = regexp.match(res.body)
return match[1] if match
end
if __FILE__ == $0 then
puts tinyurl('http://ll.jus.or.jp/2008/info/xgihyo')
end
|
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
クリップボード(や同等の機能)へテキストを転送するプログラムをお願いします。 また可能でしたらクリップボードのデータを取り出すプログラムもお願いします。
システムに依存する内容ですが、応用範囲が広いと思いましたので出題させてもらいました。
設定ファイルのイメージも載せてください。
ここで設定ファイルとは、
・項目名と値のペアが書いてあるファイル
・フォーマットはその言語で扱いやすいものでよい
・コードと分離され、コードに影響を与えずに変更が可能
を条件とします。ファイルが難しければ同等のものでもかまいません(テーブル、環境変数など)。
例)
----
ファイル:ShowPrice.ini
ITEM_NAME=りんご
ITEM_COST=200
> showPrice()
「りんご」は210円(税込み)
----
ITEM_NAME=みかん
ITEM_COST=100
> showPrice()
「みかん」は105円(税込み)
ソースコードからコメント部分を削除するプログラム decomment を書いてください. すくなくとも,decomment を記述したのと同じ言語で書かれているソースコードが 扱えるようにしてください.
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、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;
}
例えば、あるクラスのあるメソッドを実行する前に他の処理を呼びたい(例えばログやトランザクション開始など)。 また、そのメソッドの終了後にも何らかの後処理を呼びたい(トランザクション終了など)。
そのような、メソッドに対するフック処理を書いてください。 ライブラリを使用してメソッドのフックを実現した場合は ライブラリの名前を紹介してくれると助かります。
適当なポリゴンを表示させて、描画するプログラムを書いてください。 ポリゴンは回転させてください。 2D処理だけなら、標準ライブラリで大体いけますが、 3D処理は追加でライブラリを利用すると思うので、 何のライブラリを利用したのか書いてください。
WEB+DB 43のRecent Perl Worldを読んで知りました。 変数を初期化するに当たってPerlでは my $var ||= 'foo'; とかきます。この不備を補うためPerlの5.10には Defined-or演算子が実装されたそうです。 $zero //= 25; このような変数のデフォルト設定を行う方法を各種言語ではどうかくのでしょうか。
不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。 つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。
お題は不動点演算子を実装することです。(Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします)
see: Wikipedia
セルオートマトンに関するお題です. 2次元タイプの'ライフゲーム'を実装して下さい. 初期値としては10行10列程度の格子上の平面に0.3程度の人口(?)密度を考え, 末端はループするようにして下さい. (例: 座標[-1, -1] = [10, 10]) それだけだと簡単すぎると思われる方は, 過密状態で間引きが発生するような機能を組み込んで下さい. 間引きは, 少なくともその後の1時間ステップにおける死亡率が, それをしなかった場合よりも小さくなれば結構です. (死亡率の最小化は複雑性が高すぎる感がありますし. ) サンプル: t = 0 [ ][*][ ][ ][ ][ ][*][*][*][ ] [ ][ ][ ][ ][*][ ][ ][*][*][ ] [ ][ ][ ][*][ ][ ][*][ ][*][ ] [*][ ][*][*][ ][ ][*][ ][ ][ ] [ ][*][ ][ ][ ][ ][ ][ ][*][ ] [*][ ][ ][ ][*][ ][*][*][ ][*] [ ][*][ ][ ][ ][ ][*][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][ ][*][ ][ ][*] [ ][ ][ ][ ][*][*][ ][ ][*][ ] t = 1 [ ][ ][ ][ ][*][ ][ ][ ][ ][*] [ ][ ][ ][ ][ ][*][ ][ ][ ][*] [ ][ ][*][ ][*][*][*][ ][*][*] [ ][*][ ][*][ ][ ][ ][ ][ ][*] [ ][ ][*][*][ ][*][*][ ][*][ ] [ ][*][ ][ ][ ][*][*][ ][*][*] [ ][ ][ ][ ][ ][*][*][*][*][*] [ ][ ][ ][ ][ ][ ][ ][ ][ ][*] [*][ ][ ][ ][ ][*][ ][ ][*][ ] [*][ ][ ][ ][ ][ ][ ][ ][ ][ ]
see: Wikipedia:ライフゲーム
以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。 1. 格子状の迷路であること。 2. 経路の幅は均等であること。 3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。 ループも認めません。 4. 出力の度にランダムな迷路であること。 ランダムシードが同じ時に同じ迷路になってしまうのはよいです。 たとえば、n=4, m=5の迷路の出力は以下のようになります。 |1|2|3|4| ―■■■■■■■■■ 1■ ■ ■ ―■■■ ■■■ ■ 2■ ■ ■ ―■ ■■■ ■ ■ 3■ ■ ■ ―■ ■■■ ■ ■ 4■ ■ ■ ■ ―■ ■ ■■■ ■ 5■ ■ ■ ■ ―■■■■■■■■■ こう言うのは、×の部分が3のルールに違反するのでダメです。 |1|2|3|4| ―■■■■■■■■■ 1■ ■×■ ■ ―■■■ ■■■ ■ 2■ ■ ■ ―■ ■■■ ■ ■ 3■ ■ ■ ―■ ■■■■■ ■ 4■ ■×××■ ■ ―■ ■×■■■ ■ 5■ ■×××■ ■ ―■■■■■■■■■ このようなループも2のルールに違反するのでダメです。 |1|2|3|4| ―■■■■■■■■■ 1■ ■ ■ ―■■■ ■ ■ ■ 2■ ■ ■ ―■ ■■■ ■ ■ 3■ ■ ■ ―■ ■■■ ■ ■ 4■ ■ ■ ■ ―■ ■ ■■■ ■ 5■ ■ ■ ―■■■■■■■■■ できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。 難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を どうやって作るのかを考えると答えが見えてくると思います。 ソースコードはJavaで150行程度になりました。
>a.py 1868/12/2
明治1年12月2日
>a.py 1926/12/24
大正15年12月24日
>a.py 2007/12/01
平成19年12月1日
>a.py 1926/12/25
大正15年12月25日 昭和1年12月25日
>a.py 1868/1/2
範囲外
>a.py 1868/100/2
範囲外
see: 和暦西暦対応表
引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。
条件:
- スートは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
ここでいう法演算とは,与えられた数(ここでは「法」と言います)で剰余をとりながら行う計算のことです.たとえば,法が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桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません).
お題#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
一応、制約条件を示しておきます。
- あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります 。
- 同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
たとえば、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個の解答が得られました。
次のような書式で与えられた「あみだくじ」があります。 (あみだくじはコード中に埋め込んでも、標準入力や 外部ファイルから読み込んでも、書きやすい方法でかまいません) A B C D E | | |-| | |-| | |-| | |-| |-| |-| |-| | |-| | | | このあみだくじをたどって A B C D E | | |-| | |-| | |-| | |-| |-| |-| |-| | |-| | | | B D C A E のように結果を表示させるプログラムを作ってください。
与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを 書いてください。 文字列の検索方向は八方全てで、また連続している(左右や上下の境界をまたがない)ものを 対象とします。出力は起点"ウ"の座標と方向のリストにしてください。 サンプル入力: リオウウリウ ウオリウオリ オリリオリウ リリオオウオ サンプル出力: (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);
}
|
「この文は0が□個,1が□個,...,9が□個あります」 が正しくなるように□を埋めてください.数値は10進数とします. 一般のn(<=16で可)進数でも解いてみてください. たとえば2進数なら 「この文は0が11個,1が100個あります」 となります.
自然数nとm(n>=m>0)が与えられたとき,nをm個の非負の整数の和で表すやり方を全て出力してください. その際,和の組(x_1, ..., x_m)は大きい順に出力してください. ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは (a > A) (a == A) かつ (b > B) (a == A) かつ (b == B) かつ (c > C) のいずれかが成り立つとき(つまりは辞書的順序)とします. 例:n = 5, m = 3が与えられたときは 5, 0, 0, 4, 1, 0, 4, 0, 1, 3, 2, 0, 3, 1, 1, ... 0, 1, 4, 0, 0, 5, を出力する.
一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください. ただし,除算や剰余算を使わないで書いてみてください. sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく" divid 4 sample => "ゆめよりもはかなき世のなかを" "なげきわびつゝあかしくらすほ" "どに四月十よひにもなりぬれ" "ば木のしたくらがりもてゆく" divid 5 sample => "ゆめよりもはかなき世の" "なかをなげきわびつゝあ" "かしくらすほどに四月十" "よひにもなりぬれば木の" "したくらがりもてゆく" divid 6 sample => "ゆめよりもはかなき" "世のなかをなげきわ" "びつゝあかしくらす" "ほどに四月十よひに" "もなりぬれば木のし" "たくらがりもてゆく"
これは、実例を見た方が簡単だと思います。 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件出力されました。
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のときも求めよ.
このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。
与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。
以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では
reverseString("文字列(もじれつ)の反転(はんてん)")
→ ")んてんは(転反の)つれじも(列字文"
のように括弧の対応は保存されませんが、reverseString2 では
reverseString2("文字列(もじれつ)の反転(はんてん)")
→ "(んてんは)転反の(つれじも)列字文"
のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。
reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
→ "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"
入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、
reverseString2("これ(は(対応のとれていない)括弧がある例です。")
→ "。すで例るあが弧括(いないてれとの応対)は(れこ"
次のような場合は対応のとれている括弧はないという解釈になります。
reverseString2("これ(も{対応の)とれていない}括弧の例です")
→ "。すで例の弧括}いないてれと)の応対{も(れこ"
日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。
---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
「 ファイル内の重複行削除(後優先) 」の続編です。
1行あたり平均60文字のデータが書き込まれた、巨大なファイルがあるとします。どのくらい巨大かというと、積んでいるメモリの10倍程度の容量があります。このファイルから、同じ内容が書かれている行を取り除くプログラムを作ってください。ただし、同じ内容が書かれている行のうち、最後に出現したものを残すものとします。
このサイズのファイルを丸ごとメモリに読み込もうとしてしまうと、 スラッシング - Wikipedia が発生することが予想されます。そこで行単位で読み込もう、というのが前回のお題の趣旨でした。
しかし



ckbx #8053() Rating5/5=1.00
[ reply ]