32nd Diary

■ キミならどう書く 2.0 - ROUND 2 - 事件編

ボクも書いてみました．

はじめに考えたアプローチは逆にたどっていく方法です． ある値について，fにどんな値を入れたら求まるのかを考えます．

• 1 <- f(2)
• 2 <- f(4)
• 4 <- f(8), f(1)
• 8, 1 <- f(16), f(2)
• 16, 2 <- f(32), f(5), f(4)
• 32, 5, 4 <- f(64), f(10), f(8), f(1)

これで，ステップ数がわかればどんな数が出現するかの可能性をすべてあげることができます． たとえば，5ステップの範囲には1, 2, 4, 5, 8, 16という数があります．

んで，左側に出てきた数を1..100のセットから消していき， セットが空になったときのステップ数が答えじゃねーですか？ とか考えて以下のコードを書きました．

def collatz(step,remain, nums)
 	next_nums = []
	if remain.empty? then
		puts "step = #{step}"
		return self
	end

	for n in nums do
		next_nums << n * 2
		if n != 1 and (n-1).modulo(3) == 0  then
			next_nums << (n-1) / 3
		end
	end
	collatz(step + 1, remain - next_nums, next_nums)
end
collatz(1, (2..100).to_a, [1])

実行．．．

step = 33

は？33？

．．．

よくよく考えると，1から100まででは通らないパスの結果も使ってしまっていることに気づきました．

何やってんだー．ダメじゃん．．．orz

追記．ってか，これだと答えであるところの k の値が求まらんではないか． 根本的にダメダメだな．．．今日のボクはどうかしていた．ということにしよう．

■ キミならどう書く 2.0 - ROUND 2 - 解決編

考えを改め，書き直しました．

おとなしく順番に求めることにしました． ただし，なるべく以前の結果を使うことにします． たとえば，f(3)のステップ数を求めることを考えます．

• f(1) -> 1
• f(2) -> f(1) -> 1
• f(3) -> f(10) -> f(5) -> f(16) -> f(8) ->　f(4) -> f(2) -> f(1) -> 1

強調した部分は以前の計算結果から明らかなので， f(3)のステップ数を計算するにはf(2)のステップ数の結果を利用します．

つまり以下のような手順となりましょう．

1. f(3)のステップ数はf(f(3)) = f(10)のステップ数に1を加えたもの
2. f(10)のステップ数はf(f(10)) = f(5)のステップ数に1を加えたもの
3. ...
4. f(4)のステップ数はf(f(4)) = f(2)のステップ数に1を加えたもの
5. f(2)のステップ数は計算済み

うーん，いかにも再帰な感じです． これを順に1〜100まで繰り返して，ステップ数を全部求めるコードを書きました． さらに，100から調べた方がヒット率がいいな，と思い，逆順に調べるコードに修正．

def f(n)
	return 1 if n == 1
	return n/2 if n & 1 == 0
	return 3 * n + 1 if n & 1 == 1
end

def collatz(step_table, n)
	if n == 1 then
		step = 1
	else
		next_n = f(n)
		next_step = step_table[next_n]

		if next_step == nil then
			step = collatz(step_table, next_n) + 1
		else
			step = next_step + 1
		end
	end
	return step_table[n] = step
end

step_table = Hash.new
100.downto 1 do |i|
	collatz(step_table, i)
end

step = step_table.values.max
k = step_table.index(step)
puts "k = #{k}, step = #{step}"

実行．．．

k = 97, step = 119

おお，たぶん正解のよう．

割と無難なコードに落ち着いたので，後で同じようなコードを書いている 人がいないか探してみようと思う．

追記．我ながらしょっぱいコードだなぁ．．． 他の人のコードみて楽しんでます．．．

■ 零崎双識の人間試験 (講談社ノベルス)(西尾 維新/take)

数日前に読んだ．

いままでのストーリーとは関係ない展開なので， しがらみなく，筆者が書きたいことを書いているのがわかる．

バトルする小説を書くのが楽しいZEEEE!!というテンションがひしひしと伝わってきます．

別にストーリー的に特に思うところはなし．（ぶ