Luaでハノイの塔

思いつきでプログラマの数学を入手。読んでへーほーふーんと感心することしきり。やっぱあれだな。学校の勉強はまじめにやっとくべきだったなと今頃後悔。高校の授業を受けたのであれば知っていて当然のことがずらずら並んでいて、それがわからなくてへこむ。
とりあえず、サンプルとしてC言語で記載されていたハノイの塔を、NScripterとLuaで実装してみた。

00.txt

*define
game
*start
最初の塔の高さは？
selnum %1,"１","２","３","４","５","６","７","８","９","10","11","12"
inc %1
hanoi %0,%1
高さ%1は最短%0手
click
end

system.lua

local tower = {}
NSExec("luasub hanoi")
function NSCOM_hanoi()
	local res = NSPopIntRef()
	NSPopComma()
	local height = math.floor(NSPopInt())
	if height < 0 then return true end
	tower[1] = {}
	tower[2] = {}
	tower[3] = {}
	for num = height, 1, -1 do
		table.insert(tower[1], num)
	end
	draw_hanoi()
	NSSetIntValue(res, hanoi( height, 1, 3, 2 ))
end

function hanoi( height, from, to, other )
	if height == 0 then return 0 end
	local seq = hanoi( height - 1, from, other, to )
	table.insert( tower[to], table.remove( tower[from] ) )
	draw_hanoi()
	hanoi( height - 1, other, to, from )
	return seq * 2 + 1
end

function draw_hanoi()
	local sp = 100
	for num = 1, 3 do
		for n, width in ipairs(tower[num]) do
			NSSpLoad(sp, ":c;>"..(width*16)..",16,#FF0000")
			NSSpMove(sp, num*160-width*8, 464-n*16, 255)
			sp = sp + 1
		end
	end
	NSUpdate()
	NSSleep(1)
	return true
end

感想

「nの高さを移動させるには、まずn-1の高さを移動させる」と言う原理は言われてみればなるほどと言うしかなく。
ああでも、再帰が使えるって素敵。

プログラマの数学