正しい文(クイズ) in Ruby DouKaku?

「この文は0が□個，1が□個，...，9が□個あります」
が正しくなるように□を埋めてください．数値は10進数とします．
一般のn(<=16で可)進数でも解いてみてください．

たとえば2進数なら
「この文は0が11個，1が100個あります」
となります．

それなりに速く終わるやつを。手元で1秒切ります。たぶん正しい気がするんですが自信は無いような。というかたぶんn=7以降は同じパターンで2種類しか解がない、と示せる気がします。

def x(b,a,n,e,z)
  if b==n
    if a==e
      puts (0...b).map{|i|"#{i.to_s(b)}*#{a[i].to_s(b)}"}*','
    end
  else
    1.upto(b<5?5:[n>1?[4-n,0].max+e[n]:99,b+2-z+n].min){|i|a[n]=i
      f=e.dup
      i.to_s(b).scan(/./){f[$&.to_i(b)]+=1}
      next if (0..n).any?{|j|f[j]>a[j]}
      x(b,a,n+1,f,z+i)}
  end
end
2.upto(16){|b|p b
  x(b,[0]*b,0,[1]*b,0)}

shinhさんのロジックを参考に、個数の初期値[x0,x1,...,x(n-1)]を全て1とし
Σx <= n + Σlength(xのn進表記).....(1)
が成り立つ範囲で個数を1ずつアップ。
  例:[1,1,2]の次に、[1,2,3],[1,2,2]をチェック。
[2,1,2]は式(1)では[1,2,2]と同じ結果になるのでチェック不要とし、計算量を削減。
変形の前後で個数のソート結果が同じになれば解としました。
  例:[1,2,5] -> [1,5,2] の場合、ソート結果は両方とも[1,2,5]で同じのため、[1,5,2]は解。
shinhさんのコードの2倍程度の時間がかかります。
また、変形過程を確認したかったのでdot言語データ作成用にmakeDotを作成しました。

def divComb(n)     #--- in:number , out:hash
  h = {}
  req = [[1]*n]
  while req != []
    w1 = req.shift
    next if h[w1]  #--- already searched
    s = w1.inject(0) {|r,i|r += i}
    c, l = [1]*n, n
    w1.map {|i|i.to_s(n).scan(/./) {c[$&.to_i]+=1; l += 1}}
    h[w1] = (c.sort != w1 ? c.sort : c)
    if s<=l        #--- add other search-req.
      (0...n).each {|i|w = w1.dup; w[i] += 1; req << w.sort}
    end
  end
  h
end

def callDivComb
  n = 2.upto(16){|i|
    divComb(i).each {|c,x|
      p [i,x] if c == x .sort
    }
    puts
  }
end

def makeDot(n)  #--- make dot data for graphviz
  puts "digraph sample#{n} {"
  divComb(n).each {|c,x|
    print c,"->",x,";\n"
  }
  puts "}"
end

callDivComb

#makeDot(3)

DouKaku?

正しい文(クイズ)

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq