Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

神奈川Ruby会議でペアプロ問題出した

先日行われた神奈川Ruby会議01 http://regional.rubykaigi.org/kana01/ 。
ここで行われた最初のセッションがペアプロ大会 http://regional.rubykaigi.org/kana01/contents/02_pair_programing.html だったんだけど、ここで出す問題を作るという大役を仰せつかった。

いろいろ悩んだ結果、ひねりのない、ストレートなコンピュータサイエンス問題にした。

当日までと当日は、問題を用意したり、当日悩んでいる人にヒントを出したり、前に出て解説したり。
必死というほどでもないんだけど、あんまり周りは見えていなくて。

終わるまで気づかなかったんだけど、出題される側の方々のなかに、コミッタ様を始めとして数多くのスーパープレイヤーがいて、なんかすごい空間だったんだなと、畏れ多いなと、いう感じがした。

幸い。私の実装は好評だったみたい。ほ。

念の為に書いておくと。
当日壇上で説明した通り、私の実装は実行速度という点では全然よろしくない。
実装が簡単になるようにという方向にフォーカスしていて、実行速度には全然フォーカスしていない。

問題の解説は、ヒントという形で問題ページからリンクされているので、そちらを。
実装例も、問題ページ問題ページからリンクされているので、そちらを。
足りてないのは解題か。

続きを読む

「中学入試から：図形と場合の数」の 実装リンク集

というわけで、解答リンク集と呼んだり実装リンク集と読んだりするいつものアレ。

前回は tweet をそのまま貼ってみたんだけど、今回は言語名とか書いていたもとの形式で。
どっちがいい？

まだ解いていない方は、
http://nabetani.hatenablog.com/entry/codeiq_countri_q1188
に問題が載っているので、まず解くところから。

CodeIQ で挑戦した方も、このブログで問題を知った方も、是非実装例を公開する方向で。

あっさり解けた方も、苦しんで解けた方も、他の方の実装を見ておくと良いと思います。
なるほどこう書くといいのかとか、いろいろね。

「中学入試から：図形と場合の数」の 解説・解題

CodeIQ に「中学入試から：図形と場合の数」という問題
https://codeiq.jp/ace/nabetani_takenori/q1188
を出した。

中学入試算数問題第5弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。

円周上を7等分する点を考え、順に点Aから点Gとします。
これらの頂点のうち A,C,E,G から3点を選び、この3点を頂点とする三角形を考えます。
作ることのできる三角形は、何種類あるでしょうか。
ただし、裏返さずに回転してぴったり重ねられる三角形は、同じ種類とします。

この問題を

円周上を【あ】等分する点を考え、点の名前を点A, 点B, ... と順につけます。
これらの頂点のうち【い】から3点を選び、この3点を頂点とする三角形を考えます。
作ることのできる三角形は、何種類あるでしょうか。
ただし、裏返さずに回転してぴったり重ねられる三角形は、同じ種類とします。

と考え、【あ】、【い】を入力として与えます。問題の答えを計算するプログラムを書いて下さい。

■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
これらのファイルの各行は
　「データID、【あ】の内容、【い】の内容、【あ】【い】の内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。

■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・辺の長さが 3, 4, 5 の三角形と 5, 4, 3 の三角形は裏返さないと重ねられれないので同種とみなしません。
・間違いの数は、5件より多く、20件より少なくなっています。

■資料
http://nabetani.sakura.ne.jp/codeiq/q1138.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.txt
　→ 調査対象およびテストデータです。

■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

続きを読む

「中学入試から：数字の個数」の実装例リンク集

毎度恒例実装例リンク集です。

今回はツイートをそのまま置く感じで。



事前に解けた方も、実装しようと努力して力尽きた方も、他の方の実装を見ておくといいと思う。
あと。解けた方は、是非解けてない方のためにも公開する方向で。

まだ解いていない方は、
http://nabetani.hatenablog.com/entry/codeiq_digicount_q1138
に問題が載っているので、まず解くところから。

「中学入試から：数字の個数」の 解説・解題

CodeIQ に「中学入試から：数字の個数」という問題
https://codeiq.jp/ace/nabetani_takenori/q1138
を出した。

中学入試算数問題第4弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題が出ることがあります。

整数aのなかに現れるnの個数を《a, n》と表します。
例えば
《110, 0》=1
《1112, 1》=3
《1234, 5》=0
《141421, 4》=2
です。
このとき、100から200までの整数の中に現れる 2 の個数の合計、つまり
《100, 2》+《101, 2》+ … +《200, 2》 を求めなさい。

この問題を

整数aのなかに現れるnの個数を《a, n》と表します。
例えば
《110, 0》=1
《1112, 1》=3
《1234, 5》=0
《141421, 4》=2
です。
このとき、AからBまでの整数の中に現れる C の個数の合計、つまり
《A, C》+《A+1, C》+ … +《B, C》 を求めなさい。

と考え、A, B, C を入力として与えます。問題の答えを計算するプログラムを書いて下さい。

■具体的な課題

下記リンクの zip 内に data.txt というファイルがあります。
これらのファイルの各行は
　「データID、空欄A〜Cの内容、空欄A〜Cの内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。

■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。
・空欄A〜C は、空白なしのコンマ区切りでならべられています。
・0<A、A+1<B<(10の18乗)、A, B はいずれも整数、C は0〜9 のいずれかです。
■資料
http://nabetani.sakura.ne.jp/codeiq/q1138.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.txt
　→ 調査対象およびテストデータです。

■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

続きを読む

FileReader が必ず close されるのかどうかの続き

FileReader が必ず close されるのかどうかの続き

FileReader が必ず close されるのかどうか ( http://nabetani.hatenablog.com/entry/2014/10/24/003239
)の続き。

結論

結論から書いてみる。

// 「BufferedReader に任せた」版
try (BufferedReader br = new BufferedReader(new FileReader(path))) {
  // do something.
}

// 「FileReader close しすぎ」版
try (
  FileReader fr = new FileReader(path);
  BufferedReader br = new BufferedReader(fr)
) {
  // do something.
}

のどちらも正当。

私の場合

  • 仕事で製品に入れるなら「FileReader close しすぎ」版を好む
  • CodeIQ の解答とかに書くなら「BufferedReader に任せた」版を好む

と思う。

とはいえ、java.nio.file.Files.newBufferedReader が使えるのなら、そのほうが良い。

私について

実は。業務での Java 歴は1年ぐらいしかない。
CodeIQ で出す問題では、必要ならちゃんとコードを読む言語に入れているけど、正直あんまり自信がない。

状況をもう一度整理

「BufferedReader に任せた」版でマズイことが起こる条件は

A0. BufferedReader の new ( コンストラクタの前 ) でエラーが発生する
A1. BufferedReader のコンストラクタ内で例外・エラーが発生する
B. A で発生した例外・エラーがキャッチされ、処理が続く
C. リークしたハンドルが GC で回収されずに貯まる

という条件の組み合わせ( ( A0 or A1 ) and B and C ) が真になる場合に限られる。

順に見ていこう。

A0. BufferedReader の new ( コンストラクタの前 ) でエラーが発生する

これが発生するのはひどくまずい状況に限られる。
これが発生しない前提の仕事も多いと思う。
発生するのはメモリ不足だけなのか、クラスローダーとかが例外を投げることもあるのか、そのあたりはよくわかっていないんだけど、いずれにせよ、プロセスごと死んでもいい場合が多いと思う。

A1. BufferedReader のコンストラクタ内で例外・エラーが発生する

一方。
BufferedReader のコンストラクタ内には

new char[8192];

のようなことが書いてあり、状況によってはメモリ不足エラーは視野に入れておくべきだと思う。
※ 例外( Exception ) は発生しない。

B. A で発生した例外・エラーがキャッチされ、処理が続く

CodeIQ の問題を解いているとかいう状況なら、エラーはキャッチされずにそのままプロセス終了になる。
問題ない。

一方。
ウェブサービスを動かしているとかいう状況だと、フレームワークにキャッチされる場合も多いと思う。
キャッチされたら即プロセス終了ということならそれで問題ないんだけど、スレッド終了とかいうことになると close されない FileReader が残ることになる。

C. リークしたハンドルが GC で回収されずに貯まる

GC で FileReader が回収されると、FileReader の中にある FileInputStream の finalize で、必要な close が呼ばれ、ファイルハンドルも回収される。と思う。（合ってる？）

「BufferedReader に任せた」版の実装は、FileReader への参照がなくなっていることがすごくわかりやすいので早い段階で GC されると想像する。

結局どうなの？

これが原因で具体的にマズイことになることは極めて稀だと思う。
実際に発生する環境が用意できる気がしない。
稀とはいえ、私の理解が正しければ、「BufferedReader に任せた」版 だとトラブルになり、「FileReader close しすぎ」版 だとトラブルにならないという状況がありうる。

一方。「FileReader close しすぎ」版 は、正常系では FileReader を close しすぎていて、実行速度面でもメモリフットプリントでももったいない感じではある。

というわけで、どちらもメリット・デメリットがあるのでケースバイケースで使い分けるというのが正解だと思う。

で。
具体的には。
ウェブサーバー内で動くとか、組み込み機器内で動くとか言うことなら、「FileReader close しすぎ」版 がよい場合が多いと思う。
デスクトップアプリケーションなら、「FileReader close しすぎ」版 が良い場合が多いと思う。

ケースバイケースなんかめんどくさいからどっちかに決めたい、ということなら、「FileReader close しすぎ」版 が良いと思う。
「常にちょっと close しすぎ」と、「極稀にファイルハンドルリークするかも。しないかも。」だと、前者のほうがマシだと感じる。

とはいえ結局。
nio を使え、ということだと思う。

最後に

識者のツッコミお待ちしております。

追記

どうも、上記話は正しくなさそうな感じ。Java 難しい。

FileReader が必ず close されるのかどうか。

Java で、

try (BufferedReader br = new BufferedReader(new FileReader(path))) {
  // do something.
}

というような記述をよく見る。
実際、上記のコードは Oracle 様 のサイト
http://docs.oracle.com/javase/jp/7/technotes/guides/language/try-with-resources.html
から連れてきたもの。

しかし。これって、 BufferedReader のコンストラクタとかその直前にあるはずのメモリ確保とかが例外を発生させると FileReader が close されないよね。

というわけで、

try (
  FileReader fr = new FileReader(path);
  BufferedReader br = new BufferedReader(fr)
) {
  // do something.
}

と書くべきだと思うんだけど、どうなんだろ。

以下、10/24の 午前1時ごろ更新

で。
Twitter に

と書いたところ、教えていただいたので tweet をはっておく。

どうも、try に両方書くのが厳密には正解だけど、書いても意味がある場合が稀なので最初に上げた例のように書くことが多い、ということみたい。

以下、10/24の 19時ごろ更新

さらに情報を頂いたので貼ります。張ります。

BufferedReader のコンストラクタ内で例外が発生するのが「対応不可能」だったり「保証のない特殊な状況」だったりするということみたい。
私は Java力不足で判断は保留。
少しずつ調べていこうと思っている。

それと。


nio なら迷いがないということみたい。
なるほど。

そして続編
FileReader が必ず close されるのかどうかの続き - Codeへの愛とCuriosity
。