#/usr/bin/ruby -Ks
#
#土のからむ動用字はなし order sensitiveなのは旧字とパーツ補充のみ
#巾、牛はorder sensitiveなし
#貝は質貭も貳貮(賦貝武)もただの異体字だから分けなくてよさそう
#合成するエントリなし: 品、者(老土丿からもれてる)
#
#[tcode-ml:2030]
#>        しんにょうを区別する必要はない。
#>逹え幸
#>達之幸* ->逹一
#
#

require 'kconv'

class BushuMap
  #2004.02.18-
  def initialize(bushulist)
    if bushulist.length != ::BLSize
      puts "Warning: mismatch lengh of bushulist"
    end
    @bushulist = bushulist
    @relh = Hash.new(0)
    if BLSize <= 25
      @addmap = [[], [], [], [], []]
    else
      @addmap = [[], [], [], [], [], [], [], []]
    end
    @addmap[2][2] = '０'
    p @bushulist
  end
  def read_from_bushulist()
    ii = -13
    @bushulist.each { |i|
      if ii == -13
        @relh[i] = 0
        ii += 1
      else
        @relh[i] = ii
        @addmap[dinc(i)+2][rinc(i)+2] = i
        ii += 1
        ii = 1 if ii == 0
        ii = 21 if ii == 20
      end
    }
    p @relh
  end
  def read_from_addmap(addmap)
    addmap.each_index { |i|
      addmap[i].each_index { |j|
        @addmap[i][j] = addmap[i][j]
        @relh[addmap[i][j]] = (i-2)*5+j-2
      }
    }
  end
  attr_reader :bushulist
  attr_reader :addmap
  attr_reader :relh
  def number(c)
    return @bushulist.index(c)
  end
  def rinc(i) #index of relbushu -> relative address
    if i.is_a?(Integer)
      i = @bushulist[i]
    end
    return (@relh[i]+12).modulo(5)-2
  end
  def dinc(i)
    if i.is_a?(Integer)
      i = @bushulist[i]
    end
    return (@relh[i]+12).divmod(5)[0]-2
  end
  def set(i, c)
    d = (i+12).divmod(5)[0]
    r = (i+12).modulo(5)
    @addmap[d][r] = c
    @relh[c] = i
  end
  def unset(i, c)
    d = (i+12).divmod(5)[0]
    r = (i+12).modulo(5)
    @addmap[d][r] = nil
    @relh[c] = 0
  end
end  #BushuMap

class CompoInfo
  def initialize(bushulist)
    @bushulist = bushulist
    @h = {}
  end
  attr_reader :h  #フォーマットについては270行あたり
  def calc_ar()
    ## 子と子の共起
    @ar0 = Array.new(BLSize)
    @ar0.each_index { |i|
      @ar0[i] = Array.new(BLSize, 0)
      @ar0[0][i] = @ar0[i][0] = @bushulist[i]
    }
    @h.each { |i, ii|
      for j in 1..BLSize
        for k in 1..BLSize
          @ar0[j][k] += 1 if ii[j] && ii[k]
        end
      end
    }
    
    for i in 0...BLSize
      print @ar0[i][0]
      for j in 1...BLSize
        if i == 0
          printf((NIKAIDATE ? "%s" : " %s"), @ar0[i][j])
        elsif @ar0[i][j] != 0
          printf((NIKAIDATE ? "%2d" : "%3d"), @ar0[i][j])
        else
          print(NIKAIDATE ? "  " : "   ")
        end
      end
      print "\n"
    end
    
    ## 子と孫の共起
    @arr = Array.new(BLSize)
    @arr.each_index { |i|
      @arr[i] = Array.new(BLSize)
      @arr[i].each_index { |j|
        @arr[i][j] = Array.new(BLSize, 0)
        @arr[i][0][j] = @bushulist[j]
        #@arr[i][j][0] = $relbushu[i] + $relbushu[j]
      }
    }
    @h.each { |i, ii|
      for j in 1...BLSize
        next unless ii[j]
        for k in 1...BLSize
          next unless @h[ii[j]][k]
          #ある孫があったらおじおば（大元の親の子）を全部調べる
          #例外: ar[*][*][0]に孫の分布
          @arr[j][k][0] += 1
          for l in 1...BLSize
            next unless ii[l]
            @arr[j][k][l] += 1
          end
        end
      end
    }
    
    for i in 0...BLSize
      for j in 0...BLSize
        if i == 0
          printf "%s", @bushulist[j] + "−"
        else
          printf "%s", @bushulist[i] + @bushulist[j]
        end
        for k in 1...BLSize
          if j == 0
            printf((NIKAIDATE ? "%s" : " %s"), @arr[i][0][k])
          else
            if i == 0
              arra = @arr[j][k][0]# + @arr[i][k][j]
            else
              arra = @arr[i][j][k] + @arr[j][i][k]
            end
            if arra != 0
              printf((NIKAIDATE ? "%2d" : "%3d"), arra)
            else
              print(NIKAIDATE ? "  " : "   ")
            end
          end
        end
        print "\n"
      end
    end
  end
  attr_reader :arr
end  #CompoInfo

##最適化例は800行あたりに

addmap11 = [
['日','月','火','山','院'],
['木','金','土','宀','車'],
['シ','目','０','サ','性'],#之え<->車革
['イ','才','口','竹','ネ'],
['糸','足','言','石','初']]

addmap12 = [#白髟辟廴走
['禾','食','王','穴','革'],
['冫','酉','〇','四','舟'],#貝->2打目シフトに統合 酉をもってくる
['彳','独','耳','雨','示']]

addmap21 = [
['羊','大','田','巾','部'],
['木','广','厂','囗','門'],
['リ','力','０','貝','隹'],#方鳥魚<->隹貝欠十
['馬','之','口','攵','米'],
['虫','女','十','心','立']]

addmap22 = [#包皿一又寸且彡白各戈点皮者圭斤衣殳匕丶由肖儿甫非刀台子艮工
['弓','病','尸','匚','行'],
['方','鳥','〇','頁','見'],
['牛','え','歹','欠','魚']]

## 初期設定
opt = ARGV.shift
if opt == '--bushu'
  MAPPINGBUSHU = true
  PACKINGTREE = false
elsif opt == '--stroke'
  MAPPINGBUSHU = false
  PACKINGTREE = true
end
#部首配置探索モード
 NIDAME = true
 NIKAIDATE = true
 OVERCAND = 0
 LOOSECHECK = true
#打鍵配置生成モード
 CHECKBUSHUMAP = true#false
#
PREFER_BIG = true
#

if NIKAIDATE
  BLSize = 39
else
  BLSize = 25
end

if NIKAIDATE
  bushulist1 = ('０' + (addmap11+addmap12).join.gsub(/[０〇]/, '')).split(//)
  bushulist2 = ('０' + (addmap21+addmap22).join.gsub(/[０〇]/, '')).split(//)
else
  bushulist1 = ('０' + (addmap11).join.gsub(/[０〇]/, '')).split(//)
  bushulist2 = ('０' + (addmap21).join.gsub(/[０〇]/, '')).split(//)
end
bushumap1 = BushuMap.new(bushulist1)
bushumap1.read_from_bushulist
bushumap2 = BushuMap.new(bushulist2)
bushumap2.read_from_bushulist


#$relbushu.each_index { |i|
#  printf "%s %d %d; ", $relbushu[i], rinc(i), dinc(i)
#}
#print "\n"

## 合成木作成

suppli = ''
$invisi = ''
begin
  File.open('suppli.txt') { |fp|
    while fp.gets
      chop!
      gsub! /\s*/, ''
      gsub! /\#.*$/, ''
      if $_ =~ /^hidden:/
        gsub! /^hidden:\s*/, ''
        $invisi << $_
      end
      suppli << $_
    end
  }
rescue
  puts "Warning: #$!"
end
suppli = suppli.split(//).uniq.join
$invisi = Hash[*$invisi.split(//).collect { |i| [i, true] }.flatten]
inrange = Regexp.new('[亜-腕' + suppli + ']')#/[亜-熙]/#

#rev = File.open('kwbushu.rev')
#rev = IO.popen('cat kwbushu.rev kwbushu.add')
rev = File.open('bushu.th')

c1 = CompoInfo.new(bushulist1)
c2 = CompoInfo.new(bushulist2)
h3 = Hash.new()
h4 = Hash.new()

#prior = '广厂囗門病尸匚之えシイ冫彳ネ初宀サ竹独院性部'.split(//)
#double = '木口'
b1kanmuri = '宀サ竹穴四雨'.split(//)
b2hen = '女貝馬米牛魚弓歹'.split(//)
b2kamae = '广厂囗門病尸匚行之え'.split(//)
b2tukuri = 'リ力隹頁見鳥攵欠部'.split(//)

$all_ch = []
newoya = []
while rev.gets
  chop!
  $_ = Kconv.kconv($_, Kconv::SJIS, Kconv::EUC)
  next unless $_ =~ /^...+$/  #等価定義排除
  i = $_.split(//)
  next unless i[0] =~ inrange
  $all_ch += i.collect { |j| j =~ inrange && j }.compact
  ##
  j1l = bushulist1.index(i[1])
  j1r = bushulist1.index(i[2])
  j2l = bushulist2.index(i[1])
  j2r = bushulist2.index(i[2])
  #if prior.include?(i[1]) && prior.include?(i[2])
  #  printf "both prior: %s\n", i.join
  #elsif prior.include?(i[1]) || prior.include?(i[2])
  #  if prior.include?(i[1]) && i[5] =~ /\w/ \
  #    || prior.include?(i[2]) && i[4] =~ /\w/
  #    printf "mismatch between prior and specifier: %s\n", i.join
  #  end
  #elsif (j1l || j2l) && (j1r || j2r)
  #  printf "vague: %s\n", i.join
  #end
  
  if i[4] == '-' && i[5] == '-'
    j1r = j2r = j1l = j2l = nil
  end
  if PREFER_BIG && (j1l || j2l) && (j1r || j2r)
    if i[1] !~ inrange
      j1r = j2r = nil
    elsif i[2] !~ inrange
      j1l = j2l = nil
    end
  end
  if MAPPINGBUSHU && OVERCAND >= 2
    if !NIDAME
      j2l = j2r = nil
    else
      j1l = j1r = nil
    end
  else  #!MAPPINGBUSHU
    if j1l && (b1kanmuri.include?(i[1]) ? i[4] == 'u' : i[4] == 'l')
      j1r = j2l = j2r = nil
    elsif j1r && (b1kanmuri.include?(i[2]) ? i[5] == 'u' : i[5] == 'l')
      j1l = j2l = j2r = nil
    elsif j2l && ( \
      b2hen.include?(i[1]) && i[4] == 'l' \
      || b2kamae.include?(i[1]) && i[4] == 'o' \
      || b2tukuri.include?(i[1]) && i[4] == 'r')
      j1l = j1r = j2r = nil
    elsif j2r && ( \
      b2hen.include?(i[2]) && i[5] == 'l' \
      || b2kamae.include?(i[2]) && i[5] == 'o' \
      || b2tukuri.include?(i[2]) && i[5] == 'r')
      j1l = j1r = j2l = nil
    elsif j2l && !( \
      b2hen.include?(i[1]) \
      || b2kamae.include?(i[1]) \
      || b2tukuri.include?(i[1]))
      j1l = j1r = j2r = nil
    elsif j2r && !( \
      b2hen.include?(i[2]) \
      || b2kamae.include?(i[2]) \
      || b2tukuri.include?(i[2]))
      j1l = j1r = j2l = nil
    elsif j2l || j2r
      j1l = j1r = nil
    end
  end  #MAPPINGBUSHU
  printf "vague: %s\n", i.join if [j1l, j1r, j2l, j2r].compact.length > 1
  if j1l
    j, c, ik = j1l, c1, i[2]
  elsif j2l
    j, c, ik = j2l, c2, i[2]
  elsif j2r
    j, c, ik = j2r, c2, i[1]
  elsif j1r
    j, c, ik = j1r, c1, i[1]
  else
    j = nil
  end
  ##
  if j
    
    if  ik =~ inrange
      if !(c.h[ik] && c.h[ik][j])  #order sensitiveな場合は先に読まれた方優先
        c.h[i[0]] = Array.new(BLSize) unless c.h[i[0]]
        c.h[ik] = Array.new(BLSize) unless c.h[ik]
        c.h[ik][j] = i[0]  #親+j=子
        c.h[i[0]][0] = ik  #子-0=親
      else
        printf "order-sensitive pattern: %s, %s\n", c.h[ik][j], i.join
        h3[i[0]] = [i[1], i[2]]
      end
    else
      newoya = newoya << ik
      h3[i[0]] = [i[1], i[2]]
    end
    next
  else
    h4[i[0]] = [i[1], i[2]]
    h4[i[1]] = 1 if i[1] =~ inrange && ! h4[i[1]]
    h4[i[2]] = 2 if i[2] =~ inrange && ! h4[i[2]]
  end
end
h3.each_key { |i|
  h4.delete(i) if h4[i]
}
$all_ch.uniq!
newoyarank = Hash.new(0)
newoya.each { |i|
  newoyarank[i] += 1
}
newoyarank = newoyarank.to_a.sort! { |i, j|
  j[1] <=> i[1]
}
print "new candidate for oyaji:\n"
print newoyarank, "\n"
print "recommended to hidden oyaji:\n"
j = h4.to_a.collect { |i, j| j }.flatten.uniq
newoyarank.each { |i|
  print i if ! j.index(i[0])  #これを親字とする対象外合成パターンがない
}
print "\n"
p h3, h4
rev.close

both = 0
c1.h.each_key { |i|
  both += 1 if c2.h[i]
}

both2 = 0
h3.each_key { |i|
  both2 += 1 if c1.h[i] || c2.h[i]
}
h4.each_key { |i|
  both2 += 1 if c1.h[i] || c2.h[i]
}

printf "total: %d\n", $all_ch.length
printf "organized: %d + %d - %d\n", c1.h.length, c2.h.length, both
printf "alone: %d or %d\n", $all_ch.length - c1.h.length - c2.h.length + both, h3.length + h4.length - both2
p $all_ch - c1.h.collect {|i, j| i } - c2.h.collect {|i, j| i } - (h3.collect {|i, j| i } | h4.collect {|i, j| i })
i = 0
c1.h.each_key { |j|
  i += 1 if !c1.h[j][0] && (!c2.h[j] || !c2.h[j][0])
}
c2.h.each_key { |j|
  i += 1 if !c2.h[j][0] && !c1.h[j]
}
printf "1st genaration: %d\n", i

if false##########################
## 合成木summery

def bushutrace(h, hh, trtr)
  for i in 1...BLSize
    next unless hh[i]
    trtr[i] = Array.new() unless trtr[i]
    if not trtr[i][0]
      trtr[i][0] = [hh[i], 1]
    else
      trtr[i][0][1] += 1
    end
    bushutrace(h, h[hh[i]], trtr[i])
  end
end

impose_h = Array.new(BLSize)
h1.each { |i, j|
  next if j[0]
  bushutrace(c1.h, j, impose_h)
}

p impose_h

## すぐ調べられること

print "repeated same bushu:\n"
for i in 1...BLSize
  print impose_h[i][i].inspect, "; "
end
print "\n"

end#####if false#####################
## 相対座標書き出し

#rubyリファレンスからコピー
class Array
  def every(&block)
    arity = block.arity
    return self.each(&block) if arity <= 0

    i = 0
    while i < self.size
      yield(*self[i, arity])
      i += arity
    end
    self
  end
end

if MAPPINGBUSHU##################################

def bushutrace_addr3(h, bushumap, hh, trtr)
  for i in 1...BLSize
    next unless h[hh][i]
#    print s[i], i
    trtr[i] = Array.new() unless trtr[i]
    n0 = trtr[0][1]
    d0 = trtr[0][3]
    ni = 0
    di = bushumap.dinc(i)
    if di > 2
      ni += 1
      di -= 4
    end
    d = d0 + di
    if d < 0 || d > 3
      ni += 1
      d = d.modulo(4)
    end
    ##trtr[i][0] = [trtr[0][0] + h[hh][i], n0 + ni, (trtr[0][2]+bushumap.rinc(i)+2).modulo(5)-2, d]
    trtr[i][0] = [trtr[0][0] + bushumap.bushulist[i], n0 + ni, (trtr[0][2]+bushumap.rinc(i)+2).modulo(5)-2, d]
    bushutrace_addr3(h, bushumap, h[hh][i], trtr[i])
  end
end

class Array
  def cdr
    r = self.dup
    r.shift
    return r
  end
end

def check_collision3(h, bushumap, critical = nil)
  sum = 0
  h.each { |i, j|
    j_h = nil
    next if j[0]
    e = Array.new(4, "ok")
    for d in 0..3
      i_h = Array.new(BLSize*2)
      i_h[0] = [i, 0, 0, d]  #字, プリフィクス数, 左右方向-2..2, 段（上から）0..3
      bushutrace_addr3(h, bushumap, i, i_h)
      j_h = []
      i_h.flatten.compact.every { |k, l, m, n|
        j_h.push([k, l, m, n]) unless $invisi[k]
      }
      len = j_h.collect { |k, l, m, n|
        [l, m, n]
      }.uniq.length
      if len < j_h.length
        print i, j_h.inspect, "\n"
        e[d] = "miss"
      end
    end
    if e.include?("miss")
      print i, e.inspect, "\n"
      sum += 1
    end
    if critical && ! e.include?("ok")
      #p j_h
      for k in 1...j_h.length-1
        for l in k+1...j_h.length
          if j_h[k].cdr == j_h[l].cdr
            #p j_h[k][0].split(//).cdr, j_h[l][0].split(//).cdr
            c = j_h[k][0].split(//).cdr + j_h[l][0].split(//).cdr
            critical.push(c)
          end
        end
      end
      #p critical
    end
  }
  return sum
end

if !NIDAME
  print "relative addresses:\n"
  printf "self-colliding on %d trees\n", check_collision3(c1.h, bushumap1)
  c1.calc_ar()
else
  print "relative addresses:\n"
  printf "self-colliding on %d trees\n", check_collision3(c2.h, bushumap2)
  c2.calc_ar()
end

## 探索

if !NIDAME
  if NIKAIDATE
set0 = [
'０',
'日','月','火',
'ネ','初','示','才','足','独','口','言','耳',
'木','金','土','禾','食','王',
'宀','サ','竹','穴','四','雨',
'イ','彳','シ','冫','車','革','目','酉',
'山','院','性','糸','石','舟']
setfix = [
nil,
'd0','1r','1r',
'd13','[1034]d','2Fpp','d123','[1034]d','2Fpp','d123','1F','2Fpp',
'd13','1r','1r','2Fppp','1r','1r',
#'d13','1r','1r','2Fppp','1r','1r',
'd123','d123','d123','2Fppp','2Fppp','2Fppp',
'd123','2Fp','d123','2Fp','d123','2Fp','d123','2F',
'1F','1F','1F','1F','1F','2F']
  else
set0 = [
'０',
'日','月','火',
'ネ','初','才','足','口','言',
'木','金','土',
'宀','サ','竹','イ','シ','目','之',
'山','院','性','糸','石']
setfix = [
nil,
'd0','1r','1r',
'd13','[1034]d','d13','[1034]d','d13','[1034]d',
'd13','1r','1r',
'd123','d123','d123','d123','d123','d123','d123',
nil]
  end
else  #NIDAME
set0 = [
'０',
'木','部','心','口','鳥',#最適化例に合わせた
'羊','大','田','广','厂','囗','門','病','尸','匚','行',
'リ','力','隹','貝','頁','攵','欠',
'之','え','虫','女','米','魚','馬','牛','方','弓','歹','見',
'巾','立','十']
setfix = [
nil,
'r0d1','r4d3','r3d4','r0d2','r4d7',
'd04','1r','1r','d123','1r','d123','1r','2Fpppp','1r','2Fpppp','1r',
'd123','d123','d123','d123','2Fp','1F','2F',
'd123','2Fp','d04','d04','d123','2Fp','d123','2Fp','2F','2F','2F','2F',
'1F','1F','1F']
end
set0.each_index { |i|
  printf("%s %s\n", set0[i], setfix[i])
}


class CooccurChecker
  #2004.02.18-
  def initialize(bushumap, arr, set0, setfix)
    @bushumap = bushumap
    @arr = arr
    for i in 1...BLSize
      for j in i...BLSize
        @arr[i][j][0]=@arr[j][i][0]=@arr[i][j][0]+@arr[j][i][0]
      end
    end
    for i in 1...BLSize
      ii = @bushumap.number(set0[i])
      i_1r = i if setfix[i] != '1r'
      setfi = setfix[i_1r]
      j_1r = i_1r
      for j in (i+1)...BLSize
        jj = @bushumap.number(set0[j])
        j_1r = j if setfix[j] != '1r'
        setfj = setfix[j_1r]
        if j_1r == i_1r
          @arr[ii][jj][0]=@arr[jj][ii][0]=99
        elsif setfi =~ /^2F/ || setfj =~ /^2F/
          @arr[ii][jj][0]=@arr[jj][ii][0]=99
        elsif setfi =~ /^d04?$/ || setfi == '[1034]d'
          if setfj =~ /^d12?3$/ || setfi == 'd0' && setfj == 'd0'
            @arr[ii][jj][0]=@arr[jj][ii][0]=99
          end
        elsif setfi =~ /^d12?3$/
          if setfj =~ /^d04?$/ || setfj == '[1034]d'
            @arr[ii][jj][0]=@arr[jj][ii][0]=99
          end
        end
      end
    end
    for i in 1...BLSize
      printf("%s", @arr[0][0][i])
      for j in 1...BLSize
        if @arr[i][j][0] != 0
          printf((BLSize <= 25 ? "%3d" : "%2d"), @arr[i][j][0])
        else
          print(BLSize <= 25 ? "   " : "  ")
        end
      end
      print "\n"
    end
  end
  
  def relative_check0(len, set0, setfix, relstack)
    both_vacant = false
    for j in 1..12
      if ! relstack.index(j) && ! relstack.index(-j)
        both_vacant = true
        break
      end
    end
    for i in 1...len
      ii = @bushumap.number(set0[i])
      next if relstack[i] > 12
      ##next if relstack[i] <= -8 || relstack[i] >= 8  #second_best
      next if relstack.index(-relstack[i])
      #next 
      k = 0
      for j in 1...BLSize
        next if j == ii
        if @arr[0][ii][j] == 0 && set0.index(@bushumap.bushulist[j]) >= len
          k += 1
        end
      end
      if k == 1
        if @arr[0][ii][@bushumap.number(set0[len])] == 0
          return -relstack[i]
        end
      elsif k == 0
        return false
      end
    end
    return true
  end
  
  def relative_check1(i, len, set0, setfix, relstack)
    return true if i > 12
    ##return true if i <= -8 || i >= 8  #second_best
    ii = @bushumap.number(set0[len])
    cmpl = relstack.index(-i)
    if cmpl
      cmpl = @bushumap.number(set0[cmpl])
      if @arr[ii][cmpl][0] > 0
        return false
      end
      return true
    else
      for j in 1...BLSize
        next if j == ii
        if @arr[ii][j][0] == 0 && set0.index(@bushumap.bushulist[j]) > len
          return true
        end
      end
    end
  end
  
  def relative_check2(newitem)
    #false: collision
    second_best = false
    newitem.each { |i|
      nd = @bushumap.dinc(i)
      nr = @bushumap.rinc(i)
      #nn = @bushumap.addmap[nd+2][nr+2]
      #nn = @bushumap.number(nn)
      nn =  @bushumap.number(i)
      #旧孫と新子
      for j in -12..12
        next if j == 0 || @bushumap.relh[i] == j
        p1d = (j+12).divmod(5)[0]-2
        p1r = (j+12).modulo(5)-2
        p2d = (nd - p1d + 2).modulo(8)-2
        p2r = (nr - p1r + 2).modulo(5)-2
        p1 = @bushumap.addmap[p1d+2][p1r+2]
        p2 = @bushumap.addmap[p2d+2][p2r+2]
        next unless p1 && p2
        p1 = @bushumap.number(p1)
        p2 = @bushumap.number(p2)
        if @arr[p1][p2][nn]+@arr[p2][p1][nn] > 0
          #if false  #プリフィクス増やし孫と折り畳み子
          if LOOSECHECK && p2d>2&&nd<=2   # || p1d==-2&&p2d==2 || p1d==2&&p2d==-2
            #print "second_best\n"
            second_best = true
          else
            return false
          end
        end
      end
      #新孫と旧子
      for j in -12..(@bushumap.relh[i] > 12 ? 12 : 27)  #1F+1F or 1F+2F or 2F+1F
        next if j == 0 || j == 20
        jd = (j+12).divmod(5)[0]-2
        jr = (j+12).modulo(5)-2
        pd = (jd + nd + 2).modulo(8)-2
        pr = (jr + nr + 2).modulo(5)-2
        jj = @bushumap.addmap[jd+2][jr+2]
        pp = @bushumap.addmap[pd+2][pr+2]
        next unless jj && pp
        jj = @bushumap.number(jj)
        pp = @bushumap.number(pp)
        if @arr[nn][jj][pp]+@arr[jj][nn][pp] > 0
          #if false
          if LOOSECHECK && (nd>2||jd>2)&&pd<=2   # || nd==-2&&jd==2 || nd==2&&jd==-2
            #print "second_best\n"
            second_best = true
          else
            return false
          end
        end
      end
    }
    return true
  end

end  #CooccurChecker

def searchmap(ci, bushulist, set0, setfix)
  bushumap = BushuMap.new(bushulist)
  relstack = [0]
  cocheck = CooccurChecker.new(bushumap, ci.arr, set0, setfix)
  i = nil
  while true
    ##print '.'
    len = relstack.length
    if ! i  #新しく積む
      p relstack if len.modulo(12) == 7
      i = -13
    else  #新しく積むのに失敗した
      #print '.'
      if len <= 1
        print "end\n"
        break
      end
      i = relstack.pop
      len -= 1
      d = (i+12).divmod(5)[0]
      r = (i+12).modulo(5)
      bushumap.unset(i, set0[len])
    end
    relcheck0 = cocheck.relative_check0(len, set0, setfix, relstack)  #対隅条件 位置が1つに決まるか（なくても動く）
    while true
      if relcheck0 == true  #これでしか埋められない穴はない
        i = i + 1
        i = 1 if i == 0
        i = 21 if i == 20
        break unless NIKAIDATE ? i <= 27 : i <= 12
      elsif relcheck0 == false  #すでに埋められなくなった穴がある
        print "false, length=%d\n", len
        i = 99
        break
      elsif relcheck0.is_a?(Integer)  #これでしか埋められない穴がある
        if i == -13
          #printf "only %d, length=%d\n", relcheck0, len
          i = relcheck0
        else
          i = 99
          break
        end
      end
      d = (i+12).divmod(5)[0]
      r = (i+12).modulo(5)
      next if bushumap.addmap[d][r]  #上書き不可
      case setfix[len]  #配置条件
      when /^r.d.$/
        next unless r == setfix[len][1..1].to_i && d == setfix[len][3..3].to_i
      when /^d04?/
        next unless d == 0 || setfix[len] == 'd04' && d == 4
      when /^d12?3/
        next unless d == 1 || d == 3 || setfix[len] == 'd123' && d == 2
      when '1r'
        next unless d == bushumap.dinc(set0[len-1])+2 && r == bushumap.rinc(set0[len-1])+2 + 1
      when '[1034]d'
        next unless r == bushumap.rinc(set0[len-1])+2
        next unless d == 0 && bushumap.dinc(set0[len-1])+2 == 1 || d == 4 && bushumap.dinc(set0[len-1])+2 == 3
      when '1F'
        next unless d >= 0 && d <= 4
      when '2F'
        next unless d >= 5 && d <= 7
      when /^2Fpp*/
        next unless r == bushumap.rinc(set0[len-setfix[len].length+2])+2
        next unless d == bushumap.dinc(set0[len-setfix[len].length+2])+2 + 4
      end
      next unless cocheck.relative_check1(i, len, set0, setfix, relstack)  #対隅条件 その位置に入れるか
      bushumap.set(i, set0[len])
      if not cocheck.relative_check2([set0[len]])  #子と孫の衝突
        bushumap.unset(i, set0[len])
        next
      end
      break
    end
    if NIKAIDATE ? i > 27 : i > 12
      next
    else
      if len + 1 >= set0.length
        puts "detected!"
        puts bushumap.addmap.collect { |j|
          j.collect { |k|
            k || '〇'
          }.join
        }
        relstack.push(i)
        print "re-checking...\n"
        critical = []
        printf "self-colliding on %d trees\n", check_collision3(ci.h, bushumap, critical)
        if critical.length > 0
          j = relstack.length
          critical.each { |c|
            k = 0
            c.each { |l|
              k = set0.index(l) if k < set0.index(l)
            }
            j = k if j > k
          }
          printf "trunc length to %d\n", j + 1
          while relstack.length > j + 1
            i = relstack.pop
            len -= 1
            bushumap.unset(i, set0[len])
          end
          p relstack
          i = relstack[-1]
        end
        next
      else
        relstack.push(i)
        i = nil
      end
    end
  end
end

if !NIDAME
  searchmap(c1, bushulist1, set0, setfix)
else
  searchmap(c2, bushulist2, set0, setfix)
end

else PACKINGTREE##################################

addmapn1 = [
#['日','月','火','初','足'],#0326.3.L9916
#['木','金','土','ネ','車'],
#['口','宀','０','竹','シ'],
#['サ','イ','目','才','院'],
#['石','言','糸','性','山'],
#['禾','食','王','示','革'],
#['耳','穴','〇','雨','冫'],
#['四','彳','舟','独','酉']]
['日','月','火','初','性'],#0530.1.L2124
['木','金','土','ネ','車'],
['口','宀','０','竹','シ'],
['サ','イ','目','才','院'],
['石','言','糸','足','山'],
['禾','食','王','示','革'],
['耳','穴','〇','雨','冫'],
['四','彳','舟','独','酉']]

addmapn2 = [
#['羊','大','田','虫','攵'],#0326.4.L4374
#['木','广','厂','リ','力'],
#['口','貝','０','囗','門'],
#['隹','馬','米','之','部'],
#['女','巾','立','心','十'],
#['欠','病','尸','方','弓'],
#['歹','頁','〇','匚','行'],
#['見','牛','魚','え','鳥']]
['羊','大','田','十','攵'],#0326.4.L2556
['木','广','厂','リ','力'],
['口','貝','０','囗','門'],
['隹','之','米','馬','部'],
['女','虫','立','心','巾'],
['欠','病','尸','方','弓'],
['歹','頁','〇','匚','行'],
['見','え','魚','牛','鳥']]

print "1dame shifts:\n"
puts addmapn1.collect { |j| j.join }
print "2dame shifts:\n"
puts addmapn2.collect { |j| j.join }

bushumapn1 = BushuMap.new(bushulist1)
bushumapn1.read_from_addmap(addmapn1)
bushumapn2 = BushuMap.new(bushulist2)
bushumapn2.read_from_addmap(addmapn2)

def bushutrace_addr5(h1, bushumap1, h2, bushumap2, hh, trtr)  #380行あたり参照のこと
  n0 = trtr[0][1]
  d10 = trtr[0][3]
  d20 = trtr[0][5]
  for i in 1...BLSize*2
    next if i == BLSize
    next if (i > BLSize ? !h2[hh] : !h1[hh])
    next unless (i > BLSize ? h2[hh][i-BLSize] : h1[hh][i])
    #print i, (i > BLSize ? h2[hh][i-BLSize] : h1[hh][i])
    trtr[i] = Array.new() unless trtr[i]
    ni = 0
    d1i = (i > BLSize ? 0 : bushumap1.dinc(i))
    d2i = (i > BLSize ? bushumap2.dinc(i-BLSize) : 0)
    if d1i > 2
      ni += 1
      d1i -= 4
    end
    if d2i > 2
      ni += 1
      d2i -= 4
    end
    #print d10, d1i, d20, d2i, "\n"
    d1 = d10 + d1i
    d2 = d20 + d2i
    if d1 < 0 || d1 > 3
      ni += 1
      d1 = d1.modulo(4)
    end
    if d2 < 0 || d2 > 3
      ni += 1
      d2 = d2.modulo(4)
    end  #        ##bushutrace_addr3と違うので注意
    trtr[i][0] = [(i > BLSize ? h2[hh][i-BLSize] : h1[hh][i]), n0 + ni, \
    (trtr[0][2]+(i > BLSize ? 0 : bushumap1.rinc(i))+2).modulo(5)-2, d1, \
    (trtr[0][4]+(i > BLSize ? bushumap2.rinc(i-BLSize) : 0)+2).modulo(5)-2, d2]
    bushutrace_addr5(h1, bushumap1, h2, bushumap2, (i > BLSize ? h2[hh][i-BLSize] : h1[hh][i]), trtr[i])
  end
end

def self_collision5?(i_h)
  j_h = []
  i_h.flatten.compact.every { |k, l, m, n, o, p|
    j_h.push([k, l, m, n, o, p]) unless $invisi[k]
  }
  len = j_h.collect { |k, l, m, n, o, p|
    [l, m, n, o, p]
  }.uniq.length
  return (len < j_h.length ? j_h : nil)
end

def maxnn(i_h)
  j_h = []
  i_h.flatten.compact.every { |k, l, m, n, o, p|
    j_h.push(l) unless $invisi[k]
  }
  nn = 0
  j_h.each { |l|
    nn = l if nn < l
  }
  return nn
end

def check_collision5(h1, bushumap1, h2, bushumap2)
  sum = 0
  (h1.to_a.collect { |i|
    i[0]
  } | h2.to_a.collect { |i|
    i[0]
  }).each { |i|
    j1 = h1[i]
    j2 = h2[i]
    #p i, j1, j2
    next if j1 && j1[0] || j2 && j2[0]
    e = Array.new(16, "ok")
    for d1 in 0..3
      for d2 in 0..3
        i_h = Array.new(BLSize*2)
        i_h[0] = [i, 0, 0, d1, 0, d2]  #字, プリフィクス数, 1打目左右, 上下, , 2打目左右, 上下
        bushutrace_addr5(h1, bushumap1, h2, bushumap2, i, i_h)
        if (j_h = self_collision5?(i_h))
          print i, j_h.inspect, "\n"
          e[d1*4+d2] = "miss"
        end
      end
    end
    if e.include?("miss")
      print i, e.inspect, "\n"
      sum += 1
    end
  }
  return sum
end

if CHECKBUSHUMAP
  print "relative addresses:\n"
  printf "self-colliding on %d trees\n", check_collision5(c1.h, bushumapn1, c2.h, bushumapn2)
end

begin
  hindo = Hash.new()  #{"字"=>[ranking, frequency]}
  hindorank = []
  #http://nozaki-lab.ics.aichi-edu.ac.jp/nozaki/asahi/kanji.html
  #前後をコメントアウトした
  File.open('nozaki-lab.txt') { |fp|
    i = 1
    ci = nil
    di = nil
    guessed_code = Kconv::UNKNOWN
    remain = $all_ch.dup
    while fp.gets
      chop!
      guessed_code = Kconv.guess($_) if guessed_code == Kconv::UNKNOWN
      $_ = Kconv.kconv($_, Kconv::SJIS, guessed_code)
      next if $_ =~ /^\s*\#/
      gsub!(/^\s*/, '')
      j = split(/\s\s*/)
      if ! ci
        for k in 0...j.length  #自動判定
          ci = k if !ci && j[k] =~ /[　-熙]/
          di = k if j[k].to_i > 100
        end
      end
      #p j
      c = j[ci]
      d = j[di]
      if c !~ inrange
        #printf "out of range: %s\n", j.inspect
        next
      elsif !(c1.h[c] || c2.h[c] || h3[c] || h4[c]) || $invisi[c]
        printf "lost: %s\n", j.inspect
        h4[c] = 0 if i < 1500
        #next
      end
      hindo[c] = [i, d.to_i]
      hindorank[i-1] = c
      i += 1
      remain.delete(c)
    end
    #あとランキングにない字を登録しないと
    remain.each { |j|
      hindo[j] = [i, 1]
      hindorank[i-1] = j
      i += 1
    }
  }

  $avehindo = 0
  hindo.each { |i, j|
    $avehindo += j[0]
  }
  $avehindo /= hindo.length
  printf "average of hindo = %d\n", $avehindo
rescue
  puts "Warning: #$!"
  hindo = nil
  hindorank = nil
end

def firstgen(h1, h2, i)
  if h1[i] && h1[i][0]
    firstgen(h1, h2, h1[i][0])
  elsif h2[i] && h2[i][0]
    firstgen(h1, h2, h2[i][0])
  else
    i
  end
end

def check_recursively(tbl, trtr)
  nn = trtr[0][1]
  r1 = trtr[0][2]
  d1 = trtr[0][3]
  r2 = trtr[0][4]
  d2 = trtr[0][5]
  return false if tbl[nn][r1][d1][r2][d2] && !$invisi[trtr[0][0]]
  for i in 1...BLSize*2
    next if i == BLSize
    next if !trtr[i]
    ret = check_recursively(tbl, trtr[i])
    return false if ret == false
  end
  return true
end

def regist_recursively(tbl, trtr)
  nn = trtr[0][1]
  r1 = trtr[0][2]
  d1 = trtr[0][3]
  r2 = trtr[0][4]
  d2 = trtr[0][5]
  tbl[nn][r1][d1][r2][d2] = trtr[0][0] unless $invisi[trtr[0][0]]
  for i in 1...BLSize*2
    next if i == BLSize
    next if !trtr[i]
    regist_recursively(tbl, trtr[i])
  end
end

def trtr_move(trtr, ni, r1i = 0, r2i = 0)
  trtr[0][1] += ni
  #trtr[0][2] = (trtr[0][2] + r1i).modulo(5)
  #trtr[0][4] = (trtr[0][4] + r2i).modulo(5)
  for i in 1...BLSize*2
    next if i == BLSize
    next if !trtr[i]
    trtr_move(trtr[i], ni, r1i, r2i)
  end
  return true
end

def init_tbl()
  tbl = Array.new(4)
  tbl.each_index { |i|  #ll, lr, rl, rr
    tbl[i] = Array.new(8)
    tbl[i].each_index { |j|  #prefix count
      tbl[i][j] = Array.new(5)
      tbl[i][j].each_index { |k|  #r1
        tbl[i][j][k] = Array.new(4)
        tbl[i][j][k].each_index { |l|  #d1
          tbl[i][j][k][l] = Array.new(5)
          tbl[i][j][k][l].each_index { |m|  #r2
            tbl[i][j][k][l][m] = Array.new(4, nil)  #d2
          }
        }
      }
    }
  }
  return tbl
end

def pseudo2stroke(tbl)
  for i in [0, 3]
    for j in 0..7
      for k in 0..4
        for l in 0..3
          tbl[i][j][k][l][k][l] = '□'
        end
      end
    end
  end
  for i in 0..3
    for j in 0..4
      for k in 0..4
        tbl[i][2][j][0][k][0] = '□'  #4ストロークの最上段
      end
    end
  end
end

def g_kana(tbl)
  hira = <<EOS.split(/\s*/)
ゎ（―）‥わゐ？ゑを
ゝ〈っ〉ゞらりるれろ
ゃ『ゅ』ょや「ゆ」よ
ぱぴぷぺぽまみむめも
ばびぶべぼはひふへほ
〜、ん。…なにぬねの
だぢづでどたちつてと
ざじずぜぞさしすせそ
がぎぐげごかきくけこ
ぁぃぅぇぉあいうえお
EOS
  kata = <<EOS.split(/\s*/)
ヮヽャパバーダザガァ
〔《“ピビ，ヂジギィ
ヴッュプブンヅズグゥ
〕》”ペベ．デゼゲェ
‐ヾョポボ・ドゾゴォ
ワラヤマハナタサカア
ヰリ‘ミヒニチシキイ
！ルユムフヌツスクウ
ヱレ’メヘネテセケエ
ヲロヨモホノトソコオ
EOS
  for i in 0..1
    for j in 0..4
      for k in 0..1
        for l in 0..4
          tbl[2][0][l][k+1][j][i+1] = hira[50*i+10*j+5*k+l]
          tbl[1][0][l][k+1][j][i+1] = kata[50*i+10*j+5*k+l]
        end
      end
    end
  end
end

def cost_brief(lrlr, nn, d1, d2)
  c = nn + 2
  dadd = [+0.5, 0, -0.1, +0.2]
  c += dadd[d1] + dadd[d2]
  if lrlr == 0 || lrlr == 3  #ll or rr
    if d2 - d1 >= 2 || d2 - d1 <= -2
      c += 0.1
    end
  else  #lr or rl
    c -= 0.2
  end
  return c
end

def cost(lrlr, nn, r1, d1, r2, d2)
  c = cost_brief(lrlr, nn, d1, d2)
  radd = [+0.2, 0, -0.1, 0, +0.2]
  c += radd[r1] + radd[r2] #- 0.16
  if lrlr == 0 || lrlr == 3  #ll or rr
    if r1 == r2
      c += 0.2
    end
  else  #lr or rl
  end
  return c
end

def fill_optimally(tbl, costtbl, hindorank)
  costrank = []
  ii = 0
  for i in 0..3
    for j in 0..7
      for k in 0..4
        for l in 0..3
          for m in 0..4
            for n in 0..3
              next if tbl[i][j][k][l][m][n]
              costrank[ii] = [cost(i, j, k, l, m, n), i, j, k, l, m, n]
              ii += 1
            end
          end
        end
      end
    end
  end
  costrank.sort! { |i, j| i[0] <=> j[0] }
  hindorank.each_index { |ii|
    trash, i, j, k, l, m, n = costrank[ii]
    tbl[i][j][k][l][m][n] = hindorank[ii]
    costtbl[i][j][k][l][m][n] = ii + 1
  }
  return costrank
end

def eval_trtr(lrlr, trtr, hindo, hindorank, costtbl)
  trl = []
  trtr.flatten.compact.every { |k, l, m, n, o, p|
    trl.push([k, l, m, n, o, p]) unless $invisi[k]
  }
  len = trl.length
  #平均頻度を求める
  c0 = 0
  trl.each { |i|
    c0 += hindo[i[0]][1]
  }
  c0 /= len
  #
  n = maxnn(trtr)
  disptbl = []
  for ni in 0..7
    break if n + ni > 7
    c = 0
    trl.each { |i|
      #打鍵位置からコスト順位を求め
      if costtbl[lrlr][i[1]+ni][i[2]][i[3]][i[4]][i[5]].is_a?(Integer)
        rank = costtbl[lrlr][i[1]+ni][i[2]][i[3]][i[4]][i[5]]
      else  #うーむ
        rank = ni * 1500 + 200
      end
      c += hindo[hindorank[rank.to_i]||hindorank[-1]][1]
      #c += Math.exp(-rank * Math.log(10) / 1000)
    }
    c /= len
    
    ave = 0
    disparse = 0
    trl.each { |i|
      #打鍵位置からコスト順位を求め
      if costtbl[lrlr][i[1]+ni][i[2]][i[3]][i[4]][i[5]].is_a?(Integer)
        rank = costtbl[lrlr][i[1]+ni][i[2]][i[3]][i[4]][i[5]]
      else  #うーむ
        rank = ni * 1500 + 200
      end
      #明らかに恣意的な調整 1470行あたり参照
      r = 1 + len.to_f ** 0.5 / 4.0
      #頻度と理想頻度の差から分散（総コスト悪化要因）を求める
      #理想状態ではコスト順==頻度順
      ave += hindo[hindorank[rank.to_i]||hindorank[-1]][1] / r - hindo[i[0]][1]
      #disparse += Math.log(hindo[hindorank[rank.to_i]||hindorank[-1]][1] * c0 / c / hindo[i[0]][1].to_f) ** 2 * c0 ** 2
      disparse += (hindo[hindorank[rank.to_i]||hindorank[-1]][1] * c0 / c / r - hindo[i[0]][1].to_f) ** 2
      #disparse += (Math.exp(-rank * Math.log(10) / 1000) * c0 / c - hindo[i[0]][1]) ** 2
    }
    ave /= len  #ave == c - c0
    disparse /= len
    #頻度はプリフィクス1個につき10倍以上変化するから
    #つまり対数分布で4は1より10に近いと判断してほしい
    ave = Math.log(c.to_f / c0)
    disparse = disparse / c0 ** 2
    #printf "ni=%d, ave=%f, disparse=%f\n", ni, ave, disparse
    disptbl[ni] = disparse + ave ** 2 / len #+ ((lrlr == 0 || lrlr == 3 || ni > 0) ? 0.2 : 0)
    break if ave <= 0
  end
  if ni == 0
    return ni, disptbl[-1]
  else
    return ni-1, disptbl[-2], ni, disptbl[-1]
  end
end

def eval_tbl(tbl, hindo)
  #平均コストを求める
  c = 0
  thindo = 0
  for i in 0..3
    for j in 0..7
      for k in 0..4
        for l in 0..3
          for m in 0..4
            for n in 0..3
              next if !tbl[i][j][k][l][m][n] || !hindo[tbl[i][j][k][l][m][n]]
              #print cost(i, j, k, l, m, n), " "
              c += cost(i, j, k, l, m, n) * hindo[tbl[i][j][k][l][m][n]][1]
              thindo += hindo[tbl[i][j][k][l][m][n]][1]
            end
          end
        end
      end
    end
  end
  return c / thindo
end

$edu = ''
begin
  File.open('edu.tbl') { |fp|
    while fp.gets
      $_ = Kconv.tosjis($_)
      chop!
      gsub! /\s*/, ''
      gsub! /\#.*$/, ''
      $edu << $_
    end
  }
  $edu = Regexp.new('[' + Regexp.quote($edu) + ']')
rescue
  puts "Warning: #$!"
  $edu = nil
end
#$edu = nil
#p $edu
print "limit the number of stroke of educational kanji\n" if $edu

def maxnn_edu(i_h)
  return -8 unless $edu.is_a?(Regexp)
  j_h = []
  i_h.flatten.compact.every { |k, l, m, n, o, p|
    j_h.push(l) if k =~ $edu && !$invisi[k]
  }
  nn = 0
  j_h.each { |l|
    nn = l if nn < l
  }
  #print nn, j_h.length
  return nn
end


$tblname = ["ll", "lr", "rl", "rr"]

def print_tbl(tbl)
  for i in 0..3  #lrlr
    for j in 0..7  #nn
      next if tbl[i][j].flatten.collect { |k| (k != '□' ? k : nil)
      }.compact.length == 0
      printf "%s %d-stroke\n", $tblname[i], j+2
      for k in 0..3  #d2
        for l in 0..3  #d1
          for m in 0..4  #r2
            for n in 0..4  #r1
              print tbl[i][j][n][l][m][k] || '　'
            end
            print "｜"
          end
          print "\n"
        end
        print "\n"
      end
      #print "\n"
    end
  end
end

def knapsack(h1, bushumap1, h2, bushumap2, h3, h4, hindo, hindorank)
  srand()
  #hh = Hash[*(h1.to_a.collect { |i|
  #  i[0]
  #} | h2.to_a.collect { |i|
  #  i[0]
  #}).collect { |i| [i, 0] }.flatten]
  hh = {}
  h1.each_key { |i|
    hh[i] = [0, 0]
  }
  h2.each_key { |i|
    hh[i] = [0, 0]
  }
  if hindo
    hh.each_key { |i|
      j = firstgen(h1, h2, i)
      hh[firstgen(h1, h2, i)][0] += 1
      hh[firstgen(h1, h2, i)][1] += hindo[i][1]
    }
    hh = hh.to_a.sort { |i, j|
      (j[1][0] != i[1][0] ? j[1][0] <=> i[1][0] : j[1][1] <=> i[1][1])
    }
  else
    hh.each_key { |i|
      j = firstgen(h1, h2, i)
      hh[firstgen(h1, h2, i)][0] += 1
    }
    hh = hh.to_a.sort { |i, j|
      j[1][0] <=> i[1][0]
    }
  end

  if hindo
    tbl = init_tbl()
    pseudo2stroke(tbl)
    g_kana(tbl)
    costtbl = init_tbl()
    pseudo2stroke(costtbl)
    g_kana(costtbl)
    costrank = fill_optimally(tbl, costtbl, hindorank)
    #print_tbl(tbl)
    printf "optimal average cost = %f\n", eval_tbl(tbl, hindo)
  end
  
  tbl = init_tbl()
  pseudo2stroke(tbl)
  g_kana(tbl)

  hh.each { |i|
    j1 = h1[i[0]]
    j2 = h2[i[0]]
    next if j1 && j1[0] || j2 && j2[0]
    i1 = i[1][0]
    i = i[0]
    print i, i1
    check = 0
    nn = 0
    if hindo
      lrlr = 0
      disparsions = []
      for j in 0..3  #lrlr
        for k in 0..3  #d1
          for l in 0..3  #d2
            i_h = Array.new(BLSize*2)
            i_h[0] = [i, 0, 0, k, 0, l]  #分散がrとdに関して独立になってればしあわせになるのですが
            bushutrace_addr5(h1, bushumap1, h2, bushumap2, i, i_h)
            next if self_collision5?(i_h)
            m = eval_trtr(j, i_h, hindo, hindorank, costtbl)
            n = maxnn(i_h)
            ntc = maxnn_edu(i_h)
            print "(ntc err)" if j == 0 && ntc > 1
            if m.length == 4
              disparsions << [m[1], j, m[0], k, l, (m[1] <= m[3])] if m[0] + n <= 2 && m[0] + ntc <= 1
              disparsions << [m[3], j, m[2], k, l, (m[3] < m[1])] if m[2] + n <= 2 && m[2] + ntc <= 1
            else
            disparsions << [m[1], j, m[0], k, l, true] if m[0] + n <= 2 && m[0] + ntc <= 1
            end
          end
        end
      end
      disparsions.sort! { |j, k| j[0] <=> k[0] }
      #j = rand(i1/4)
      #if i1/4 >= 2 && j > 0 && disparsions.length > j
      #  printf "(kill best %d)", j
      #  disparsions[0..j-1] = nil
      #end
      print "\n"
      p disparsions[0, 2]
      #p i_h if i1 >= 20
      if disparsions.length == 0
        p i_h
        print "ummmm...\n"
        exit(1)
      end
      i_h = nil
      dispprec = []
      j = 0
      disparsions.each { |trash, lrlr, nn, d1, d2, better|
        #print [trash, lrlr, nn, d1, d2].inspect, ", "
        k = false
        for r1 in 0..4
          for r2 in 0..4
            i_h = Array.new(BLSize*2)
            i_h[0] = [i, 0, r1, d1, r2, d2]
            bushutrace_addr5(h1, bushumap1, h2, bushumap2, i, i_h)
            m = eval_trtr(lrlr, i_h, hindo, hindorank, costtbl)
            n = maxnn(i_h)
            ntc = maxnn_edu(i_h)
            next unless m[0] + n <= 2 && m[0] + ntc <= 1
            if m.length == 4
              m[0..1] = nil if (better ? m[1] > m[3] : m[1] <= m[3]) && m[2] + n <= 2 && m[2] + ntc <= 1
            end
            trtr_move(i_h, m[0])
            if check_recursively(tbl[lrlr], i_h)
              dispprec << [m[1], lrlr, m[0], r1, r2, i_h]
              k = true
            end
          end
        end
        j += 1 if k
        break if dispprec.length > 60 || j > 6
      }
      i_h = nil
      if dispprec.length > 0
        dispprec.sort! { |j, k| j[0] <=> k[0] }
        j = rand(i1/4).to_i
        j = 0 if j >= dispprec.length
        printf "(kill best %d)", j if j > 0
        score, lrlr, nn, r1, r2, i_h = dispprec[j]
        print score, ' '
      end
      #print "\n"
      if ! i_h
        p i_h
        print "ummmm...\n"
        exit(1)
      end
    else  #!hindo
      while true
        lrlr = rand(4)
        r1 = rand(5)
        d1 = rand(4)
        r2 = rand(5)
        d2 = rand(4)
        i_h = Array.new(BLSize*2)
        i_h[0] = [i, nn, r1, d1, r2, d2]
        bushutrace_addr5(h1, bushumap1, h2, bushumap2, i, i_h)
        if check_recursively(tbl[lrlr], i_h) && ! self_collision5?(i_h)
          break
        end
        check += 1
        if check > 10000
          nn += 1
          check = 0
        end
      end
    end  #if hindo
    regist_recursively(tbl[lrlr], i_h)
    print $tblname[lrlr], i_h[0].inspect, "\n"
  }

  print_tbl(tbl)
  print "\n"
  
  ha = []
  h3.each_key { |i|
    ha << i unless h1[i] || h2[i]
  }
  h4.each_key { |i|
    ha << i unless h1[i] || h2[i]
  }
  ha.collect! { |i| [i, hindo[i][0]] }.sort! { |i, j| i[1] <=> j[1] }
  printf "not-organized chars: %d\n", ha.length
  
  j = 0
  ave = 0
  ha.each { |i|
    i = i[0]
    c, lrlr, nn, r1, d1, r2, d2 = costrank[j]
    while tbl[lrlr][nn][r1][d1][r2][d2]
      j += 1
      c, lrlr, nn, r1, d1, r2, d2 = costrank[j]
    end
    tbl[lrlr][nn][r1][d1][r2][d2] = i
    ave += hindo[i][1] - (hindo[hindorank[j]||hindorank[-1]][1])
  }
  ave /= ha.length
  printf "deviation of not-organized chars = %d\n", ave
  #マイナスなら隙間が空きすぎてる 目標: avehindo以下
  #1190行あたりで調整、だが教育漢字打数制限をやるとそういう意味での「詰め込み」が効かない
  printf "average cost = %f\n", eval_tbl(tbl, hindo)
  print_tbl(tbl)

  print "\n"
  print "key for srand(): ", srand(), "\n"
end

knapsack(c1.h, bushumapn1, c2.h, bushumapn2, h3, h4, hindo, hindorank)

end##MODE##################################