DouKaku? Language detail: Other - 's unsolved challenges

島の数をカウントする (Nested Flatten)

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

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

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

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

行列式の計算 (Nested Flatten)

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)

入力の'('と')'の対応をとってください。

ただし、コード中に'('と')'を含まないでください。

漢字の九九にinspireされました。

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 - トラックバックを打つ (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

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'を実装してください。

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

最低限必要な機能は、

上下スクロール
検索

です。

LL Golf Hole 1 - tinyurl.comを使ってURLを短縮する (Nested Flatten)

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スクリプト

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

環境変数の取得 (Nested Flatten)

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

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

コード圧縮 (Nested Flatten)

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

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

コメントの削除 (Nested Flatten)

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

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

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

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

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

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

参考；Wikipedia 頻度分析

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

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)

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

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

自分自身のファイル名を知る方法 (Nested Flatten)

自分自身のファイル名を知る方法を示してください。

ビルド後のファイルが、hogehoge.exeであれば、
”hogehoge.exe”が表示されるようなプログラムを書いてください。
スクリプト言語でも同様です。

ファイル名が変更されたらそれに追従するようにしてください。

see: #3301

不動点演算子 (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のプロセスが立ち上がり、指定したコマンドを実行することが条件です。

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

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

西暦 to 和暦 (Nested Flatten)

西暦を和暦に変換するプログラムを書いてください。元号の切り替わる日など、複数の表記が可能な場合には両方表示し、西暦が無効な日付の場合には「範囲外」と表示するようにしてください。対応すべき日付は明治元年以降とします。

>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: 和暦西暦対応表

ワーカスレッドを安全に終了させるまで待機 (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

与えられた並べ替えを実現するあみだくじの生成 (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)

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

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個の解答が得られました。

正整数のゲーデル数化？ (Nested Flatten)

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数
goedel を定義してください．

ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk]
をなすとし，dk が 1 の位，d1 が 10^(k-1) の位です．また，pk は k番目の素数です．

goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108

see: ゲーデル数

文字列の八方向検索 (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: ヤング図形

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

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

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

自然数の分割 (Nested Flatten)

自然数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,
を出力する．

四字熟語パズルの作成 (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)

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

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

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

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

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

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

制限時間内のキー入力検査 (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さんの投稿です。ご協力ありがとうございます。

改行をBRタグに置き換える (Nested Flatten)

一部のHTMLタグを通すフィルタどう書く？の続編です。前回の条件を満たしつつ、入力中の改行を<br/>に置き換えてください。ただし、たとえば"<a\nhref=...>"といったようにタグの中に改行がある場合、単純に置換するわけには行かないことに注意してください。

また、ユーザの入力注の<br>は<br/>に変換してください。

このお題はperezvonさんの提案を元にした三部作の二問目です。ご協力ありがとうございました。

立方根の計算 (Nested Flatten)

xは0以上1000未満の実数です。 y * y * y = xになるような実数y(立方根)を小数点以下12桁以上の正確さで求める関数cube_rootを作って下さい。

ただし、このお題の趣旨は実数区間での探索なので、立方根関数があっても使ってはいけません。指数関数と対数関数も禁止します。

Pythonで表現した入出力の例：

>>> cube_root(10.0)
2.1544346900318834
>>> _ ** 3
9.9999999999999947
>>> cube_root(100.0)
4.6415888336127793
>>> _ ** 3
100.00000000000003

一部のHTMLタグを通すフィルタ (Nested Flatten)

ユーザが入力した文字列から、一部のタグだけを許可して他をエスケープするコードを書いてください。要件は次のようになります。

通すタグはAとBRとSTRONGのみ。大文字小文字は区別しない。
それ以外のタグとして意味を持ちうる文字列は<を<に変換することで無効化する(削除するのではない。>は変換してもしなくてもよい)
Aタグのhrefとname以外の属性は削除する。BRやSTRONGの属性はすべて削除する。

このお題はperezvonさんの提案を元にしています。ありがとうございました。ただ、いきなりだと難しいかと思ったので、肝の部分以外を先に出題しました。このお題は続編で徐々に難しくなっていきます。

追記：属性に<や>が含まれてしまうケースに漏れのある解答が多いようなのでテストケースを追加します。
これは「この出力なら十分」という意味です。この出力の通りでなければいけないという意味ではありません。

<script foo="<script>alert('bar')</script>">alert('foo')</script>
&lt;script foo="&lt;script&gt;alert('bar')&lt;/script&gt;"&gt;alert('foo')&lt;/script&gt;


<script foo="<a href='link'>link</a>">alert('foo')</script>
&lt;script foo="&lt;a href='link'&gt;link&lt;/a&gt;"&gt;alert('foo')&lt;/script&gt;

<a href='www.g>oogle.com'>link</a>

<a href="./www.g%3Eoogle.com">link</a>

文字列からの情報抽出 (Nested Flatten)

与えられた文字列から特定の条件を満たす文字列を抽出するコードを書いてください。状況としてはテキスト形式で渡された原稿の中から、画像のファイル名を抽出するようなものをイメージしてください。

サンプル入力

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からの挑戦状です。

PageRankの計算 (Nested Flatten)

ページランク - Wikipediaを求めるプログラムを作ってください。(PageRankはGoogleの商標です)

詳しい導出方法は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]

このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。

分散関数呼び出し (Nested Flatten)

分散関数呼び出しを実装してください．

呼び出される関数は，定価を整数で，割引率(%)を整数で受け取り，
文字列で「販売価格 ○円（定価○円から○%引き）」を返すものとします．
また，数字は3桁のカンマ区切りにするものとします．

たとえば，pricestring(2000, 20) なら
"販売価格 1,600円 (定価2,000円から20%引き)"
を返します．

関数の呼び出し元と，呼び出される側は，物理的に異なる
サーバに配置できることを条件とします．
呼び出し方法は問いませんが，呼び出し方法に名前がある場合，
それをタグに加えてください．
（XML-RPC，SOAP，CORBA，RMI，など）

また，作成した関数を直列に1万回呼び出して，
実行にかかった時間を測定してください．
測定時は別サーバでなくても構いません．
（なるべく別サーバが望ましいです）

測定環境として，
・サーバとクライアントのCPU・メモリ
・同一サーバ内での実行か別サーバでの実行か
・別サーバの場合，通信経路．（100Mbps Ethernet等）
・言語のバージョン
・ミドルウェアを使用している場合，その名前とバージョン
も併記してください．

1つの言語で複数の分散関数呼び出しの実装方法がある場合，
複数の回答を歓迎します．

出題の意図は，様々な分散呼び出し方法の実装例と，
レスポンス速度の確認にあります．

このお題は沢渡みかげさんの投稿です。まったく手を加えないでいい完成度の投稿で本当に助かります。ありがとうございました。

全ての組み合わせ (Nested Flatten)

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

与えた条件を満たす候補 (Nested Flatten)

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。ご投稿ありがとうございました。
元ネタの充足可能性問題 - Wikipedia は、同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

モノクロ画像の類似検索 (Nested Flatten)

1024 * 768のサイズのモノクロ二値画像が100枚あるとします。その中の一枚を指定したときに、その画像以外で一番その画像に似ている画像を見つけるコードを書いてください。なお、同じ位置のピクセルが同じ値であるほど「似ている」とします。

説明のために2*3のサイズで説明します。

画像1
■■■
■■■

画像2
□□□
□□□

画像3
■■■
□□□

指定された画像
■■■
■□□

この場合、画像1とは4つのピクセルが同じ値なので類似度は4、画像2との類似度は2、画像3とは上半分の3つと下半分の白2つが一致するので類似度は5、よって一番類似しているのは画像3となります。

このお題の趣旨は検索処理の実行速度にあるので、実行してみて実用的な速度で動くことを確認することを強く推奨します。可能であればマシンのスペックと実行にかかった時間を書いてもらえると参考になっておもしろいと思います。

なおこのお題はC言語からスクリプト言語への挑戦状です。スクリプト言語に有利な問題が多すぎるので、この手の問題も大募集します。

「組合せ型の最小完全ハッシュ関数」の逆関数 (Nested Flatten)

まずは最小完全ハッシュ関数の作り方の後半部分をご覧ください。

「組み合わせ型の最小完全ハッシュ関数」とは下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)

>>> for xs in make_perm(5, 2):
	print xs, "=>", hash(xs, 5, 2)

	
[1, 1, 0, 0, 0] => 9
[1, 0, 1, 0, 0] => 8
[1, 0, 0, 1, 0] => 7
[1, 0, 0, 0, 1] => 6
[0, 1, 1, 0, 0] => 5
[0, 1, 0, 1, 0] => 4
[0, 1, 0, 0, 1] => 3
[0, 0, 1, 1, 0] => 2
[0, 0, 1, 0, 1] => 1
[0, 0, 0, 1, 1] => 0

「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)

さて、ここからが本題です。組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。

このお題はshuyoさんの提案を元に作成しました。ありがとうございました。