# The state (`S`) is a square grid, modeled as a one-dimensional array of Tile.
# read from left to right then top to bottom.
#
# An action (`A`) is the relative position of the tile to swap with the hole.
# Therefore, `-1` for left, `1` for right, `-width` for up and `width` for down.
class PuzzleProblem
	super SearchProblem[ArrayCmp[Tile], Int]

	# The initial grid. use letters for tiles, and . for the hole.
	var initial_grid: String

	# The width of the grid.
	# Eg. 3 for a 8-puzzle grid
	var width: Int is noinit

	# Construct a state form `initial_grid`
	redef fun initial_state do
		var g = initial_grid
		var len = g.length
		var width = len.sqrt.to_i
		self.width = width
		if width * width != len then
			print "Error: {g} has {len} tiles. A square number, like {width*width} is needed"
			exit 1
		end
		var res = new ArrayCmp[Tile]
		for i in [0..g.length[ do
			var c = g.chars[i]
			if c == ' ' or c == '.' then
				var hole = new Tile('.', -1)
				self.hole = hole
				res.add hole
			else if c >= '1' and c <= '9' then
				var t = new Tile(c, '1'.distance(c))
				res.add t
			else if c >= 'a' and c <= 'z' then
				var t = new Tile(c, 'a'.distance(c))
				res.add t
			else if c >= 'A' and c <= 'Z' then
				var t = new Tile(c, 'A'.distance(c))
				res.add t
			else
				print "Error: illegal tile {c} in {g}"
				exit 1
			end
		end
		return res
	end

	# Get the four available movements, or 3 on a edge, or 2 in a corner.
	redef fun actions(state)
	do
		var h = get_hole(state)
		var x = h % width
		var y = h / width
		var res = new Array[Int]
		if x >= 1 then res.add(-1)
		if x < width-1 then res.add(1)
		if y >= 1 then res.add(-width)
		if y < width-1 then res.add(width)
		return res
	end

	# Return the state where the tile at hole+action has moved
	redef fun apply_action(state, action)
	do
		# Copy the state
		var res = new ArrayCmp[Tile].with_capacity(state.length)
		res.add_all(state)

		# Get the hole and the tile next to it
		var h = get_hole(res)
		var t = h + action

		# Move (by swapping the tile and the hole)
		res[h] = res[t]
		res[t] = hole

		return res
	end

	# The special empty tile for fast retrieval.
	var hole: Tile is noinit

	# What is the position of the hole?
	fun get_hole(state: Array[Tile]): Int
	do
		return state.index_of(hole)
	end

	# Each tile is at its correct position
	redef fun is_goal(state)
	do
		for i in [0..state.length[ do
			var t = state[i]
			if t != hole and t.goal_idx != i then return false
		end
		return true
	end

	# The sum of the Manhattan distances of each tile to its goal
	# Not the best heuristic but the simplest to implement among the good ones.
	redef fun heuristic(state)
	do
		var p = 0
		var i = -1
		for t in state do
			i += 1

			# The hole does not count
			if t == hole then continue

			var dx = (i % width - t.goal_idx % width).abs
			var dy = (i / width - t.goal_idx / width).abs

			# Add Manhattan distance
			p += dx + dy
		end
		return p.to_f
	end

	# Print the grid
	fun print_state(state: Array[Tile])
	do
		for i in [0..state.length[ do
			var t = state[i]
			if t == hole then
				printn "."
			else
				printn t.symbol
			end
			if (i+1) % width == 0 then print ""
		end
	end

	# Print the plan with words.
	fun print_plan(plan: Sequence[Int])
	do
		var s = new Array[String]
		for i in plan do
			if i == -1 then
				s.add "right(>)"
			else if i == 1 then
				s.add "left(<)"
			else if i == -width then
				s.add "down(v)"
			else if i == width then
				s.add "up(^)"
			else
				abort
			end
		end
		print "Solution in {plan.length} moves: {s.join(" ")}"
	end

	redef fun make_memory do
		var res = super
		res.add new RBTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
		res.add new BinTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
		return res
	end
end