円周率の中から、日付とみなせる10桁の部分文字列を発見する

find_date_from_PI.rb

#!/usr/bin/env ruby

# 円周率の中から、日付とみなせる10桁の部分文字列を発見する
# (http://d.hatena.ne.jp/hyuki/20090314#pi)

# PI_STRは、円周率の小数第1位～500位を文字列で表したもの
# from ftp://pi.super-computing.org/pub/pi10m/pi10m.ascii.01of10
PI_STR = (
  "14159265358979323846264338327950288419716939937510"+
  "58209749445923078164062862089986280348253421170679"+
  "82148086513282306647093844609550582231725359408128"+
  "48111745028410270193852110555964462294895493038196"+
  "44288109756659334461284756482337867831652712019091"+
  "45648566923460348610454326648213393607260249141273"+
  "72458700660631558817488152092096282925409171536436"+
  "78925903600113305305488204665213841469519415116094"+
  "33057270365759591953092186117381932611793105118548"+
  "07446237996274956735188575272489122793818301194912")

# TRANS_TABLEは、日付のみを受理する有限オートマトン(FA)の遷移図

def rule_accept_all(dest) # どんな数字でもdestへ遷移する場合
  ret = {}
  (0..9).each{ |i| ret[i] = dest }
  ret
end

def rule_accept_nonzero(dest) # 0以外だったらdestへ遷移する場合
  ret = {}
  (1..9).each{ |i| ret[i] = dest }
  ret
end

def rule_accept_under5(dest) # 5以下だったらdestへ遷移する場合
  ret = {}
  (0..5).each{ |i| ret[i] = dest }
  ret
end

TRANS_TABLE = {
  :A => {0=>:B, 1=>:C},
  :B => {2=>:D, 1=>:E, 3=>:E, 5=>:E, 7=>:E, 8=>:E,
         4=>:F, 6=>:F, 9=>:F},
  :C => {0=>:E, 2=>:E, 1=>:F},
  :D => {0=>:G, 1=>:H, 2=>:H},
  :E => {0=>:G, 1=>:H, 2=>:H, 3=>:I},
  :F => {0=>:G, 1=>:H, 2=>:H, 3=>:J},
  :G => rule_accept_nonzero(:K),
  :H => rule_accept_all(:K),
  :I => {0=>:K, 1=>:K},
  :J => {0=>:K},
  :K => {0=>:L, 1=>:L, 2=>:M},
  :L => rule_accept_all(:N),
  :M => {0=>:N, 1=>:N, 2=>:N, 3=>:N},
  :N => rule_accept_under5(:O),
  :O => rule_accept_all(:P),
  :P => rule_accept_under5(:Q),
  :Q => rule_accept_all(:R)}
INIT_STATE = :A # FAの開始状態
END_STATE = :R  # FAの終了状態

# メイン部
class String
  def digit_at(pos)
    # 文字列のpos文字目が数字ならその数(Integer)を、
    # そうでなければnilを返す
    tmp = self[pos]
    if (?0..?9).include?(tmp)
      tmp - ?0
    else
      nil
    end
  end
end

def main
  for i in 0...(PI_STR.length-10)
    state = INIT_STATE
    for j in 0...10
      state = TRANS_TABLE[state][PI_STR.digit_at(i+j)]
      case state
      when END_STATE
        puts "from digit #{i+1}: #{PI_STR[i,j+1]}"
        return
      when nil # nilになる＝FAに拒否される(日付になっていない)
        break
      end
    end
  end
end

main()