Railsチュートリアル3章のエラー解決×2

Ruby on Railsチュートリアル 3章でエラーが発生したため、その解決方法を書き残します。

該当箇所は3.3.2節、わざとテストを失敗させるところです。

環境

• ホストOS：Windows 10
• ゲストOS：CentOS 7
  • VirtualBoxで動作
  • VirtualBoxのフォルダ共有機能を使用
  • Vagrantで環境管理
• Ruby on Railsチュートリアル Rails 5.1対応 (第4版)
  • rails バージョン5.1.4

エラーメッセージ

長いですが全部貼ります。

このメッセージ、前半と後半でそれぞれ独立のエラーが発生しています。

[vagrant@localhost sample_app]$ rails test
Running via Spring preloader in process 16123
rails aborted!
ActiveRecord::Tasks::DatabaseAlreadyExists: ActiveRecord::Tasks::DatabaseAlreadyExists
/vagrant_data/sample_app/bin/rails:9:in `require'
/vagrant_data/sample_app/bin/rails:9:in `<top (required)>'
/vagrant_data/sample_app/bin/spring:15:in `require'
/vagrant_data/sample_app/bin/spring:15:in `<top (required)>'
bin/rails:3:in `load'
bin/rails:3:in `<main>'

Caused by:
Errno::ETXTBSY: Text file busy @ apply2files - /vagrant_data/sample_app/db/test.sqlite3
/vagrant_data/sample_app/bin/rails:9:in `require'
/vagrant_data/sample_app/bin/rails:9:in `<top (required)>'
/vagrant_data/sample_app/bin/spring:15:in `require'
/vagrant_data/sample_app/bin/spring:15:in `<top (required)>'
bin/rails:3:in `load'
bin/rails:3:in `<main>'
Tasks: TOP => db:test:load => db:test:purge
(See full trace by running task with --trace)
Run options: --seed 25191

# Running:

Run options: --seed 25191

# Running:

EE

Error:
StaticPagesControllerTest#test_should_get_about:
NameError: undefined local variable or method `static_pages_about_url' for #<StaticPagesControllerTest:0x0000561eb6178d08>
    test/controllers/static_pages_controller_test.rb:15:in `block in <class:StaticPagesControllerTest>'


Traceback (most recent call last):
        27: from -e:1:in `<main>'
        26: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/2.5.0/rubygems/core_ext/kernel_require.rb:59:in `require'
        25: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/2.5.0/rubygems/core_ext/kernel_require.rb:59:in `require'
        24: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application/boot.rb:19:in `<top (required)>'
        23: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:135:in `run'
        22: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:135:in `loop'
        21: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:141:in `block in run'
        20: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:171:in `serve'
        19: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:171:in `fork'
        18: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:63:in `block in autorun'
        17: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:136:in `run'
        16: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `__run'
        15: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `map'
        14: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `block in __run'
        13: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/line_filtering.rb:9:in `run'
        12: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:319:in `run'
        11: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:347:in `with_info_handler'
        10: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:360:in `on_signal'
         9: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:320:in `block in run'
         8: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:320:in `each'
         7: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:321:in `block (2 levels) in run'
         6: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:334:in `run_one_method'
         5: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:802:in `record'
         4: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:802:in `each'
         3: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:803:in `block in record'
         2: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:23:in `record'
         1: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:70:in `format_rerun_snippet'
/home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:70:in `method': undefined method `test_should_get_about' for class `Minitest::Result' (NameError)

原因1：VirtualBoxの共有フォルダ機能

まず前半のほうです。

ActiveRecord::Tasks::DatabaseAlreadyExists: ActiveRecord::Tasks::DatabaseAlreadyExists
/vagrant_data/sample_app/bin/rails:9:in `require'
/vagrant_data/sample_app/bin/rails:9:in `<top (required)>'
/vagrant_data/sample_app/bin/spring:15:in `require'
/vagrant_data/sample_app/bin/spring:15:in `<top (required)>'
bin/rails:3:in `load'
bin/rails:3:in `<main>'

Caused by:
Errno::ETXTBSY: Text file busy @ apply2files - /vagrant_data/sample_app/db/test.sqlite3
/vagrant_data/sample_app/bin/rails:9:in `require'
/vagrant_data/sample_app/bin/rails:9:in `<top (required)>'
/vagrant_data/sample_app/bin/spring:15:in `require'
/vagrant_data/sample_app/bin/spring:15:in `<top (required)>'
bin/rails:3:in `load'
bin/rails:3:in `<main>'

test.sqlite3というファイルがビジーで操作できない、という内容のエラーです。

この問題については以下のページに情報があります。

ruby on rails - Errno::ETXTBSY: Text file busy @ unlink_internal - Stack Overflow

これはVirtualBoxの共有フォルダ内にrailsのプロジェクトを作ってしまった際に発生する問題のようです。

※Vagrantが関連しているかどうかは不明ですが、Vagrantは単にVirtualBoxの共有フォルダ機能を有効にしているだけなので、おそらく関連はないと思います。

問題となっているのはtest.sqlite3、これはデータベースファイルです。プロジェクト作成時のデータベース利用設定では、テスト用のデータベースはプロジェクトディレクトリ内にSQLiteのDBファイルを作るようになっています。これがうまくいっていないようです。

解決策としては、1つはプロジェクトを共有フォルダの外で作ってしまうことです。またはデータベース設定を変更して、共有フォルダの外にデータベースを作るようにしてもよいです。今回は後者の方法を採ります。

データベースの設定はconfig/database.ymlに記述されています。これを以下のように変更します。

# SQLite version 3.x
#   gem install sqlite3
#
#   Ensure the SQLite 3 gem is defined in your Gemfile
#   gem 'sqlite3'
#
default: &default
  adapter: sqlite3
  pool: <%= ENV.fetch("RAILS_MAX_THREADS") { 5 } %>
  timeout: 5000

development:
  <<: *default
  #ついでに変更
  #database: db/development.sqlite3
  database: /var/rails_db/development.sqlite3

# Warning: The database defined as "test" will be erased and
# re-generated from your development database when you run "rake".
# Do not set this db to the same as development or production.
test:
  <<: *default
  #ここを変更
  #database: db/test.sqlite3
  database: /var/rails_db/test.sqlite3

production:
  <<: *default
  #ついでに変更
  #database: db/production.sqlite3
  database: /var/rails_db/production.sqlite3

場所は/tmp/とかでも良いのですが、/var/rails_db/というディレクトリを作ってそこに入れることにしました。

以下のコマンドでディレクトリを作り、オーナーを作業ユーザに変更します。ユーザ名とグループ名（vagrant:vagrant）はそれぞれの環境によって異なるのでご注意ください。

[vagrant@localhost sample_app]$ sudo mkdir /var/rails_db
[vagrant@localhost sample_app]$ sudo chown vagrant:vagrant /var/rails_db

これで前半のエラーは出なくなるはずです。

原因2：minitestとrailsのバージョン相性

次に後半のエラーに対処していきます。

Traceback (most recent call last):
        27: from -e:1:in `<main>'
        26: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/2.5.0/rubygems/core_ext/kernel_require.rb:59:in `require'
        25: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/2.5.0/rubygems/core_ext/kernel_require.rb:59:in `require'
        24: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application/boot.rb:19:in `<top (required)>'
        23: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:135:in `run'
        22: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:135:in `loop'
        21: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:141:in `block in run'
        20: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:171:in `serve'
        19: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/spring-2.0.2/lib/spring/application.rb:171:in `fork'
        18: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:63:in `block in autorun'
        17: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:136:in `run'
        16: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `__run'
        15: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `map'
        14: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:159:in `block in __run'
        13: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/line_filtering.rb:9:in `run'
        12: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:319:in `run'
        11: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:347:in `with_info_handler'
        10: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:360:in `on_signal'
         9: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:320:in `block in run'
         8: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:320:in `each'
         7: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:321:in `block (2 levels) in run'
         6: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:334:in `run_one_method'
         5: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:802:in `record'
         4: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:802:in `each'
         3: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/minitest-5.11.3/lib/minitest.rb:803:in `block in record'
         2: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:23:in `record'
         1: from /home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:70:in `format_rerun_snippet'
/home/vagrant/.anyenv/envs/rbenv/versions/2.5.0/lib/ruby/gems/2.5.0/gems/railties-5.1.4/lib/rails/test_unit/reporter.rb:70:in `method': undefined method `test_should_get_about' for class `Minitest::Result' (NameError)

Minitest::Resultというクラスが期待されているメソッドを持っていない、というエラーです。

この問題について、そのものズバリの記事を書いてくださっている方がいます。

Ruby on Rails チュートリアル３章のテストのバグとその対応メモ

今回railsのバージョン5.1.4を使っているが、テストに使っているgemのminitestは新しいバージョンが入るため、実装が合わずに上手く動いていないようです。

解決策は、Gemfileにminitestのバージョン指定を書き加えることです。

source 'https://rubygems.org'

gem 'rails',        '5.1.4'
gem 'puma',         '3.9.1'
gem 'sass-rails',   '5.0.6'
gem 'uglifier',     '3.2.0'
gem 'coffee-rails', '4.2.2'
gem 'jquery-rails', '4.3.1'
gem 'turbolinks',   '5.0.1'
gem 'jbuilder',     '2.7.0'

group :development, :test do
  gem 'sqlite3', '1.3.13'
  gem 'byebug',  '9.0.6', platform: :mri
end

group :development do
  gem 'web-console',           '3.5.1'
  gem 'listen',                '3.1.5'
  gem 'spring',                '2.0.2'
  gem 'spring-watcher-listen', '2.0.1'
end

group :test do
  gem 'rails-controller-testing', '1.0.2'
  gem 'minitest-reporters',       '1.1.14'
  gem 'guard',                    '2.13.0'
  gem 'guard-minitest',           '2.4.4'
  gem 'minitest',                 '5.10.3'    # ここを追加
end

group :production do
  gem 'pg', '0.20.0'
end

修正後、以下のコマンドを実行します。

[vagrant@localhost sample_app]$ bundle update
[vagrant@localhost sample_app]$ bundle install

結果

以上2つのエラー対策により、正常に「テスト失敗」させることができました。

[vagrant@localhost sample_app]$ rails test
Running via Spring preloader in process 16455
/vagrant_data/sample_app/db/schema.rb doesn't exist yet. Run `rails db:migrate` to create it, then try again. If you do not intend to use a database, you should instead alter /vagrant_data/sample_app/config/application.rb to limit the frameworks that will be loaded.
Run options: --seed 46335

# Running:

Run options: --seed 46335

# Running:

EE

Error:
StaticPagesControllerTest#test_should_get_about:
NameError: undefined local variable or method `static_pages_about_url' for #<StaticPagesControllerTest:0x0000561a90598ed0>
    test/controllers/static_pages_controller_test.rb:15:in `block in <class:StaticPagesControllerTest>'


bin/rails test test/controllers/static_pages_controller_test.rb:14

....

Finished in 1.254642s, 2.3911 runs/s, 1.5941 assertions/s.

  1) Error:
StaticPagesControllerTest#test_should_get_about:
NameError: undefined local variable or method `static_pages_about_url' for #<StaticPagesControllerTest:0x0000561a90598ed0>
    test/controllers/static_pages_controller_test.rb:15:in `block in <class:StaticPagesControllerTest>'

3 runs, 2 assertions, 0 failures, 1 errors, 0 skips



Finished in 1.299065s, 2.3094 runs/s, 1.5396 assertions/s.
3 runs, 2 assertions, 0 failures, 1 errors, 0 skips

AtCoder AGC023 B - Find Symmetries O(N^3)解法でのTLE対処

AtCoder Grand Contest 023 お疲れ様でした。A, Bの2完でした。（C通したかった…）

今回のB問題について、想定解である 解法を素直に実装すると、RubyではTLEしてしまったので、その対処法をまとめたいと思います。

問題

B - Find Symmetries

入力として の正方行列が与えられます。

の正方行列を縦横にずらす方法は、縦 通り、横 通りで 通りあります。（はみ出たぶんは でループします）

その 通りのうち、対称行列になっているものはいくつありますか、という問題。

想定解

公式解説PDF

愚直解は、 通りのずらし方それぞれについて、 個の要素をチェックします。計算量は です。

これはさすがに間に合わないので、何か規則性はないか考えてみたところ…対称行列を「右下斜め」にずらしたものは、やはり対称行列である、ということを思い付きました。逆もまた然りです。

具体的には、以下の図で説明できます。行列を「右下斜め」にずらしても、比較対象のペアとなる要素は変わりません。

「右下斜め」のずらし方は 通りで、これを同一視できるので、計算量が 1つぶん減って となります。実装においては、列をずらさずに、行だけを 通りずらしたものをチェックすればよいでしょう。もちろん逆でも大丈夫です。

…というところまでが公式解説の内容です。C++等の高速な言語であれば、これを素直に書けば通るのではないかと思います。

Ruby実装（TLE）

コンテスト中最初に提出したコードがこちらです。TLEしています。

TLE1：Submission #2427824 - AtCoder Grand Contest 023

ほぼ同じ構造で、なるべく無駄を省こうとしたコードがこちらです。チェックする要素を約半分に削減したり、return による大域脱出を試みたりしています。これでもTLE。

TLE2：Submission #2434543 - AtCoder Grand Contest 023

これは の手続きを素直に3重ループで書いたものであり、1つ1つの要素（文字1つ）について==での比較を行っています。

制約は なので、最も時間が掛かる入力ケースは a が300×300個ある行列です。これをTLE2のコードで実行すると、AtCoderのコードテストで

こうなります。惜しい…。

Ruby実装（AC）

コンテスト中にACしたコードがこちら。1699ms、ギリギリ間に合っています。

AC1：Submission #2429046 - AtCoder Grand Contest 023

TLE2のように関数化して return を使うとこうなります。実行時間にほとんど差はないです。

AC2：Submission #2434803 - AtCoder Grand Contest 023

どうしたのかというと、「転置行列」を使いました。

Rubyに限った話ではないと思いますが、2重配列というのは「配列の配列」です。行列の 行 列の要素を ss[i][j] と記載できるように2重配列を構成した場合、行それぞれが配列となっています。

ss = [            # 以下の行列を示す。
    [1, 2, 3],    # 1 2 3
    [4, 5, 6],    # 4 5 6
    [7, 8, 9]     # 7 8 9
]

そこで、「要素同士の比較ではなく、行同士の比較にすれば、Rubyで処理するループは2重ループになるのではないか？」と考えました。配列同士の比較はおそらく なので全体オーダーは変わっていませんが、Rubyの内部実装（C言語）で処理されるので高速化が期待できます。定数倍の改善と言い換えても良いかもしれません。

実際に比較しなければいけないのは行と列ですが、これを行と行の比較にしたいです。ということで思いつくのは転置です。入力行列の転置行列を予め格納しておいて、それを対称行列の判定に使えないか考えてみます。

横に1つずらした行列が対称行列であるための条件は、例えば1行目 ] と1列目 ] が等しいことです。この ] は、転置行列の3行目と一致します。他の列についても同様に、転置行列のほうに対応する行が存在します。当たり前といえば当たり前なのですが。

この性質を使えば、「入力行列の行をシフトしたもの」と「入力行列の転置行列の行」を比較することで、対称行列のチェックができます。

# ssが元の行列、sstが転置行列
(0...N).each do |a|
    success = true
    (0...N).each do |i|
        unless ss[i] == sst[(i+a)%N]
            success = false
            break
        end
    end
    if success
        sum += N
    end
    (0...N).each do |i|
        ss[i].rotate!(1)
    end
end

行のシフトには Array#rotate! を使いました。破壊的メソッドを使って、ずらし幅が1つ進むごとに1つずつシフトしています。多くの場合、非破壊的メソッドよりも破壊的メソッドのほうが速いです。

Array#rotate! は、引数が正の数の場合配列を左にずらすので注意です（これで1WA…）

[1, 2, 3].rotate(1)    # => [2, 3, 1]

追記

Submission #2436958 - AtCoder Grand Contest 023

転置を使うというアイデアはそのままに、各行を配列ではなく文字列として扱うようにすると、==での比較がさらに高速になり120msで通りました。

さいごに

Rubyのような言語を使っていると、オーダーで示される計算量だけではなく、定数倍の部分にも気を使わなければいけないことが多いですね。時間がかかる処理をC言語実装に任せる、というのは重要な視点だなあと思いました。

AtCoder AGC022-C Remainder Game 思考メモ

概要

以下の記事に乗っかって、私が「Remainder Game」を解いたときの方針について書いてみます。

競技プログラミングの強みと「典型力」について - chokudaiのブログ

AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと - pepsin-amylaseのブログ

私はこのコンテスト本番に参加してないので（AGC022の翌日にAtCoder登録しました）、後からのんびり解きました。時間はお昼ご飯タイム込みで100分くらいかかっています。

公式解説PDFではグラフ理論を使っていますが、私の解答では使っていません。ただ結局はグラフ探索っぽいDPになっているので、本質的にはそんなに違わないのかもしれません。

提出コード

Submission #2324376 - AtCoder Grand Contest 022

Rubyです。この問題をRubyで通しているの、これを書いている時点で私だけでした…

Rubyで95msなので、わりと速い？かもしれません。

考察

問題文の最もメインとなる記述は以下です。

正の整数 を選ぶ。数列のそれぞれの要素 について、アオキは を「 を で割った余り」に置き換えるか、 をそのままにするかを選べる。この一連の操作のコストは（書き換えた要素の数によらず） である。

整数の剰余の性質からすぐに分かることは以下です。

• より大きな で割ることでは、数字は変化しない。
• 以下の で割った余りは、より小さく、 より小さい。

なので、ある数 を に変化させようと思うと、 より大きな を用いても意味がありません。また、今まで選んできた 以上の数を用いても意味がありません。

言い換えると、選ぶ の列としては、 以下の数からなる（狭義の）単調減少数列のみを考えれば十分であることがわかります。

というわけで、 を に変化させることができる手続きの列を、必要な全ての について列挙してしまおうと考えました。入力となる数は50以下とそこまで大きくないので、全列挙でも間に合う可能性があると考えました。余りを取る手続きは数を小さいほうに遷移させていくので、小さい数について求めた手続き列が、大きい数についての計算で使えます。動的計画法（DP）を使います。

というところでまずはDPの実装を始めました。コストについて考えるのは後回しにします。

DPを書く

# dp[i][j]: iをjに変化させることができる手続き列の集合。
# 例えば3を0にするには、3%1=0, 3%3=0, 3%2=1,1%1=0の3つがあるので
# dp[3][0] = [[1],  [3], [2, 1]] となる
# （ただし、実際には[2, 1]は「無駄」なので含まない。本文参照）
# 手続きが存在しない/見つかっていない場合はdp[i][j] = nilとする
dp = Array.new(max_a+1){Array.new(max_a+1)}
 
(0..max_a).each do |i|
    dp[i][i] = [[]]
end

# dp[i%k][j]を使ってdp[i][j]を更新する。
# iに手続きkを行ったあとdp[i%k][j]に含まれる手続き列を行えば、iをjに変化させることができる。
# i>j かつ i>=k の範囲しか意味を持たないので、ループ範囲を絞れる 
(1..max_a).each do |i|
    (0..i-1).each do |j|
        (1..i).each do |k|
            if dp[i%k][j]
                dp[i][j] ||= []
                dp[i%k][j].each do |pro|
                    dp[i][j].push([k] + pro) unless dp[i][j].include?(pro)
                end
            end
        end
    end
end

dp の定義とループでやっていることについては、コード中のコメントで簡単に補足しています。

このDPにおいては「無駄なパターンを数え上げないこと」が大事で、無駄なパターンが増えるとどんどん後のほうでパターン数が爆発していきます。全列挙と言ってはいますが、明らかに無駄なものは存在します。それを弾いているのが以下のコードです。

dp[i%k][j].each do |pro|
  dp[i][j].push([k] + pro) unless dp[i][j].include?(pro) # ここ
end

pro は dp[i%k][j] に含まれる手続き列で、これの先頭に k を加えれば dp[i][j] の要素が出来上がります。ただ、k を加えなくても、元の手続き列で i を j に変化させられる場合、この k を含んだパターンを使うことはコストの無駄なので、加えなくて良いです。

実際の例を挙げます。例えば3を0にするには、3%1=0 3%3=0 3%2=1,1%1=0 という手続き列のパターンがあり、これを全て含めると dp[3][0] = [[1], [3], [2, 1]] となります。ただし、[1] だけで十分なのに、[2, 1] とわざわざ2を使うのは無駄です。上記の処理では、こういったものを弾いています。

最初はこの処理を入れておらず、無駄にパターンが増大しているせいで処理時間とメモリを大量に消費していました。無駄が多いことは、実際に dp の中身をデバッグ出力しているうちに気付きました。

10以下の範囲で列挙した dp は、以下のようになります。

分かりやすいものだと、dp[6][0] = [[1], [2], [3], [6]] です。6の約数のどれで割っても余りが0になります。この他にも例えば [4, 2] なども条件を満たしますが、[2] だけで十分なので入っていません。これは先述の「無駄なパターン」に該当します。

ところで、今回パターンの全列挙を行っているのは、この1回のDPで求めた結果を最後まで使うためです。対して公式解説PDFの方法では、部分問題を何度も解くかわりに、1回の部分問題はグラフの到達可能性という簡単な問題となっています。

実際の入力から最適コストを計算

DPによって、i を j に変化させることができる手続きの列を列挙できました。というところで、実際の入力を扱います。入力 のペアそれぞれを、手続きの列にマッピングします。

arr_of_procs = N.times.map{|i| dp[a[i]][b[i]]}

どれかのペアについて dp[a[i]][b[i]] が nil である場合は、 を に変化させる手続き列が存在しないということなので、-1を出力して終了します。

ここからどのように最適コストを求めればよいか考えます。

手続き のコストは です。これは、手続き を行ったときのコストが、手続き のコスト合計より高いことを意味します。つまり、代わりに小さな数値をいくら使うことになろうとも、大きな数値は使いたくないわけです。

この考えのもとで、使う数を決めている部分が以下です。

use = 0
arr_of_procs.each do |procs|
    need = procs.map{|pro| pro.max}.min
    use = [need, use].max
end

min と max がごちゃごちゃして分かりにくいので…実例を挙げます。例えば、dp[13][2] = [[7, 4], [8, 3], [11]] です。これらの手続き列のうち、最もコストが低いのは [7, 4] です。要素の数に関わらず、最大値が一番小さい手続き列が、最もコストの小さいものになります。つまりこのペアにとっては、次に が選ばれることが最も嬉しいです。

各ペアについてこのような数を求めていき、その最大値を使う…というのが、上のコードでやっている処理です。

使う数が決まったら、コスト加算とともに、その use による手続きを行います。

if use > 0
    cost += 2**use
    arr_of_procs.each do |procs|
        procs.each do |pro|
            pro.delete(use)
        end
    end
end

実装コードでは、全ての手続き列から use を削除しています。ただ、a[i] %= use と置き換えて dp[a[i]][b[i]] を代入し直したほうが、分かりやすくて速いと思います…

これを繰り返していくと、いずれかの手続き列が [] になります。こうなると、そのペアについてはそれ以上の手続きは不要です。（手続きによって の2つの数が一致したということを意味します。）なので、そのペアを取り除いていきます。全てのペアが取り除かれた時点で手続きは終了です。

arr_of_procs.length.times do |i|
    arr_of_procs[i] = nil if arr_of_procs[i].include?([])
end
arr_of_procs.compact!
break if arr_of_procs.length == 0

最後にコストを出力して終わりです。

さいごに

かなり長くなりました。読んでくださった方、ありがとうございました。

私自身、公式解説PDFだけだとなかなか理解が追いつかない問題も多く、思考過程や実装などを解説した他の方の文章は非常に助かっています。この文章も、誰かの参考になれば幸いです（実装が競技プログラミングではマイナーなRubyというのが申し訳ないですが…）

Rubyでポンの対戦を作っています

まだ全然できてないけど。

とりあえずフィールドを2つ並べて、左は自分が動かして、右はAIで動かして、どちらかがゲームオーバーになったら終了、っていうのはできました。

あとはオジャマを作れば一応対戦はできる…かな？オジャマを作るのもけっこう面倒そうですが。

ゆくゆくはこれの入力と描画をJavaScriptなどに置き換えて、Web上にホスティングしてブラウザで遊べるようにするとか、オンライン対戦とか、できたらいいなーという野望を持っているのですが…いつになることやら。まだまだ勉強すべきことはたくさんありますね。

リファクタリングと妥協を繰り返して君だけの.rubocop.ymlを作ろう

前回Rubocopで315個の警告を出した話を書きましたが、色々警告の意味を調べたり試行錯誤しながら、.rubocop.ymlを作って警告ゼロまで持っていきました。

超あまあま設定です。

Lint/NonLocalExitFromIterator:
  Enabled: false

eachの中でreturnとか書くのを許す設定。

def hoge
  (0...X).each do |x|
    return if ...
  end

  ...
end

のように、配列の要素を順に見て行って、要素の1つでもある条件を満たしていたら即メソッド終了、みたいなときに使いたい。

Lint/UnderscorePrefixedVariableName:
  Enabled: false

_で始まる変数名を許す設定。

(0...X).each do |x|
  (x...X).each do |_x|
    ...
  end
end

のように、同じ次元（？）の変数で多重ループを回すときの変数名として使いたい。

Metrics/AbcSize:
  Max: 35

Metrics/ClassLength:
  Max: 200

Metrics/CyclomaticComplexity:
  Max: 9

Metrics/MethodLength:
  Max: 25

Metrics/LineLength:
  Max: 100

Metrics/PerceivedComplexity:
  Max: 11

メトリクス系はわりと適当ですが、リファクタリングしていって「これ以上減らすのはしんどい」と思った時点での値を目安にしてます。

Style/BracesAroundHashParameters:
  Enabled: false

ハッシュをメソッドの引数にするときに{}を省略できるけど、書いてもいい設定。

Style/Documentation:
  Enabled: false

ドキュメント用のコメントは付けなくていい設定。

Style/GuardClause:
  Enabled: false

Style/Next:
  Enabled: false

ガード節にできるところでif endでもいい設定。ガード節にするかif endにするかは意味として自然なほうを採用したいので、行数だけ見てガード節にさせようとする設定はオフに。

Style/HashSyntax:
  EnforcedStyle: hash_rockets

ハッシュリテラル書くときの=>これ。前回も書きました。

Style/LineEndConcatenation:
  Enabled: false

文字列などを複数行に渡って書くときに、行末の+でつないでもよい設定。単に他言語と共通する記法にしたいだけ。

Style/NumericLiterals:
  Enabled: false

長い桁の数を10_000などと書かなくてもいい設定。慣れない。

Style/RedundantReturn:
  Enabled: false

returnがなくてもいい場所で書いてもいい設定。明示的に値を返してメソッドが終わる時は書くようにしたい。書いてないと、後ろ側に何か処理を加えたい時、そこにreturnがあるべきなのかどうか分からなくなりそう。

Style/SymbolProc:
  Enabled: false

array.map(&:somemethod)みたいな書き方ができる場所でしなくてもいい設定。慣れない。

.rubocop.ymlに書いた項目は以上。Ruby哲学は難しい…

Rubocopを走らせたら664行のコードで315個のoffenseが出た

昨日の時点でのRubyでポンのコードをかけてみたら、

1 file inspected, 315 offenses detected
Created .rubocop_todo.yml.
Run `rubocop --config .rubocop_todo.yml`, or
add inherit_from: .rubocop_todo.yml in a .rubocop.yml file.

ひどい。

警告数ランキング

吐き出された.rubocop_todo.ymlを見て、多いやつから順に見ていく。

1位：77個

# Offense count: 77
# Cop supports --auto-correct.
Style/TrailingWhitespace:
  Enabled: false

ぶっちぎりで大量に警告されてるのが、行末のスペース。要は何かというと、インデント中の空行のスペース。

行を足すときはあったほうが何かと便利だし、わざと残してる人もけっこういるみたいで、悩みどころ。エディタでの保存時に行末スペース全部取ってくれる機能があったので、それを使うことにした。

空行のインデントは活かす前提で、空でない行の末尾スペースを警告してくれる設定があればいいのにな、とは思います。

2位：33個

# Offense count: 33
# Cop supports --auto-correct.
# Configuration parameters: EnforcedStyle, SupportedStyles, ProceduralMethods, FunctionalMethods, IgnoredMethods.
Style/BlockDelimiters:
  Enabled: false

{}とdo endをちゃんと使い分けろって話。今のエディタだとeachの後にスペースを入れた時点で{|| }まで補完してくれるので、全部{}になってた。

ぶっちゃけどっちでも良いような気もしていたが、「if や while が end で終わるので、それとそろえたほうがよい」というのを見て確かにそうだと思ったので、行をまたぐ場合はdo endに直すことにする。ついでにエディタも乗り換えてやろうか。

3位：24個

# Offense count: 24
# Cop supports --auto-correct.
# Configuration parameters: MultiSpaceAllowedForOperators.
Style/SpaceAroundOperators:
  Enabled: false

演算子前後のスペース不足ね。はい、心当たりあります。

panels[x+1][y-1]
# panels[x + 1][y - 1] って書けって言われてる

こういう奴。個人的には前者のほうが見やすいんだけど…ちょっと保留。

4位：23個

# Offense count: 23
# Cop supports --auto-correct.
# Configuration parameters: EnforcedStyle, EnforcedStyleForEmptyBraces, SupportedStyles.
Style/SpaceInsideHashLiteralBraces:
  Enabled: false

ハッシュの{の後とか}の前にスペースが要るか、とかそういう話。両方試したけど特にどっちでも良いかなと思ったので、デフォルト設定に従ってみる。

少し特殊ケースですが、

input_hash = { :up          => Input.key_push?(K_UP),
               :down        => Input.key_push?(K_DOWN),
               :right       => Input.key_push?(K_RIGHT),
               :left        => Input.key_push?(K_LEFT),
               :exchange    => Input.key_push?(K_SPACE),
               :force_slide => Input.key_down?(K_Z)      }

みたいな時の閉じカッコってどこに置くのがスマートなんでしょね。何となくの感覚で、最長の行の末尾+スペース1個の位置に置いてるけど。

5位：22個

# Offense count: 22
# Cop supports --auto-correct.
# Configuration parameters: SupportedStyles, UseHashRocketsWithSymbolValues.
Style/HashSyntax:
  EnforcedStyle: hash_rockets

=>これ。すいません、これは使わせてください。好きなんです。

理由は単純で、リテラル記述と値の取り出しでキーの見た目が同じになるから、です。

hash = { :first => 1, :second => 2 }
puts hash[:first] # 見た目が同じ

hash = { first: 1, second: 2 }
puts hash[:first] # 見た目が変わる

まとめ

315個はさすがにビビりましたが、種類自体はそんなに多くないので…一通り意味を調べて、「これは譲れねえ！」ってやつだけ見逃してもらって、自動修正（auto_correct）してもらおうと思います。

本当に怖いのは、登場回数が少なくてかつauto_correctできないやつだったりしますよね（クラスが長いとか…）

パズルゲームのAIってどうやって作ればいいんだろう

今日、将棋の棋士とコンピュータが戦う電王戦（in ニコニコ生放送）を観てました。私は第3戦から見始めたのですが、すごく面白かったですね。多くの解説者やコメントが、無条件に棋士を応援する感じだったのは、ちょっと違うよなあと思ったのですが。

パネポンのAIを作りたい

さて、あの将棋ソフトのようなすごいものを作ろうとは全く思ってないのですが、パネルでポンのクローンとして作っている「Rubyでポン」にも、AIを付けたいとは思っていまして。

パネル交換や消滅といった基本動作、連鎖と同時消しの判定まではできてきたので、次にやるとしたら対戦かなと。対戦だとおじゃまを落とすとかの機能ももちろん必要なのですが、対戦相手のAIはとにかく何をすれば良い感じに実装できるのか全く予想がつかないので、最近は「パズルゲーム AI」みたいなので検索をかけてたりしたわけです。いまいち良い情報はなかったですが。

というわけで、どういう要素を作ればいいのかもやーっと考えているものを、整理も兼ねて書き出してみようと思います。評価関数式とか強化学習とか今の自分の知識じゃできっこないのでルールベースです。

ルール1：パネルを消す

横を入れ替えて行けば消せるパネルを探して消す。基本となる操作です。横1列に同色パネルが3つあるか、隣り合う横3列で1個以上ずつ同じ色のパネルがあれば、揃えにいく、とかですか。

パネルを一度落とさないと（高さの座標を崩さないと）消せないパターンについては、上記の単純な方法だと探せないので、難しいかも。

ルール2：同時消しを狙う

基本的には縦消しが主だと思いますが、隣り合う横4列以上に同じ色があった場合、同時消しを狙うようにします。

ルール3：連鎖を狙う

ちょっと難しくなってきました。組み連鎖のパターンを覚えてもらって、その形が横移動だけで作れそうかということを判定するとか（ぷよぷよだと、連鎖の形はかなり定跡化されてますよね）。ただそれだとパネポンっぽくないので、なんとかしてアクティブ連鎖をさせられないかなー。

ルール4：整地する

対戦ですぐ死なないようにするためには必要でしょう。特に実装は難しくなさそう？

消える処理の探索を簡単にするために、常にある程度は整地しておく、というアルゴもありかなーとは思います。

ルール5：おじゃまを優先して消す

これも対戦用。おじゃまを待ち構える連鎖（いわゆるカウンター）もできるといいですね。

本当は詰み防止の消せるパネル残しとかもやりたいけど、とりあえずそこまではいいかな…

さあ、作ろう

みたいなのを考えつつも、まだ全然コードに手をつけられていない自分。明日は書こうと思います。