2
Help us understand the problem. What are the problem?

posted at

updated at

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

はじめに

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

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

但し、julializerRipper.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}"

getsread_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

sortreverseもそのまま使用できます。

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

ArrayArray(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

RegexpRegexに変換する必要があります。

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 の作者さんありがとう
  • プルリクよろしくお願いします

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
2
Help us understand the problem. What are the problem?