# encode / decode Mojibake-ed string
class String
  def u
    self.dup.force_encoding('utf-8')
  end
end

# Mojibake
class Mojibake
  attr_reader :hint

  def self.encode(src)
    self.new.encode(src)
  end

  def encode(src)
    src.force_encoding('cp932')
      .encode('utf-8', undef: :replace, invalid: :replace, replace: "\0")
      .gsub(/\0+/, '・'.u)
  end

  def decode(src)
    d = Decoder.new(src)
    r = d.decode
    @hint = d.hint
    r
  end

  def code_to_char(src)
    src.b.gsub(/\\x([0-9a-f][0-9a-f])/i){$1.to_i(16).chr}.u
      .scrub{|c| c.bytes.map{'\\x'+_1.ord.to_s(16).upcase}.join}
  end

  # Decoder
  class Decoder
    H = -'\\\\x[0-9A-F][0-9A-F]'

    def self.utf8_code
      return @utf8 if @utf8
      # cp932 = {}
      utf8 = {}
      ((0x81..0x9F).to_a+(0xE0..0xFF).to_a).each do |c1|
        ((0x40..0x7E).to_a+(0x80..0xFC).to_a).each do |c2|
          s = [c1, c2].pack('c*').force_encoding('cp932')
          u = s.encode('utf-8', 'cp932')
          next if u.ord >= 0xe000 && u.ord <= 0xf8ff  # 私的領域
          # cp932[s.b] = s.encode('utf-8')
          utf8[u.b] = u
        rescue EncodingError
        end
      end
      @utf8 = utf8
    end

    self.utf8_code

    attr_reader :hint

    def initialize(src)
      @src = src
    end

    def decode
      a = phase1(@src)
      a = phase2(a)
      a = phase3(a)
      phase4(a)
    end

    # 文字列を文字の配列に分割する
    # @param src [String]
    # @return [Array<String>]
    def phase1(src)
      s = src.u.tr('・'.u, "\0").encode('cp932', undef: :replace, invalid: :replace, replace: "\0").u
      chars = s.chars
      a = []
      while (c = chars.shift)
        if !c.valid_encoding? && a.last && !a.last.valid_encoding? && !utf8_first?(c)
          a.last.concat c
        elsif c == "\0" && a.last && !a.last.valid_encoding? && chars[0] && !chars[0].valid_encoding? && !utf8_first?(chars[0])
          a.last.concat c
          a.last.concat chars.shift
        else
          a.push c
        end
      end
      b = []
      while (c = a.shift)
        if c != "\0" && c.b =~ /\0/ && candidate(c).empty?
          b.concat c.b.split(/\0/).map(&:u)
        else
          b.push c
        end
      end
      b.delete("\0")
      b
    end

    def utf8_first?(c)
      c.b.ord >= 0xc2
    end

    # 不完全な文字の候補を作成する
    # 候補が１つだけならそれを採用する
    # @param src [Array<String>]
    # @return [Array<String or Array<String>>]
    def phase2(src)
      src.map do |c|
        next c if c.valid_encoding?
        a = candidate(c)
        if a.empty?
          c
        elsif a.size == 1
          a[0]
        else
          a
        end
      end
    end

    # 候補の文字を元の文字化けが再現するものに絞り込む
    # @param src [Array<String or Array<String>>]
    # @return [Array<String or Array<String>>]
    def phase3(src)
      s = src.dup
      out = []
      t = []
      while (c = s.shift)
        if c.is_a? String
          out.push c
          t.push c
          next
        end
        while s[0].is_a? Array
          c2 = s.shift
          x = []
          if c.size * c2.size > 100000  # 候補の組み合わせ数
            out.push(c, c2)
            out.concat s
            return out
          end
          product(c, c2) do |a|
            e = Mojibake.encode([t, a].join)
            e.delete_suffix!('・'.u)
            x.push a.join if @src.b.start_with? e.b
          end
          c = x
        end
        if s[0].is_a? String
          c2 = s[0]
          x = []
          product(c, [c2]) do |a|
            e = Mojibake.encode([t, a].join)
            e.delete_suffix!('・'.u)
            x.push a[0] if @src.b.start_with? e.b
          end
        else
          x = c
        end
        out.push x.empty? ? c : x.size == 1 ? x[0] : x
        t.push x[0]
      end
      out
    end

    # 複数候補がある文字を「(n)」に置き換える
    # @param src [Array<String or Array<String>>]
    def phase4(src)
      out = []
      src.each do |c|
        if c.size > 100
          out.concat zip(*c.map(&:chars)).map{_1.uniq.sort}
        else
          out.push c
        end
      end
      hint = {}
      i = 1
      out = out.map do |c|
        if c.is_a? String
          c
        else
          x = "(#{i})"
          hint[x] = c
          i += 1
          x
        end
      end
      @hint = hint
      out.join.scrub{|c| '\x'+c.b.ord.to_s(16).upcase}
    end

    # same as Enumerator.product
    def product(*x, &)
      if x.size == 1
        x[0].map{[_1]}.each(&)
      else
        x[0].product(*x[1..], &)
      end
    end

    def zip(a, *x)
      a.zip(*x)
    end

    def utf8_code
      self.class.utf8_code
    end

    def candidate(e)
      list = []
      re = Regexp.new('\A(.*)'+e.b.gsub(/\0/, '(.+)')+'(.*)\z')
      utf8_code.each do |b, u|
        next unless re =~ b
        unless ($3 || $2).empty?
          m = $1 + $2 + $3.to_s
          next if m.force_encoding('cp932').encode('utf-8') rescue nil
          next if m.b[0].force_encoding('cp932').encode('utf-8') rescue nil
        end
        list.push u
      end
      list
    end
  end
end

if $PROGRAM_NAME == __FILE__
  require 'power_assert'
  require 'power_assert/colorize'
  def assert(&block)
    PowerAssert.start(block, assertion_method: __callee__) {|pa| puts pa.message_proc.call unless pa.yield}
  end
  m = Mojibake.new

  s = 'もじばけをふくげんするよ'
  assert { m.decode(m.encode(s)) == 'もじばけをふくげんするよ' }
  assert { m.hint == {} }

  s = '文字化けを復元するよ'
  assert { m.decode(m.encode(s)) == '(1)字化けを復(2)るよ' }
  assert do
    expected = {
      '(1)' => %w[文 斃],
      '(2)' => %w[允遙 兇す 兇恙 兇遙 兄す 兄恙 兄遙 元す 元恙 元遙 充す 充恙 充遙 兆す 兆恙 兆遙],
    }
    m.hint == expected
  end

  s = '江戸川コナンの正体は工藤新一'
  assert { m.decode(m.encode(s)) == '江戸川コナンの正体(1)工藤新(2)' }
  assert do
    expected = {
      '(1)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
      '(2)' => %w[一 丑 下 且 丘 三 七 上 丈 丞 世 丁 不 丙 万 与 丐 丕 丗],
    }
    m.hint == expected
  end

  s = 'もう食べられないよう'
  assert { m.decode(m.encode(s)) == 'もう食べられな(1)よ(2)' }
  hint = {
    '(1)' => %w[ぃ い ぅ う ぇ],
    '(2)' => %w[ぁ あ ぃ い ぅ う ぇ え ぉ お か が き ぎ く ぐ け げ こ ご さ ざ し じ す ず せ ぜ そ ぞ た だ],
  }
  assert { m.hint == hint }

  assert { m.decode('あいうえお') == '\x82\xA0\x82\xA2\x82\xA4\x82\xA6\x82\xA8' }
  assert { m.hint == {} }

  s = '春は、あけぼの。やうやう白くなりゆく山ぎは、すこしあかりて、紫だちたる雲の、細くたなびきたる。'
  assert { m.decode(m.encode(s)) == '春は、あけぼの。や(1)(2)(3)(4)くなりゆく山ぎ(5)、すこしあかりて、紫だちたる雲の、細くたなびきたる(6)' }
  hint = {
    '(1)' => %w[ぁ ぃ い ぅ う ぇ],
    '(2)' => %w[や 悄 肄 還],
    '(3)' => %w[ぁ ぃ い ぅ う ぇ],
    '(4)' => %w[白 陽],
    '(5)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(6)' => %w[　 、 。 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー 〔 〕 〈 〉 《 》 「 」 『 』 【 】 〒 〓 ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ 〝 〟],
  }
  assert { m.hint == hint }

  s = '夏は、夜。月のころは、さらなり。闇もなほ。螢のおほく飛びちがひたる、また、ただ一つ二つなど、ほのかにうち光りて行くも、をかし。雨など降るも、をかし。'
  assert { m.decode(m.encode(s)) == '夏(1)、夜。月のころは、さらなり。闇もなほ。螢のおほく飛(2)ちが(3)たる、また、ただ一つ二つなど、ほのかに(4)光りて行くも、をかし。雨など降るも、をかし(5)' }
  hint = {
    '(1)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(2)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(3)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(4)' => %w[ぁ遡 ぃち ぃ遡 ぃ聡 いち い遡 い聡 ぅち ぅ遡 ぅ聡 うち う遡 う聡 ぇち ぇ遡 ぇ聡],
    '(5)' => %w[　 、 。 〃 々 〆 〇 〔 〕 〈 〉 《 》 「 」 『 』 【 】 〒 〓 〝 〟],
  }
  assert {m.hint == hint }

  s = 'われらは、これに反する一切の憲法、法令及び詔勅を排除する。'
  assert { m.decode(m.encode(s)) == 'われら(1)、これに反する(2)憲法(3)法令及(4)詔勅を排除する(5)' }
  hint = {
    '(1)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(2)' => %w[一刃 一切 一刀 一分 一刄],
    '(3)' => %w[、 ぁ め チ],
    '(4)' => %w[　 、 。 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー 〔 〕 〈 〉 《 》 「 」 『 』 【 】 〒 〓 ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ 〝 〟],
    '(5)' => %w[　 、 。 〃 々 〆 〇 〔 〕 〈 〉 《 》 「 」 『 』 【 】 〒 〓 〝 〟],
  }
  assert { m.hint == hint }

  s = '陸海空軍その他の戦力は、これを保持しない。国の交戦権は、これを認めない。'
  assert { m.decode(m.encode(s)) == '陸海空軍その他(1)戦力(2)、これを保持しな(3)国の交戦権は、これを認めな(4)' }
  hint = {
    '(1)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(2)' => %w[　 ・ ゛ ゜ ヽ ヾ ゝ ゞ 〃 々 〆 〇 ー ね の は ば ぱ ひ び ぴ ふ ぶ ぷ む プ ヘ ベ ペ ホ ボ ポ マ],
    '(3)' => %w[ぁт ぁ頂 ぃ。 ぃ砂 ぃ頂 ぃ栂 ぃ堂 い。 いт い砂 い頂 い栂 い堂 ぅ。 ぅт ぅ砂 ぅ頂 ぅ栂 ぅ堂 う。 うт う砂 う頂 う栂 う堂 ぇ。 ぇт ぇ砂 ぇ頂 ぇ栂 ぇ堂 だｂ だ＂],
    '(4)' => %w[ぁ あ ぃ い ぅ う ぇ え ぉ お か が き ぎ く ぐ け げ こ ご さ ざ し じ す ず せ ぜ そ ぞ た だ],
  }
  assert{ m.hint == hint }
end