Language detail: C++ - 's unsolved challenges
入力の'('と')'の対応をとってください。
ただし、コード中に'('と')'を含まないでください。
漢字の九九に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
|
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
|
'tail'を実装してください。
巨大なファイルでも効率的に動作するようにしてください。
最低限必要な機能は、
- 行数指定
- 「-f」パラメータの対応
です。
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
|
スペースやインデントなど、本来は必要なく開発効率を上げるために記述が許可されている項目について、 それらを可能な限り減らし、コードを短くするコード書いてください。 また、投稿時に対象とする言語と、実際の処理結果を記載できるとわかり易いかと思います。 以下詳細 ・全てを行う必要はありません、どこまで行うかは任意です。 ・ローカル宣言など、消しても動作に関係のない構文の削除や置き換えを行っても構いません。 ・必ず同じ入力に同じ結果が返るのであれば処理内容を変えることもかまいませんが、推奨・強制はしません。 ・コンパイラや実行環境に依存する圧縮は避けてください。
整数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
標準入力から与えられたソースコードの変数名
を置換するプログラムを作ってください。
最近はリファクタリングツールなどの普及でこ
のような需要は少ないかと思われますが、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;
}
see: Wikipedia 閏年
nを入力としてn年の年間カレンダーを返すプログラムを作ってください
少なくとも日曜日と土曜日が判別出来るようにしてください
出力は標準出力でもファイルでも構いません
デザインは各自のお好みで
出力例1:
(y-calendar 2008)=>
#=Saturday, @=Sunday
2008/1 1 2 3 4 #5 @6 7 ...
2008/2 1 #2 @3 4 5 6 7 ...
...
2008/12 1 2 3 4 5 #6 @7 ...
出力例2:
(y-calendar 2008)=>
M T W T F S S M
2008/ 1 1 2 3 4 5 6 7 ...
2008/ 2 1 2 3 4 ...
...
2008/12 1 2 3 4 5 6 7 8 ...
出力例3:
(y-calendar 2008)は2008.htmlを出力する
2008.htmlの中身
----
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>2008 calendar</title>
<style type="text/css">
* {font-family: monospace;}
span {margin: 0px 3px;}
span.sunday {color:red;font-weight:bold;}
span.saturday {color:blue;font-weight:bold;}
dd ul li{display:inline;}
</style>
</head>
<body>
<h1>2008 calendar</h1>
<dl>
<dt>2008/1</dt>
<dd><ul>
<li><span class="weekday">1</span></li>
<li><span class="weekday">2</span></li>
<li><span class="weekday">3</span></li>
<li><span class="weekday">4</span></li>
<li><span class="saturday">5</span></li>
<li><span class="sunday">6</span></li>
...
</ul></dd>
...
</dl>
</body>
</html>
----
スレッドプールに複数のワーカスレッドが待機しており、メインスレッドはいつでもワーカスレッドに仕事を渡せるような状態になっているとします。
さて、メインスレッドからスレッドプールにいくつか仕事を与え、メインスレッドは与えた仕事すべてが終了するまで待機し、次の処理に行ってはいけない、というようなコードを書いてください。 ＃現実に書く機会が多そうなコードですね…。
ここでの仕事の内容は、適当に5秒から15秒の間スレッドをスリープする、というもので結構です。 また、ワーカスレッドのスレッドプール自体の使用を終了するか、または残して再利用するかは問いません。できればコメントにスレッドプールを残したかどうかを書いてください。
お題#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番目の最大公約数を求めたときのループ回数を教えてください
- 標準でついている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)?)?)
|
与えられた四字熟語のリストから下のように四角く配置することのできる熟語の組み合わせを探すプログラムを作成してください。
出力例:
無憂無風 礼 林 千 火 万水千山 知行合一 者 筆 不 勾 言語道断
四字熟語は左から右、上から下へ読むものとします。また右上隅の漢字と左下隅の漢字は異なるものでなければいけません。
四字熟語のデータは扱いやすい形(たとえばユニコード文字列のリスト)で与えられていると仮定して構いません。サンプルデータが必要であれば FOR Microsoft IME The四字熟語辞典(データ / 文書作成) にテキスト形式のデータが入っているのでそれを使えると思います。
問題の規模の参考までに、40行程度のPythonスクリプトでこのデータ(重複をのぞいて8312件)を処理してみたところ2.4GHzのCPUで13秒程度かかりました。結果は8133件出力されました。
与えられた文字列を前後反転する関数 reverseString2 を書いてください。
ただし、reverseString2 は単純に文字列を反転するのではなく、括弧の対応
を保存するようにしてください。
以前のお題で作成した単純に与えられた文字列を単純に前後反転したもの返す
reverseString では
reverseString("文字列(もじれつ)の反転(はんてん)")
→ ")んてんは(転反の)つれじも(列字文"
のように括弧の対応は保存されませんが、reverseString2 では
reverseString2("文字列(もじれつ)の反転(はんてん)")
→ "(んてんは)転反の(つれじも)列字文"
のように括弧の対応が保存されます。
括弧文字は、'('と')'、'{'と'}'、'['と']'で、それぞれASCII文字と仮定し
てください。
reverseString2("対応[の{とれている(さまざまな)括弧}の(例)]です。")
→ "。すで[(例)の{弧括(なまざまさ)るいてれと}の]応対"
入力文字列では対応の取れている括弧の内側には対応の取れない括弧文字はな
いと解釈してください。たとえば、
reverseString2("これ(は(対応のとれていない)括弧がある例です。")
→ "。すで例るあが弧括(いないてれとの応対)は(れこ"
次のような場合は対応のとれている括弧はないという解釈になります。
reverseString2("これ(も{対応の)とれていない}括弧の例です")
→ "。すで例の弧括}いないてれと)の応対{も(れこ"
日本語対応にする場合の文字のエンコーディングは実装側で都合のよいように
仮定してください。日本語対応であることは望ましいですが、必須ではありま
せん。
---
このお題はnobsunさんに投稿いただきました。ご協力ありがとうございます。
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さんからの投稿です。ご投稿ありがとうございました。助かります。
Pythonで34行のスクリプトを書いて得られた出力の例が下のようになります。
37 199148647.999978 58 24591257752.000000 67 147197952743.999999 163 262537412640768744.000000この問題は光成さんに教えて頂いた e^{π*sqrt{163}}≒26253741640768744 が元になっています。ご協力ありがとうございました。
また、ユーザの入力注の<br>は<br/>に変換してください。
このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。
- 通すタグは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>
詳しい導出方法は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]
このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。
分散関数呼び出しを実装してください． 呼び出される関数は，定価を整数で，割引率(%)を整数で受け取り， 文字列で「販売価格 ○円（定価○円から○%引き）」を返すものとします． また，数字は3桁のカンマ区切りにするものとします． たとえば，pricestring(2000, 20) なら "販売価格 1,600円 (定価2,000円から20%引き)" を返します． 関数の呼び出し元と，呼び出される側は，物理的に異なる サーバに配置できることを条件とします． 呼び出し方法は問いませんが，呼び出し方法に名前がある場合， それをタグに加えてください． （XML-RPC，SOAP，CORBA，RMI，など） また，作成した関数を直列に1万回呼び出して， 実行にかかった時間を測定してください． 測定時は別サーバでなくても構いません． （なるべく別サーバが望ましいです） 測定環境として， ・サーバとクライアントのCPU・メモリ ・同一サーバ内での実行か別サーバでの実行か ・別サーバの場合，通信経路．（100Mbps Ethernet等） ・言語のバージョン ・ミドルウェアを使用している場合，その名前とバージョン も併記してください． 1つの言語で複数の分散関数呼び出しの実装方法がある場合， 複数の回答を歓迎します． 出題の意図は，様々な分散呼び出し方法の実装例と， レスポンス速度の確認にあります．このお題は沢渡 みかげさんの投稿です。 まったく手を加えないでいい完成度の投稿で本当に助かります。 ありがとうございました。
ソースコードの複数行にまたがる範囲を、範囲の前後に何かを書き足すだけで実行しないようにしてください。 「その範囲を削除する」などはダメです。 何重まで入れ子にできるか、どのような制限があるかを明記してください。 例えばJavaであれば/*～*/で複数行のコメントアウトができますが、入れ子/* /* */ */にできません。 Pythonであれば"""～"""で文字列化することでコメントアウトでき、'''～'''も使えるので2重まで入れ子にできます。
このお題は、無制限に入れ子にできるCommon Lispからの挑戦状です。 プログラミングシンポジウムで前田敦司先生の発表を聞いて思いつきました。
アクセスログの各行の先頭にIPアドレスがあります．そのIPアドレスを逆引き結果のFQDNで置き換えてください．
逆引きが出来なかった場合は，IPアドレスのまま残します． IPアドレス以外の部分は，そのまま加工せずに残してください．
----
例）192.168.7.1 が逆引きできない場合
210.166.209.71 - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
↓
mikage.to - - [26/Jul/2007:22:32:47 +0900] "GET / HTTP/1.1" 403 283 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
192.168.7.1 - - [26/Jul/2007:22:32:48 +0900] "GET /favicon.ico HTTP/1.1" 404 290 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.8.1.5) Gecko/20070713 Firefox/2.0.0.5"
----
アクセスログは膨大な量があるため，現実的な時間で処理できるよう，以下の条件をつけます．
・メモリに入りきらないような巨大なログも処理できるようにしてください．（ファイル全体をメモリに読み込むのはNG）
・十分な速度で処理できるよう，並列化する等の工夫をしてください．
・DNSサーバに大量のリクエストが行かないよう，結果をキャッシュしてDNSサーバへのアクセスを削減してください． なお，DNSのTTLは無視して結果をキャッシュしてかまいません． （ログの記録された時間の逆引きするタイミングがずれているため，正確な逆引きは元々無理なので）
名前解決はgethostbyaddrを利用しても良いですし，再帰的に名前解決が出来るDNSサーバと直接通信してもかまいません．
ログを順次読み取り処理する部分を，データを共有しつついかに並列化するか，という部分を問うのが目的です．
このお題は沢渡みかげさんの投稿です。ご投稿ありがとうございます。
Ruby で表現すると、 以下のような「fooという関数を呼び出す関数」#bar、#bazがあるとき
def bar; foo end def baz; foo endこのbar, bazの返り値が以下のようになるような関数fooを定義してください。
bar #=> "bar" baz #=> "baz"
このお題は匿名の「Smalltalk からの挑戦状」を元に作成しました。 確かにこの手のリフレクションの機能が言語によってどう違うのかは興味深いところです。 リフレクションを使う問題をいくつか考えてみたいと思います。 ご投稿ありがとうございました。
----テンプレート----
From: [[from]] To: [[to]] Subject: [[name]]さんにメッセージが届いています [[name]]さんに[[fromname]]さんからメッセージが届いています。 以下のURLからアクセスできます。 [[url]]----テンプレート----
----差し込みデータ----
from => 'from@example.org', to => 'to@example.org', name => 'どう書く', fromname => '管理者', url => 'http://ja.doukaku.org/',----差し込みデータ----
----出力----
From: from@example.org To: to@example.org Subject: =?ISO-2022-JP?B?GyRCJEkkJj1xJC8kNSRzJEslYSVDJTshPCU4JCxGTyQkJEYkJCReJDkbKEI=?= Date: Fri, 13 Jul 2007 22:27:32 +0900 Message-ID: <0.1184333252.27836.123@example.org> MIME-Version: 1.0 Content-Type: text/plain; charset="ISO-2022-JP" Content-Transfer-Encoding: 7bit どう書くさんに管理者さんからメッセージが届いています。 以下のURLからアクセスできます。 http://ja.doukaku.org/----出力----
※実際の上記出力の日本語部分の文字コードはISO-2022-JPです．
差し込みタグの形式は[[名称]]でなくてもかまいません．
言語標準以外のライブラリを使った場合，それをタグに書いてください．
このお題は沢渡みかげさんの投稿を元にHTMLタグなどを付加したものです。 サンプル入出力までそろった投稿で非常に助かりました。ありがとうございます。
追記：補足があったのでこちらもご覧ください。 出題の意図(埋もれないように)
この二つの長方形が重なっているかどうかを判定するコードを書いてください。なお辺で接する場合(例えば(0, 0, 100, 100)と(100, 0, 200, 100))は重なっていないものとします。
なお変数名に関して、例えば1番目の長方形の左上隅x座標がleft[0]なのかleft1なのか、それともrect1.leftなのかは自由に選んで構いません。
支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。
例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。Pythonで表現するならば下のような挙動をする関数を作ってください。
>>> pay(147, {1: 2, 10: 4, 100: 3})
{1: 2, 100: 2}
2007-07-01追記： minkeさんの指摘通り、「手元にある全てのコインを渡せば、結果としてもっとも枚数が少なくなる」
ので、「渡した硬貨がおつりで返ってくるような渡し方は禁止」と条件を追加します。
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 ]