7の個数

count7.rb

#7を置くパターンを洗い出す
#例)
#3桁の数字の場合、7が含まれるパターンは
#[0, 0, 7]
#[0, 7, 0]
#[0, 7, 7]
#[7, 0, 0]
#[7, 0, 7]
#[7, 7, 0]
#[7, 7, 7]
#なので、これらを作成してブロックに渡す
def pattern_of_7(pos, i, &b)
  if i >= pos.size
    b.call pos if pos.include? 7
  else
    [0, 7].each do |j|
      t = pos[i]
      pos[i] = j
      pattern_of_7(pos, i + 1, &b)
      pos[i] = t
    end
  end
end


#最大nまで置けるとしたときに実際における数値のリスト
#例)
# 0 ... 0
# 1 ... 0, 1
#   略
# 6 ... 0, 1, 2, 3, 4, 5, 6
# 7 ... 0, 1, 2, 3, 4, 5, 6
# 8 ... 0, 1, 2, 3, 4, 5, 6, 8
# 9 ... 0, 1, 2, 3, 4, 5, 6, 8, 9
$candidate_num = 10.times.map{|e| tmp = (0 .. e).to_a; tmp.delete(7); tmp}

#indexまでの位置に関してary1,ary2を先頭から辞書順での大小を返す
def compare_with_index(ary1, ary2, index)
  ret = 0
  0.upto(index) do |i|
    ret = ary1[i] <=> ary2[i]
    return ret if ret != 0
  end
  0
end

def count_variation_sub(pat, max_pattern, index)
  if index >= pat.size
    #すべての桁を埋められたら有効な数字が一つできたのでカウントする
    #p [:ok, pat, index]
    1
  else
    if pat[index] == 7
      if compare_with_index(pat, max_pattern, index) > 0
        #固定で入っている7の桁までですでに対象数字より大きくなっている場合はカウントしない
        #p [:ng, pat, index]
        0
      else
        count_variation_sub(pat, max_pattern, index + 1)
      end
    else
      if index != 0 &&  (compare_with_index(pat, max_pattern, index - 1) < 0)
        #今までに調べた位置(index-1)までの数値ですでに対象数値よりも小さければ、
        #残りはプレースホルダの位置に0,1,2,3,4,5,6,8,9の九つの数字を入れる組み合わせなので
        # 9 ^ (プレースホルダの個数乗)
        #でパターン数が一気に計算できる
        return 9 ** pat[index .. -1].count(0)
      end
      
      #最左の桁か、今までに調べた位置(index-1)までの桁数が対象数値と同じになっているのであれば、
      #今から調べる桁(index)は対象数値のindex位置の数値まで(から7を除いた数字)しか選択できない。
      range = $candidate_num[max_pattern[index]]

      count = 0
      range.each do |i|
        t = pat[index]
        pat[index] = i
        #今の位置(index)以降のプレースホルダに置ける数字のパターンで作れる種類の合計が求める数
        count += count_variation_sub(pat, max_pattern, index + 1)
        pat[index] = t
      end
      count
    end
  end
end

#プレースホルダのパターンpatから、対象数値max_patternまでの数値で作れる数字の個数を返す
#例)
# pat = [7, 0]
# max_pattern = [8, 0]  80以下の数字
#の場合count_variation(pat, max_pattern)は
# 70, 71, 72, 73, 74, 75, 76, 78, 79
#の9個の数値が作れるので、
# 9
#を返す(77はpat = [7, 7]のほうで計算される)
def count_variation(pat, max_pattern)
  count_variation_sub(pat, max_pattern, 0)
end

#1～nまでの数字に存在する7の数を返す
def count7(n)
  max_pattern = n.to_s.chars.map(&:to_i)
  
  #対象数字の桁数個の要素を確保する
  pos = Array.new(n.to_s.size, 0)
  
  count = 0
  
  #nの桁数で7が置けるパターンを洗い出す
  pattern_of_7(pos, 0) do |pat|
    #p [:start_pat, pat]
    #p [:pat_count, count_variation(pat, max_pattern)]
    
    #7の位置のパターン毎に、そのパターンを満たす数字の個数を求めて、それにパターン中の7の数をかければ
    #そのパターンで発生する7の個数が求まる。
    count += count_variation(pat, max_pattern) * pat.count(7)
  end
  count
end

#検算用の単純に1～対象数字までに存在する7の数を数えるメソッド
def check(n)
  1.upto(n).inject(0) do |acc, i|
    if i.to_s =~ /7/
      #p i
    end
    acc + i.to_s.chars.count('7')
  end
end

target_list = [
  99,
  77777,
  23678947,
  732465890,
  1912478368,
]
  
def solve(n)
  s = Time.now
  ret = count7(n)
  t = Time.now - s
  puts "n =%10d %10d %f(sec)" % [n, ret, t]
end

target_list.each do |n|
  solve(n)
end