Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/bin/ruby
# coding: utf-8
require 'readline'
require 'yaml'
require 'optparse'
$opt = Hash.new
$opt[:shuffle] = true
OptionParser.new do |x|
x.on("--state-file=FILE", String, "State file") do |f|
$opt[:state] = YAML.load(File.open(f, "r").read)
end
x.on("--max-selections=NUMBER", Integer, "Maximum number of choices to ask you") do |m|
$opt[:max_sel] = m - 1
end
x.on("--[no-]shuffle", "(Don\'t) shuffle the list before sorting") do |x|
$opt[:shuffle] = x
end
end.parse!
module InteractiveHeapSort
@@prompt = "## 一番好きなのを選びなさい (%d回目)"
@@readline_prompt = "> <!-- --> "
class Quit < RuntimeError
def to_s
"Aborted"
end
end
def yesno(prompt)
Readline.completion_proc = proc do |m|
%w[yes no].select { |x| x.match(m) }
end
loop do
ret = Readline.readline("#{prompt} (yes/no)> ", false)
break false if ret =~ /^\s*no.*$/
break true if ret =~ /^\s*yes.*$/
puts "Please answer 'yes' or 'no'."
end
end
private
def parse_command(string, name, arguments, &block)
spa = string.split(/\s+/)
spa.delete("")
return false if spa[0] != name
spa.delete_at 0
h = Hash.new
opt = OptionParser.new do |x|
arguments.each do |n|
x.on("#{n}[=VAR]") do |v|
h[n] = v
end
end
end
begin
opt.parse!(spa)
rescue OptionParser::ParseError => e
puts "Error: " + e.to_s
return true
end
block.call(spa, h)
end
def draw_tree(factor, root, last, a = [])
raise ArgumentError if root < 0
raise ArgumentError if factor < 2
raise ArgumentError if last < 0
return if root >= last
return if root >= length
last = length if last > length
fst = root * factor + 1
lst = fst + factor - 1
return if fst >= last
lst = last - 2 if lst >= last - 1
t = ""
e = ""
puts self[root] if a.empty?
(fst...lst).each do |i|
puts "#{a.join}#{t} #{self[i]}"
draw_tree(factor, i, last, a + [""])
end
puts "#{a.join}#{e} #{self[lst]}"
draw_tree(factor, lst, last, a + [" "])
end
def draw_dot(stream, factor, root, last, depth = 0)
raise ArgumentError if root < 0
raise ArgumentError if factor < 2
raise ArgumentError if last < 0
return if root >= last
return if root >= length
last = length if last > length
fst = root * factor + 1
lst = fst + factor - 1
return if fst >= last
lst = last - 2 if lst >= last - 1
if depth == 0
stream.puts "graph G {"
stream.puts " n#{root} [label=\"#{self[root]}\"]"
end
(fst..lst).each do |i|
stream.puts " n#{i} [label=\"#{self[i]}\"]"
end
(fst..lst).each do |i|
stream.puts " n#{root} -- n#{i}"
end
(fst..lst).each do |i|
draw_dot(stream, factor, i, last, depth + 1)
end
if depth == 0
stream.puts "}"
puts "Done!"
end
end
# m: heap factor
# children: n * m + 1 to (n + 1) * m
# parent: (n - 1) / m
def question(factor, parent, l = length)
raise ArgumentError unless (0..l).cover?(parent)
fst = parent * factor + 1
lst = fst + factor
return nil if fst >= l
lst = l if lst > l
children = (fst...lst).to_a
ss = [parent] + children
@q_cnt ||= 0
@q_cnt += 1
if @heap_sort_state &&
@heap_sort_state.key?("answers") &&
@q_cnt <= @heap_sort_state["answers"].size
a = @heap_sort_state["answers"][@q_cnt - 1]
return a if ss.find_index(a)
ret = @heap_sort_state["answers"].slice!(@q_cnt..-1)
if ret && !ret.empty?
$stderr.puts "NOTE: Saved answers after Q.#{@q_cnt} were removed."
end
end
cnt = 0
messages = ss.map do |i|
next nil unless i < length
cnt += 1
"%d. %s" % [cnt, self[i]]
end
messages.compact!
puts
puts @@prompt % @q_cnt
puts
messages.each do |m|
puts " %s" % m
end
messages << "quit"
messages << "firmed"
messages << "draw-tree"
messages << "draw-dot"
Readline.completion_proc = Proc.new do |a|
messages.select { |m| m.match(a.to_s) }
end
puts
loop do
buf = Readline.readline(@@readline_prompt, true)
raise Quit unless buf
raise Quit if parse_command(buf, "quit", []) { 1 }
next if parse_command(buf, "firmed", []) do
if l == length
puts "## まだ何も確定していませんよ"
else
puts
puts "## 確定済みリスト"
puts
(length - 1).downto(l) do |i|
puts " %d. %s" % [length - i, self[i]]
end
end
true
end
next if parse_command(buf, "dump-array", []) do
self.each_with_index do |x, i|
puts "%d. %s" % [i, x]
end
true
end
next if parse_command(buf, "draw-tree", ["-r", "-f"]) do |m, h|
n = -1
if h.key?(:f)
n = h[:f].to_i - 1
end
d = -1
if h.key?(:d)
n = h[:d].to_i - 1
end
ll = l
if 0 <= d
ll = 0.upto(d).inject(0) do |i, j|
i + factor ** j
end
end
if ll > l
ll = l
end
if 0 <= n && n < ss.size
draw_tree(factor, ss[n], ll)
else
draw_tree(factor, 0, ll)
end
true
end
next if parse_command(buf, "draw-dot", ["-r", "-f"]) do |fa, h|
begin
out = $stdout
if ! fa.empty?
if File.exists?(fa[0])
break true unless yesno("Overwrite \"#{fa[0]}\"?")
end
out = File.open(fa[0], "w")
end
n = -1
if h.key?(:f)
n = h[:f].to_i - 1
end
d = -1
if h.key?(:d)
n = h[:d].to_i - 1
end
ll = l
if 0 <= d
ll = 0.upto(d).inject(0) do |i, j|
i + factor ** j
end
end
if ll > l
ll = l
end
if 0 <= n && n < ss.size
draw_dot(out, factor, ss[n], ll)
else
draw_dot(out, factor, 0, ll)
end
rescue SystemCallError => e
puts "Error: #{e.to_s}"
end
true
end
buf.sub!(/^\s*(\d*)\D.*$/, "\\1")
nbuf = buf.to_i - 1
if nbuf >= 0 && nbuf < ss.size
ans = ss[nbuf]
if @heap_sort_state
@heap_sort_state["answers"] ||= Array.new
@heap_sort_state["answers"] << ans
end
break ans
end
end
end
def swap(i, j)
self[i], self[j] = self[j], self[i]
end
def heap_leaf(m)
s = length
pp = (s - 1) / m
loop do
a = question(m, pp)
if a && a != pp
swap(a, pp)
heap_up(m, a)
end
break if pp == 0
pp -= 1
end
end
def heap_up(m, pp, l = length)
loop do
a = question(m, pp, l)
break unless a
break if a == pp
swap(a, pp)
pp = a
end
end
def heap_down(m)
(length - 1).downto(1) do |i|
swap(0, i)
heap_up(m, 0, i)
end
end
public
def heap_sort!(heap_factor = nil)
heap_factor ||= (Math.log(length) / Math.log(2)).to_i - 1
if @heap_sort_state && @heap_sort_state.is_a?(Hash)
@heap_sort_state["init"] = self.dup
end
raise TypeError, "Factor must be an integer" unless
heap_factor.is_a?(Integer)
heap_factor = 2 if heap_factor < 2
@q_cnt = nil
heap_leaf(heap_factor)
heap_down(heap_factor)
end
def heap_sort_state=(stat)
@heap_sort_state = stat
end
def heap_sort_state
@heap_sort_state
end
end
if $opt.key?(:state)
@ary = $opt[:state]["init"]
if $opt[:state]["max_sel"]
$opt[:max_sel] = $opt[:state]["max_sel"]
end
else
file = DATA
if not ARGV.empty?
fn = ARGV[0]
if fn != "-"
file = File.open(ARGV[0], "r")
else
file = $stdin
end
end
@ary = file.read.split(/\s+/).uniq
@ary.shuffle! if $opt[:shuffle]
$opt[:state] = Hash.new
if $opt[:max_sel]
$opt[:state]["max_sel"] = $opt[:max_sel]
end
end
@ary.extend InteractiveHeapSort
begin
@ary.heap_sort_state = $opt[:state]
@ary.heap_sort!($opt[:max_sel])
rescue InteractiveHeapSort::Quit
yn = proc do |m|
%w[yes no].select { |x| x.match(m) }
end
Readline.completion_proc = yn
ret = Readline.readline("Save state? (yes/no)> ", false)
if ret =~ /^\s*y/i
loop do
Readline.completion_proc = Readline::FILENAME_COMPLETION_PROC
fn = Readline.readline("Enter filename> ", false)
exit 1 unless fn
fn.sub!(/\s*$/, "")
if File.exists?(fn)
next unless @ary.yesno("Overwrite \"#{fn}\"?")
end
File.open(fn, "w") do |fp|
fp.print $opt[:state].to_yaml
end
break
end
end
exit 0
end
@ary.reverse!
as = (Math.log(@ary.length - 1) / Math.log(10)).to_i + 1
puts
puts "## 結果"
puts
@ary.each_with_index do |x, i|
puts "%*d. %s" % [as, i + 1, x]
end
__END__
フシギダネ
フシギソウ
フシギバナ
ヒトカゲ
リザード
リザードン
ゼニガメ
カメール
カメックス
キャタピー
トランセル
バタフリー
ビードル
コクーン
スピアー
ポッポ
ピジョン
ピジョット
コラッタ
ラッタ
オニスズメ
オニドリル
アーボ
アーボック
ピカチュウ
ライチュウ
サンド
サンドパン
ニドラン♀
ニドリーナ
ニドクイン
ニドラン♂
ニドリーノ
ニドキング
ピッピ
ピクシー
ロコン
キュウコン
プリン
プクリン
ズバット
ゴルバット
ナゾノクサ
クサイハナ
ラフレシア
パラス
パラセクト
コンパン
モルフォン
ディグダ
ダグトリオ
ニャース
ペルシアン
コダック
ゴルダック
マンキー
オコリザル
ガーディ
ウインディ
ニョロモ
ニョロゾ
ニョロボン
ケーシィ
ユンゲラー
フーディン
ワンリキー
ゴーリキー
カイリキー
マダツボミ
ウツドン
ウツボット
メノクラゲ
ドククラゲ
イシツブテ
ゴローン
ゴローニャ
ポニータ
ギャロップ
ヤドン
ヤドラン
コイル
レアコイル
カモネギ
ドードー
ドードリオ
パウワウ
ジュゴン
ベトベター
ベトベトン
シェルダー
パルシェン
ゴース
ゴースト
ゲンガー
イワーク
スリープ
スリーパー
クラブ
キングラー
ビリリダマ
マルマイン
タマタマ
ナッシー
カラカラ
ガラガラ
サワムラー
エビワラー
ベロリンガ
ドガース
マタドガス
サイホーン
サイドン
ラッキー
モンジャラ
ガルーラ
タッツー
シードラ
トサキント
アズマオウ
ヒトデマン
スターミー
バリヤード
ストライク
ルージュラ
エレブー
ブーバー
カイロス
ケンタロス
コイキング
ギャラドス
ラプラス
メタモン
イーブイ
シャワーズ
サンダース
ブースター
ポリゴン
オムナイト
オムスター
カブト
カブトプス
プテラ
カビゴン
フリーザー
サンダー
ファイヤー
ミニリュウ
ハクリュー
カイリュー
ミュウツー
ミュウ
チコリータ
ベイリーフ
メガニウム
ヒノアラシ
マグマラシ
バクフーン
ワニノコ
アリゲイツ
オーダイル
オタチ
オオタチ
ホーホー
ヨルノズク
レディバ
レディアン
イトマル
アリアドス
クロバット
チョンチー
ランターン
ピチュー
ピィ
ププリン
トゲピー
トゲチック
ネイティ
ネイティオ
メリープ
モココ
デンリュウ
キレイハナ
マリル
マリルリ
ウソッキー
ニョロトノ
ハネッコ
ポポッコ
ワタッコ
エイパム
ヒマナッツ
キマワリ
ヤンヤンマ
ウパー
ヌオー
エーフィ
ブラッキー
ヤミカラス
ヤドキング
ムウマ
アンノーン
ソーナンス
キリンリキ
クヌギダマ
フォレトス
ノコッチ
グライガー
ハガネール
ブルー
グランブル
ハリーセン
ハッサム
ツボツボ
ヘラクロス
ニューラ
ヒメグマ
リングマ
マグマッグ
マグカルゴ
ウリムー
イノムー
サニーゴ
テッポウオ
オクタン
デリバード
マンタイン
エアームド
デルビル
ヘルガー
キングドラ
ゴマゾウ
ドンファン
ポリゴン2
オドシシ
ドーブル
バルキー
カポエラー
ムチュール
エレキッド
ブビィ
ミルタンク
ハピナス
ライコウ
エンテイ
スイクン
ヨーギラス
サナギラス
バンギラス
ルギア
ホウオウ
セレビィ
キモリ
ジュプトル
ジュカイン
アチャモ
ワカシャモ
バシャーモ
ミズゴロウ
ヌマクロー
ラグラージ
ポチエナ
グラエナ
ジグザグマ
マッスグマ
ケムッソ
カラサリス
アゲハント
マユルド
ドクケイル
ハスボー
ハスブレロ
ルンパッパ
タネボー
コノハナ
ダーテング
スバメ
オオスバメ
キャモメ
ペリッパー
ラルトス
キルリア
サーナイト
アメタマ
アメモース
キノココ
キノガッサ
ナマケロ
ヤルキモノ
ケッキング
ツチニン
テッカニン
ヌケニン
ゴニョニョ
ドゴーム
バクオング
マクノシタ
ハリテヤマ
ルリリ
ノズパス
エネコ
エネコロロ
ヤミラミ
クチート
ココドラ
コドラ
ボスゴドラ
アサナン
チャーレム
ラクライ
ライボルト
プラスル
マイナン
バルビート
イルミーゼ
ロゼリア
ゴクリン
マルノーム
キバニア
サメハダー
ホエルコ
ホエルオー
ドンメル
バクーダ
コータス
バネブー
ブーピッグ
パッチール
ナックラー
ビブラーバ
フライゴン
サボネア
ノクタス
チルット
チルタリス
ザングース
ハブネーク
ルナトーン
ソルロック
ドジョッチ
ナマズン
ヘイガニ
シザリガー
ヤジロン
ネンドール
リリーラ
ユレイドル
アノプス
アーマルド
ヒンバス
ミロカロス
ポワルン
カクレオン
カゲボウズ
ジュペッタ
ヨマワル
サマヨール
トロピウス
チリーン
アブソル
ソーナノ
ユキワラシ
オニゴーリ
タマザラシ
トドグラー
トドゼルガ
パールル
ハンテール
サクラビス
ジーランス
ラブカス
タツベイ
コモルー
ボーマンダ
ダンバル
メタング
メタグロス
レジロック
レジアイス
レジスチル
ラティアス
ラティオス
カイオーガ
グラードン
レックウザ
ジラーチ
デオキシス
ナエトル
ハヤシガメ
ドダイトス
ヒコザル
モウカザル
ゴウカザル
ポッチャマ
ポッタイシ
エンペルト
ムックル
ムクバード
ムクホーク
ビッパ
ビーダル
コロボーシ
コロトック
コリンク
ルクシオ
レントラー
スボミー
ロズレイド
ズガイドス
ラムパルド
タテトプス
トリテプス
ミノムッチ
ミノマダム
ガーメイル
ミツハニー
ビークイン
パチリス
ブイゼル
フローゼル
チェリンボ
チェリム
カラナクシ
トリトドン
エテボース
フワンテ
フワライド
ミミロル
ミミロップ
ムウマージ
ドンカラス
ニャルマー
ブニャット
リーシャン
スカンプー
スカタンク
ドーミラー
ドータクン
ウソハチ
マネネ
ピンプク
ペラップ
ミカルゲ
フカマル
ガバイト
ガブリアス
ゴンベ
リオル
ルカリオ
ヒポポタス
カバルドン
スコルピ
ドラピオン
グレッグル
ドクロッグ
マスキッパ
ケイコウオ
ネオラント
タマンタ
ユキカブリ
ユキノオー
マニューラ
ジバコイル
ベロベルト
ドサイドン
モジャンボ
エレキブル
ブーバーン
トゲキッス
メガヤンマ
リーフィア
グレイシア
グライオン
マンムー
ポリゴンZ
エルレイド
ダイノーズ
ヨノワール
ユキメノコ
ロトム
ユクシー
エムリット
アグノム
ディアルガ
パルキア
ヒードラン
レジギガス
ギラティナ
クレセリア
フィオネ
マナフィ
ダークライ
シェイミ
アルセウス
ビクティニ
ツタージャ
ジャノビー
ジャローダ
ポカブ
チャオブー
エンブオー
ミジュマル
フタチマル
ダイケンキ
ミネズミ
ミルホッグ
ヨーテリー
ハーデリア
ムーランド
チョロネコ
レパルダス
ヤナップ
ヤナッキー
バオップ
バオッキー
ヒヤップ
ヒヤッキー
ムンナ
ムシャーナ
マメパト
ハトーボー
ケンホロウ
シママ
ゼブライカ
ダンゴロ
ガントル
ギガイアス
コロモリ
ココロモリ
モグリュー
ドリュウズ
タブンネ
ドッコラー
ドテッコツ
ローブシン
オタマロ
ガマガル
ガマゲロゲ
ナゲキ
ダゲキ
クルミル
クルマユ
ハハコモリ
フシデ
ホイーガ
ペンドラー
モンメン
エルフーン
チュリネ
ドレディア
バスラオ
メグロコ
ワルビル
ワルビアル
ダルマッカ
ヒヒダルマ
マラカッチ
イシズマイ
イワパレス
ズルッグ
ズルズキン
シンボラー
デスマス
デスカーン
プロトーガ
アバゴーラ
アーケン
アーケオス
ヤブクロン
ダストダス
ゾロア
ゾロアーク
チラーミィ
チラチーノ
ゴチム
ゴチミル
ゴチルゼル
ユニラン
ダブラン
ランクルス
コアルヒー
スワンナ
バニプッチ
バニリッチ
バイバニラ
シキジカ
メブキジカ
エモンガ
カブルモ
シュバルゴ
タマゲタケ
モロバレル
プルリル
ブルンゲル
ママンボウ
バチュル
デンチュラ
テッシード
ナットレイ
ギアル
ギギアル
ギギギアル
シビシラス
シビビール
シビルドン
リグレー
オーベム
ヒトモシ
ランプラー
シャンデラ
キバゴ
オノンド
オノノクス
クマシュン
ツンベアー
フリージオ
チョボマキ
アギルダー
マッギョ
コジョフー
コジョンド
クリムガン
ゴビット
ゴルーグ
コマタナ
キリキザン
バッフロン
ワシボン
ウォーグル
バルチャイ
バルジーナ
クイタラン
アイアント
モノズ
ジヘッド
サザンドラ
メラルバ
ウルガモス
コバルオン
テラキオン
ビリジオン
トルネロス
ボルトロス
レシラム
ゼクロム
ランドロス
キュレム
ケルディオ
メロエッタ
ゲノセクト
ハリマロン
ハリボーグ
ブリガロン
フォッコ
テールナー
マフォクシー
ケロマツ
ゲコガシラ
ゲッコウガ
ホルビー
ホルード
ヤヤコマ
ヒノヤコマ
ファイアロー
コフキムシ
コフーライ
ビビヨン
シシコ
カエンジシ
フラベベ
フラエッテ
フラージェス
メェークル
ゴーゴート
ヤンチャム
ゴロンダ
トリミアン
ニャスパー
ニャオニクス
ヒトツキ
ニダンギル
ギルガルド
シュシュプ
フレフワン
ペロッパフ
ペロリーム
マーイーカ
カラマネロ
カメテテ
ガメノデス
クズモー
ドラミドロ
ウデッポウ
ブロスター
エリキテル
エレザード
チゴラス
ガチゴラス
アマルス
アマルルガ
ニンフィア
ルチャブル
デデンネ
メレシー
ヌメラ
ヌメイル
ヌメルゴン
クレッフィ
ボクレー
オーロット
バケッチャ
パンプジン
カチコール
クレベース
オンバット
オンバーン
ゼルネアス
イベルタル
ジガルデ
ディアンシー
フーパ

全ポケモン 720 匹を好きな順で並び替え

使い方

起動

Ruby でそのまま実行してくれればok。

Gem は使ってないけど、stdlib, YAML および Readline のサポートが必要です。

なお、名前を改行区切り(つまり1行に一つ)で書いたテキストファイルを引数に渡せば、ポケモンのリストの代わりにそれが使えます。

回答パート

提示されたリストから、最も好き(嫌い)なものを選んでいきます。

## 一番好きなのを選びなさい

 1. クヌギダマ
 2. マダツボミ
 3. フレフワン
 4. バニプッチ
 5. タネボー
 6. ヒメグマ
 7. ウルガモス
 8. ツタージャ

>

この場合であれば、1〜8 の番号を入力して Enter を押します。

これをひたすら答えていくと、好きな順番に並びます。

コマンドリスト

firmed

確定済みのリストを表示します。

draw-tree [root] [depth]

現在のヒープ木を描画します。

[root] が 0 の場合は、ヒープ木の根元から、それ以外の場合は、現在の質問の選択肢の番号以下のヒープ木を表示します。

[depth] 表示する深さの限界を指定します。省略したり、0 を指定すると無制限に表示します。

draw-dot

現在のヒープ木 (全体) を dot 言語で出力します。

出力先は今の所、端末のみです。また、レイアウトされていないので、画像にするには、Graphviz などのレイアウトのできるソフトが必要です。

quit

終了します。終了する際に、途中経過を保存できます。保存したファイルを --state-file= オプションで指定すると、続きから再開できます。

備考

よりよい回答ができるよう (?)、開始前にリストはシャッフルされます。

ポケモンの並び替えでは、最低でも 808 回は質問されます。多いと 2000 回以上質問される場合もあります。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.