An inspector of a string that occurs three times successively, and generators

repeat3.rb

#!/usr/bin/env ruby

# repeat3.rb : an inspector of a string that occurs three times successively,
#              and generators of a string which consists of "a" and "b"
#              and has no substring that occurs three times successively
#   by takehikom

module Repeat3
  class Inspector
    def initialize
      @seq = ""
      @flag_found = false
      @pos = -1
      @len = -1
    end
    attr_reader :seq, :pos, :len

    def found?
      @flag_found
    end

    def read(io_or_string, flag_verbose = false)
      case io_or_string
      when String
        c = io_or_string[0, 1]
      when IO, StringIO
        c = io_or_string.read(1)
      else
        raise
      end
      return nil if c.nil?
      puts "receive \"#{c}\"" if flag_verbose
      @seq += c
      inspect_tail
    end

    def read_all(io_or_string, flag_verbose = false)
      case io_or_string
      when String
        io_or_string.each_char do |c|
          read(c)
        end
      when IO, StringIO
        while !io.eof?
          read(io_or_string)
        end
      else
        raise
      end
      @flag_found
    end

    def inspect_tail
      i = 1
      while i * 3 <= @seq.length
        s1 = @seq[-i, i]
        s2 = @seq[-i * 2, i]
        s3 = @seq[-i * 3, i]
        if s1 == s2 && s2 == s3
          @flag_found = true
          @len = i
          @pos = @seq.length - i * 3
          return true
        end
        i += 1
      end
      return false
    end

    def to_s_found
      @seq[0...@pos] +
        "(" + @seq[@pos, @len] + ")" +
        "(" + @seq[@pos + @len, @len] + ")" +
        "(" + @seq[@pos + @len * 2, @len] + ")"
    end

    def to_s(flag_verbose = false)
      if flag_verbose
        found? ? "%s; pos=%d; len=%d" % [to_s_found, pos, len] :
          "%s; not found" % @seq
      else
        found? ? to_s_found : @seq
      end
    end
  end

  class Generator1
    def srand(seed)
      Random.srand(seed)
    end

    def write(num = 1, flag_verbose = false)
      c = (1..num).to_a.map { "ab"[rand(2)] }.join
      puts "send \"#{c}\"" if flag_verbose
      c
    end
  end

  class Generator2
    def initialize
      @write_count = 0
      @period = create_large_a("a", "b").length + create_large_b("a", "b").length
      @a = "a"
      @b = "b"
      @buffer = @a + @b
    end

    def write(num = 1, flag_verbose = false)
      c = (1..num).to_a.map { |i| next_char }.join
      puts "send \"#{c}\"" if flag_verbose
      @write_count += num
      c
    end

    def next_char
      if @buffer.empty?
        @buffer = @a + @b
        @a, @b = create_large_a(@a, @b), create_large_b(@a, @b)
        @buffer += @a + @b
      end
      c = @buffer[0, 1]
      @buffer = @buffer[1..-1]
      c
    end

    def create_large_a(str_a, str_b)
      [str_a, str_a, str_b, str_a, str_a, str_b, str_b, str_a, str_b].join
    end

    def create_large_b(str_a, str_b)
      [str_a, str_a, str_b, str_b, str_a, str_b, str_b, str_a, str_b].join
    end
  end

  class Generator3
    # Wikipedia日本語版「千日手」より：
    # 同一局面に戻る手順AとBがあるとき、A-B-BA-BAAB-BAABABBA-... と、
    # それまでの手順を逆にしてつなげることで、同一手順3回を回避しながら
    # 同一局面を繰り返すことができる。
    def initialize
      @seq_sent = ""
      @flag_reverse = false
      @buffer = "ab"
    end

    def write(num = 1, flag_verbose = false)
      c = (1..num).to_a.map { next_char }.join
      puts "send \"#{c}\"" if flag_verbose
      c
    end

    def next_char
      if @buffer.empty?
        @buffer = @seq_sent.tr("ab", "ba")
      end
      c = @buffer[0, 1]
      @buffer = @buffer[1..-1]
      @seq_sent += c
      c
    end
  end
end

if __FILE__ == $0
  case ARGV.first
  when "g1"
    # ruby repeat3.rb g1
    # ruby repeat3.rb g1 1000 1111
    #   乱数の種を1ずつ増やしていき，それぞれでaとbからなる文字列を
    #   ランダムに生成
    ARGV.shift
    seed_from = (ARGV.shift || 10000).to_i
    seed_to = (ARGV.shift || 10999).to_i
    trial = 100
    seed_from.upto(seed_to) do |seed|
      ins = Repeat3::Inspector.new
      gen = Repeat3::Generator1.new; gen.srand(seed)
      trial.times do
        ins.read(gen.write(1))
        break if ins.found?
      end
      puts "seed=#{seed}; #{ins.to_s(true)}"
    end
  when "g2", "g3"
    # ruby repeat3.rb g2
    # ruby repeat3.rb g2 10000
    # ruby repeat3.rb g3
    # ruby repeat3.rb g3 10000
    #   同一文字列が3回連続しないよう生成（乱数不使用）
    gen = (/2/ =~ ARGV.first ? Repeat3::Generator2 : Repeat3::Generator3).new
    ARGV.shift
    trial = (ARGV.shift || 2000).to_i
    mid_count = trial >= 1000 ? trial / 10 : trial + 1
    count = mid_count
    ins = Repeat3::Inspector.new
    trial.times do |i|
      ins.read(gen.write(1))
      break if ins.found?
      count -= 1
      if count == 0
        $stderr.puts "#{i + 1}..."
        count = mid_count
      end
    end
    puts ins.to_s(true)
  else
    # ruby repeat3.rb
    #   aとbからなる文字列をランダムに生成（実行ごとに出力は変わる）
    ins = Repeat3::Inspector.new
    loop do
      c = "ab"[rand(2)]
      ins.read(c, true)
      break if ins.found?
    end
    puts ins.to_s(true)
  end
end