AtCoder用のmixタスクを作ってみた

この記事は Elixir Advent Calendar 2020 17日目の記事です

昨日は @koga1020 さんで「Refactoring a Function in Elixir」のblog postを読んでみようでした！

---

9月に参加した Elixir Digitalization Implementors #1 にて、ElixirでAtCoderに参加できるということを教えていただきました

今まで会社にも競技プログラミングやっている人たちがいて、面白いらしいということを聞いてはいたのですが、新しい言語勉強するのもなーって思い、参加していませんでした。。。
(去年に試しに一回だけコンテストやってみましたが、それっきりでした)

ただElixirで参加できるのなら、仕事でElixir書く機会もないし、やってみるかと思い改めて参加してみたところ、ドハマリし、現在 緑レート目指して精進中です

コンテストに参加していると、コードをテンプレートコードのコピペや実行などが面倒だと思ったので、mixタスクを書いてみました。

作成したもの

ex_at_coder という名前で公開しております

hex
https://hex.pm/packages/ex_at_coder

Github

簡単な機能紹介

今のところは以下の機能があります

• ログイン
• 提出用テンプレート作成
• 提出用コードの実行テスト

インストール

hexに登録してあるので、以下をmix.exsに記述した上でmix deps.getでインストールすることができます。

mix.exs

{:ex_at_coder, ">0.0.0"}

ログイン

$ mix atcoder.login [username] [password]

指定されたusername passwordでAtCoderにログインします。

終了しているコンテストなどはログインしなくても閲覧できますが、開催中の場合はログインが必須になります。
ログインに成功した場合は、現在のディレクトリにcookie.txtが作成されます。

cookieをまるごとテキストファイルで保存しちゃっているのがあんまりよくない気がしますが、とりあえずこうしちゃっています

提出用コードの作成

$ mix atcoder.new [contest]

上記コマンドで指定したコンテスト用の提出ファイルの雛形とテストケースの作成を行います。
例えば AtCoder Regular Contest 109( https://atcoder.jp/contests/arc109 )でしたら
arc109 と指定します

$ mix atcoder.new arc109
Generated ex_at_coder app
* creating lib/arc109
* creating lib/arc109/a.ex
* creating lib/arc109/test_case
* creating lib/arc109/test_case/a.yml
* creating lib/arc109/b.ex
* creating lib/arc109/test_case/b.yml
* creating lib/arc109/c.ex
* creating lib/arc109/test_case/c.yml
* creating lib/arc109/d.ex
* creating lib/arc109/test_case/d.yml
* creating lib/arc109/e.ex
* creating lib/arc109/test_case/e.yml
* creating lib/arc109/f.ex
* creating lib/arc109/test_case/f.yml
✨ Generate code for arc109
👍 Good Luck

コマンドを実行すると、提出用コードと実行テスト用のテストケースのyamlファイルを出力します。

問題はhttps://atcoder.jp/contests/[contest]/tasksのページから取得します。
提出ファイルの雛形に用いるテンプレートのEEXは以下の形でconfig.exsで指定することができます。

config :ex_at_coder,
  template_path: "lib/template.eex"

defmodule <%= @namespace %>.Main do
    def read_single() do
    IO.read(:line) |> String.trim() |> String.to_integer()
  end

  def read_array() do
    IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
  end

  def main() do
    n = 
      IO.read(:line)
      |> String.trim()
      |> String.to_integer()

    IO.puts(n)
  end
end

提出用コードの実行テスト

$ mix atcoder.test [contest] [problem]

指定したコンテスト、問題のテストケースを実行します。
デフォルトでは問題ページにある入出力サンプルをテストケースとして実行します

テストケースの入出力は lib/[contest]/test_case 以下にある yaml で設定できます。

lib/arc109/test_case/a.yml

- name: sample1
  in: |
    2 1 1 5
  out: |
    1

- name: sample2
  in: |
    1 2 100 1
  out: |
    101

- name: sample3
  in: |
    1 100 1 100
  out: |
    199

実装について

ここからが本記事のメインになります。
実装にあたって苦労したところは主に以下の点になります。

• ログイン状態の保持
• mixタスク上でのコードの実行
• mixタスク上で標準入力/出力を制御する

ログイン状態の保持

ex_at_coderは HTTPoison + Flokiの組み合わせで実装しました。
ログイン部分は以下のような実装になっています

  @base_url "https://atcoder.jp"

  def login(username, password) do

    csrf_token =
      HttpClient.get(@base_url <> "/login")
      |> Floki.parse_document!()
      |> Floki.attribute("input[name=csrf_token]", "value")
      |> List.first()

    params =
      [
        username: username,
        password: password,
        csrf_token: csrf_token
      ]

    HttpClient.post(@base_url <> "/login", params)
    ...
  end

ログインフォームにアクセスし、CSRFトークンを探して、それをログインフォームのエンドポイントにPOSTリクエストし、得たcookieを使う・・・といった感じになります。

ただしここで少しハマったのがAtCoderのサイトは毎リクエストごとに set-cookieでセッションcookieを上書きしているようでした。

HTTPoisonはset-cookieを自動でいい感じにstoreしてくれる機能はありませんから、自前でどうにかする必要があります。

以下のforumに投稿されたコードを参考にリクエストごとにcookie.txtに吐き出すようにしてみました
Help with HTTPoison POST - Elixir Forum

これで一応ログイン状態は保持できるようになりました

提出用コード/テストケースの作成

こちらは単純に問題ページの中からサンプルケースを探して、ymlに落とし込んでいるだけです。
yamlまわりに関しては以下のライブラリを使わせていただきました。

ファイル生成については、以下の関数を使用しました。

Mix.Generator.create_file/3
Mix.Generator.copy_template/4
このへんを使うといい感じに出力してくれるので楽ですね

生成するコードのモジュール名は defmodule [Contest].[Problem].Main do の形式にしてしまっています。

AtCoderで提出するときは defmodule Main do のような形にする必要があるのですが、mixプロジェクト内で他のモジュールと名前がかぶってしまうとよくないので、コンテスト名.問題名をつけるようにしました。

mixタスク上でのコードの実行

$ mix atcoder.test arc109 a

としたときに　Arc109.A.Main.main() を実行してあげたいです。

最初は単純に以下のように実行すればいいと考えていたのですが、

:timer.tc(Arc109.A.Main, :main, [])
# 実行時間を取得したいので:timer.tc/3を使用する

他のmixプロジェクトにインストールして実行したときに問題がおきるようになってしまいました。

:timer.tc(Arc109.A.Main, :main, [])
# 実行すると :undef エラーになってしまう

Elixirのコンパイル周りがどうなっているのか全然わかりませんが、おそらくmixタスクとして実行する際は大本のmixプロジェクトのモジュールはロードされていないのだと思います。

そこでModule Kernel モジュールなどそれっぽいモジュールを探したところ、使えそうなモジュールを発見しました

それが Codeモジュールになります。
この中の Code.require_file/1 を実行前に呼び出すようにしたところ、無事に実行されるようになりました

Code.require_file(file) # file: "lib/arc109/a.ex"
:timer.tc(Arc109.A.Main, :main, [])
# 実行された🎉

mixタスク上での標準入力/出力の制御

AtCoderでは問題文の入力を標準入力で、解答を標準出力で行います。

例えば入力された数値を2倍するという問題があったときは以下のようなコードになります。

defmodule Main do
  def main() do
    input = IO.read(:line) |> String.trim() |> String.to_integer
    IO.puts(input * 2)
  end
end

これをmixタスクでテストケースの確認を実行するときにymlに書かれた入力を標準入力として渡し、解答を標準出力から取得する必要があります

最初は以下のようなスタブを渡そうかと思いましたが、なんとなくすっきりしなく、別の方法をさがしました。

defmodule Main do
  def main(io \\ IO) do
    input = io.read(:line) |> String.trim() |> String.to_integer
    io.puts(input * 2)
  end
end
# mix atcoder.text時には別のIOを渡す

そこでElixirのテストライブラリであるExUnitがそういえば標準出力をキャプチャしていた気がするなと思い、コードを覗いてみました。

それっぽいのはこの辺ですね。

lib/ex_unit/lib/ex_unit/capture_io.ex

  defp do_capture_io(:standard_io, options, fun) do
    prompt_config = Keyword.get(options, :capture_prompt, true)
    encoding = Keyword.get(options, :encoding, :unicode)
    input = Keyword.get(options, :input, "")

    original_gl = Process.group_leader()
    {:ok, capture_gl} = StringIO.open(input, capture_prompt: prompt_config, encoding: encoding)

    try do
      Process.group_leader(self(), capture_gl)
      do_capture_gl(capture_gl, fun)
    after
      Process.group_leader(self(), original_gl)
    end
  end

どうやら StringIO と Process.group_leader が肝っぽいです。

というわけで、参考にしつつ以下のようにしてみました

    original_gl = Process.group_leader()
    {:ok, io} = StringIO.open("1", capture_prompt: false, encoding: :unicode)
    Process.group_leader(self(), io)

    {runtime, output} =
      try do
        {runtime, _} = :timer.tc(Arc109.Main.A, :main, [])
        runtime
      catch
        _, _ ->
          {-1, :error}
      else
        runtime ->
          {:ok, {_input, output}} = StringIO.close(io)
          {runtime, output |> String.trim}
      after
        Process.group_leader(self(), original_gl)
      end

# output => "2"

標準入力/出力をコード上でコントロールすることができました

おそらく以下のような流れで処理している気がします

1. Process.group_leader() で現在実行している処理の親プロセス?を取得
2. StringIO.open/2 で疑似的なIOデバイスを作成
3. Process.group_leader(self(), io) で親プロセスを先程作成したIOデバイスに変える
4. 処理を実行
5. StringIO.close(io) で疑似IOデバイスを終了し、バッファに残っている文字列を取得する
6. Process.group_leader(self(), originarl_gl) でもとの親プロセスに戻す

※詳しい方いらっしゃいましたらやわらかいマサカリを投げていただけると嬉しいです！

これでコードの実行と実行結果の取得ができましたので、テストケースのyamlと照らしあわせ、正解かどうかを判定しています。

{_, :error} -> IO.ANSI.red_background <> IO.ANSI.white <> " RE " <> IO.ANSI.reset()
{_, o} when o != test_out -> IO.ANSI.yellow_background <> IO.ANSI.black <> " WA " <> IO.ANSI.reset()
{r, _} when r > 2000_000 -> IO.ANSI.yellow_background <> IO.ANSI.black <> " TLE " <> IO.ANSI.reset()
_ -> IO.ANSI.green_background <> IO.ANSI.black <> " AC " <> IO.ANSI.reset()

ちなみに結果部分は上記のようなIO.ANSIを使って色付けしています。
本当はもっとかっこいい出力にしたいのですが、僕ではこれが限界でした・・・

まとめ

というわけで拙作 ex_at_coder の紹介をさせていただきました！
まだまだ機能不足＆色々不安定ですが、コメントやPRなどをいただけると嬉しいです！！

AtCoderでのElixirについて

本題とは関係ないですが、最後にAtCoderでElixirを使う感想もちょろっと書こうと思います。
ぶっちゃけAtCoderでElixirの使用は向いてないと思います

AtCoderで実行速度が遅いと言われているPython, Rubyあたりと比べても更に10倍以上遅い気がします。
AtCoderでは実行時間に制限があるため、これが非常に厳しいです。。。。

また競技プログラミングで使うアルゴリズムでは配列,Mapなどをよく使うのですが、Elixirではこれらのデータに対して O(1) でアクセスすることができません。
これが非常に厳しく 10^5 ~ オーダーのデータ管理が要求されるため、実行時間が膨らみがちでです。

まだそれほどの量の問題を解いたわけではありませんが、想定解どおりに実装しても実行時間オーバーになることも珍しくないような気がしています.

Elixirで解けないのが悔しすぎて、何を血迷ったか Elixir Forum に助けを求めたこともありました
https://elixirforum.com/t/can-someone-solve-this-competitive-programming-problem-in-elixir/35252

.....ですが、やはりElixirのシンタックスは素晴らしく、パターンマッチングを使って(自分基準で)美しいコードで問題を解けたときなどは非常に達成感があります

そもそもまだまだ実力不足なので、実際のコンテストに参加したときにElixirのせいで成績がふるわなかったということは今のところありません。。。。

さらにそもそもElixirで解けない問題があるというのも、Elixir愛が足りていないだけかもしれません
そこでもっともっとElixirを使ってAtCoderに参加してくれる人が増えてくれると、効率的な書き方が発見され、解ける問題が増えるかもしれません！！

ちなみに僕が現在Elixirでこれ無理だろって諦めてしまった問題は、例えば以下になります。
解いてくれる錬金術師をお待ちしております！！！！

• 三井住友信託銀行プログラミングコンテスト2019 D Luck Pin
• AtcoderBeginnerContest113 C ID
• AtcoderBeginnerContest138 D Ki
• AtCoder Beginner Contest 153 E - Crested Ibis vs Monster
• Tenka1 Programmer Contest C - 4/N