Find nearest substring of your number from pi

compare-pi.rb

#!/usr/bin/env ruby

# compare-pi.rb : Find nearest substring of your number from pi
#   by takehikom

require "net/http"
require "uri"
require "kconv"

module ComparePI
  PI_FILE = "pi.txt"

  class Collector
    def initialize; end

    def start
      uri = "http://xn--w6q13e505b.jp/value/decimal.html"
      digit = 1000
      res = Net::HTTP.post_form(URI.parse(uri), {"digs" => digit.to_s})

      digit_s = ""
      flag_digit = false
      res.body.toutf8.each_line do |line|
        if line.index("＝3.")
          flag_digit = true
        elsif flag_digit
          if line.index("</pre>")
            flag_digit = false
            break
          else
            digit_line = line.strip.gsub(/[^[:digit:]]/, "")
            digit_s << digit_line
          end
        end
      end

      if $DEBUG
        print "Collected #{digit_s.length} digits"
        if digit_s.length <= 20
          puts ": #{digit_s}"
        else
          puts ": #{digit_s[0, 10]} ... #{digit_s[-10, 10]}"
        end
      end

      open(ComparePI::PI_FILE, "w") do |f_out|
        f_out.puts digit_s
      end
    end
    alias :do_collect :start
  end

  class Checker
    def initialize(n)
      @number = n.to_s
      if !test(?f, ComparePI::PI_FILE)
        puts "Collecting digits..."
        ComparePI::Collector.new.do_collect
      end
      @flag_quiet = !$DEBUG
    end

    def start
      analyze
      print_result
    end

    def analyze
      @pi = open(ComparePI::PI_FILE).read.gsub(/[^[:digit:]]/m, "")
      @min_dist = @number.length + 1
      @min_pos = -1
      @match_pos_a = []

      0.upto(@pi.length - @number.length).each do |pos|
        pi_str = @pi[pos, @number.length]
        if @number == pi_str
          print "!" unless @flag_quiet
          $stdout.flush
          @match_pos_a << pos
          if @min_dist > 0
            @min_dist = 0
            @min_pos = pos
          end
        else
          lev = LevenshteinDistance.new(@number, pi_str)
          if @min_dist > lev.distance
            @min_dist = lev.distance
            @min_pos = pos
          end
        end
        if !@flag_quiet && pos > 0
          if pos % 10000 == 0
            print "#{pos}"
            $stdout.flush
          elsif pos % 1000 == 0
            print "."
            $stdout.flush
          end
        end
      end
      puts unless @flag_quiet
    end

    def print_result
      if @min_dist == 0
        puts "\"#{@number}\" occurs at #{@match_pos_a.map {|n| num_to_pos(n)}.join(', ')}"
      else
        puts "Nearest substring of \"#{@number}\" is \"#{@pi[@min_pos, @number.length]}\" (distance = #{@min_dist}) at #{num_to_pos(@min_pos)}"
      end
    end

    def num_to_pos(num)
      "\#%d" % [num + 1]
    end
  end
end

# http://d.hatena.ne.jp/takehikom/20090518/1242595006
class LevenshteinDistance
  def initialize(str1, str2)
    @before, @after = str1, str2
    analyze
  end
  attr_reader :before, :after

  def before_substr(len); @before[0, len].join; end
  def after_substr(len); @after[0, len].join; end

  def analyze
    @before = @before.split(//u) if String === @before
    @after = @after.split(//u) if String === @after

    col = @before.size + 1
    row = @after.size + 1
    @dist = row.times.inject([]) {|a, i| a << [0] * col}
    @seq = row.times.inject([]) {|a, i| a << [""] * col}
    @dir = row.times.inject([]) {|a, i| a << [9] * col}
    col.times {|i|
      @dist[0][i] = i;
      @seq[0][i] = (i == 0) ? [""] : @seq[0][i - 1] + [before_substr(i)]
    }
    row.times {|i|
      @dist[i][0] = i;
      @seq[i][0] = (i == 0) ? [""] : [after_substr(i)] + @seq[i - 1][0]
    }

    @before.size.times do |i|
      @after.size.times do |j|
        cost = (@before[i] == @after[j]) ? 0 : 1
        x = i + 1
        y = j + 1
        d1 = @dist[y][x - 1] + 1
        d2 = @dist[y - 1][x] + 1
        d3 = @dist[y - 1][x - 1] + cost
        @dist[y][x] = dmin = [d1, d2, d3].min

        case dmin
        when d1
          @seq[y][x] = @seq[y][x - 1] + [before_substr(i + 1)]
          @dir[y][x] = 1
        when d2
          @seq[y][x] = [after_substr(j + 1)] + @seq[y - 1][x]
          @dir[y][x] = 2
        else
          @seq[y][x] = @seq[y - 1][x - 1].map {|s| s + @before[i]}
          if cost == 1
            @seq[y][x].unshift(after_substr(j + 1))
          end
          @dir[y][x] = 3
        end
      end
    end
  end

  def distance
    @dist[-1][-1]
  end

  def sequence
    @seq[-1][-1].reverse
  end

  def debug_print
    require "pp"
    pp @dist
    @seq.each_with_index do |f, i|
      f.each_with_index do |g, j|
        puts "@seq[#{i}][#{j}]<#{@dir[i][j]}> = #{g.inspect}"
      end
    end
  end
end

if __FILE__ == $0
  if ARGV.empty?
    puts "usage: #{__FILE__} number [...]"
    puts "usage: #{__FILE__} -c number..."
    puts "usage: #{__FILE__} -g"
    exit
  end

  case ARGV.first
  when /-g/
    ComparePI::Collector.new.do_collect
    exit
  when /-c/
    param = [ARGV[1..-1].join]
  else
    param = ARGV
  end
  param.each do |item|
    ComparePI::Checker.new(item).start
  end
end