四則ソルバ書いてみました

再帰的に四則を解くアルゴリズム。遅い。計算量とかよく知らない。

def copy(a,m,n)
	b = []
	for i in 0..(a.length()-1)
		if i != m && i != n
			b[i] = a[i]
		else
			b[i] = nil
		end
	end
	return b.compact
end

def shisoku_sub(a,n,siki)
	num = a.length()
	if a.length() == 1 then
		if a[0] == n then
			puts siki
			@ans << siki
		end
	else
		for i in 0..(num-1)
			for j in 0..(num-1)
				unless i == j
					if i > j then
						shisoku_sub(copy(a,i,j).push(a[i]+a[j]),n,copy(siki,i,j).push("("+siki[i]+"+"+siki[j]+")"))
						shisoku_sub(copy(a,i,j).push(a[i]*a[j]),n,copy(siki,i,j).push("("+siki[i]+"×"+siki[j]+")"))
					end
					shisoku_sub(copy(a,i,j).push(a[i]-a[j]),n,copy(siki,i,j).push("("+siki[i]+"-"+siki[j]+")"))
					if a[j] != 0 then
						shisoku_sub(copy(a,i,j).push(Rational(a[i],a[j])),n,copy(siki,i,j).push("("+siki[i]+"÷"+siki[j]+")"))
					end
				end
			end
		end
	end
end

def shisoku(a,n)
	@ans = []
	siki = a.map do |i|
		i.to_s
	end
	shisoku_sub(a,n,siki)
	puts "complete!!"
	puts @ans.uniq
end

shisoku([3,3,8,8],24) #=> (8÷(3-(8÷3)))

累乗対応は桁が大きくなりすぎて失敗。対数は丸め誤差がこわい。
メモ化なる概念を知ったので今度試してみようと思う。

どうでもいいけど四則ソルバで検索して出てくる記事書いてるのだいたい灘校生で面白い。