# Let's play some games!

A new RPG called **_Demon Wars_** just came out! Imagine the surprise when you buy it after work, go home, start you _GameStation X_ and it happens to be too difficult for you. Fortunately, you consider yourself a computer connoisseur, so you want to build an AI that tells you every step you have to make to **defeat the evil Demon Lord** and win the game. For now, let's program a simulator.

This game features procedurally generated stages like this one:


  Health: ♥️ ♥️ ♥️   Atk: 1   Def: 1   Bag: []  
K   E     |    X#        C      E   S#  D  
    E     #######               ###### E E 
##### #####                          ###-##
     M                                 EEE 
                     ###   ###             
                     #       ##E##E##      
     ^               #          C  K#      
               C      #   H   ##E##E##       



As you can see in the upper status bar, your player starts with **three Health Points**, **1 Attack**, **1 Defense** and an empty **Bag**. These are the only stats that you have to care about for the game. As for the map, we can see many different things, so let's explain every tile one by one:
* `^` or `v` or `<` or `>` => **Player** (you). It can face any of four directions.
* `#` => **Wall**. You cannot pass through here.
* `C` => **Coin _[object]_**.
* `M` => **Merchant**. They will go away if you give them **three coins**.
* `K` => **Key _[object]_**. They can open a door, after which they break _(yes, like in horror games)_.
* `-` and `|` => **Doors** _(there are two doors in the map above)_.
* `H` => **Health Potion _[object]_**. It refuels your life to three hearts.
* `S` => **Shield**. It gives **+1 defense** permanently.
* `X` => **Dual Swords**. It gives **+1 attack** permanently.
* `E` => **Enemy**. Has **1 Health Point** and **2 Attack**.
* `D` => **Demon Lord**. Has **10 Health Points** and **3 Attack**. You win the game if you kill him.

Now, _Demon Wars_ is a turn based game with tank controls. Each turn you can either:
* Move forward.
* Change direction.
* Use an item.
* Attack the enemy you have in front of you.


Will you be able to defeat your foe and save us all?

---------------------

# Attack mechanics and enemies

When you use the attack command, you will attack the enemy right in front of you and deal **the same amount of damage as your attack stat**:


 E                         E
>E    === [Attack] ==>    > 
 E                         E



**However**, an enemy can attack you (whatever your orientation is), as long as you are on an adjacent cell to the enemy (vertically or horizontally, not diagonally) and if one of those conditions is fullfilled:

* If you turn your character during the turn.
* If you move away from them (_D&D's opportunity attack_ :D).
* If you use a potion. You will still recover your life points, but then you will be attacked.

The damage formula is `max(0, (Enemy's attack stat) - (Your defense stat))`. Just remember that you attack and use objects **before** the enemies besides you attack. Here is an example where two enemies would attack you:


EEE                        EEE
 >E    === [Attack] ==>     > 
EEE                        EEE


But enemies are more than obstacles, each time you defeat three of them (demon lord not included), you level up! This level increase will give you **+1 attack** permanently.

# Object usage mechanics

There are only three cases where it is acceptable to use objects:
* When you use a key in front of a closed door.


 #                          #
>|    === [Use Key] ==>    > 
 #                          #



* When you use a coin in front of a merchant (repeat three times for them to go away).



>M  === [Use Coin] ==>  >M  === [Use Coin] ==>  >M  === [Use Coin] ==> > 




* When you refuel your life using a potion (you must have suffered some damage).

Any other object usage is considered **invalid**. Also, this is more or less standard, but you have to walk over an object to pick it up automatically.

---------------------

# Your task

Write a function `rpg(field: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]` that takes the initial state of the game map and a list of actions and returns the new state of the map and the player after executing them in order. All these actions must be valid (no using objects in invalid spots, attacking thin air, going out of bounds, etc), so if any of them turns out not to be valid, return `None`. **Dying counts as an invalid state**.

The order of the elements of the output tuple is: (`new map state`, `health`, `attack`, `defense`, `sorted bag`)

The syntax of the actions is as follows:
* `F` to move forward.
* `^`, `>`, `v` and `<`to rotate the player.
* `A` to attack the enemy you have in front of you.
* `C`, `K` and `H` to use a coin, a key and a health potion, respectively.

**Technical notes:** 
* You **can** mutate the input (and probably should), but it is not necessary.
* There will only be one Demon Lord per map, but every other tile may be repeated two or even more times.
* Only the tiles marked as **[object]** will be stored in your bag (i.e. keys, coins and potions).
* Only valid inputs will be given.

----------------

As always, I hope you have fun with this kata :)

Difficulty: MEDIUM
Tags: Game theory

Starter code:
def rpg(field, actions):
	

Solutions:
def rpg(field, actions):
	p = Player(field)
	try:
		for m in actions:
			if m == 'A':
				p.attack()
			elif m in 'HCK':
				p.use(m)
			elif m in '<^>v':
				p.rotate(m)
			p.checkDmgsAndAlive()
			if m == 'F':
				p.move()
	except Exception as e:
		return None
	return p.state()

class Player:
	DIRS = dict(list(zip('<>^v', ((0, -1), (0, 1), (-1, 0), (1, 0)))))

	def __init__(self, field):
		(self.h, self.atk, self.d, self.bag, self.xps) = (3, 1, 1, [], 0)
		self.field = field
		self.pngs = {}
		for (x, r) in enumerate(self.field):
			for (y, c) in enumerate(r):
				if c in self.DIRS:
					(self.x, self.y, self.c) = (x, y, c)
					(self.dx, self.dy) = self.DIRS[c]
				elif c == 'D':
					self.pngs[x, y] = {'h': 10, 'atk': 3}
				elif c == 'E':
					self.pngs[x, y] = {'h': 1, 'atk': 2}
				elif c == 'M':
					self.pngs['M'] = {'coins': 3}

	def state(self):
		return (self.field, self.h, self.atk, self.d, sorted(self.bag))

	def rotate(self, c):
		(self.dx, self.dy) = self.DIRS[c]
		self.c = self.field[self.x][self.y] = c

	def move(self):
		self.field[self.x][self.y] = ' '
		self.x += self.dx
		self.y += self.dy
		c = self.field[self.x][self.y]
		assert c not in '#ED-|M' and self.x >= 0 and (self.y >= 0)
		if c != ' ':
			self.takeThis(c)
		self.field[self.x][self.y] = self.c

	def checkAhead(self, what):
		(x, y) = (self.x + self.dx, self.y + self.dy)
		assert self.field[x][y] in what
		return (x, y)

	def takeThis(self, c):
		if c not in 'SX':
			self.bag.append(c)
		if c == 'S':
			self.d += 1
		elif c == 'X':
			self.atk += 1

	def use(self, c):
		self.bag.remove(c)
		if c == 'C':
			(x, y) = self.checkAhead('M')
			self.pngs['M']['coins'] -= 1
			if not self.pngs['M']['coins']:
				self.field[x][y] = ' '
		elif c == 'H':
			assert self.h < 3
			self.h = 3
		elif c == 'K':
			(x, y) = self.checkAhead('|-')
			self.field[x][y] = ' '

	def attack(self):
		(x, y) = nmy = self.checkAhead('ED')
		self.pngs[nmy]['h'] -= self.atk
		if self.pngs[nmy]['h'] < 1:
			del self.pngs[nmy]
			self.field[x][y] = ' '
			(lvlUp, self.xps) = divmod(self.xps + 1, 3)
			self.atk += lvlUp

	def checkDmgsAndAlive(self):
		for (dx, dy) in list(self.DIRS.values()):
			nmy = (self.x + dx, self.y + dy)
			if nmy in self.pngs:
				self.h -= max(0, self.pngs[nmy]['atk'] - self.d)
				assert self.h > 0


only_show_wrong()

class RPG:

	def __init__(self, field, actions):
		frame = ['#'] * (len(field[0]) + 2)
		self.field = [frame] + [['#'] + line + ['#'] for line in field] + [frame]
		self.actions = actions
		self.l = len(self.field)
		self.pack = {'H': 3, 'X': 1, 'S': 1}
		self.bag = []
		self.moves = {'<': (0, -1), '>': (0, 1), '^': (-1, 0), 'v': (1, 0)}
		self.x = self.find_player(self.field, lambda e: any(('<' in e, '>' in e, '^' in e, 'v' in e)))
		self.y = self.find_player(self.field[self.x], lambda e: e in '<>^v')
		self._player = self.field[self.x][self.y]
		self.back = None
		self.boss = 10
		self._result = 1
		self.use_coint = 0
		self.level_up = 0
		self.ready_atack = []
		self.use_item = {'K': self.use_key, 'C': self.coint_act, 'H': self.get_energy, 'A': self.atack}

	def __call__(self):
		for (i, act) in enumerate(self.actions):
			self.use_item.get(act, self.make_step)(act, act != 'F')
			if not self._result:
				break
			self.enemy_status(i, act)
		if self.use_coint:
			(x, y) = self.step
			if self.field[x][y] != 'M':
				return
		return self.result

	@property
	def game_over(self):
		self._result = None

	@property
	def step(self):
		move = self.moves[self._player]
		return (self.x + move[0], self.y + move[1])

	@property
	def result(self):
		if self._result:
			return ([line[1:-1] for line in self.field[1:-1]], *self.pack.values(), sorted(self.bag))

	@property
	def set_player(self):
		self._player = self.field[self.x][self.y]
		return self._player

	def enemy_status(self, i, act):
		for (x, y) in [(self.x + 1, self.y), (self.x - 1, self.y), (self.x, self.y + 1), (self.x, self.y - 1)]:
			if self.field[x][y] in 'DE':
				self.ready_atack.append(self.field[x][y])
		if self.ready_atack:
			(pref_a, next_a, l) = (self.actions, self.actions, len(self.actions) - 1)
			if i and i < l and (pref_a[i - 1] in '<>^vF') and (next_a[i + 1] == 'F') and (act == 'F') or (act in '<>^vAH' and i != l) or (act == 'F' and i < l and (next_a[i + 1] in '<>v^')):
				self.enemy_atack()
			self.ready_atack = []

	def enemy_atack(self):
		for enemy in self.ready_atack:
			self.pack['H'] -= max(0, (2, 3)[enemy == 'D'] - self.pack['S'])
			if self.pack['H'] <= 0:
				self.game_over

	def act(self):
		if self.back in '|-M#E':
			self.game_over
		if self.back in 'KCH':
			self.bag.append(self.back)
		if self.back in 'SX':
			self.pack[self.back] += 1

	def ded(self, x, y):
		self.field[x][y] = ' '

	def use_key(self, key, x):
		(x, y) = self.step
		if key in self.bag and self.field[x][y] in '|-':
			self.drop(key)
			self.ded(x, y)
		else:
			self.game_over

	def atack(self, x, z):
		(x, y) = self.step
		if self.field[x][y] == 'E':
			self.ded(x, y)
			self.level_up += 1
			if self.level_up == 3:
				self.pack['X'] += 1
				self.level_up = 0
		elif self.field[x][y] == 'D':
			self.boss -= self.pack['X']
			if self.boss <= 0:
				self.ded(x, y)
		else:
			self.game_over

	def coint_act(self, coint, i):
		if coint not in self.bag:
			self.game_over
			return
		self.use_coint += i
		self.drop(coint)
		if self.use_coint == 3:
			(x, y) = self.step
			if self.field[x][y] == 'M':
				self.use_coint = 0
				self.ded(x, y)
			else:
				self.game_over

	def get_energy(self, energy, x):
		if energy not in self.bag or self.pack[energy] >= 3:
			self.game_over
			return
		self.drop(energy)
		self.pack[energy] = 3

	def drop(self, element):
		del self.bag[self.bag.index(element)]

	def make_step(self, element, p):
		way = (self.set_player, element)[p]
		if not p:
			self.field[self.x][self.y] = ' '
			(self.x, self.y) = self.step
		if self.x < 1 or self.x >= self.l - 1 or self.y < 1 or (self.y >= len(self.field[self.x]) - 1):
			self.game_over
			return
		if self.field[self.x][self.y] != ' ':
			self.back = self.field[self.x][self.y]
			self.act()
		self.field[self.x][self.y] = way
		self.set_player

	@staticmethod
	def find_player(field, condition):
		return next((i for (i, e) in enumerate(field) if condition(e)))

def rpg(f, a) -> Tuple[List[List[str]], int, int, int, List[str]]:
	play_game = RPG(f, a)
	return play_game()


only_show_wrong()

def rpg(map: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]:

	class Hero:

		def __init__(self, coordy, coordx, pointer):
			self.coordx = coordx
			self.coordy = coordy
			self.health = 3
			self.attack = 1
			self.defence = 1
			self.pointer = pointer
			self.bag = []
			self.kills = 0
			self.lvlupkills = 0

	class Monsters:

		def __init__(self, coordy, coordx, attack, health):
			self.coordx = coordx
			self.coordy = coordy
			self.attack = attack
			self.health = health

	class DemonLord(Monsters):
		pass

	class Merchant:

		def __init__(self, coordy, coordx):
			self.coordx = coordx
			self.coordy = coordy
			self.health = 3

	def initiate(field):
		monstdict = {}
		merchdict = {}
		hero = 0
		for y in range(len(field)):
			for x in range(len(field[y])):
				if field[y][x] == 'E':
					monstdict[y, x] = Monsters(y, x, 2, 1)
				elif field[y][x] == 'D':
					monstdict[y, x] = DemonLord(y, x, 3, 10)
				elif field[y][x] in ('^', '>', 'v', '<'):
					hero = Hero(y, x, field[y][x])
				elif field[y][x] == 'M':
					merchdict[y, x] = Merchant(y, x)
		return (monstdict, hero, merchdict)

	def monsters_move(hero, monstdict):
		for i in [(hero.coordy, hero.coordx - 1), (hero.coordy + 1, hero.coordx), (hero.coordy, hero.coordx + 1), (hero.coordy - 1, hero.coordx)]:
			if i in monstdict:
				hero.health -= max(0, monstdict[i].attack - hero.defence)

	def forward_coords(hero):
		pointer = {'^': (0, -1), '>': (1, 0), 'v': (0, 1), '<': (-1, 0)}
		coordx = hero.coordx + pointer[hero.pointer][0]
		coordy = hero.coordy + pointer[hero.pointer][1]
		return (coordx, coordy)

	def move_forward(hero, field, monstdict, merchdict):
		monsters_move(hero, monstdict)
		field[hero.coordy][hero.coordx] = ' '
		coords = forward_coords(hero)
		hero.coordx = coords[0]
		hero.coordy = coords[1]
		if 0 <= hero.coordy < len(field) and 0 <= hero.coordx < len(field[hero.coordy]) and (field[hero.coordy][hero.coordx] not in ('D', 'E', 'M', '#', '-', '|')):
			if field[hero.coordy][hero.coordx] in ('C', 'H', 'K'):
				hero.bag.append(field[hero.coordy][hero.coordx])
			elif field[hero.coordy][hero.coordx] == 'S':
				hero.defence += 1
			elif field[hero.coordy][hero.coordx] == 'X':
				hero.attack += 1
			field[hero.coordy][hero.coordx] = hero.pointer
			return True
		else:
			return False

	def change_pointer(hero, field, monstdict, merchdict, pointer):
		monsters_move(hero, monstdict)
		hero.pointer = pointer
		field[hero.coordy][hero.coordx] = pointer
		if hero.health <= 0:
			return False
		return True

	def use_coin(hero, field, monstdict, merchdict):
		monsters_move(hero, monstdict)
		coords = forward_coords(hero)
		x = coords[0]
		y = coords[1]
		if 'C' in hero.bag and (y, x) in merchdict and (hero.health > 0):
			merchdict[y, x].health -= 1
			hero.bag.pop(hero.bag.index('C'))
			if merchdict[y, x].health == 0:
				field[y][x] = ' '
				del merchdict[y, x]
			return True
		return False

	def use_potion(hero, field, monstdict, merchdict):
		if 'H' in hero.bag and hero.health != 3:
			hero.health = 3
			hero.bag.pop(hero.bag.index('H'))
		else:
			return False
		monsters_move(hero, monstdict)
		return True if hero.health > 0 else False

	def use_key(hero, field, monstdict, merchdict):
		coords = forward_coords(hero)
		x = coords[0]
		y = coords[1]
		monsters_move(hero, monstdict)
		if 'K' in hero.bag and 0 <= x < len(field[y]) and (0 <= y < len(field)) and (field[y][x] in ('-', '|')) and (hero.health > 0):
			field[y][x] = ' '
			hero.bag.pop(hero.bag.index('K'))
			return True
		return False

	def attack(hero, field, monstdict, merchdict):
		coords = forward_coords(hero)
		x = coords[0]
		y = coords[1]
		if (y, x) in monstdict:
			monstdict[y, x].health -= hero.attack
			if monstdict[y, x].health <= 0:
				hero.lvlupkills += 1
				if hero.lvlupkills == 3:
					hero.attack += 1
					hero.lvlupkills = 0
				hero.kills += 1
				field[y][x] = ' '
				del monstdict[y, x]
		else:
			return False
		monsters_move(hero, monstdict)
		return True if hero.health > 0 else False
	field = [[str(x) for x in line] for line in map]
	initialize = initiate(field)
	monstdict = initialize[0]
	hero = initialize[1]
	merchdict = initialize[2]
	actionsdict = {'F': move_forward, 'A': attack, 'C': use_coin, 'K': use_key, 'H': use_potion}
	for i in actions:
		if i in actionsdict:
			flag = actionsdict[i](hero, field, monstdict, merchdict)
		else:
			flag = change_pointer(hero, field, monstdict, merchdict, i)
		if not flag or hero.health <= 0:
			return None
	return (field, hero.health, hero.attack, hero.defence, sorted(hero.bag))


only_show_wrong()

def rpg(game: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]:

	class GameObject:

		def __init__(self, game, h, a, d, l=None):
			self.g = game
			self.l = l if l is not None else (0, 0)
			self.h = h
			self.a = a
			self.d = d

		@property
		def is_alive(self):
			return self.h > 0

		def take_damage(self, attack):
			damage = max(0, attack - self.d)
			self.h -= damage
			if not self.is_alive:
				self.handle_death()
				return True

		def attack(self, other):
			return other.take_damage(self.a)

		def handle_death(self):
			self.g.removeObj(self.l)

	class Player(GameObject):
		direction_table = {'^': lambda self: (self.l[0], self.l[1] - 1), '>': lambda self: (self.l[0] + 1, self.l[1]), 'v': lambda self: (self.l[0], self.l[1] + 1), '<': lambda self: (self.l[0] - 1, self.l[1])}

		def __init__(self, game, s, l=None, b=None):
			super().__init__(game, 3, 1, 1, l)
			self.s = s
			self.b = b if b is not None else []
			self.exp = 0

		def __check_forward(self):
			new_loc = Player.direction_table[self.s](self)
			if self.g.is_within_bounds(new_loc):
				(x, y) = (new_loc[0], new_loc[1])
				obj = self.g.field[y][x]
				return (new_loc, obj)
			else:
				return None

		def handle_death(self):
			self.g.player = None
			super().handle_death()

		def __find_item(self, item):
			for i in range(len(self.b)):
				if self.b[i] == item:
					return self.b.pop(i)
			return None

		def __pickup_item(self, item):
			if item in 'CKH':
				self.b.append(item)
			elif item == 'X':
				self.a += 1
			else:
				self.d += 1

		def rotate(self, symb):
			self.s = symb
			(x, y) = (self.l[0], self.l[1])
			self.g.field[y][x] = self.s

		def move(self):
			new_loc = self.__check_forward()
			if new_loc is None or new_loc[1] in '#MED-|':
				return False
			if new_loc[1] in 'CKHSX':
				self.__pickup_item(new_loc[1])
			self.g.removeObj(self.l)
			self.l = new_loc[0]
			(x, y) = (self.l[0], self.l[1])
			self.g.field[y][x] = self.s
			return True

		def attack(self):
			maybe_enemy = self.__check_forward()
			if maybe_enemy is None or maybe_enemy[1] not in 'ED':
				return False
			(loc, symb) = (maybe_enemy[0], maybe_enemy[1])
			if symb == 'E':
				enemy = self.g.enemies[loc]
				if super().attack(enemy):
					self.add_exp()
			else:
				super().attack(self.g.demonlord)
			return True

		def add_exp(self):
			self.exp += 1
			if self.exp == 3:
				self.a += 1
				self.exp = 0

		def use_item(self, item_s):
			item = self.__find_item(item_s)
			if item is None:
				return False
			if item == 'H':
				if self.h < 3:
					self.h = 3
					return True
				else:
					return False
			if item == 'C':
				maybe_merch = self.__check_forward()
				if maybe_merch is None or maybe_merch[1] != 'M':
					return False
				merch_loc = maybe_merch[0]
				self.g.merchants[merch_loc].take_damage(1)
				return True
			if item == 'K':
				maybe_door = self.__check_forward()
				if maybe_door is None or maybe_door[1] not in '-|':
					return False
				door_loc = maybe_door[0]
				self.g.removeObj(door_loc)
				return True

	class Enemy(GameObject):

		def __init__(self, game, l=None):
			super().__init__(game, 1, 2, 0, l)

		def handle_death(self):
			del self.g.enemies[self.l]
			super().handle_death()

	class DemonLord(GameObject):

		def __init__(self, game, l=None):
			super().__init__(game, 10, 3, 0, l)

		def handle_death(self):
			self.g.demonlord = None
			super().handle_death()

	class Merchant(GameObject):

		def __init__(self, game, l=None):
			super().__init__(game, 3, 0, 0, l)

		def handle_death(self):
			del self.g.merchants[self.l]
			super().handle_death()

	class Game:

		def __init__(self, field):
			self.field = field
			self.player = None
			self.merchants = {}
			self.enemies = {}
			self.demonlord = None
			self.find_game_objects()

		def find_game_objects(self):
			for y in range(len(self.field)):
				for x in range(len(self.field[y])):
					if self.field[y][x] == 'M':
						self.merchants[x, y] = Merchant(self, (x, y))
					if self.field[y][x] == 'E':
						self.enemies[x, y] = Enemy(self, (x, y))
					if self.field[y][x] == 'D':
						self.demonlord = DemonLord(self, (x, y))
					if self.field[y][x] in '^><v':
						self.player = Player(self, self.field[y][x], (x, y))

		def is_within_bounds(self, loc):
			return 0 <= loc[0] and loc[0] < len(self.field[0]) and (0 <= loc[1]) and (loc[1] < len(self.field))

		def check_enemies(self, loc):
			directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
			for d in directions:
				new_loc = (loc[0] + d[0], loc[1] + d[1])
				if self.is_within_bounds(new_loc):
					if new_loc in self.enemies:
						self.enemies[new_loc].attack(self.player)
					elif self.demonlord and new_loc == self.demonlord.l:
						self.demonlord.attack(self.player)
				if self.player is None:
					return False
			return True

		def removeObj(self, loc):
			(x, y) = (loc[0], loc[1])
			self.field[y][x] = ' '

		def run_game(self, action_list):
			for action in action_list:
				prev_loc = self.player.l
				success = True
				if action in '^><v':
					self.player.rotate(action)
				elif action == 'A':
					success = self.player.attack()
				elif action in 'CKH':
					success = self.player.use_item(action)
				else:
					success = self.player.move()
				if not success:
					return None
				is_alive = self.check_enemies(prev_loc)
				if not is_alive:
					return None
			return (self.field, self.player.h, self.player.a, self.player.d, sorted(self.player.b))
	game = Game(game)
	return game.run_game(actions)


only_show_wrong()

def rpg(field: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]:
	print(field, actions)
	width = len(field[0])
	height = len(field)
	player = None
	lords = 0
	merchants = {}
	enemies = {}
	for (y, row) in enumerate(field):
		for (x, c) in enumerate(row):
			if c in dirchr:
				if player is None:
					player = (x, y)
					direction = dirchr.index(c)
					field[y][x] = ' '
				else:
					raise ValueError
			elif c == 'D':
				if lords:
					raise ValueError
				enemies[x, y] = 10
				lords += 1
			elif c == 'E':
				enemies[x, y] = 1
			elif c == 'M':
				merchants[x, y] = 3
	if not player:
		raise ValueError
	health = 3
	attack = 1
	defense = 1
	bag = []
	killed = 0
	(x, y) = player
	for a in actions:
		if a == 'F':
			health -= check_enemy_attack(field, width, height, x, y, defense)
			x += dx[direction]
			y += dy[direction]
			if x < 0 or x >= width or y < 0 or (y >= height) or (field[y][x] not in ' CKHSX'):
				return None
			obj = field[y][x]
			field[y][x] = ' '
			if obj in 'CKH':
				bag.append(obj)
			elif obj == 'S':
				defense += 1
			elif obj == 'X':
				attack += 1
		elif a in dirchr:
			direction = dirchr.index(a)
			health -= check_enemy_attack(field, width, height, x, y, defense)
		elif a in 'ACKH':
			if a in 'CKH':
				if a not in bag:
					return None
				bag.remove(a)
			(tx, ty) = (x + dx[direction], y + dy[direction])
			if tx < 0 or tx >= width or ty < 0 or (ty >= width):
				return None
			target = field[ty][tx]
			if a in valid_target and target not in valid_target[a]:
				return None
			if a == 'A':
				enemies[tx, ty] -= attack
				if enemies[tx, ty] <= 0:
					field[ty][tx] = ' '
					killed += 1
					if killed == 3:
						attack += 1
						killed = 0
				health -= check_enemy_attack(field, width, height, x, y, defense)
			elif a == 'C':
				merchants[tx, ty] -= 1
				if not merchants[tx, ty]:
					field[ty][tx] = ' '
			elif a == 'K':
				field[ty][tx] = ' '
			elif a == 'H':
				health = 3
				health -= check_enemy_attack(field, width, height, x, y, defense)
		if health <= 0:
			return None
	field[y][x] = dirchr[direction]
	return (field, health, attack, defense, sorted(bag))
dirchr = '^>v<'
dx = (0, 1, 0, -1)
dy = (-1, 0, 1, 0)
valid_target = dict(A='DE', C='M', K='-|')
enemy_attack = dict(D=3, E=2)

def check_enemy_attack(field, width, height, px, py, defense):
	damage = 0
	for (x, y) in ((px, py - 1), (px + 1, py), (px, py + 1), (px - 1, py)):
		if x >= 0 and x < width and (y >= 0) and (y < height) and (field[y][x] in 'DE'):
			attack = enemy_attack[field[y][x]]
			if attack > defense:
				damage += attack - defense
	return damage


only_show_wrong()
player = ['^', 'v', '<', '>']
items = [' ', 'K', 'C', 'H', 'S', 'X']

def rpg(field: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]:
	health = 3
	attack = 1
	defense = 1
	killed = 0
	bag = []
	demon_health = 10
	merchant_greed = 3
	for action in actions:
		(cell, x, y, x2, y2) = find_player(field)
		if action == 'F':
			if cell not in items:
				return None
			field[y2][x2] = field[y][x]
			field[y][x] = ' '
			if cell == ' ':
				pass
			elif cell == 'X':
				attack += 1
			elif cell == 'S':
				defense += 1
			else:
				bag.append(cell)
		elif action in player:
			field[y][x] = action
		elif action == 'K':
			if cell not in ['-', '|'] or 'K' not in bag:
				return None
			field[y2][x2] = ' '
			bag.remove('K')
		elif action == 'A':
			if cell not in ['E', 'D']:
				return None
			enemy_health = (demon_health if cell == 'D' else 1) - attack
			if enemy_health <= 0:
				field[y2][x2] = ' '
				if cell == 'E':
					killed += 1
					if killed == 3:
						killed = 0
						attack += 1
			else:
				demon_health = enemy_health
		elif action == 'C':
			if cell != 'M' or 'C' not in bag:
				return None
			merchant_greed -= 1
			bag.remove('C')
			if merchant_greed == 0:
				field[y2][x2] = ' '
		elif action == 'H':
			if health == 3 or 'H' not in bag:
				return None
			health = 3
			bag.remove('H')
		health = check_enemy_near(field, x, y, health, defense)
		if health <= 0:
			return None
	bag.sort()
	return (field, health, attack, defense, bag)

def check_enemy_near(field, x, y, health, defense):
	w = len(field[0])
	h = len(field)
	for (dx, dy) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
		(x2, y2) = (x + dx, y + dy)
		if 0 <= x2 < w and 0 <= y2 < h:
			if field[y2][x2] == 'E':
				health -= max(0, 2 - defense)
			elif field[y2][x2] == 'D':
				health -= max(0, 3 - defense)
	return health

def get_direction(player):
	if player == '^':
		return (0, -1)
	elif player == 'v':
		return (0, 1)
	elif player == '<':
		return (-1, 0)
	elif player == '>':
		return (1, 0)

def find_player(field):
	w = len(field[0])
	h = len(field)
	for y in range(h):
		for x in range(w):
			if field[y][x] in player:
				(dx, dy) = get_direction(field[y][x])
				(x2, y2) = (x + dx, y + dy)
				return (field[y2][x2] if 0 <= x2 < w and 0 <= y2 < h else None, x, y, x2, y2)
	return (None, 0, 0, 0, 0)


dir_dict = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}

def rpg(field, actions):
	(width, height) = (len(field[0]), len(field))
	(field, actions) = ([list(line) for line in field], list(actions))
	found = False
	for row in range(height):
		if found:
			break
		for col in range(width):
			if field[row][col] in dir_dict:
				player_loc = (row, col)
				player_dir = field[row][col]
				target_loc = (row + dir_dict[player_dir][0], col + dir_dict[player_dir][1])
				found = True
				break
	(hlh, atk, des, bag) = (3, 1, 1, [])
	mer_dict = {}
	(enemy_count, dl_hlh) = (0, 10)
	for action in actions:
		if action not in dir_dict:
			if target_loc[0] < 0 or target_loc[0] >= height or target_loc[1] < 0 or (target_loc[1] >= width):
				return None
			target_tile = field[target_loc[0]][target_loc[1]]
		if action == 'C':
			if target_tile != 'M':
				return None
			if action not in bag:
				return None
			bag.remove(action)
			if target_loc not in mer_dict:
				mer_dict[target_loc] = 2
			else:
				mer_dict[target_loc] = mer_dict[target_loc] - 1
				if mer_dict[target_loc] == 0:
					field[target_loc[0]][target_loc[1]] = ' '
		elif action == 'K':
			if target_tile not in '-|':
				return None
			if action not in bag:
				return None
			bag.remove(action)
			field[target_loc[0]][target_loc[1]] = ' '
		else:
			if action == 'F':
				if target_tile in ['C', 'K', 'H']:
					bag.append(target_tile)
					bag.sort()
				elif target_tile == 'S':
					des = des + 1
				elif target_tile == 'X':
					atk = atk + 1
				elif target_tile != ' ':
					return None
				field[target_loc[0]][target_loc[1]] = player_dir
				field[player_loc[0]][player_loc[1]] = ' '
			elif action in dir_dict:
				player_dir = action
				field[player_loc[0]][player_loc[1]] = action
				target_loc = (player_loc[0] + dir_dict[player_dir][0], player_loc[1] + dir_dict[player_dir][1])
			elif action == 'A':
				if target_tile == 'E':
					field[target_loc[0]][target_loc[1]] = ' '
					enemy_count = enemy_count + 1
					if enemy_count == 3:
						enemy_count = 0
						atk = atk + 1
				elif target_tile == 'D':
					dl_hlh = dl_hlh - atk
					if dl_hlh <= 0:
						field[target_loc[0]][target_loc[1]] = ' '
				else:
					return None
			elif action == 'H':
				if action not in bag:
					return None
				hlh = 3
				bag.remove(action)
			for d in dir_dict:
				check_loc = (player_loc[0] + dir_dict[d][0], player_loc[1] + dir_dict[d][1])
				if check_loc[0] >= 0 and check_loc[0] < height and (check_loc[1] >= 0) and (check_loc[1] < width):
					if field[check_loc[0]][check_loc[1]] == 'E':
						hlh = hlh - max(0, 2 - des)
					elif field[check_loc[0]][check_loc[1]] == 'D':
						hlh = hlh - max(0, 3 - des)
					if hlh <= 0:
						return None
			if action == 'F':
				player_loc = target_loc
				target_loc = (target_loc[0] + dir_dict[player_dir][0], target_loc[1] + dir_dict[player_dir][1])
	return tuple([field, hlh, atk, des, bag])


D = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}

def rpg(field, actions):
	g = [list(x) for x in field]
	(HP, Atk, Def, Boss, En) = (3, 1, 1, 10, 0)
	BC = BK = BH = 0
	px = py = 0
	mechanics = {}
	for i in range(len(g)):
		for j in range(len(g[i])):
			if g[i][j] in '^v<>':
				(px, py) = (i, j)
			if g[i][j] == 'M':
				mechanics[i, j] = 3

	def move(p, q, c):
		nonlocal BK, BC, BH, Atk, Def
		k = g[q[0]][q[1]]
		if k == 'K':
			BK += 1
		elif k == 'C':
			BC += 1
		elif k == 'X':
			Atk += 1
		elif k == 'S':
			Def += 1
		elif k == 'H':
			BH += 1
		(g[q[0]][q[1]], g[p[0]][p[1]]) = (c, ' ')

	def bounds(x, y):
		return 0 <= x < len(g) and 0 <= y < len(g[x])

	def attack(i, j, e):
		nonlocal HP, Def
		k = g[i][j]
		(nx, ny) = (i + D[k][0], j + D[k][1])
		for (x, y) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
			if bounds(x, y) and g[x][y] in 'DE':
				if not (e == 'A' and x == nx and (y == ny)):
					HP -= max({'D': 3, 'E': 2}[g[x][y]] - Def, 0)
	for e in actions:
		if e == 'H':
			if BH <= 0 or HP == 3:
				return None
			(BH, HP) = (BH - 1, 3)
		attack(px, py, e)
		k = g[px][py]
		if e == 'F':
			(ox, oy) = (px, py)
			(px, py) = (px + D[k][0], py + D[k][1])
			if not bounds(px, py) or g[px][py] not in ' CKXSH':
				return None
			move((ox, oy), (px, py), k)
		if e in '^v<>':
			g[px][py] = e
		(nx, ny) = (px + D[k][0], py + D[k][1])
		if e == 'K':
			if not bounds(nx, ny):
				return None
			if g[nx][ny] not in '-|' or BK <= 0:
				return None
			g[nx][ny] = ' '
			BK -= 1
		elif e == 'A':
			if not bounds(nx, ny) or g[nx][ny] not in 'DE':
				return None
			if g[nx][ny] == 'E' and Atk >= 1:
				En += 1
				if En % 3 == 0:
					Atk += 1
				g[nx][ny] = ' '
			elif g[nx][ny] == 'D':
				Boss -= Atk
				if Boss <= 0:
					g[nx][ny] = ' '
					break
				HP -= max({'D': 3, 'E': 2}[g[nx][ny]] - Def, 0)
		elif e == 'C':
			if not bounds(nx, ny) or g[nx][ny] != 'M' or BC <= 0:
				return None
			mechanics[nx, ny] -= 1
			if mechanics[nx, ny] == 0:
				g[nx][ny] = ' '
			BC -= 1
	if HP <= 0:
		return None
	Bag = ['C'] * BC + ['H'] * BH + ['K'] * BK
	return (g, HP, Atk, Def, Bag)


only_show_wrong()

def rpg(field, actions):
	newfield = [[val for val in row] for row in field]
	playerpos = [0, 0, 0]
	playerstats = [3, 1, 1, 0]
	playerbag = []
	myactions = actions
	demonlord_hp = [10]
	merchants = []
	for row in newfield:
		for val in row:
			if val == '^':
				playerpos[0] = row.index(val)
				playerpos[1] = newfield.index(row)
				playerpos[2] = 0
			elif val == '>':
				playerpos[0] = row.index(val)
				playerpos[1] = newfield.index(row)
				playerpos[2] = 1
			elif val == 'v':
				playerpos[0] = row.index(val)
				playerpos[1] = newfield.index(row)
				playerpos[2] = 2
			elif val == '<':
				playerpos[0] = row.index(val)
				playerpos[1] = newfield.index(row)
				playerpos[2] = 3
			elif val == 'M':
				merchants.append([row.index(val), newfield.index(row), 3])
	for action in myactions:
		lastplayerpos = playerpos[:]
		legalmove = True
		if action == 'F':
			legalmove = forward(newfield, playerpos, playerbag, playerstats)
		elif action == '^':
			playerpos[2] = 0
			newfield[playerpos[1]][playerpos[0]] = getplayerstring(playerpos)
		elif action == '>':
			playerpos[2] = 1
			newfield[playerpos[1]][playerpos[0]] = getplayerstring(playerpos)
		elif action == 'v':
			playerpos[2] = 2
			newfield[playerpos[1]][playerpos[0]] = getplayerstring(playerpos)
		elif action == '<':
			playerpos[2] = 3
			newfield[playerpos[1]][playerpos[0]] = getplayerstring(playerpos)
		elif action == 'A':
			legalmove = attack(newfield, playerpos, playerstats, demonlord_hp)
			if legalmove == 'win':
				print('we won!')
				break
		elif action == 'C':
			legalmove = coin(newfield, playerpos, playerbag, merchants)
		elif action == 'K':
			legalmove = key(newfield, playerpos, playerbag)
		elif action == 'H':
			legalmove = health(playerbag, playerstats)
		if legalmove == False:
			print('Encountered invalid!')
			print('last action: ' + action)
			return None
		enemies = getajanba(newfield, lastplayerpos)
		if len(enemies) > 0:
			print('Printing enemies!')
			print('last action: ' + action)
			for enemy in enemies:
				print(enemy)
		for enemy in enemies:
			damagetodeal = max(0, 2 - playerstats[2]) if enemy == 'E' else max(0, 3 - playerstats[2])
			playerstats[0] -= damagetodeal
			if playerstats[0] <= 0:
				return None
	sortedbag = playerbag if len(playerbag) <= 1 else sorted(playerbag)
	return (newfield, playerstats[0], playerstats[1], playerstats[2], sortedbag)

def forward(field, playerpos, bag, playerstats):
	infront = check_front(field, playerpos)
	if infront == False:
		return False
	obj = infront[0]
	posx = infront[1]
	posy = infront[2]
	if obj == '#' or obj == 'M' or obj == '-' or (obj == '|') or (obj == 'E') or (obj == 'D'):
		return False
	elif obj == 'C' or obj == 'K' or obj == 'H':
		bag.append(obj)
		print('obtained: ' + obj + '   bag is now: ')
		print(bag)
		field[posy][posx] = ' '
	elif obj == 'S':
		playerstats[2] += 1
		field[posy][posx] = ' '
	elif obj == 'X':
		playerstats[1] += 1
		field[posy][posx] = ' '
	field[playerpos[1]][playerpos[0]] = ' '
	field[posy][posx] = getplayerstring(playerpos)
	playerpos[0] = posx
	playerpos[1] = posy
	return True

def attack(field, playerpos, playerstats, demonlord):
	infront = check_front(field, playerpos)
	if infront == False:
		return False
	enemy = infront[0]
	posx = infront[1]
	posy = infront[2]
	if enemy == 'E':
		field[posy][posx] = ' '
		playerstats[3] += 1
		if playerstats[3] >= 3:
			playerstats[1] += 1
			playerstats[3] = 0
		return True
	elif enemy == 'D':
		demonlord[0] -= playerstats[1]
		if demonlord[0] <= 0:
			field[posy][posx] = ' '
			return 'win'
	else:
		return False

def coin(field, playerpos, playerbag, merchants):
	if 'C' not in playerbag:
		return False
	infront = check_front(field, playerpos)
	if infront == False:
		return False
	obj = infront[0]
	posx = infront[1]
	posy = infront[2]
	if obj != 'M':
		print('No merchant in front!')
		return False
	for merchant in merchants:
		if merchant[0] == posx and merchant[1] == posy:
			playerbag.remove('C')
			merchant[2] -= 1
			print('giving coin to merchant')
			if merchant[2] <= 0:
				field[posy][posx] = ' '
				print('merchant should b gone')
			break
	return True

def key(field, playerpos, playerbag):
	if 'K' not in playerbag:
		return False
	infront = check_front(field, playerpos)
	if infront == False:
		return False
	obj = infront[0]
	posx = infront[1]
	posy = infront[2]
	if obj != '-' and obj != '|':
		return False
	field[posy][posx] = ' '
	playerbag.remove('K')
	return True

def health(playerbag, playerstats):
	if playerstats[0] >= 3:
		return False
	if 'H' not in playerbag:
		return False
	playerstats[0] = 3
	playerbag.remove('H')
	return True

def check_front(field, playerpos):
	posx = playerpos[0]
	posy = playerpos[1]
	posdir = playerpos[2]
	if posdir == 0:
		posx += 0
		posy -= 1
	elif posdir == 1:
		posx += 1
		posy -= 0
	elif posdir == 2:
		posx += 0
		posy += 1
	elif posdir == 3:
		posx -= 1
		posy -= 0
	if (posx < 0 or posx >= len(field[0])) or (posy < 0 or posy >= len(field)):
		return False
	obj = field[posy][posx]
	return [obj, posx, posy]

def getplayerstring(playerpos):
	if playerpos[2] == 0:
		return '^'
	elif playerpos[2] == 1:
		return '>'
	elif playerpos[2] == 2:
		return 'v'
	elif playerpos[2] == 3:
		return '<'

def getajanba(field, playerpos):
	enemylist = []
	tocheck = [[playerpos[0] + 1, playerpos[1]], [playerpos[0] - 1, playerpos[1]], [playerpos[0], playerpos[1] + 1], [playerpos[0], playerpos[1] - 1]]
	for check in tocheck:
		posx = check[0]
		posy = check[1]
		if (posx < 0 or posx >= len(field[0])) or (posy < 0 or posy >= len(field)):
			continue
		obj = field[posy][posx]
		if obj == 'E' or obj == 'D':
			enemylist.append(obj)
	return enemylist


only_show_wrong()
playerDirections = {'^': (0, -1), '<': (-1, 0), '>': (1, 0), 'v': (0, 1)}
items = ('X', 'K', 'H', 'S', 'C')

def rpg(field: List[List[str]], actions: List[str]) -> Tuple[List[List[str]], int, int, int, List[str]]:
	player = {'x': 0, 'y': 0, 'direction': (0, 0), 'char': '', 'health': 3, 'attack': 1, 'defense': 1, 'inventory': [], 'levelCounter': 0, 'coinsCounter': 0}
	demonLord = 10
	for (y, str) in enumerate(field):
		for (x, char) in enumerate(str):
			if char in playerDirections:
				player['x'] = x
				player['y'] = y
				player['direction'] = playerDirections[char]
				player['char'] = char
				break
		else:
			continue
		break
	for action in actions:
		if action in playerDirections:
			player['direction'] = playerDirections[action]
			player['char'] = action
		elif action == 'F':
			enemiesClose = []
			for dir in playerDirections.values():
				adjacent = ''
				try:
					positions = (max(0, player['y'] + dir[1]), max(0, player['x'] + dir[0]))
					adjacent = field[positions[0]][positions[1]]
				except:
					adjacent = ''
				if adjacent == 'E' or adjacent == 'D':
					player['health'] -= max(0, (2 if adjacent == 'E' else 3) - player['defense'])
			field[player['y']][player['x']] = ' '
			player['x'] += player['direction'][0]
			player['y'] += player['direction'][1]
			if player['x'] < 0 or player['y'] < 0 or player['y'] >= len(field) or (player['x'] >= len(field[player['y']])):
				return None
			nextTile = field[player['y']][player['x']]
			if not nextTile in items and nextTile != ' ':
				return None
			if nextTile in items:
				if nextTile == 'X':
					player['attack'] += 1
				elif nextTile == 'S':
					player['defense'] += 1
				else:
					player['inventory'].append(nextTile)
		elif action in player['inventory']:
			if action == 'H':
				if player['health'] < 3:
					player['health'] = 3
				else:
					return None
			elif action == 'K':
				nextTilePos = (player['y'] + player['direction'][1], player['x'] + player['direction'][0])
				if nextTilePos[1] < 0 or nextTilePos[0] < 0 or nextTilePos[0] >= len(field) or (nextTilePos[1] >= len(field[nextTilePos[0]])):
					return None
				nextTile = field[nextTilePos[0]][nextTilePos[1]]
				if nextTile == '-' or nextTile == '|':
					field[nextTilePos[0]][nextTilePos[1]] = ' '
				else:
					return None
			else:
				nextTilePos = (player['y'] + player['direction'][1], player['x'] + player['direction'][0])
				if nextTilePos[1] < 0 or nextTilePos[0] < 0 or nextTilePos[0] >= len(field) or (nextTilePos[1] >= len(field[nextTilePos[0]])):
					return None
				if field[nextTilePos[0]][nextTilePos[1]] == 'M':
					player['coinsCounter'] += 1
					if player['coinsCounter'] >= 3:
						field[nextTilePos[0]][nextTilePos[1]] = ' '
				else:
					return None
			player['inventory'].remove(action)
		elif action == 'A':
			nextTilePos = (player['y'] + player['direction'][1], player['x'] + player['direction'][0])
			nextTile = field[nextTilePos[0]][nextTilePos[1]]
			if nextTile == 'E':
				field[nextTilePos[0]][nextTilePos[1]] = ' '
				player['levelCounter'] += 1
				if player['levelCounter'] >= 3:
					player['levelCounter'] = 0
					player['attack'] += 1
			elif nextTile == 'D':
				demonLord -= player['attack']
				if demonLord <= 0:
					field[nextTilePos[0]][nextTilePos[1]] = ' '
			else:
				return None
		else:
			return None
		if action == 'A' or action == 'H' or action in playerDirections:
			for dir in playerDirections.values():
				adjacent = ''
				try:
					positions = (max(0, player['y'] + dir[1]), max(0, player['x'] + dir[0]))
					adjacent = field[positions[0]][positions[1]]
				except:
					adjacent = 'X'
				if adjacent == 'E' or adjacent == 'D':
					player['health'] -= max(0, (2 if adjacent == 'E' else 3) - player['defense'])
		if player['health'] <= 0:
			return None
	field[player['y']][player['x']] = player['char']
	return (field, player['health'], player['attack'], player['defense'], sorted(player['inventory']))