プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

AtCoderで、提出したschemeプログラムを向こうでコンパイルする方法

今日も今日とて、一番得意な?言語であるschemeで、ちょくちょくAtCoderの問題を解いています。


さて、今回はタイトルの通り、AtCoderのシステム内でなんとかschemeをコンパイルして使う、ということについてです。
それをやろうと思ったきっかけはこの問題。

AtCoder Beginner Contest #06 B問題 トリボナッチ数列


この回は確か、初めてBeginner Contestで時間内に3問解けた回です。嬉しい。
ただ、このB問題は、1つ目のコードを提出した時にTLE(=制限時間(=2sec)オーバー)になっていました。
そのコードは以下のものです。

(define nn (read))
 
(define (trib an ann annn count limit) (cond ((< limit 3) 0)
                                              ((= limit count) an)
                                              (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit))))
 
(define answer (trib 1 0 0 3 nn))
(display answer)
(newline)

tribという関数は、引数として、an、ann、annn、count、limitを持っています。
それぞれ順に、a_(n)、a_(n-1)、a_(n-2)、n、目標を表しています。
多分、この問題をschemeで解こうとするには割と妥当なコードだと思うのですが・・・
これがTLEとなってので、かなり焦りました。まだ経験の少ない僕にとって、絶対解けると思っていたものがTLEになると焦るものです。

そして、この問題で与えられるnのサイズが最大で1000000であることから、何回も呼び出される関数tribのどっかの手間をなくしたらいいのかな、と思いました。
というわけで、少し改善した結果がこちら。

(define nn (read))

(define (trib an ann annn count limit) (cond ((= limit count) an)
                                              (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit))))
 
(define answer (if (< nn 3) 0 (trib 1 0 0 3 nn)))
(display answer)
(newline)

初めに提出したものだと、tribの引数limitが3より小さいかどうかを毎回判定していますが、これはかなり無駄なことなので、それを省きました。
その代わり、答えを表すanswerというものを求めるときに、その条件分岐が入っています。
このコードを提出すると、ACとなりました。よかったよかった。

しかし、このコードで通ったものの、かかった時間は1947ms。制限が2sec(=2000ms)なので、ギリギリなんてもんじゃないです。
このコンテストが終わってからも、ずっと気になっていました。これってなんとかならないのかと。


AtCoderのルールではschemeコードはコンパイルなしで使われるんです。仕方ないですかね。連絡してお願いしてみたいですが、なかなかschemeユーザーもいないので、無理かなぁ・・・
そして、じゃあコンパイルをなんとかやるプログラムを作ろう、となったわけです。

MIT/GNUschemeのドキュメントには、"cf"というコンパイルの関数があるとのこと。
よく分からないけど、やってみよう、ということで、色々試しまくりました。
ルール内にある、AtCoderシステムに対する攻撃、になっていないとは思うのですが、もし何か分かる方がいれば連絡を頂けると嬉しいです・・・。

さて、方針は次のようなものです。
1,まず、向こうのサーバで、新しい .scm ファイルを作る。
2,そこに、コンパイルして使いたい関数を書き込む。
3,それを "cf"コマンドでコンパイルし、"load"で読み込み、使う。

1でファイルを作るには、まず

(define port (open-output-file "func.scm"))

とします。これで、("func.scm"というファイルがないので)新しく"func.scm"というファイルが作られ、変数portにそれへの出力用ポートが入ります。
そして、S式を書き込むには以下のようにすればOKです。

(display '(ここに定義とか) port)

'をつけましょう。
そして、

(close-output-port port)

で、ポートを閉じます。
最後にコンパイルとコンパイルしたものを読み込むには

(cf "func")
(load "func")

でOKです。".scm"は不要です。
そして、出来たコードがコチラ。

(define nn (read))
 
(define port (open-output-file "func.scm"))
 
(display '(define (trib an ann annn count limit) (cond ((= limit count) an)
                                              (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit)))) port)
 
(close-output-port port)
(cf "func")
(load "func")
 
(define answer (if (< nn 3) 0 (trib 1 0 0 3 nn)))
(display answer)
(newline)

さて、このコードを"compile.scm"という名前で保存し、手元のターミナルで確認。
MIT/GNU schemeを起動してやってみると・・・

*************-no-MacBook-Air:scheme_study **********$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Wednesday May 21, 2014 at 12:46:49 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "compile.scm")

;Loading "compile.scm"...100000

;  Generating SCode for file: "func.scm" => "func.bin"... done
;  Compiling file: "func.bin" => "func.c"...
;    clang -DHAVE_CONFIG_H -DMIT_SCHEME -I/usr/local/include  -O3 -Wall -Wundef -Wpointer-arith -Winline -Wstrict-prototypes -Wnested-externs -Wredundant-decls -Wextra -Wno-sign-compare -Wno-unused-parameter -Wold-style-definition  -isysroot //Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -fconstant-cfstrings -DSIGNAL_HANDLERS_CAN_USE_SCHEME_STACK -frounding-math  -DENABLE_LIARC_FILE_INIT -I/usr/local/Cellar/mit-scheme/9.1.1/lib/mit-scheme-c/include -o /Users/fujiiryousuke/Desktop/scheme_study/func.o -c /Users/fujiiryousuke/Desktop/scheme_study/func.c
;    clang   -isysroot //Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -fconstant-cfstrings -DSIGNAL_HANDLERS_CAN_USE_SCHEME_STACK -Wl,-syslibroot,//Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk -framework CoreFoundation  -bundle -bundle_loader /usr/local/Cellar/mit-scheme/9.1.1/bin/mit-scheme-c -o /Users/fujiiryousuke/Desktop/scheme_study/func.so /Users/fujiiryousuke/Desktop/scheme_study/func.o
;  ... done
;  Loading "func.so"... done
7927
;... done
;Unspecified return value

1 ]=> 

トリボナッチの100000番目(を10007で割った数)、7927が求められました!
おぉ!すごい!
ということで提出。
しかし、WA・・・なんやねん・・・
サンプルの全てがWAでした。

ここで絶望しましたが、なんとか考えて、無駄な書き込みがあるのでは、となりました。
関数を別のファイルに書き込んで、"cf"でコンパイルせずに"load"で読み込んで使う、というプログラムを書いて提出してみたところ(つまり、上のプログラムの

(cf "func") 

を取り除いたもの)、それはACとなりました。
ってことは、コンパイルするときに出るメッセージがダメなんだな・・・へっへっへ・・・ということで、なんとか防ぐ方法を考えました。

んで、またドキュメントを色々読んで、見つけました!

set-notification-output-port!

というやつを使えばよい!
これの引数としてportを与えると、警告メッセージとかがそっちに出るようになります。
だから、"cf"を使う前でこれをして、使い終わったらそのportを閉じればいいですね。
そして、書いてみたコードがコチラ。"output.txt"というファイルを作って、コンパイルメッセージはそっちに出すようにしました。

(define nn (read))
 
(define port (open-output-file "func.scm"))
(display
 
'(define (trib an ann annn count limit) (cond ((= limit count) an)
                                              (else (trib (modulo (+ an ann annn) 10007) an ann (+ count 1) limit))))
port)
 
(newline port)
(close-output-port port)
 
(define port2 (open-output-file "output.txt"))
 
(set-notification-output-port! port2)
 
;(load "func.scm")
(cf "func.scm")
(load "func")
 
(close-output-port port2)
 
 
(define answer (if (< nn 3) 0 (trib 1 0 0 3 nn)))
(display answer)
(newline)

そして提出すると・・・AC!!
ついに!やったぞ!

そして、時間は526ms!コンパイルなしだと同じコードで1947msだったことを考えると、大分な進歩です。
あー、頑張ってよかった。
前の記事のやつに至っては、コンパイルして初めてACとなるようなものだったので、これからもこのテクニックは使っていこうと思います。ただ、AtCoderというシステムがどうやって動いているのかは分かりませんが、何かしら迷惑をかけてしまっていないかだけが心配です。何せファイルを新しく2個作っているわけですから・・・

というわけで、AtCoderシステムにてschemeコードをコンパイルする方法でした。
今回は以上です。

広告を非表示にする