A* solver for Fish Are Not Naturally Monogamous

fishgame.py

"""fishgame

Solver for Fish Are Not Naturally Monogamous
http://www.kongregate.com/games/chickenprop/fish-are-not-naturally-monogamous"""

def flip_sex(fish):
	return {"M":"F", "F":"M"}[fish]

def trivial_heuristic(fg):
	return 0
def unmatched_heuristic(fg):
	bad_matches = [ fg[fish] for fish in fg.fish_locs if fg.paired(fish) != 1 ]
	return max( bad_matches.count("M"), bad_matches.count("F") )

class FishGame:
	def __init__(self, from_state):
		if isinstance(from_state, FishGame):
			self.board = [ row[:] for row in from_state.board ]
			self.sex_changes = from_state.sex_changes
			self.fish_locs = from_state.fish_locs[:]
		else:
			text_repr = str(from_state).rstrip()
			lines = text_repr.split("\n")
			try:
				self.sex_changes = int(lines[-1])
				lines = lines[:-1]
			except:
				self.sex_changes = 0
			nb_rows = len(lines)
			nb_cols = max(map(len, lines))
			self.board = [ [" "]*nb_cols for _ in range(nb_rows) ]
			self.fish_locs = []
			for row in range(nb_rows):
				cur_line = lines[row]
				for col in range(nb_cols):
					if len(cur_line) > col:
						cur_c = cur_line[col]
						if cur_c in "#MF":
							self.board[row][col] = cur_c
							if cur_c in "MF":
								self.fish_locs.append((row,col))
	def __repr__(self):
		return "\n".join("".join(row) for row in self.board)+"\n%d\n"%(self.sex_changes,)
	def __getitem__(self, cell):
		(row,col) = cell
		return self.board[row][col]
	def __setitem__(self, cell, value):
		(row,col) = cell
		self.board[row][col] = value
	def neighbours(self, cell):
		(row,col) = cell
		neighbours = [ (row-1,col), (row,col-1), (row,col+1), (row+1,col) ]
		neighbours = [ (row,col) for (row,col) in neighbours if (0 <= row < len(self.board)) and (0 <= col < len(self.board[0])) ]
		neighbours = [ cell for cell in neighbours if self[cell] != "#" ]
		return neighbours
	def paired(self, fish):
		assert(fish in self.fish_locs)
		return len([ other_fish for other_fish in self.neighbours(fish) if self[other_fish] == flip_sex(self[fish]) ])
	@property
	def sex_imbalance(self):
		all_fish = [ self[fish] for fish in self.fish_locs ]
		return abs(all_fish.count("M") - all_fish.count("F"))/2
	@property
	def is_solved(self):
		return all(self.paired(fish)==1 for fish in self.fish_locs)
	def get_moves(self):
		if self.sex_imbalance > self.sex_changes:
			return []
		else:
			moves = []
			for fish in self.fish_locs:
				if self.sex_changes > 0:
					new_state = FishGame(self)
					new_state[fish] = flip_sex(self[fish])
					new_state.sex_changes -= 1
					moves.append(new_state)
				if self.paired(fish) == 0:
					for new_cell in self.neighbours(fish):
						if self[new_cell] == " ":
							new_state = FishGame(self)
							new_state[fish], new_state[new_cell] = new_state[new_cell], new_state[fish]
							new_state.fish_locs.remove(fish)
							new_state.fish_locs.append(new_cell)
							moves.append(new_state)
			return moves
	def solve(self, heuristic = unmatched_heuristic): #A*
		def insert_where(target_cost):
			least, most = 0, len(open_list)
			while least < most:
				insert_at = int((least+most)/2)
				next_cost = open_list[insert_at]["total_cost"]
				if next_cost < target_cost:
					least = insert_at + 1
				else:
					most = insert_at
			return least
		def add_move(new_state, old_move):
			if repr(new_state) not in closed_list:
				cost_to = old_move["cost_to"] + 1
				cost_from = heuristic(new_state)
				new_move = {"path": old_move["path"]+[new_state],
							"cost_to": cost_to,
							"cost_from": cost_from,
							"total_cost": cost_to + cost_from}
				open_list.insert(insert_where(new_move["total_cost"]), new_move)
		
		open_list = []
		closed_list = set()
		add_move(self, {"path":[], "cost_to": -1})
		while open_list:
			cur_move = open_list.pop(0)
			cur_state = cur_move["path"][-1]
			if cur_state.is_solved:
				return cur_move["path"]
			repr_state = repr(cur_state)
			if repr_state not in closed_list: # cause strings are hashable
				closed_list.add(repr_state)
				if len(closed_list)%1000 == 0:
					print(len(closed_list))
				for next_state in cur_state.get_moves():
					add_move(next_state, cur_move)
		
		raise ValueError("FishGame.solve: Unsolvable")

def walkthrough(repr_text):
	for move in FishGame(repr_text).solve():
		print(move)
		input()

LEVEL_0 = """
#####
#  F#
# ###
# #
#M#
###
0
"""

LEVEL_1 = """
 ###
##F#####
#F     #
## # ###
 #M# #
 #M###
 ###
0
"""

LEVEL_2 = """
 ###
 #F#
 # ##
##  #
#MF #
##  #
 # ##
 #M#
 ###
0
"""

LEVEL_3 = """
 ###
 #F#
 # ##
##  #
#FM #
##  #
#MF #
##  #
 # ##
 #M#
 ###
2
"""

LEVEL_4 = """
  ###
### ###
# FMF #
###F###
  # #
  ###
3
"""

LEVEL_5 = """
   ###
 ###M#
##F# ##
#M   M#
## #F##
 #F###
 ###
2
"""

LEVEL_6 = """
  ###
  #F###
### FM#
#FM ###
### FM#
#FM ###
###M#
  ###
2
"""

LEVEL_7 = """
  #####
 ##M#M##
##  #  ##
#M ### M#
## # # ##
#F # # F#
##     ##
 ##F#F##
  #####
0
"""

LEVEL_8 = """
  ###
  #F#
### ###
#FM FM#
### ###
#FM FM#
#FM FM#
### ###
  #M#
  ###
4
"""

LEVELS = (LEVEL_0, LEVEL_1, LEVEL_2, LEVEL_3, LEVEL_4, LEVEL_5, LEVEL_6, LEVEL_7, LEVEL_8)

if __name__ == "__main__":
	try:
		level_num = int(input("Solve level (default: latest) > "))
	except:
		level_num = -1
	walkthrough(LEVELS[level_num])