使用 Ruby 解 Code Jam

这几天开始注意到 Code Jam，规则还不是很熟悉，做了两个题目练习一下。貌似只用提交答案，所以语言并没有限制。我就用 Ruby 试着解了个题目。

之前用过 Ruby 做过计算，Ruby 的计算能力实在堪忧，但是语法的表现力还是很令人满意的，简言之就是：写起来很爽，跑起来很慢，很慢。使用 JRuby 倒是可以快点，但仅仅是快一点点 :(

题目

APAC 2015 Round A #A Password Attacker

这是一个排列组合的问题，m 个字符组成长度为 n 的字符串 (m<=n)，每个字符至少出现一次，求组合数目。

每个字符至少出现一次，则有 n-m 个字符可以是 m 个字符中的任意字符，使用递归穷尽 n-m 字符所有组合情况。每种情况下，第 i 个字符出现 xi 次，则有

x1 + x2 + … + xm = n

其中 xi >= 1

组合次数为

n! / (x1! … xm!)

将每种组合数相加就能得到总的组合数目。

但是，但是，这只能解决 samll dataset，即使改写成 C++，还是不能解决 large dataset。看来还有更好的解决方法。

Ruby 相关

文件读取

fin = File.open(filename)

读取一行 n,m

m, n = fin.readline.split.map(&:to_i)

非常方便的 map inject

@nums.map{|i| MMath.factorial(i) }.inject(&:*)

Ruby 中的 Array Hash 很方便

@nums = Array.new(m) { 1 }

@@factorials = { 0 => 1, 1 => 1 }

还有，不用关心Int大小的问题，自动转化成 BinInteger

代码

class Solution
  def ways(m, n)

    @m, @n = m, n
    @nums = Array.new(m) { 1 }
    @n_factorial = MMath.factorial(@n)

    trav(n-m) % 1000000007
  end

  def trav(k)
    if k==0
      @n_factorial / @nums.map{|i| MMath.factorial(i) }.inject(&:*)
    else
      (0...@m).map do |i|
        @nums[i] += 1
        result = trav(k-1)
        @nums[i] -= 1
        result
      end.inject(&:+)
    end
  end
end

class MMath
  @@factorials = { 0 => 1,
                   1 => 1 }

  def self.factorial(n)
    @@factorials[n] ||= n * factorial(n-1)
  end
end


fin = File.open('A-small-practice.in')
fout = File.open('A-small-practice.out', 'w')
t = fin.readline.to_i
i = 1
while i <= t
  puts i
  m, n = fin.readline.split.map(&:to_i)
  fout.write "Case #%d: %d\n" % [i,  Solution.new.ways(m, n)]
  i += 1
end
fout.close