Route 477

■ [kmc] おおさと杯

部内の若者向けプログラミングコンテスト、通称「おおさと杯」の第３回が行われました。

基本的にICPCのような感じ(風船マークもあるよ！)で3時間6問なんですが、言語はC系だけではなく、RubyとHaskellも 使えるという充実ぶり。

僕はせっかくなのでRubyで参加しましたが、問題を読み間違ったりなんだりで結局3問しか解けず…駄目駄目ですね。 とはいえ、Rubyでコンテスト的なプログラムを書くのもなかなか新鮮で楽しかったです。次回はHaskellか!?(入力が一番大変そうだ…^^;)

■ [spoj] Sphere Online Judge

で、Rubyとかが使えるOnline Judgeとかないよねーという話をしたら、Sphere Online Judge(SPOJ) というサイトがあると教えてもらいました。

uvaやPKUのような感じで、使用可能な言語は なんと驚きの35種類！

C (gcc 4.0.0-8)
C99 strict (gcc 4.0.0-8)
C++ (g++ 4.0.0-8)
Pascal (gpc v20030830)
Pascal (fpc 2.0.4)
Java (j2se jdk 5.0)
Nice (nicec 0.9.6)
JAR (j2se jdk 5.0)
C# (mcs 1.0.1)
Nemerle (ncc 0.2.1)
Smalltalk (gst 2.1.7)
Assembler (nasm 0.98.38)
Algol (a60 0.20a-4)
Fortran (g77 3.3.3)
ADA 95 (gnat 3.15p)
Bash (bash 2.05b-15)
Perl (perl 5.8.3)
Python (python 2.4)
Ruby (ruby 1.8.1)
Lua (lua 5.0.2)
Icon (iconc 9.4.2)
Pike (pike 7.4.35)
PHP (php 4.3.8-9)
Scheme (guile 1.6)
Scheme (qobi 0.9+0.10a)
Common Lisp (gcl 2.6.5)
Common Lisp (clisp 2.33.2)
Haskell (ghc 6.4.1)
Ocaml (ocaml 3.08.1)
Clips (clips 6.21)
Prolog (swipl 5.2.7)
Whitespace (wspace 0.3)
Brainf**k (bf2c)
Intercal (ick 0.24)
Text (pure text)

C/C++/C#/Java等の基本的なところからPerl/Python/Ruby/Pike/Luaのようなスクリプト言語、Lisp,Scheme/Haskell/Ocamlのような関数型言語から Bash/nasm/Whitespace/Brainf**kのような変り種まで幅広く取り揃えられています。

…しかし最後の「Text」ってのはどういう言語なんでしょうか？ 期待されるoutputをすべてそのまま予想したらAccept？

■ [spoj] SPOJをネタにRaccを使ってみるテスト

1. TEST

こりゃー簡単ですよね。インタプリタ走らすまでもなく解けるぜ！

…と思ったら改行の処理を忘れて1miss ＿|‾|○

2. PRIME1

require 'mathn' してPrime#each使ったら一発じゃね!? と思ったのですが、TLE。もうちょっと真面目にやらないと駄目なようです。 ああ、難易度順に並んでるというわけではないのね。

3. SBSTR1

文字列Aに文字列Bが含まれているかを判定する問題。これこそString#include?一発では？と思ったら…

Please note, that the solution may only be submitted in the following languages: Brainf**k, Whitespace and Intercal.

4. ONP

四則演算+αの式を逆ポーランド記法に直す問題。要するにパーサ書けばいい、んですが…

せっかくだから俺はこの青のRaccを使うぜ！

いや、いいんですよ！Raccの練習だから！

gotokenさんの記事 (今は亡きCマガ…;涙) を見つつ、onp.y を書いてみる。

# exp = exp (+,-,*,/,^) exp |
#       '(' exp ')' |
#     = IDENT
class OnpParser
  prechigh
    left '^'
    left '/'
    left '*'
    left '-'
    left '+'
  preclow
rule
  exp : exp '+' exp { result += "#{val[2]}+" }
      | exp '-' exp { result += "#{val[2]}-" }
      | exp '*' exp { result += "#{val[2]}*" }
      | exp '/' exp { result += "#{val[2]}/" }
      | exp '^' exp { result += "#{val[2]}^" }
      | '(' exp ')' { result = val[1] }
      | IDENT
      ;
end

こんな感じかね？

あとスキャナ部分も書かんといかんらしいので、

require 'onp.tab.rb'
class OnpParser
  def parse(str)
    scan(str)
    do_parse
  end

  private
  def scan(str)
    @q = []
    until str.empty?
      case str
      when /\A\s+/
        # skip
      when /\A([a-z])/
        @q.push [:IDENT, $1]
      when /\A./
        # +-*/^()
        c = str[0].chr
        @q.push [c, c]
      end
      str = $'
    end
    @q.push [false, '$end']
  end

  def next_token
    @q.shift
  end
end

gets
while line=gets
  puts OnpParser.new.parse(line.chomp)
end

こんな感じで。要するにパーザクラスのnext_tokenメソッドで [トークンの種類、トークンの中身] という配列をひとつずつ返せばいいらしい。 上では記事の例と同じように、scanメソッドで一気に全てのトークンを切り出しています。

というわけでONPは解けた、と思う、んですが…

submitしたらNZEC(non-zero exit codeらしい)だったよ！

require 'racc/parser' だけでもNZECになるので、どうもraccは使えない予感。

…ですよねー(´・∀・｀)