螺旋状に格子点を順に列挙する Enumerator クラス

spiral.rb

########## 
### 螺旋状に格子点を順に列挙する Enumerator クラス
#
#  -max_levels <= x <= +max_levels
#  -max_levels <= y <= +max_levels
#  の範囲の格子点 (x, y) を列挙する
# 
#  ただし，中心 (0, 0) から 
#  -> ( 1, 0) -> ( 1,  1) -> ( 0,  1) -> (-1,  1)
#  -> (-1, 0) -> (-1, -1) -> ( 0, -1) -> ( 1, -1)
#  のように「螺旋状に」列挙する
# 
class  Spirals
	include Enumerable

	def initialize max_levels=5
		@max_levels = max_levels
	end

	def each
		lattice_point = { :x=>0, :y=>0 }

		(0..@max_levels).each do |level|
			# 右
			yield(lattice_point)

			((level*2)-1).times do
				lattice_point[:y] += 1
				yield(lattice_point)
			end

			# 上
			(level*2).times do
				lattice_point[:x] -= 1
				yield(lattice_point)
			end

			# 左
			(level*2).times do
				lattice_point[:y] -= 1
				yield(lattice_point)
			end

			# 下
			(level*2).times do
				lattice_point[:x] += 1
				yield(lattice_point)
			end

			lattice_point[:x] += 1

		end

	end

end





########################################################################
########################################################################
########################################################################
if($0==__FILE__) then
 	#テストコード

	require 'prime'

	class QuadraticForm
		def initialize a,b,c
			@a = a
			@b = b
			@c = c
		end

		def apply x,y
			@a*x*x + @b*x*y + @c*y*y
		end
	end


	###### <CASE 0>
	# [-100 <= x <= 100], [-100 <= y <= 100] の範囲内にある格子点を螺旋状に列挙する
	def testCase0
		puts "### test case 0"

		spirals = Spirals.new 1
		spirals.each_with_index do |lattice_point, index|

			print "#{index}: "
			p lattice_point
			
		end

		puts ""
		puts ""
		puts ""
	end


	###### <CASE 1>
	def testCase1
		puts "### test case 1"

		qf = QuadraticForm.new(1,1,6)

		forms = {}


		# [-100 <= x <= 100], [-100 <= y <= 100] の範囲内にある格子点を螺旋状に列挙する
		spirals = Spirals.new 50
		spirals.each_with_index do |lattice_point, index|

			x = lattice_point[:x]
			y = lattice_point[:y]

			p = qf.apply(x,y)

			# 二次形式 p が '素数' のときだけ拾う
			if x.gcd(y) == 1 && p > 0 && Prime.prime?(p) then
				xx = (x >= 0) ? "#{x}" : "(#{x})"  
				yy = (y >= 0) ? "#{y}" : "(#{y})"  

				tuple = ["#{xx}*#{xx} + #{xx}*#{yy} + 6*#{yy}*#{yy}", x, y]

				if forms.has_key?(p) then
					forms[p].push tuple
				else
					forms.store(p, [tuple])
				end
			end

		end



		sorted_forms = forms.sort
		sorted_forms.each do |form|
			prime  = form[0]
			tuples = form[1]

			min_tuple = tuples.min_by {|tuple| tuple[1]*tuple[1] + tuple[2]*tuple[2] }   # ノルムが小さい二次形式を代表として１つとる

			puts "#{prime} = #{min_tuple[0]}"

		end

	end


	# テストケースの実行
	testCase0
	testCase1

end ## if($0==__FILE__)