辞書順に数を並べる

@Nabetani さんの問題
http://nabetani.sakura.ne.jp/hena/orde22numord/
を解いてみた。
m 以上 n 以下の自然数を b 進表記して辞書順に並べたとき、x 番目の数を求めよという問題。
他の方の実装が
http://qiita.com/Nabetani/items/99e38a39165e1905b415
にある。

だらだらやってたら3時間くらいかかった。
言語は Ruby。

# u を kn 桁(= n の桁数)の数として、順序が u の順序以下のものの数
def f(u, m, n, b, km, kn)
  v = b * u - b ** kn
  [u / b ** (kn - km) - m + 1, 0].max - [u - n, 0].max +
  (km...kn).inject(0) {|s| s + (v /= b) + 1}
end

def solve(m, n, b, x)
  km, kn = [m, n].map {|j| j.to_s(b).size}
  u = (b ** (kn - 1)...b ** kn).bsearch {|u| f(u, m, n, b, km, kn) >= x}
  # この時点で、u は目的の数の末尾に0個以上の '0' が付いている
  u / b ** (f(u, m, n, b, km, kn) - x + (u > n ? 1 : 0)) # 末尾の 0 を削る
end

DATA.each do |s|
  j, t, e = s.split
  puts "%2s %-30s %d" % [j, t, ans = solve(*t.split(',').map(&:to_i))]
  fail unless ans == e.to_i
end

__END__
0   2,15,3,8                        14
1   6,8,8,1                         8
2   6,6,5,1                         6
3   4,11,5,2                        6
4   9,17,8,2                        10
5   73,82,18,5                      77
6   70,149,2,48                     95
7   82,119,15,26                    107
8   40,127,26,47                    86
9   851,950,31,89                   939
10  660,807,34,143                  802
11  962,1227,34,186                 1075
12  544,1258,25,245                 869
13  1208,7380,2,803                 4630
14  2,100000000,10,1                10
15  1642,6626,3,4354                2029
16  8623,15873,2,4188               12810
17  7013,16409,17,3919              10931
18  7222,13243,19,3623              10844
19  4421,87412,5,62080              60697
20  51812,61593,22,2957             54768
21  44260,67742,17,15128            59387
22  90929,696974,36,84356           175284
23  1,100000000,2,50000000          92108858
24  101262,924931,7,341846          358105
25  211114,675661,33,312769         523882
26  1,100000000,36,50000000         11855060
27  1,100000000,10,100000000        99999999
28  826566,1444644,36,186226        1012791
29  6687091,6985458,4,251580        6938670
30  4219082,6179401,12,538113       4757194
31  7781931,8634872,23,217457       7999387
32  818218,64845924,12,57752258     30039084
33  4987258,11760092,32,6741567     11728824
34  7075964,28431054,22,11548591    18624554
35  26065964,66252692,18,29196596   63208819
36  66097362,104618756,16,32740764  98838125