Babashka なら Clojure でも AtCoder ができるんじゃないか？

AtCoder with Babashka

Clojure は実行が遅い！ (というか最近のバージョンアップデートで既存のコードも TLE するようになった orz)

Babashka (https://github.com/babashka/babashka) ならもうちょっと早く実行できるんじゃないか？という実験と、Clojure でも B 問題くらいならまだ解ける、という話です。

Install

git clone https://github.com/MokkeMeguru/atcoder-babashka
cd atcoder-babashka
rm -rf .git
./install.sh

babashka が $HOME/.bbsk に保存されます。

AtCoder をやってみる

サンプルとして、ABC086A Product https://atcoder.jp/contests/abs/tasks/abc086_a をやってみましょう。

まずは、環境を立ち上げます。

make env PROBLEM=https://atcoder.jp/contests/abs/tasks/abc086_a

テストの入力、出力、そして編集すべきコード (codes/abs/abc086_a.clj) が生成されます。

python tools/build_env.py https://atcoder.jp/contests/abs/tasks/abc086_a
2021-04-18 01:00:51,680 - build_env - INFO - start
2021-04-18 01:00:51,803 - build_env - INFO - migrate test inputs
2021-04-18 01:00:51,804 - build_env - INFO - migrate test outputs
2021-04-18 01:00:51,804 - build_env - INFO - migrate source code
2021-04-18 01:00:51,804 - build_env - INFO - catch file create error codes/abs/abc086_a.clj is already exist
2021-04-18 01:00:51,804 - build_env - INFO - done

コードを書く

コードの生成を確認したら、実際にコードを書いてみましょう。 本レポジトリでは AtCoder の形式としてテンプレートとなりそうなものを、 tools/templates/temp.clj として生成しています。

サンプル実装

(defn ->input-model [_]
  (let [[a b] (->> (read-line) trim split-by-white (map #(Integer/parseInt %)))]
    [a b]))

(defn solve [[a b]]
  (even? (* a b)))

(defn output [even?]
  (if even?
    (println "Even")
    (println "Odd")))

コードを書いたら、テストを行う

テスト方法は大きく分けて2つあります。

一つは、REPL を用いたもので、こちらはお使いの環境に従って下さい。
もう一つは、AtCoder のサンプル入力を用いたもので、次のようにしてテストを行うことが出来ます。

make test PROBLEM=https://atcoder.jp/contests/abs/tasks/abc086_a

ログとしては次のようになります。

python tools/test_code.py https://atcoder.jp/contests/abs/tasks/abc086_a
2021-04-18 01:11:28,245 - test_code - INFO - start
Test Case 0 :passed 👍
Test Case 1 :passed 👍
2021-04-18 01:11:28,272 - test_code - INFO - end

テストが通ったら

AtCoder のページより、提出を行って下さい。

Q & A

テンプレートを変えたいんだけど

Makefile の TEMPLATE を変えるか、 make env の引数に TEMPLATE=<path-to-template> を追加して下さい。

AtCoder の Clojure 流石におそすぎない？

はい、遅いです。特に競プロゴリゴリしたい言語ではないので、あんまり言語アップデートなどにアンテナを張っていなかったせいです。
ただ、アップデートで AC が TLE に化けているらしいので、ちょっとやだなーと思っています。

(テストのため、AtCoder に登録したら解くべき精選過去問 10 問を Clojure で解いてみた https://qiita.com/fireflower0/items/92af088fea314a6cbcc2 さんのコードをお借りしました。ありがとうございます。)

その他

Clojure で 競技プログラミング！というのは、趣味でやりたい人を除いて、正直な所全くおすすめできません。 理由としては、

• 人気のあるツールは環境が整っているので、高いスコアが得られやすい
• 知見が少ない (出題者の脳みそも有限なので、過去の問題の知見が生きやすい)
• 知見のアウトプットに苦しい

などが挙げられます。

また、少なくとも AtCoder なら Python 使ったほうが良いです。(メモリとか実行速度とか以前に、許されているライブラリが多すぎるため) あとは C++ (AtCoder Library) とか、それぞれの公式が推しているものを使いましょう。

例えば、Python で組み合わせを計算するならば、

seq = range(10)

import itertools

len(list(itertools.combinations(seq, 2))) == 45

とすればアルゴリズムを考えずとも実装できますが (チューニングの話はさておき)、Clojure では

(def seq (range 10))

(defn combination
  ([n k]
   (cond
     (or (zero? n) (zero? k)) []
     (< n k) []
     (= n k) (mapv vector (range n) (range n))
     :else (vec (filter some? (combination n k [] 0)))))
  ([n k candidate acc]
   (cond
     (= k (count candidate)) [candidate]
     (<= n acc) nil
     :else (concat (combination n k (conj candidate acc) (inc acc))
                   (combination n k candidate (inc acc))))))

(= 45 (count (combination 10 2)))

とだいぶ面倒くさくなります。