Ruby を Crystal にトランスパイル してAtCoder に登録したら解くべき精選過去問 10 問を解いてみた

はじめに

Atcoderのコンテストにて、RubyでTLEが解消しないこと、ないでしょうか。
私はあります。
Rubyのコードを速い言語にトランスパイルして欲しいと思ったこと、ないでしょうか。
私はあります。

前回記事にてripperの内容が少し理解できましたので、それをcrystalに応用してみました。

但し、julializerはRipper.sexpを使用、こちらはRipper.lexを使用しています。

また、諸先輩の記事を参照させていただきました。

Crystallizer

crystallizer

require 'ripper'

module Crystallizer
  class << self

    def ruby2crystal(source)
      transpile(Ripper.lex(source))
    end

    private
      def transpile(s)
        arr = []
        s.map do |w|
          arr << case w[2]
          when "gets", "readline"
            "read_line"
          when "/="
            "//="
          when "/"
            "//"
          when "Array"
            if s.to_s.include?("to_i")
              if s.to_s.include?("split")
                "Array(Array(Int32))"
              else
                "Array(Int32)"
              end
            elsif s.to_s.include?("to_f")
              if s.to_s.include?("split")
                "Array(Array(Float64)"
              else
                "Array(Float64)"
              end
            else
              "Array()"
            end
          when "Regexp"
            "Regex"
          else
            w[2]
          end
        end
        arr.join('')
          .gsub(".chomp", "")
          .gsub("&:", "&.")
      end
  end
end

やっていることは原始的で、Ripper.lexでスキャンした文字列を変換しているだけです。

use

require_relative 'lib/crystallizer2'

filename = "atcoder/exam11.rb"

code = File.open(filename){ _1.read }
transcode = Crystallizer::ruby2crystal(code)
puts transcode

仕様として、外部ファイルを読み込んで標準出力に表示します。
今のところこうしないと、式展開puts "#{a + b + c} #{s}"がうまく変換できないようです。

精選過去問 10 問

ruby

a = gets.to_i
b, c = gets.split.map(&:to_i)
s = gets.chomp
puts "#{a+b+c} #{s}"

crystal

a = read_line.to_i
b, c = read_line.split.map(&.to_i)
s = read_line
puts "#{a+b+c} #{s}"

getsをread_lineに、&:を&.に変換しています。
chompは削除しなくても正しく動作します。

ruby

a, b = gets.split.map(&:to_i)
if a * b % 2 == 0
  puts "Even"
else
  puts "Odd"
end

crystal

a, b = read_line.split.map(&.to_i)
if a * b % 2 == 0
  puts "Even"
else
  puts "Odd"
end

ifは三項演算子でも大丈夫です。

ruby

s = gets.chomp
puts s.count("1")

crystal

s = read_line
puts s.count("1")

ruby

n = gets.to_i
a = gets.split.map(&:to_i)
ans = 0
while a.all?{ |e| e % 2 == 0 }
  a.map!{ |e| e / 2 }
  ans += 1
end
puts ans

crystal

n = read_line.to_i
a = read_line.split.map(&.to_i)
ans = 0
while a.all?{ |e| e % 2 == 0 }
  a.map!{ |e| e // 2 }
  ans += 1
end
puts ans

rubyの演算子/は、crystalでは//になります。

ruby

a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
ans = 0
(0..a).each do |aa|
  (0..b).each do |bb|
    (0..c).each do |cc|
      if aa * 500 + bb * 100 + cc * 50 == x
        ans += 1
      end
    end
  end
end
puts ans

crystal

a = read_line.to_i
b = read_line.to_i
c = read_line.to_i
x = read_line.to_i
ans = 0
(0..a).each do |aa|
  (0..b).each do |bb|
    (0..c).each do |cc|
      if aa * 500 + bb * 100 + cc * 50 == x     
        ans += 1
      end
    end
  end
end
puts ans

ruby

n, a, b = gets.split.map(&:to_i)
ans = 0
(1..n).each do |x|
  y = x
  t = 0
  while x > 0
    t += x % 10
    x /= 10
  end
  if a <= t && t <= b
    ans += y
  end
end
puts ans

crystal

n, a, b = read_line.split.map(&.to_i)
ans = 0
(1..n).each do |x|
  y = x
  t = 0
  while x > 0
    t += x % 10
    x //= 10
  end
  if a <= t && t <= b
    ans += y
  end
end
puts ans

ruby

n = gets.to_i
a = gets.split.map(&:to_i).sort.reverse
ans = 0
n.times do |i|
  if i % 2 == 0
    ans += a[i]
  else
    ans -= a[i]
  end
end
puts ans

crystal

n = read_line.to_i
a = read_line.split.map(&.to_i).sort.reverse    
ans = 0
n.times do |i|
  if i % 2 == 0
    ans += a[i]
  else
    ans -= a[i]
  end
end
puts ans

sortもreverseもそのまま使用できます。

ruby

n = gets.to_i
d = Array.new(n){ gets.to_i }.sort
ans = 1
(n - 1).times do |i|
  if d[i + 1] > d[i]
    ans += 1
  end
end
puts ans

crystal

n = read_line.to_i
d = Array(Int32).new(n){ read_line.to_i }.sort  
ans = 1
(n - 1).times do |i|
  if d[i + 1] > d[i]
    ans += 1
  end
end
puts ans

ArrayをArray(Int32)に変換するところは、力業の感があります。誰か教えて

ruby

n, y = gets.split.map(&:to_i)
0.upto(y / 10000) do |a|
  0.upto(y / 5000) do |b|
    if a * 10000 + b * 5000 + (n - a - b) * 1000 == y && a + b <= n
      puts "#{a} #{b} #{n - a - b}"
      exit
    end
  end
end
puts "-1 -1 -1"

crystal

n, y = read_line.split.map(&.to_i)
0.upto(y // 10000) do |a|
  0.upto(y // 5000) do |b|
    if a * 10000 + b * 5000 + (n - a - b) * 1000 == y && a + b <= n
      puts "#{a} #{b} #{n - a - b}"
      exit
    end
  end
end
puts "-1 -1 -1"

ruby

s = gets.chomp
r = Regexp.new("^(dream|dreamer|erase|eraser)*$")
if r.match(s)
  puts "YES"
else
  puts "NO"
end

crystal

s = read_line
r = Regex.new("^(dream|dreamer|erase|eraser)*$")
if r.match(s)
  puts "YES"
else
  puts "NO"
end

RegexpはRegexに変換する必要があります。

ruby

n = gets.to_i
txys = Array.new(n){ gets.split.map(&:to_i) }
t0 = x0 = y0 = 0
txys.each do |txy|
  kd = (txy[1] - x0).abs + (txy[2] - y0).abs
  td = (txy[0] - t0).abs
  if kd > td || kd % 2 != td % 2
      puts "No"
      exit
  end
  t0 = txy[0]
  x0 = txy[1]
  y0 = txy[2]
end
puts "Yes"

crystal

n = read_line.to_i
txys = Array(Array(Int32)).new(n){ read_line.split.map(&.to_i) }
t0 = x0 = y0 = 0
txys.each do |txy|
  kd = (txy[1] - x0).abs + (txy[2] - y0).abs
  td = (txy[0] - t0).abs
  if kd > td || kd % 2 != td % 2
      puts "No"
      exit
  end
  t0 = txy[0]
  x0 = txy[1]
  y0 = txy[2]
end
puts "Yes"

Array(Array(Int32))の部分は要検討です。

思いの外、シンプルな変換でいけました。

もう少し熟成させたいものです。

まとめ

• ripper の作者さんありがとう
• crystal の作者さんありがとう
• プルリクよろしくお願いします