こんにちは。hiraです。
半月ほど前にNintendo Switchとマリオオデッセイを購入しました。
所謂箱庭アクションゲームが好きなので、マリオオデッセイは絶対面白いだろうなと思って購入しましたが、実際面白かったです。
「バンジョーとカズーイの大冒険」の精神的後継作と噂される「Yooka-Laylee」がSwitchで発売され、しかも日本語化されるらしいことがわかったので、それも今から楽しみです。
Japanese support will be coming to Switch via a post-launch update https://t.co/uvKKUiEwYv
— Playtonic (@PlaytonicGames) December 5, 2017
しりとり
みなさん「しりとり」を知っているでしょうか。知っていますよね？
「子供の遊戯」と侮るなかれ、単語の属性(動物しりとり等)や文字数に関して制限を加えればかなり高度な知的遊戯となります。
無制限で、有名な「る攻め」それに対抗する、ルール、ルノアール、ルミノール ...を使った「る返し」で激しい攻防をしても面白いはずです。
前置きはこのくらいにして、今回はRubyの組み込みクラス・モジュールのpublicなメソッド名でしりとりをすることを考えてみます。
色々と遊ぶに当たって考慮する点を考えつつ、最終的には「最長しりとり問題」について答えを出したいと思います。
Rubyのバージョンは2.4.3として考えていきます。
辞書の準備
何はともあれ辞書が必要です。
以下のコードで取得できると思います。
irbやpryを使うとIRBやPRYクラス等が混入するので、rbファイルを使って実行する必要があります。
classes_and_modules = ObjectSpace.each_object.select do |object|
(object.kind_of?(Class) || object.kind_of?(Module))
end
words = classes_and_modules.flat_map { |c| c.methods + c.instance_methods }
.uniq.map(&:to_s).select { |m| m =~ /\A([a-z].*)?[a-z][!?]?\z/i }.sort
p words.size # => 1174
ObjectSpaceからクラスとモジュールを抽出し、それらからprivateなクラスメソッドとインスタンスメソッドを取得し、重複を除き、末尾の!や?を無視したときに、開始文字と終了文字がアルファベットであるものだけを抽出しています。
:__FILE__, :__id__のようなメソッドは今回除きます。:hogehoge=のようなsetterも今回は対象外です。
:[]や:>といったメソッドも当然除外です。
!?と=の境界はなんとなくです。
単語の分布
開始文字と終了文字の分布を見ていきます。まずは開始文字から
start_char = (:a..:z).map { |char| [char, words.count { |word| word.downcase.start_with?(char.to_s) }] }.to_h
# =>
{
:a => 60, :b => 38, :c => 107, :d => 77, :e => 84, :f => 63, :g => 44, :h => 16, :i => 48,
:j => 1, :k => 6, :l => 55, :m => 50, :n => 28, :o => 17, :p => 79, :q => 2, :r => 102
:s => 146, :t => 75, :u => 36, :v => 12, :w => 21, :x => 0, :y => 4, :z => 3
}
xで始まるメソッドは一個もないようです。また、j, q, y, zが少ない(5個以下)ですね。それぞれ詳しく見ていくと、(複数クラス・モジュールにまたがるものは一つだけ示しています。)
| 開始文字 | メソッド名 |
|---|---|
| j | Array#join |
| q | Numeric#quo, Regexp.quote |
| y | Gem::Version.yaml_initialize, Time#yday, Time#year, Proc#yield |
| z | Numeric#zero?, Enumerable#zip, Time#zone |
終了文字の方も、調べると以下のようになります。
end_char = (:a..:z).map { |char| [char, words.count { |word| word.downcase.delete('!?').end_with?(char.to_s) }] }.to_h
# =>
{
:a => 9, :b => 13, :c => 45, :d => 112, :e => 221, :f => 14, :g => 28, :h => 61, :i => 4,
:j => 2, :k => 22, :l => 48, :m => 17, :n => 63, :o => 18, :p => 45, :q => 4, :r => 78,
:s => 161, :t => 125, :u => 1, :v => 8, :w => 3, :x => 13, :y => 59, :z => 0
}
zで終わるメソッドがないようです。同様に少ない個数の文字だけ詳しく見ると
| 終了文字 | メソッド名 |
|---|---|
| i | Numeric#i, Delegator.public_api, Float#to_i, Gem.ui |
| j | Numeric#conj, Gem::Specification#sort_obj |
| q | Thread::Queue#deq, Thread::Queue#enq, Array#uniq, Array#uniq! |
| u | Gem::Platform#cpu |
| w | Class#new, Time.now, Kernel#throw |
そして、しりとりで一番重要なのが、その比率ですね。「る」が強いのは、「る」で終わる単語に比べて「る」で始まる単語が少ないからです。始まる単語が少なければ強いというわけではありません。
ということで、それぞれのアルファベットについて、その文字で始まる単語数をその文字で終わる単語数で割ったものを求めてみます。
(:a..:z).map { |char| [char, (start_char[char] * 1.0 / end_char[char]).round(3)] }.to_h
# =>
{
:a => 6.667,
:b => 2.923,
:c => 2.378,
:d => 0.688,
:e => 0.38,
:f => 4.5,
:g => 1.571,
:h => 0.262,
:i => 12.0,
:j => 0.5,
:k => 0.273,
:l => 1.146,
:m => 2.941,
:n => 0.444,
:o => 0.944,
:p => 1.756,
:q => 0.5,
:r => 1.308,
:s => 0.907,
:t => 0.6,
:u => 36.0,
:v => 1.5,
:w => 7.0,
:x => 0.0,
:y => 0.068,
:z => Infinity
}
この値が小さければ小さいほど、終わる単語に比べて始まる単語が不足しているということなので、一般に積極的にそれで終わる単語を言っていくとよいです。
ただ、xが0なのは問題です。xで終わる単語は、
Complex, bsearch_index, each_index, each_with_index, find_index hex index, load_path_insert_index, max, minmax, prefix, rindex, with_index
と11個ありますが、これらを言われた時点で負けが確定するというのはゲームバランスが悪いですね。
xは日本語しりとりでいう「ん」のように終わる単語を言ったら負けにするのが妥当でしょう。
yも0.068と小さいです。yで始まる単語は、yday, year, yieldの3つです。
ydayはそのままy返しができ、yearは(read_binary, ruby)でそのまま返され、yieldは(day, dependency, directory, directory?, display, dummy?)でそのまま返されるため、むしろyで終わる単語を先に言った方が不利になり、そこまでゲームバランスを崩すものとはならなそうです。
eも0.38と少なめですが、eで始まる単語は84個あるのでそこまで問題にならなそうです。他は少なくとも0.5程度あるので、大丈夫じゃないでしょうか？
これで心置きなくできますね。
最長しりとり問題
それでは最後に最長しりとり問題を解いて終わりにします。
最長しりとり問題といえば、昔「トリビアの泉」の「トリビアの種」というコーナーで「広辞苑の収録語でしりとりを続けたとき〜」というのがあったのを記憶していますが、あんな感じです。
卒業論文でポケモンの最長しりとり問題を扱ったという話も、少し話題(参考: ポケモンでしりとりしたら最長何匹まで続く？ 数学の卒論がネットで話題に)になりました。
普通に手当たり次第に解こうとすると、計算時間は指数関数オーダーになり、単語数1000個もあるとなかなか難しくなってきますが、この論文にあるようなアルゴリズムを使うと一瞬で解くことができます。
ざっくりいうと、文字を頂点、単語を辺と捉えるとしりとりは有向グラフとしてとらえることができ、最長しりとりは、そのグラフから最も辺の数が多い、準オイラー路(一筆書きができる路)を探すことに他なりません。
そしてこれは、整数計画問題に帰着でき、それによってより早く計算を行うことが可能というわけです。
詳しくは論文を見ていただければと思います。
結果だけ見せてしまうと、最長は700個で、一例を示すと、
ungetc -> class_exec -> close_on_exec? -> caller_locations -> scopes -> segments -> singleton_class -> singleton_class? -> singleton_methods -> source_paths -> sources -> specs -> status -> stress -> stubs -> success? -> suffixes -> superclass -> satisfies_requirement? -> taint -> target -> test -> thread_variable_get -> thread_variable_set -> to_int -> trust -> try_convert -> tanh -> Hash -> hash -> handle_interrupt -> to_fullpath -> host -> to_h -> hypot -> test_files -> scan -> nan? -> named_captures -> seek -> keys -> sample -> each_byte -> each_line -> each_slice -> each_value -> enable -> enclose -> encode -> encode! -> escape -> exclusive -> executable -> executable? -> exit_code -> exit_value -> extname -> each_entry -> yday -> yaml_initialize -> each_codepoint -> take -> enq -> quote -> even? -> name -> each -> has_test_suite? -> each_object -> take_while -> exception -> name_tuple -> encode_with -> has_value? -> each_with_object -> terminate -> extension_api_version -> namespace -> end_with? -> home -> env_requirement -> test_file -> expand_path -> homepage -> event -> thread_variable? -> exact? -> time -> exist? -> to_ruby_for_cache -> exit -> total_time -> exit! -> trace -> extend_object -> transpose -> each_cons -> scrub -> b -> backtrace_locations -> select -> this -> sin -> names -> sanitize -> ensure_default_gem_subdirectories -> scrub! -> blocks -> select! -> thread_variables -> slice_when -> needs -> set_backtrace -> ensure_gem_subdirectories -> sub -> build_args -> setrlimit -> times -> source_exception -> next_values -> setbyte -> ensure_subdirectories -> shift -> to_s -> source_location -> non_nil_attributes -> setproctitle -> entries -> socket? -> to_specs -> shuffle -> error_bytes -> sort -> to_yaml_properties -> shuffle! -> errors -> sort! -> tr_s -> sid_available? -> executables -> source_set -> tr_s! -> signame -> exists? -> split -> transform_values -> size -> exitstatus -> sqrt -> transform_values! -> size? -> extensions -> slice -> extra_rdoc_files -> sec -> cache_dir -> random_number -> rdev_major -> rdev_minor -> readchar -> receiver -> rectangular -> remainder -> ri_dir -> rmdir -> rdev -> vendor_dir -> rect -> to_r -> raise_if_conflicts -> slice_after -> raised_exception -> numerator -> reject -> to_str -> raw_require_paths -> spec_cache_dir -> reject! -> tr -> rdoc_options -> spec_dir -> replacement -> tr! -> readagain_bytes -> spell_checker -> report -> trace_var -> readlines -> stubs_for -> request -> try_enter -> requirement -> try_mon_enter -> requirements_list -> to_hash -> hour -> reset -> traverse -> each_char -> reason -> negative? -> each_pair -> reopen -> none? -> enter -> repeated_combination -> normalize -> enum_for -> repeated_permutation -> name_list -> truncate -> error -> report_on_exception -> next -> try_activate -> error_char -> required_ruby_version -> next! -> type -> extension_dir -> rassoc -> casecmp -> p -> pop -> parameters -> setpgrp -> path_separator -> regexp -> platform -> matching_specs -> signm -> maxgroups -> sum -> members -> system -> member? -> reset_nil_attributes_to_default -> to_enum -> mkdir -> result -> to_sym -> map -> pid -> define_singleton_method -> divmod -> dev -> valid? -> default -> tainted? -> default_gems_use_full_paths? -> seed -> datadir -> rand -> daemon -> new_cond -> date -> egid -> default_rubygems_dirs -> send -> default_bindir -> raw_seed -> description -> new_seed -> default_executable -> eid -> default_sources -> setegid -> default_dir -> read -> default_value -> enabled? -> defined_class -> seteuid -> default_ext_dir_for -> rewind -> deflate -> enclosed? -> dependencies -> setgid -> default_spec_cache_dir -> rid -> delete -> end -> dependent_gems -> setgid? -> default_specifications_dir -> round -> delete! -> euid -> dependent_specs -> setpgid -> deprecate -> exclude_end? -> detect_gemdeps -> setregid -> destination_encoding_name -> exited? -> development_dependencies -> setresgid -> dirname -> expand -> digits -> setresuid -> disable -> extend -> dirs -> setreuid -> done_installing_hooks -> setrgid -> div -> validate_dependencies -> setruid -> define_finalizer -> require_paths -> setsid -> default_cert_path -> has_conflicts? -> setuid -> disassemble -> each_key -> yield -> denominator -> required_attributes -> setuid? -> default_key_path -> has_unit_tests? -> signaled? -> dev_major -> requirements -> singleton_method -> dev_minor -> runtime_dependencies -> singleton_method_added -> default_gemspec_stub -> blockdev? -> validate_permissions -> srand -> drop -> pass -> skip -> polar -> rstrip -> post_build -> dump -> paths -> sleep -> ppid -> dup -> peek_values -> step -> platform_defaults -> stop -> platforms -> stop? -> pos -> strip -> post_build_hooks -> strip! -> post_install_hooks -> slice! -> exp -> post_reset_hooks -> sub! -> bump -> pred -> default_exec_format -> tap -> prepend -> dir -> rstrip! -> private_class_method -> default_gem? -> map! -> private_method_defined? -> delete_at -> trap -> proc -> copy_stream -> matches_spec? -> const_missing -> grep_v -> valid_encoding? -> gcdlcm -> method_missing -> getlocal -> label -> load_yaml -> local -> last -> tail -> latest_specs -> safe_level -> last_error -> Rational -> ldexp -> post_install -> lcm -> module_eval -> lchmod -> default_external -> lib_dirs_glob -> base_label -> list -> tell -> lib_files -> signal -> latest_spec_for -> readable_real? -> locale_charmap -> post_uninstall -> load -> default_internal -> ljust -> to_yaml -> licenses -> syscall -> latest_version_for -> readpartial -> loop -> pre_install -> location_of_caller -> real -> lstrip -> pre_uninstall -> lstrip! -> private_call? -> local_variable_get -> throw -> wait_until -> lines -> symlink -> kill -> load_defaults -> slice_before -> email -> latest_gc_info -> oct -> to_io -> options -> signo -> owner -> respond_to? -> open -> nonzero? -> original_platform -> mkfifo -> object_id -> downto -> offset -> to_write_io -> os -> source -> errno -> odd? -> deq -> quo -> ord -> disasm -> marshal_dump -> primitive_errinfo -> outdated_and_latest_version -> nil? -> local_variable_defined? -> doc_dir -> real? -> locked? -> distance -> eql? -> load_env_plugins -> source_encoding_name -> equal? -> load_plugin_files -> spec_file -> eval -> load_plugins -> spec_name -> executable_real? -> log -> gcd -> destination_encoding -> gemspec_stub -> binding -> getegid -> dig -> geteuid -> done_installing -> getpgrp -> post_uninstall_hooks -> String -> getgm -> method_names -> sanitize_string -> getgid -> deprecate_constant -> tag -> getpgid -> downcase -> encoding -> grep -> pre_install_hooks -> set_encoding -> getsid -> detect -> termsig -> getuid -> downcase! -> external_encoding -> group -> pre_reset_hooks -> skip_during -> gunzip -> pre_uninstall_hooks -> source_encoding -> gzip -> private_instance_methods -> stopsig -> glob -> base_dir -> required_rubygems_version -> nesting -> gsub -> bin_dir -> rpartition -> num_waiting -> gsub! -> bindir -> ruby_api_version -> new -> warning -> getc -> captures -> set_trace_func -> caller -> register_default_spec -> casecmp? -> putc -> chars -> spec -> center -> remove_spec -> class -> specific? -> chdir -> remove_unresolved_default_spec -> class_names -> subsec -> class_variables -> succ -> clear_default_specs -> succ! -> clear_paths -> sync -> chardev? -> values_at -> to_c -> clock_getres -> start -> to_proc -> codepoints -> spawn -> nsec -> conflicting_dependencies -> string -> getutc -> conflicts -> self -> flat_map -> printf -> fileno -> of -> fixed_encoding? -> gmtoff -> first_lineno -> outdated -> delete_if -> fail -> local_variable_set -> to_f -> fcntl -> loaded_specs -> squeeze -> eof -> fill -> local_variables -> squeeze! -> eof? -> find_all -> lvar_names -> stime -> erf -> from_yaml -> lineno -> owned? -> delegating_block -> keep_if -> fdatasync -> constants -> store -> each_gemspec -> corrections -> stopped? -> default_proc -> chr -> rjust -> to_spec -> clear -> raw_data -> add_platform -> metadata -> all -> lambda -> arg -> gamma -> all? -> lambda? -> asciicompat_encoding -> getwd -> dst? -> to_a -> argv -> values -> strftime -> extensions_dir -> ruby_version -> now -> waitall -> lgamma -> add_spec -> call -> lstat -> tv_nsec -> ceil -> loaded_from -> module_exec -> class_eval -> load_from_binary_extra_data -> add_trace_func -> cos -> stat -> tv_sec -> count_objects -> sprintf -> find_unresolved_default_spec -> cvar_names -> swapcase -> each_spec -> cover? -> rubyforge_project -> tv_usec -> chomp -> private_methods -> swapcase! -> erfc -> chomp! -> protected_instance_methods -> synchronize -> exec -> chop -> protected_methods -> stubbed? -> default_path -> has_rdoc -> chop! -> public_instance_methods -> super_method -> detach -> has_rdoc? -> clamp -> public_methods -> sort_obj -> join -> nlink -> kind_of? -> fsync -> cpu -> ui -> i -> instance_of? -> frexp -> public_api -> itself -> force_encoding -> gm -> matches_for_glob -> build_info_dir -> rubygems_version -> next_float -> to_i -> is_a? -> assoc -> coredump? -> puts -> sysread -> drop_while -> empty? -> year -> run -> normalize_yaml_input -> to_path -> hex
となります。
まとめ
Rubyに自信がある人は是非やってみてください。私はやりません。