ふとAtCoderのルールを見てみると、言語にPrologが追加されてました。
今僕はAtCoderをJavaかSchemeで解いています。よくこのブログではSchemeを使う理由を「扱える整数の幅がでっけぇ」みたいに書いてますが、もっというと
・大学で習った言語のうちの1つだから
・他にAtCoderで使っている人が少なくて嬉しいから
というのが根本的な理由です。
ただですね、、、人生で一番最初に習った言語はPrologなんですよ。。。
ちなみに、それゆえプログラミングに取り組むのが2年くらい遅れました。大学2年？のときくらいに授業でやって、「さっぱり分からん、プログラミングってあまり得意じゃないな」と思って、なんとなく避けるようになったという経緯です。
そのあと、大学院の研究でRを使い→誘われた競技プログラミングの大会(オンサイト)でRを使って必死に解き→競技プログラミングにハマる、という流れで現在に至ります。
前置きが長くなりましたが、私は上記の条件を満たすPrologでAtCoderを解かなければいけない。いけないんだ。
ということで、とりあえずPrologでAtCoderの問題をいくつか解くぞという記事です。
参考にさせていただいた記事
qiita.com
@n4o847さん、Prologは無事、AtCoderで使えるようになりました・・・！
入出力について
AtCoderをやる上で一番難しいでおなじみ、標準入出力。上記の初めて出た競技プログラミングの大会でも、大会時間の半分は"Rでの標準入出力のやり方"を調べるのに使ったのを鮮明に覚えています。
@n4o847さんのQiita記事を参考にすると、数字や文字列を受け取るときは、自分で新しい関数を定義しなきゃいけないようです。
get_string(String) :- current_input(Input), read_string(Input, ' \n', '', _, String). get_number(Number) :- get_string(String), number_string(Number, String).
get_numberの中にget_stringを使っていることに注意。get_numberのみでは動作しません。
文字は、もともと関数があります。
get_char(A).
N個の数字を入力するには、引数2個の下記のような関数を定義します。
get_numbers(0, []). get_numbers(N, [X|Xs]) :- get_number(X), N1 is N - 1, get_numbers(N1, Xs).
解いてみるぞ！
直近のAtCoderBeginngerContestのA問題を解いてみます。
ABC170のA問題
入力される数字5個を足し、15から引くとよい。
get_string(String) :- current_input(Input), read_string(Input, ' \n', '', _, String). get_number(Number) :- get_string(String), number_string(Number, String). main :- get_number(X1), get_number(X2), get_number(X3), get_number(X4), get_number(X5), Ans is 15 - X1 - X2 - X3 - X4 - X5, write(Ans). :- main.
無事AC。
もうちょいムズいのも解いてみるぞ！
次は、inputが可変個の問題にチャレンジ。最近の問題から、下記を解いてみます。
atcoder.jp
入力される数の個数であるNがN <= 1000だから、挿入ソートでも充分間に合うなぁと書こうとするも・・・・
全く書けず・・・・・・・
普段もSchemeでプログラムを書いたりするから、リスト的な書き方には慣れてると思っていたものの、Prologは論理型。やはり関数型と違う・・・
例えば、リストの先頭k個の数の合計を算出する関数get_k_numsというものを書く場合、Schemeだとこうなります。
(define (get_k_nums k list) (if (= k 0) 0 (+ (car list) (get_k_nums (- k 1) (cdr list)))))
ただ、Prologの場合はこう。
get_k_nums(X, 0, 0). get_k_nums([X|Xs], C, Sum) :- C1 is C - 1, get_k_nums(Xs, C1, Nextsum), Sum is Nextsum + X.
特に、 『get_k_nums(Xs, C1, Nextsum)』と『Sum is Nextsum + X.』の順番にとても違和感。
色々トライして、エラーになる原因を考えて(AtCoderのコードテストだとエラー原因がちゃんと出ず)、とやってきたから今は少し分かるようになってきましたが、取り組み始めた段階では全く上手くいかず・・・
そして、最終的にはWikipediaのPrologのページ(めちゃくちゃ例が充実している)を参照して挿入ソートを書き、無事ACとなりました。。。
コードはこんな感じ。
get_string(String) :- current_input(Input), read_string(Input, ' \n', '', _, String). get_number(Number) :- get_string(String), number_string(Number, String). insert_sort(L1,L2) :- insert_sort(L1,[],L2). insert_sort([],L,L). insert_sort([A|R],L1,L) :- insert(A,L1,L2), insert_sort(R,L2,L). insert(A,[],[A]). insert(A,[B|R],[A,B|R]) :- A @=< B,!. insert(A,[B|R1],[B|R2]) :- A @> B, insert(A,R1,R2). get_numbers(0, []). get_numbers(N, [X|Xs]) :- get_number(X), N1 is N - 1, get_numbers(N1, Xs). get_k_nums(X, 0, 0). get_k_nums([X|Xs], C, Sum) :- C1 is C - 1, get_k_nums(Xs, C1, Nextsum), Sum is Nextsum + X. main :- get_number(N), get_number(K), get_numbers(N, A), insert_sort(A, B), get_k_nums(B, K, Ans), write(Ans). :- main.
ちなみに、かかった計算時間は89ms。計算速度自体は問題なさそうです。
まだまだ上手く書けないですが、たまにはPrologにも取り組んで行きたいところです。
まずは自分がこれまで書いてきたSchemeのコードをPrologに直していくところからでしょうか。もしナイスな勉強方法や、Prologゆえにキレイに解けるAtCoderの問題があればご教示いただけると幸いです。
マイナー言語でAtCoder解く、頑張るぞ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
