CodeIQ：ナルシストなナルシシスト数

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ナルシストなナルシシスト数」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

数学用語ランキングなどで話題になることが多い「ナルシシスト数」。
Wikipedia(ナルシシスト数)によると、

ナルシシスト数（ナルシシストすう、英: narcissistic number）とは、n桁の自然数であって、その各桁の数のn乗の和が、元の自然数に等しくなるような数をいう。例えば、1³ + 5³ + 3³ = 153 であるから、153 はナルシシスト数である。
です。
そして、こうも書かれています。

十進法に限らず、他の基数においても同様にナルシシスト数を定義できる。
では、標準入力から n が与えられたとき、n 進数で2桁以上のナルシシスト数を小さい方から n 個求め、標準出力に n 進数で順に出力してください。
( n 進数で2桁以上のナルシシスト数が n 個以下の場合は、すべて出力してください。)
なお、n は10以下の整数とします。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def toNarcissisticNumber(s, n)
	ret = 0
	s.chars{|a| ret += a.to_i**n}
	return ret
end

def solve(n)
	v = n
	ret = []

	while (s = v.to_s(n)) && (m = s.length) <= n
		if v == toNarcissisticNumber(s, m) then ret << s end
		if ret.length == n then break
		else v += 1
		end
	end

	return ret
end


#main
while line = gets
	line.strip!
	if line.empty? then next end

	n = line.to_i
end

for ret in solve(n)
	puts ret
end

解説

ナルシスト数について知らなかったため、10進数以外の場合についてて計算してみる必要がありましたが、基本的に素直にプログラムすれば解けます。

10進数以外の場合

問題の引用では省略していますが、例として10進数と3進数の場合の結果が例示されています。3進数の場合の答えは「12、22、122」となっていたので手で計算してどうなるのかを検証してみます。
3進数で2桁の数は10、11、12、20、21、22です。
10 ≠ 1²（10進数） + 0²（10進数） = 1（10進数） = 1（3進数）
11 ≠ 1²（10進数） + 1²（10進数） = 2（10進数） = 2（3進数）
12 = 1²（10進数） + 2²（10進数） = 5（10進数） = 12（3進数）
20 ≠ 2²（10進数） + 0²（10進数） = 4（10進数） = 11（3進数）
21 ≠ 2²（10進数） + 1²（10進数） = 5（10進数） = 12（3進数）
22 = 2²（10進数） + 2²（10進数） = 8（10進数） = 22（3進数）

つまり、元の数（3進数）を10進数として扱ってナルシスト数を計算し、結果を元の進数表現になおしたものが元の数と同じになれば良いということがわかります。

toNarcissisticNumber(s, n)

この関数が上記の計算を行う関数です。sは元の数のn進数表現、nは入力値です。
sを1文字ずつ取り出して数値に変換してnで乗じた値を足し合わせるだけです。

solve()

ごく単純に2桁以上の値を小さい方から総当たりしてn個になるまで探索しています。
この問題で最悪の計算量を要求されるのはn=10の時で10桁になりますが、問題で10桁の場合は例示されており一番大きな数が93084でした。この程度なら総当たりして問題ないので、9進数以下も大丈夫だろうということで総当たりとしました。

まず、n進数で2桁の最小の数はnです。n=3なら3（10進数）は10（3進数）、n=5なら5（10進数）は10（5進数）です。なので最初の数はnから始めれば良いことになります。コードではnを桁数のチェックにも使うのでvにコピーして使用しています。
13行目のs=v.to_s(n)でvのn進数の文字列を作り、m=s.lengthでその数の桁数を求めています。これらはwhileの終了条件になっていますが、s=v.to_s(n)は常にtrueなので(m=s.length) <= nだけが終了条件です。これはn桁を超えたら終わりを意味します。

14行目でナルシスト数かどうかをチェックし、ナルシスト数なら結果に追加します。
15〜16行目は結果の数がn個になったら終了、そうでなければ次の数にすると言う処理です。

雑感

仕様は満たしていますが模範解答かというとそうではない気がします。10けたの場合で0.2秒と少しで終わりますが、5桁までしか計算していません。本来は10桁まで計算しても1秒以下で終わるべきなのではと思います。