CodeIQ：道順は違っても結果は同じ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「道順は違っても結果は同じ」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

正方形が縦横に敷き詰められたマス目を考えます。
このマス目を上下左右に一筆書きの要領で移動するとき、その経路を記録します。
例えば、以下の左図のように移動するとき、「ULDL」と記録することにします。
（上への移動は「U」、下への移動は「D」、右への移動は「R」、左への移動は「L」）
ところが、開始位置を変えて、右図のように移動すると「RRUL」と記録されます。

訪問したマスの組み合わせを考えると、上記の二つは同じ内容を意味します。
なお、一度通過したマスは通れないものとします。

標準入力からある移動経路が与えられたとき、同じ組み合わせになる道順がいくつあるかを求め、その個数を標準出力に出力してください。
（標準入力から与えられる移動経路も含めてカウントします。）

上記の例の場合、「ULDL」と「RURD」「RDLL」「RRUL」の4通りですので、以下のように出力します。

【入出力サンプル1】
標準入力

ULDL
標準出力

4
同様に、「ULD」が与えられた場合は、「DRU」「RDL」「URD」「RUL」「LUR」「LDR」「DLU」を加えた8通りですので、以下のように出力します。

【入出力サンプル2】
標準入力

ULD
標準出力

8
なお、入力文字列は最長で18文字とし、不正な文字列は入力されないものとします。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Count = 0
$Results = []

# 入力値からマップを作る
# 開始地点を[0,0]として移動した場所の相対座標を配列にする。
# "ULDL"なら[[0,0], [0,-1], [-1,-1], [-1,0], [-2,0]]となる
def toMap(line)
	route = [[0,0]]
	ptn = {
		"U"=>[0,-1],
		"D"=>[0,1],
		"L"=>[-1,0],
		"R"=>[1,0],
	}

	line.chars{|c|
		route << [route.last[0] + ptn[c][0], route.last[1] + ptn[c][1]]
	}

	return route
end

# 再帰的に経路が通過可能かを調べる
# @param map 残りの通過可能地点の座標リスト
# @param path 通過済みの座標リスト
def walk(map, path)
	# 進行可能な方向リスト
	dir = [[0,-1], [0,1], [-1,0], [1,0]]

	# 各方向に進めるかを試す
	for d in dir
		npath = path.dup
		nmap = map.dup

		# 現在の位置（pathの最後の座標）から移動した方向に座標があるかをチェックする
		# 同時に残りの座標から削除する
		pos = nmap.delete([npath.last[0] + d[0], npath.last[1] + d[1]])

		# 座標がなかったらその方向には進めないので無視する
		if pos != nil then
			npath << pos

			# マップが空（=全ての場所を回った）場合、結果をカウントする
			# そうでない場合、続きを探索する
			if nmap.empty? then
				$Results << npath
				$Count += 1
			else
				walk(nmap, npath)
			end
		end
	end
end

# 問題を解く
# 全ての座標から開始して、全座標を通るルートがあるかを探索する
def solve(map)
	for i in 0...map.size
		nmap = map.dup
		st = nmap.delete_at(i)
		path = [st]
		walk(nmap, path)
	end
end

#DEBUG
def printResults
	for ret in $Results
		printRoute(ret)
	end
end

#DEBUG
def printRoute(path)
	route = ""
	for i in 1...path.size
		mv = [path[i][0] - path[i-1][0], path[i][1] - path[i-1][1]]
		if mv == [0,-1] then route += "U"
		elsif mv == [0,1] then route += "D"
		elsif mv == [-1,0] then route += "L"
		elsif mv == [1,0] then route += "R"
		else
			route = "BAD ROUTE!!"
			break
		end
	end
	puts route + " : " + path.to_s
end

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

	map = toMap(line)
	solve(map)
	p $Count
end

解説

★★の問題ですが難しいと思いました。
プログラムが難しいと言うより、どう考えたらいいのかがわからず、結構悩みました。

考え方

入力値を座標にします。これをマップと呼びます。
その各座標から全ての座標を1回ずつ通る経路を探索します。

探索は次のように行います。
マップから任意の座標を取り出します。
マップからは取り出した座標を削除します。
取り出した座標から上下左右に移動した場合の位置を計算し、マップに残った座標に移動後の座標が存在するかをチェックします。存在しない場合は範囲外かすでに通過した座標なので無視します。存在する場合、その座標を取り出して上下左右に移動しチェック、を繰り返します。
マップに座標がなくなったら全てのマスを通ったことになるのでカウントします。

toMap()

この関数で入力値をマップにします。
最初(0,0)にいるとします（10行目）。
入力値を1文字ずつ取り出して、Uなら(0,-1)、Dなら(0,+1)、Lなら(-1,0)、Rなら(+1,0)だけ座標を移動して記録します。
最終的に座標のリストができるのでそれを返します。

solve()

マップに基づいて問題を解きます。
この関数は全ての座標をスタート地点として探索を開始するだけで、実際の探索を行うのはwolk()です。

walk()

探索を行う関数です。
引数mapは残っている座標のリスト、pathは通過した座標のリストです。

最初mapはスタート地点を除いた座標のリスト、pathにはスタート地点の座標が渡されてきます。
33〜54行目のループで上下左右に移動した場合の処理を行います。
再帰的にwalkを呼び出すのでpathとmapはコピーします（34〜35行目）。
現在の座標（pathの最後の要素）から移動した座標を計算します。そしてその座標がマップ（実際にはコピーしたnmap）にあるかをチェックし、あれば削除します。rubyの場合、Array#delete()が引数に指定した値を持つ要素を削除し、削除できた場合はその値を、削除できなかった場合（なかった場合）はnilを返すのでArray#delete()でこれらの処理を一括して行えます。
座標がマップ(実際はnmap)にあった場合（42〜53行目）、経路の最後に追加し（43行目）、マップが空になったら結果をカウントアップします（47〜49行目）。マップが空でなければ残りの座標と経路情報をwalk()に渡して再帰的に処理します（50〜51行目）。
$Resultsに全ての座標を回った場合の経路情報を記録していますがデバッグのためで答えを求めるだけなら不要です。

雑感

最初、この問題を読んだ時の感想は「全然わからない（正確には制限時間内に終わりそうなロジックが思いつかない）」でした。
時間的にはどうかわからないけれど、解くことはできそうな方法として入力値をマップ（実際のコードのような座標のリストではなく、左下を(0,0)として入力値の範囲を含む2次元配列で表現したもの）を作って、マップ上の任意の2点（スタートとゴール）の経路探索をやるしかないか、うまく行くかはわからないけどどっちにしろマップは必要だろう、と思ってtoMap()を書き始めたら解答のロジックを思いついたと云う具合でした。