最終更新: 2022-02-11T22:02+0900
先日解いていた「JOIG 2021/2022 本選競技課題」(テストケースのダウンロードができる) の F 問題へのこの提出に関して>20220129p01.05。
Hash#shift を意味がある限り繰り返したあとで Hash#clear を呼ぶようにしている(25 行目)。shift は破壊的なメソッドだから shift を十分に呼び出した後の Hash は空になっているはずで、clear を呼ぶ意味はなさそうに思える。それでも呼ぶようにしているのは、これがないとテストケースの in/05-01.txt に限ってスクリプトの応答がなくなって TLE になると思ったから。少なくともローカル Windows 環境では Ruby-2.7 と Ruby-2.5 で止まる。Ruby-1.9 は平気。他のテストケースでは止まらないけど、問題のケースでは必ず止まる。止まるタイミングはバラバラだけど、いずれも Hash への代入で止まっているようだった。
再現スクリプトはこんな感じ(これを見つけたから日記に書いている)。他所で再現するかは、どうでしょうね。
Many = 100 # 10 回では少ない。テキトーに大きく。
Some = 100 # ウチでは 30 回目までは到達しない。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
Some.times{|some|
warn "#{some} begin"
hash = {}
Many.times{
some.times{|j|
k = Random.rand 0..Many
hash[k] = 1 # maybe hang
}
0 while hash.shift
}
warn "#{some} end"
}
warn :exit
Ruby-2.5 と Ruby-2.7 では "N begin" (N は 20 前後) を表示して止まる。2.5 より 2.7 の方が早く止まるという傾向はあるけど、具体的な回数にはバラツキがある。それはまあ乱数を使ってるからだと思うけど、ハッシュのキーを k に代えて j にしたり、シャッフルした順列にしたりすると止まらなくなるので(正常動作)、乱数は外せない。
こういう Issue「Bug #17779: 特定の順序でHashのkeyを削除した場合に Hash#first が遅くなる - Ruby master - Ruby Issue Tracking System」を思い出したけど、全然関係はなさそう？ 全然わからない。
AtCoder のコードテストを使わせてもらったら(目的外失礼)、こういう結果。AtCoder の Ruby も今のバージョンは 2.7。
| 終了コード | 9 |
| 実行時間 | 10501 ms |
| メモリ | 9112 KB |
標準エラー出力は 30 begin で途切れている。完走しても 10 秒もかかるはずないから、ハングして実行を打ち切られたのだと思う。コードテストとジャッジサーバーが同じだとして、ジャッジサーバーのスペックはこう>Linux ip-***-***-***-*** 4.15.0-1041-aws #43-Ubuntu SMP Thu Jun 6 13:39:11 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux*⁑。
Ruby-3.1 が「ウチの Ruby」に今日加わりました。大体ループの 20 から 30 回目で止まるんだけど、弾みで 2 回だけ完走したりもした。
パラメータが２つもあると面倒なので。
改訂するにあたって予想外に止まらなくなったりした(正常動作)のを通して、たぶん直接的な原因もわかった。
# ウチではだいたい 20 から 30 回で "empty?: true" を最後にして止まる。
# ウチの Ruby-2.5: ruby 2.5.5p157 (2019-03-15 revision 67260) [x64-mingw32]
# ウチの Ruby-2.7: ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x64-mingw32]
# ウチの Ruby-3.1: ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x64-mingw-ucrt]
H = {}
100.times{|n|
while H.size < n
k = Random.rand 0..1<<30
H[k] = 1 # たぶんここで止まる。
end
warn "size: #{H.size} before shifting."
H.shift until H.empty?
raise if H.shift # no exception. だけど Hash が空になった後の shift が後でハングをひき起こす？
warn "empty?: #{H.empty?}"
}
warn :exit
Hash を空にする方法として 0 while H.shift を選ぶとその後の Hash#[]= でハングするが、Hash を空にする方法として H.shift until H.empty? を選ぶとハングしなかった。条件を揃えていくと、Hash#empty? が作用してハングを回避しているのではなく、Hash が空になったあとの Hash#shift がハングをひき起こしているようだった。ちなみに Hash#clear にハングを回避する効果があるらしいのは、JOIG の問題への提出で確認済み(とはもう書いた)。
投稿して次に見たときにはすべてが終わっていた。早いぜ。
こういう仕組みだったようです。
メモ：entries_bound は使用中のビン（DELETEDになったビンを含む）の数に（ほぼ）対応していて、これをみてテーブルをリビルドしている（rebuild_table_if_necessary）。空のハッシュに対する Hash#shift はなぜか entries_bound を 0 にしているので、リビルドすべきタイミングを逃し、ビンがすべて使用中になった状態で空きビンを探そうとするので無限ループに陥っていた（find_table_bin_ind）。
最終更新: 2021-06-11T11:27+0900
以前書いた。「最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな？ 右辺の一時記憶が必要？ 多重代入は遅くて時々評価順が難しい、というのが現在の評価。」「クイズです。a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあ」
そしてこの PR が多重代入について>Evaluate multiple assignment left hand side before right hand side by jeremyevans · Pull Request #4390 · ruby/ruby マージされている。
3.1.0 から変わりそう？ 評価順が変わってパフォーマンスがさらにちょっと遅くなる？ 新しい評価順っていうのが、
従来は２が最初にあって、１と３がインターリーブされていた。……ということが PR の概要欄と NEWS の修正に書いてある。
パフォーマンス劣化の理由は左辺の評価結果を一時的に蓄える必要があるからか？
いやあ、あっさり変えるし変えられるもんなんだなあ。まあたぶん、Ruby ユーザーの 1 % も変化に気がつかないだろうとは思う。
非効率だしバグらせやすいし、作り込む価値がないと言っている？
自分はもうこの仕様について(穴にはまった実体験から)知っているので、常に穴を意識して書くし、逆に評価順を利用することもあるけど、これまで幸運にも意識せずに来られた大多数のユーザーが、将来的潜在的には驚きとともに多重代入の評価順の詳細を理解させられるんだろうな、ということを考えると、「作り込む価値はある。ただしうまく実装できる限りにおいては」という評価が妥当かなと思う。
最終更新: 2020-12-08T00:48+0900
４月に「多重代入は遅くて時々評価順が難しい」と書いたけど、さらに難しいケースを考えた。クイズです。
a = *0..5 #=> [0,1,2,3,4,5] b = *0..5 #=> [0,1,2,3,4,5] a[i=2] #=> 2 b[j=2] #=> 2 a[i+=1] = a[i] # a はどうなる？ b[j+=1],= b[j] # b はどうなる？ a #=> [0,1,2,3,4,5] b #=> [0,1,2,2,4,5]
a の結果を確認してから予想してカンマを付けたら予想通りの結果になったので驚きはないけど、やっぱり普通の代入とは違うんだなあと、それが遅くなる理由かなあと、思いました。
ゴルファーしかこんなコードを書こうとはしない？ その通り。
最終更新: 2021-01-19T03:44+0900
最近こういう記事を読んだ(20200912p01)。「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita」
その少し前に雰囲気で書こうとしたけど、バランスの取り方に対する理解が雑で完成しなかった(20200604p01.04)。
Ruby の標準添付ライブラリにある SortedSet は内部構造がハッシュテーブルでありキーの順序付けが利用できない。ありていに言えばキーの二分探索をしたいができない。「RBTree ライブラリ (https://rubygems.org/gems/rbtree) が利用可能である場合、内部記憶としてハッシュの代わりに RBTree を使用します
」ということが書いてあるけど、RBTree が利用可能だったことがない。
性能はまったく期待できない。まったく。
注意すれば省メモリにはなるかもしれないけど、出し入れのたびに配列の全長のおよそ半分を右へ左へ動かしていたのでは、他に何も期待できない。
注意を要するのは rotate_l/rotate_r の実装。このとき(20200905p01.07)のように、不必要に膨大なメモリ要求が実行速度まで低下させかねない。
すばらしき(20200912p01.03) Array#fill メソッドにならって、Array#rotate も第２引数以降を使って対象範囲を受け付けたらいい。
内部構造は「社長から始めて決まったやり方で社員を一列に並べていったら、ある社員とその部下と部下の部下以下末端までを一定の連続する範囲で表せるのではないかと考えた。なんのことはないそれって深さ優先探索と同じ順番だったのだけど」(20200607p01.02)と書いたときのものと同じ。
その後の検索で「最小共通祖先 [いかたこのたこつぼ]」というページを見つけて、「LCA」「オイラーツアー」という用語を仕入れている。そんな感じの構造。
ちょっと待て、このドメイン名は……。20200905p01.03 で参照した AtCoder の ikatakos さんと同じでは？
苦労の 70 % くらいは sink と push の２メソッドを見出すところにあった気がする。実装することではなくシグニチャを発見するまでのところに。でも、どういう操作が必要か、どういう操作であれば十分か、実装を始めてデバッグをする過程でしか見つけられないジレンマ。
以前にも似たようなことを書いている。「メソッド名を決めるまでで 9割が終わってる。」 そのときはその後の検索で「最小全域木」「プリム法」「クラスカル法」という用語を仕入れてクラスカル法で再実装しているが、今回はどうか。AVL木とか赤黒木とか知らないよ？>「平衡二分探索木 - Wikipedia」
ソート列における順序と内部配列における添字という、２つの数字を元にして each メソッドが簡略化できそうな気がする。したい。
つまり、現在の向き(行きか帰りか)と次の添字がわかるならスタックがいらなくなる。開始点(最小値の添字)はもうわかっている。
あっ、これ二分探索のためにあらかじめ並べ替えたソート済み配列だ(いま気がついた)。Array#bsearch_index と Array#insert で済むものをよくも難しく書き直したものだ。
メモリブロックの移動を減らすためにギチギチに詰め込まないでルーズに管理しようとしたら、固定長の大きさを持っていて最大値と最小値で特徴付けられる疎な配列(リスト)の入れ子構造に行き当たって、ピボットはいらないな、そうするとこれ木じゃないな、ただの(入れ子になった)ソート列になっちゃったな、と。じゃあ原点に戻ってあれも(並べ方が素直じゃないだけの)ソート列だな、と気がついた次第。
持っていることも忘れていた『[単行本] K. メールホルン, P. サンダース【アルゴリズムとデータ構造―基礎のツールボックス】 シュプリンガー・ジャパン株式会社』をぱらぱらめくってると、(a,b)-木という構造があって、これは木の各ノードが最長で長さ b の子ノード列を持つらしくて、つまりは入れ子になったソート列なんだけど……。
入れ子になったソート済み配列もやっぱり木？
最終更新: 2013-04-15T03:23+0900
どうせ Rubyマクロはコマンドの先頭を小文字にする必要があって他のマクロと同じように書けないのだし、使われてないからこれまでに書かれたマクロ資産との互換性を図る必要もないし、例外とリークの元になり実行前の負荷も発生させる SCRIPTITEM_GLOBALMEMBERSフラグを落とすのがいいと思う。ScriptEngine名が "RubyScript." で始まるときとかに限って。
SCRIPTITEM_GLOBALMEMBERSフラグを落とすと $Editor.insTextだけのマクロは何十回でも問題なく実行できてるけど、それだけで安心してよいものか。Editorと書いたときのように(数字で始まるマクロコマンドを呼んだときも？)初回で確実に落ちるというだけならいいけど、何回も実行してるうちに運が悪ければ落ちるというのがあれば
最終更新: 2013-02-22T00:42+0900
日本語を含むフルパスを File.expand_pathすると、文字列そのものは変化しない(ように見える)のにファイルを見失う。
C:\>irb19
irb(main):001:0> File.directory? "C:/コピー"
=> true
irb(main):002:0> File.directory? File.expand_path "C:/コピー"
=> false
irb(main):003:0> "C:/コピー" == File.expand_path("C:/コピー")
=> true
irb(main):004:0> RUBY_DESCRIPTION
=> "ruby 1.9.3dev (2011-09-23 revision 33323) [i386-mswin32_100]"
irb(main):005:0> $:
=> ["C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby/1.9.1", "C:/Program Fi
les (x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby/1.9.1/i386-msvcr100", "C:/Program Files
(x86)/ActiveScriptRuby-1.9/lib/ruby/site_ruby", "C:/Program Files (x86)/ActiveScriptRuby-1
.9/lib/ruby/vendor_ruby/1.9.1", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/vend
or_ruby/1.9.1/i386-msvcr100", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/vendor
_ruby", "C:/Program Files (x86)/ActiveScriptRuby-1.9/lib/ruby/1.9.1", "C:/Program Files (x
86)/ActiveScriptRuby-1.9/lib/ruby/1.9.1/i386-mswin32_100"]
irb(main):006:0>
ところで Rubyは Unicode文字を含む(Shift_JIS(※)に含まれない文字を含む)パスを扱えるようになっているだろうか。方法はあるけどやり方を間違えていただけだろうか。
2009年に書いた自分のスクリプトをきちんと動くようにしようと引っ張り出してきた。Rubyの対象バージョンを 1.8から 1.9.3にして ruby-mp3infoを GitHubからダウンロードしてきた最新版に差し替えただけで肝心な部分はほとんど終了。それにしても、4年前の自分がきっちりボトムアップでプログラムを構造化していたことに驚いた。最近 PRS-650のために書いたスクリプトとは比べられない。Rubyは、こうあるべきと書き手が考えるソースコードの流れを比較的自由に表現できる言語であるから、言語の制約を気にせず頭の中に理想形を持っておくのが大事。クラス構文があるからクラスを作るんでなく、こう書きたいという欲求を満たす選択肢としてクラスがある。理想の有無が同じ書きたいように書いた結果に雲泥の差が生じる理由。忘れてた。
このバグだ。>Backport #5629: Windows環境で日本語を含むパスに対して、File.expand_path が存在しないパスを返すパターンが存在する。 - Backport93 - Ruby Issue Tracking System。一年前に 1.9.3にバックポートされて解決してる。Ruby-1.9.3-p385にアップデートするにはいいタイミングだったし、都合のいい理由付けになった。
似たような問題がまだ requireに残ってたみたい >Bug #7881: Windows でパスに日本語を含むスクリプトからの require が失敗する - ruby-trunk - Ruby Issue Tracking System
最終更新: 2013-03-03T06:08+0900
--- ruby-mp3info-master\lib\mp3info.rb~ Wed Feb 13 16:34:42 2013
+++ ruby-mp3info-master\lib\mp3info.rb Wed Feb 13 20:48:38 2013
@@ -272,7 +272,7 @@
next unless tag_value
@tag[key] = tag_value.is_a?(Array) ? tag_value.first : tag_value
- if %w{year tracknum}.include?(key)
+ if %w{year}.include?(key)
@tag[key] = tag_value.to_i
end
# this is a special case with id3v2.2, which uses
@@ -381,7 +381,7 @@
puts "@tag has changed" if $DEBUG
# @tag1 has precedence over @tag
- if @tag1 == @tag1_orig
+ if @tag1 == @tag1_orig && ! @tag1.empty?
@tag.each do |k, v|
@tag1[k] = v
end
@@ -418,7 +418,7 @@
((@tag1_orig["year"] != 0) ? ("%04d" % @tag1_orig["year"].to_i) : "\0\0\0\0"),
@tag1_orig["comments"]||"",
0,
- @tag1_orig["tracknum"]||0,
+ @tag1_orig["tracknum"].to_i,
@tag1_orig["genre"]||255
].pack("Z30Z30Z30Z4Z28CCC")
file.write(str)
Vistaの Windows Explorerでタグを書き換えると encoding_indexが 0(iso-8859-1)になるんだけど、これを信用して変換すると日本語文字が化けるので Windows-31Jにしてみた。
require "mp3info" ID3v2::TEXT_ENCODINGS[0] = "Windows-31J"
最終更新: 2011-10-01T04:28+0900
練習問題。それも Aだけ。Bは撃墜されました。
# small用
def last_output(n, k)
snappers = [false] * n
k.times{
# 電流をたどってひっくり返す。
0.upto(n-1){|i|
snappers[i] = ! snappers[i]
break if snappers[i] # previously OFF (=next snapper's IN was OFF)
}
}
return snappers.all?
end
# large用
def last_output(n, k)
# k1 = 2**n-1 # k1:最初に n個の snapperがすべて ONになる操作回数.
# k = p*k1+(p-1) を満たす自然数pが存在するなら電球は ON.
return (k+1)%(1<<n) == 0
end
caseno = 0
$stdin.readline; # drop # of cases.
$stdin.each_line{|ln|
n,k = *ln.scan(/\d+/).map(&:to_i)
break unless k
caseno += 1
puts "Case ##{caseno}: #{last_output(n,k)?'ON':'OFF'}"
}
最終更新: 2011-05-19T13:48+0900
7. In app code, never use force_encoding to convert BINARY data into a particular encoding. By the time you've reached app code, you have lost the information about which encoding is being used. Instead, find where the String came into Ruby, and fix it to set up the encoding based on the information it knows.
アプリケーションコードの場合、バイナリデータを特定のエンコーディングに変換するために force_encoding を決して使わないこと。アプリケーションコードをいじっているのであれば 使用されているエンコーディングに関する情報をたたくさん持っているはずである。 この場合、その文字列がどこからRubyにやってきたかを突き止め、わかっている情報に 基づいてエンコーディングを設定するように修正すること。
いまもって Ruby 1.9のエンコーディングに関するベストプラクティスがわからないので、すごくためになるリスト。7はこう理解した。
(文字列のエンコーディング情報が失われた)末端コードで、(その場で必要とされるエンコーディングに基づいて場当たり的に) force_encodingしないこと。その文字列の来歴をたどって一番根っこ(※ライブラリの修正が必要かも)で正しい情報(※ないのなら慣習に従うか、その不完全なプロトコルを捨てる)に基づいて force_encodingすること。(末端コードで必要に応じて行うのは encodeだったり encode!)
最終更新: 2011-04-16T21:35+0900
前にこうならんかな？って書いたのをもう一度。
require 'hoge'
したときに hoge.rbなり hoge.soなりが taintedな $LOAD_PATH要素に基づいて発見されたときは SecurityError。見つからなければ taintedな要素はスルー。という動作を Rubyに期待したい。今は taintedな $LOAD_PATH要素を無造作に File.expand_pathして SecurityErrorが起こるに任せているんではなかったか。
1.9.2では(確かめたわけではないけど)汚染されたパスの展開がセキュリティエラーにつながってるから、汚染されたパスが $LOAD_PATHの末尾にあった場合は $SAFE=1の状況下で require 'cgi'が成功する。require '存在しないファイル'はセキュリティエラー。汚染されたパスを基に展開を試行したかどうかが分かれ目。
1.8.7では $SAFE=1の状況下で汚染された文字列を引数にした File.expand_pathは 1.9.2と違い成功するものの、上のような場合でも require 'cgi'に失敗する。これは requireが内部的に File.expand_pathを呼び出し――これは 1.9.2とは違いセキュリティエラーを起こさないけれど 1.9.2同様汚染された文字列を返す――、その汚染された戻り値を使った require_internal(仮名)が 1.9.2とは違い $SAFE=1のときにセキュリティエラーを起こしてるのだと思う。挙動からの推測。
一貫性が欲しかったね。できれば実用的なものが。特定のディレクトリ(汚染された$LOAD_PATH要素)に特定の .rb, .soファイル(requireされたファイル)があるかないか判った(SecurityError or not)ところでどうだというの。
最終更新: 2011-03-15T00:15+0900
「HCF(n,d)=1」には用語の説明があると思ったんだけどなかった。n/dの nと dは最大公約数が 1の既約分数だとすると意味がとおるので HCF=Highest Common Factorだと決めた(でっちあげ)。
分数とはなんぞやだとか切断だとか小難しく考えてしまったが(実際には考えられるほど知らない)、ワンライナーだった。3/7より少し小さい100万個の分数を小数になおして、一番小さいものを見つける。有理数にして比較しないのは時間がかかるから。公約数をみつけたりする時間だろうか。
require 'rational'
p Rational(*(2..1_000_000).inject([0,1]){|answer,d|
answer[0]/answer[1].to_f < (d*3-1)/7/d.to_f ? [(d*3-1)/7,d] : answer
})
Project Euler Problem #71 « KeyZero Conversation
分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか！
分単位のお時間がかかります。(訳:一時間はかからないけど……)
何倍も速くなるので「Integer#prime_division」を使う代わりに 100万要素の配列を使ってる。トレードオフで使用メモリは数MBから 100MB超になるが。 小手先のチューンよりアルゴリズムを改良しろってのはもっともだけど、かなしいかな、できることとできないことがあるのです。
LIMIT = 1_000_000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
print d,"\r"
count += d-1 # 1) とりあえず d-1 通りの分子を計上し、
d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
# 2) 8分の6など通分可能なものを差し引きする。
(1..(pfs[d].size)).each{|r|
cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
count -= (-1)**(r%2+1) * cms.map{|cm| (d-1)/cm }.inject(&:+)
}
}
p count
Ruby 1.9からバックポートされてきた(のだと思われる見覚えのないメソッド) cycle, tap, combination, permutation, productといったメソッドが便利だ。あとは自然数を無限に生成し続ける無限リストのようなものをどれだけ簡単に書けるかだ。なにかショートカットがあるのだろうか。これでは長すぎる。
Enumerable::Enumerator.new(lambda{|&block| n=0; loop{ block.call n+=1 } }, :call).each{|x| p x }
それと、block.callの部分を yieldにできないのもわかりにくい。Procと blockと lambdaの微妙な違いによるものなのだろうか。
Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけど、カウンタが Floatになっちゃうのが不満。
1.upto(1/0.0){|n| p n }
あれ？ Fixnumだ。Floatになるのは stepだった。
1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...
明示的に Fixnumの増分: 1を指定しても n は Float. この違いはなんだろう。
cycleの使い道として zipを想定していたが拒否されてしまった。
irb> [1,2,3,4,5].zip([0]) => 1, 0], [2, nil], [3, nil], [4, nil], [5, nil irb> [1,2,3,4,5].zip([0].cycle) TypeError: can't convert Enumerable::Enumerator into Array from (irb):2:in `zip' from (irb):2 from :0 irb> RUBY_DESCRIPTION => "ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32]"
最終更新: 2012-11-01T13:41+0900
説明が面倒なのと誰も知りたくないだろうから適当に、備忘のためだけに。
%{literal} の literal部分で \{ や \} を使う人間がいるとは思わなかった。(違う種類の括弧を使えばいいじゃない。開閉の釣り合いがとれてれば同じ種類の括弧でもエスケープ不要だし)だのに Ruby1.9の rake.rbにこんなパターンが……
%r{[*?\[\{]}
%r{余分な開き括弧{。間違いはインタープリタを通す前から目立つように}
2のは Rubyインタープリタに対するエスケープ、と同時に正規表現パターンとしてのエスケープですよ。%r[\[] と /\[/ が同じパターンになって、%r[[] がRubyのシンタックスエラー、/[/ がパターンのコンパイルエラーになるんだから。(ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32] / ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-mswin32])
最終更新: 2010-04-22T02:07+0900
やってみた。Time.parseの問題がわからなかったのと、ブロック変数が外のローカル変数を変更してしまうかどうかという問題(Rubyのバージョンは？回答形式が)以外はたぶん問題なし。で、回答を送信すると一分かそれ以上待たされた後、「一度しか回答できません」だって。ええええ。たしかにそう書いてあるのは読んだけど、以前回答したことも忘れてるんですよ。そんなこと言われても。
そういう要求をするのも、それを額面通りに実施してしまうのも、ある意味感心するけど首を傾げてしまう。回答は適当に受け付けて、後でフィルタリングしてから利用すればいいじゃない。とここで「すでに受験した方は，前回の回答結果を参照できます。」とも書かれてるのに気付いた。ログインを要求されたから見られなかったけど、回答を(回答者の要求に応じて参照できるようにしながら)抱え続けるのって誰得？ Ruby検定の予想問題からのピックアップに過ぎないんですよ、この問題って。
回答形式が 一つ選べという問題だったのにチェックボックスが使われていた。他は問題形式によってラジオボタンとチェックボックスが適切に使い分けられていたから、出題形式を間違えたかフォームを間違えたか後でフォームだけ変更されたか。はてさて。
最終更新: 2013-08-20T01:04+0900
「makeplex salon：あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ」経由で「人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか」
粘菌でも迷路問題を解けるというのだから負けてはいられない。Rubyで一時間半弱かかった。
#! ruby
# coding: Shift_JIS
# 迷路データ
maze = <<MAZE
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
MAZE
# マップ
class Point
def initialize(x, y)
@x, @y = x, y
end
attr_reader :x, :y
def ==(other)
@x == other.x && @y == other.y
end
def to_s
"(#{@x},#{@y})"
end
def left
Point.new(@x-1, @y)
end
def right
Point.new(@x+1, @y)
end
def up
Point.new(@x, @y-1)
end
def down
Point.new(@x, @y+1)
end
end
class Map
def initialize(maze)
lines = maze.strip.split(/\r\n?|\n/)
@height = lines.length
@width = lines.first.length
y = -1
@map = lines.map{|line| y += 1
x = -1
line.split(//).map{|ch| x += 1
if(ch == 'G')
@goal = Point.new(x, y)
nil
elsif(ch == 'S')
@start = Point.new(x, y)
nil
elsif(ch == '*')
-1
else
nil
end
}
}
end
attr_reader :height, :width
attr_reader :start, :goal
def []=(point, value)
@map[point.y][point.x] = value
end
def [](point)
@map[point.y][point.x]
end
def up(point)
return -1 if point.y-1 < 0
return @map[point.y-1][point.x]
end
def down(point)
return -1 if self.height <= point.y+1
return @map[point.y+1][point.x]
end
def left(point)
return -1 if point.x-1 < 0
return @map[point.y][point.x-1]
end
def right(point)
return -1 if self.width <= point.x+1
return @map[point.y][point.x+1]
end
end
map = Map.new(maze)
#puts "width×height = #{map.width}×#{map.height}"
#puts "start:#{map.start} / goal:#{map.goal}"
map[map.goal] = 0;
#puts "goal=#{map[map.goal]}"
# 先端
nodes = [map.goal]
while node = nodes.shift
next if node == map.start
[node.left, node.right, node.up, node.down].each{|nxt|
case(map[nxt])
when -1
# 壁
when nil
# 未踏
map[nxt] = map[node] + 1
nodes.push(nxt)
else
# 既に到達したルートがある
if(map[node] + 1 < map[nxt])
map[nxt] = map[node] + 1
nodes.push(nxt) unless nodes.include?(nxt)
end
end
}
end
# Map to result
map.height.times{|y|
map.width.times{|x|
point = map[Point.new(x,y)]
print point == -1 ? '***' : ("% 3d"%point)
}
puts
} if false
result = maze.strip.split(/\r\n?|\n/)
node = map.start
until node == map.goal
[node.left, node.right, node.up, node.down].each{|nxt|
if(map[nxt] == map[node] - 1)
node = nxt
result[nxt.y][nxt.x] = '$'
break
end
}
end
puts result.join("\n")
ノードっていうのはひとマスのこと。「先端」っていうコメントが適当すぎる(植物では頂端分裂組織っていうらしい)。方針はゴールからスタートに向けて、一マス移動するごとに一ポイントを加算しながら全方位に触手を伸ばしていき、すでに他の触手が通過した道は、自分が最適な場合にのみ侵入するこの判断は不要。全ての触手が行き場を失うかスタートに到達するかしたら終了。スタートから一ずつ減っていく数字をたどると(一少ない数をもつ隣接マスが二つ以上あっても解答に求められていないので無視する)ゴールへ着き、それが最短経路(だったらいいな)。
最初は粘菌方式をまねようと思ったが、通路をすべて覆った状態からスタートして、スタートとゴールにつながっていない島を切り捨て、袋小路から撤退するのはいい。遠回りと近道を取捨選択するためにどういう評価をすればいいのかを決められなかった。どうすればいいの？粘菌は何を考えてる？例えば
二番目のリンク先のトラックバックを見てる。みんな優秀なのね、C++で一時間もかかってないし。何人かが言及している「BFS」。それって一般的知識？ 幅優先探索(Breadth-First Search)か最良優先探索(Best-First Search)の略だということはわかった。
壁のもつポイントを -1 に設定したことで、壁に侵入しないことを保証する when節を省略してもよかったんじゃないだろうか。気付くのが遅れたが。
ゴールにも $ って書き込んでら。(スタートには書きこまんように気をつけたんだが)
粘菌すごい。
培地に、三個以上の餌を置く。粘菌は迷路の実験のように最短距離を結ぶか？
結果は違った。
粘菌は、丸く、複数の経路を持つ管を作った。「最短経路だと一カ所故障したら必ず孤立する場所が出ます。だから粘菌は、一カ所が故障しても全体はつながり、なおかつ距離がなるべく短い経路を作ったのです」
部分部分がどういう反応をするとそういう結果になるんだろ？？？
粘菌の行動原理は、量子ドット間の近接場光を介したエネルギー移動プロセスに類似している
♭ BorsJoigreeBS GE VC KX LJ UZ ZY RW MS IS ML JE AL FWUN BR EJ AV DD XQ..
♭ ds14050解析班はどこだ？