# Kata Task

A bird flying high above a mountain range is able to estimate the height of the highest peak.

Can you?

# Example

## The birds-eye view



^^^^^^
 ^^^^^^^^
  ^^^^^^^
  ^^^^^
  ^^^^^^^^^^^
  ^^^^^^
  ^^^^


## The bird-brain calculations


111111
 1^^^^111
  1^^^^11
  1^^^1
  1^^^^111111
  1^^^11
  1111



111111
 12222111
  12^^211
  12^21
  12^^2111111
  122211
  1111



111111
 12222111
  1233211
  12321
  12332111111
  122211
  1111



`Height = 3`

# Series

* Bird Mountain
* [Bird Mountain - the river](https://www.codewars.com/kata/bird-mountain-the-river)

Source: codewars | Difficulty: EASY
Tags: Graph algorithms

Starter code: def peak_height(mountain):
	

Solutions:
def peak_height(mountain):
	M = {(r, c) for (r, l) in enumerate(mountain) for c in range(len(l)) if l[c] == '^'}
	h = 0
	while M:
		M -= {(r, c) for (r, c) in M if {(r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c)} - M}
		h += 1
	return h


from scipy.ndimage.morphology import binary_erosion as erode, numpy as np

def peak_height(mountain):
	(M, n) = (np.array([*map(list, mountain)]) == '^', 0)
	while M.any():
		(M, n) = (erode(M), n + 1)
	return n


def peak_height(mountain):
	(lX, lY) = (len(mountain), len(mountain[0]))
	(top, lst) = (0, [[0] * lY for _ in range(lX)])
	for (x, row) in enumerate(mountain):
		for (y, v) in enumerate(row):
			lst[x][y] = (v == '^') + (0 < x < lX - 1 and 0 < y < lY - 1 and (v == '^') and min(lst[x - 1][y], lst[x][y - 1]))
			top |= lst[x][y] > 0
	for x in reversed(range(1, lX - 1)):
		for y in reversed(range(1, lY - 1)):
			lst[x][y] = min(lst[x][y], lst[x + 1][y] + 1, lst[x][y + 1] + 1)
			top += top < lst[x][y]
	return top


def peak_height(mountain):
	points = {(row, col) for (row, lst) in enumerate(mountain) for col in range(len(lst)) if lst[col] == '^'}
	height = 0
	while points:
		points -= {(row, col) for (row, col) in points if {(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)} - points}
		height += 1
	return height


from collections import defaultdict

def peak_height(mountain):
	heights = defaultdict(int)
	(h, w) = (len(mountain), len(mountain[0]))
	heights.update({(x, y): 0 if mountain[y][x] == ' ' else -1 for x in range(w) for y in range(h)})
	res = 0
	while True:
		todo = []
		for y in range(len(mountain)):
			for x in range(len(mountain[y])):
				if heights[x, y] == -1:
					neighbors = [heights[x + a, y + b] for (a, b) in [(1, 0), (-1, 0), (0, 1), (0, -1)] if heights[x + a, y + b] > -1]
					if neighbors:
						todo.append((x, y, 1 + min(neighbors)))
		for (x, y, v) in todo:
			heights[x, y] = v
			res = max(res, v)
		if not todo:
			return res


def peak_height(mountain):
	new_mnt = [['x' for i in range(len(mountain[0]))] for _ in range(len(mountain))]
	for i in range(len(mountain)):
		for j in range(len(mountain[0])):
			if mountain[i][j] == '^':
				if i > 0 and j > 0 and (i < len(mountain) - 1) and (j < len(mountain[0]) - 1):
					if mountain[i + 1][j] == ' ' or mountain[i - 1][j] == ' ' or mountain[i][j + 1] == ' ' or (mountain[i][j - 1] == ' '):
						new_mnt[i][j] = 1
				else:
					new_mnt[i][j] = 1
			else:
				new_mnt[i][j] = 0
	done = False
	round = 1
	while not done:
		done = True
		for i in range(0, len(new_mnt) - 1):
			for j in range(0, len(new_mnt[0]) - 1):
				if new_mnt[i][j] == 'x':
					if new_mnt[i + 1][j] == round or new_mnt[i - 1][j] == round or new_mnt[i][j + 1] == round or (new_mnt[i][j - 1] == round):
						new_mnt[i][j] = round + 1
					else:
						done = False
		round += 1
	maxVal = 0
	for l in new_mnt:
		maxVal = max(maxVal, max(l))
	return maxVal


from math import floor

def peak_height(mountain):
	a = []
	for i in mountain:
		b = []
		for j in i:
			if j == ' ':
				b.append(0)
			else:
				b.append(1)
		a.append(b)
	for m in range(floor(min(len(a), len(a[0])) / 2)):
		for i in range(1 + m, len(a) - 1 - m):
			for j in range(1 + m, len(a[0]) - 1 - m):
				if a[i][j] > 0:
					a[i][j] = min(a[i - 1][j], a[i + 1][j], a[i][j - 1], a[i][j + 1]) + 1
	return max([max(i) for i in a])


from collections import Counter

def neigthboors(peaks):
	for (x, y) in peaks:
		yield (x, y - 1)
		yield (x - 1, y)
		yield (x, y)
		yield (x + 1, y)
		yield (x, y + 1)

def peak_height(mountain):
	mountain = [(x, y) for (y, row) in enumerate(mountain) for (x, p) in enumerate(row) if p == '^']
	i = 0
	while mountain:
		mountain = [x_y for (x_y, cnt) in list(Counter(neigthboors(mountain)).items()) if cnt == 5]
		i += 1
	return i


def peak_height(mountain):
	neighbours = lambda z: {z + 1j ** d for d in range(4)}
	mountain = {x + 1j * y for (x, r) in enumerate(mountain) for (y, c) in enumerate(r) if c == '^'}
	(height, base) = (0, set().union(*map(neighbours, mountain)) - mountain)
	while mountain:
		height += 1
		base = set.union(*map(neighbours, base)) & mountain
		mountain -= base
	return height


def peak_height(mountain):

	def condition1(a, b, mountian):
		return a == 0 or a == len(mountain) - 1 or b == 0 or (b == len(mountain[0]) - 1)

	def condition2(a, b, k):
		if k == -1:
			return any([mountain_list[a + 1][b] == ' ', mountain_list[a - 1][b] == ' ', mountain_list[a][b + 1] == ' ', mountain_list[a][b - 1] == ' '])
		else:
			return any([mountain_list[a + 1][b] == k + 1, mountain_list[a - 1][b] == k + 1, mountain_list[a][b + 1] == k + 1, mountain_list[a][b - 1] == k + 1])

	def loop_firt(list):
		for (a, i) in enumerate(list):
			for (b, j) in enumerate(i):
				if j == '^' and condition1(a, b, mountain):
					list[a][b] = 1
				elif j == '^' and condition2(a, b, -1):
					list[a][b] = 1

	def loop_again(list, y):
		for (a, i) in enumerate(list):
			for (b, j) in enumerate(i):
				if j == '^' and condition1(a, b, mountain):
					pass
				elif j == '^' and condition2(a, b, y - 1):
					list[a][b] = y + 1

	def the_biggest(list):
		for i in mountain_list:
			for j in i:
				if type(j) == int:
					yield j
				elif j == ' ':
					pass
	if mountain == []:
		return []
	x = ['^', 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
	y = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
	mountain_list = []
	list2 = []
	for i in mountain:
		list1 = []
		for j in i:
			list1.append(j)
		mountain_list.append(list1)
	for i in range(len(x)):
		if i == 0:
			loop_firt(mountain_list)
		else:
			loop_again(mountain_list, i)
	for i in mountain_list:
		list1 = []
		for j in i:
			list1.append(str(j))
		list2.append(''.join(list1))
	if list(the_biggest(mountain_list)) == []:
		return 0
	else:
		return max(list(the_biggest(mountain_list)))