# Task
 IONU Satellite Imaging, Inc. records and stores very large images using run length encoding. You are to write a program that reads a compressed image, finds the edges in the image, as described below, and outputs another compressed image of the detected edges.
 
 A simple edge detection algorithm sets an output pixel's value to be the maximum absolute value of the differences between it and all its surrounding pixels in the input image. Consider the input image below:

 ![](http://media.openjudge.cn/images/1009_1.jpg)

 The upper left pixel in the output image is the maximum of the values |15-15|,|15-100|, and |15-100|, which is 85. The pixel in the 4th row, 2nd column is computed as the maximum of |175-100|, |175-100|, |175-100|, |175-175|, |175-25|, |175-175|,|175-175|, and |175-25|, which is 150.
 
 Images contain 2 to 1,000,000,000 (10^9) pixels. All images are encoded using run length encoding (RLE). This is a sequence of pairs, containing pixel value (0-255) and run length (1-10^9). Input images have at most 1,000 of these pairs. Successive pairs have different pixel values. All lines in an image contain the same number of pixels.
  
 For the iamge as the example above, the RLE encoding string is `"7 15 4 100 15 25 2 175 2 25 5 175 2 25 5"`
 
 ```
 Each image starts with the width, in pixels(means the first number 7)
 This is followed by the RLE pairs(two number is a pair).
 7      ----> image width
 15 4   ----> a pair(color value + number of pixel)
 100 15       ...........ALL.......................
 25 2         ..........THESE......................
 175 2        ...........ARE.......................
 25 5         ..........PAIRS......................
 175 2        ...........LIKE......................
 25 5         ..........ABOVE......................
 ```
 
 Your task is to calculate the result by using the edge detection algorithm above. Returns a encoding string in the same format as the input string.
 
# Exaple

 `Please see examples in the example test block.`
 
# Input/Output


 - `[input]` string `image`
 
 A RLE string of image.
 
 
 - `[output]` a string
 
 A RLE string calculate by using the edge detection algorithm.

Difficulty: MEDIUM_HARD

Starter code:
def edge_detection(image):
	

Solutions:
import itertools

def edge_detection(image):
	data = [int(datum) for datum in image.split(' ')]
	width = data.pop(0)
	(inbuf, rowcounts) = fill_buffer(width, data)
	outbuf = detect_edges(inbuf)
	outdata_list = encode(outbuf, rowcounts)
	outdata = [str(datum) for datum in outdata_list]
	return str(width) + ' ' + ' '.join(outdata)

def fill_buffer(width, data):
	buf = []
	rowcounts = dict()
	(row, row_ndx) = ([], 0)
	while data:
		(val, runlen) = (data.pop(0), data.pop(0))
		if row == [] and runlen > 3 * width:
			buf += [[val] * width] * 3
			rowcounts[row_ndx + 1] = runlen // width - 2
			row_ndx += 3
			row = [val] * (runlen % width)
			continue
		take = min(runlen, width - len(row))
		runlen -= take
		row += [val] * take
		if len(row) < width:
			continue
		buf.append(row)
		row_ndx += 1
		row = []
		if row == [] and runlen > 3 * width:
			buf += [[val] * width] * 3
			rowcounts[row_ndx + 1] = runlen // width - 2
			row_ndx += 3
			row = [val] * (runlen % width)
			continue
		while runlen > 0:
			take = min(runlen, width - len(row))
			runlen -= take
			row += [val] * take
			if len(row) == width:
				buf.append(row)
				row_ndx += 1
				row = []
	return (buf, rowcounts)

def pairs_from(iterable, fillvalue=None):
	args = [iter(iterable)] * 2
	return itertools.zip_longest(*args, fillvalue=fillvalue)

def detect_edges(inbuf):
	length = len(inbuf)
	width = len(inbuf[0])
	outbuf = [([-1] * width).copy() for _ in range(length)]
	if 1 == width == length:
		return [[0]]
	if 1 == length:
		outbuf[0][0] = abs(inbuf[0][0] - inbuf[0][1])
		outbuf[0][width - 1] = abs(inbuf[0][width - 2] - inbuf[0][width - 1])
		for col in range(1, width - 1):
			val = inbuf[0][col]
			outbuf[0][col] = max(abs(val - inbuf[0][col - 1]), abs(val - inbuf[0][col + 1]))
		return outbuf
	if 1 == width:
		outbuf[0][0] = abs(inbuf[0][0] - inbuf[1][0])
		outbuf[length - 1][0] = abs(inbuf[length - 2][0] - inbuf[length - 1][0])
		for row in range(1, length - 1):
			val - inbuf[row][0]
			outbuf[row][0] = max(abs(val - inbuf[row - 1][0]), abs(val - inbuf[row + 1][0]))
		return outbuf
	BOT = length - 1
	RT = width - 1
	(top_lf, top_rt) = (inbuf[0][0], inbuf[0][RT])
	(bot_lf, bot_rt) = (inbuf[BOT][0], inbuf[BOT][RT])
	outbuf[0][0] = max(abs(top_lf - inbuf[0][1]), abs(top_lf - inbuf[1][0]), abs(top_lf - inbuf[1][1]))
	outbuf[0][RT] = max(abs(top_rt - inbuf[0][RT - 1]), abs(top_rt - inbuf[1][RT - 1]), abs(top_rt - inbuf[1][RT]))
	outbuf[BOT][0] = max(abs(bot_lf - inbuf[BOT - 1][0]), abs(bot_lf - inbuf[BOT - 1][1]), abs(bot_lf - inbuf[BOT][1]))
	outbuf[BOT][RT] = max(abs(bot_rt - inbuf[BOT - 1][RT - 1]), abs(bot_rt - inbuf[BOT - 1][RT]), abs(bot_rt - inbuf[BOT][RT]))
	for col in range(1, RT):
		val = inbuf[0][col]
		outbuf[0][col] = max(abs(val - inbuf[0][col - 1]), abs(val - inbuf[0][col + 1]), abs(val - inbuf[1][col - 1]), abs(val - inbuf[1][col]), abs(val - inbuf[1][col + 1]))
		val = inbuf[BOT][col]
		outbuf[BOT][col] = max(abs(val - inbuf[BOT - 1][col - 1]), abs(val - inbuf[BOT - 1][col]), abs(val - inbuf[BOT - 1][col + 1]), abs(val - inbuf[BOT][col - 1]), abs(val - inbuf[BOT][col + 1]))
	for row in range(1, BOT):
		val = inbuf[row][0]
		outbuf[row][0] = max(abs(val - inbuf[row - 1][0]), abs(val - inbuf[row - 1][1]), abs(val - inbuf[row][1]), abs(val - inbuf[row + 1][0]), abs(val - inbuf[row + 1][1]))
		val = inbuf[row][RT]
		outbuf[row][RT] = max(abs(val - inbuf[row - 1][RT - 1]), abs(val - inbuf[row - 1][RT]), abs(val - inbuf[row][RT - 1]), abs(val - inbuf[row + 1][RT - 1]), abs(val - inbuf[row + 1][RT]))
	for row in range(1, BOT):
		for col in range(1, RT):
			val = inbuf[row][col]
			outbuf[row][col] = max(abs(val - inbuf[row - 1][col - 1]), abs(val - inbuf[row - 1][col]), abs(val - inbuf[row - 1][col + 1]), abs(val - inbuf[row][col - 1]), abs(val - inbuf[row][col + 1]), abs(val - inbuf[row + 1][col - 1]), abs(val - inbuf[row + 1][col]), abs(val - inbuf[row + 1][col + 1]))
	return outbuf

def encode(buf, rowcounts):
	width = len(buf[0])
	val_rl = list()
	for row_ndx in range(len(buf)):
		encoded_row = [(val, len(list(grp))) for (val, grp) in itertools.groupby(buf[row_ndx])]
		if row_ndx in rowcounts:
			val_rl.append((encoded_row[0][0], width * rowcounts[row_ndx]))
		else:
			for (val, count) in encoded_row:
				val_rl.append((val, count))
	encoding = list()
	(old_val, old_rl) = val_rl.pop(0)
	for (val, rl) in val_rl:
		if val == old_val:
			old_rl += rl
		else:
			encoding += (old_val, old_rl)
			(old_val, old_rl) = (val, rl)
	encoding += (old_val, old_rl)
	return encoding


rle = []
one_color_flag = 0

def getline(w):
	nonlocal rle, one_color_flag
	rezl = []
	while w > 0:
		rle0 = rle[0]
		rle1 = rle[1]
		if rle1 > w:
			rle[1] -= w
			rezl.extend([rle0 for i in range(w)])
			one_color_flag += 1
			return rezl
		else:
			rezl.extend([rle0 for i in range(rle1)])
			one_color_flag = 0
			w -= rle1
			rle.pop(0)
			rle.pop(0)
	return rezl

def edge_detection(rle_str):
	nonlocal rle, one_color_flag
	rle = [int(x) for x in rle_str.split(' ')]
	width = rle.pop(0)
	data_length = sum(rle[1::2])
	height = data_length // width
	width3 = width * 3
	rez = [width]
	width_bound = width - 1
	height_bound = height - 1
	l2 = getline(width)
	l1 = l2
	curr_dev = -99999
	y = 0
	while y < height:
		l0 = l1
		l1 = l2
		if y < height_bound:
			l2 = getline(width)
		x = 1
		t = [l1[1], l0[0], l0[1], l2[0], l2[1]]
		c = max(abs(min(t) - l1[0]), abs(max(t) - l1[0]))
		if curr_dev == c:
			rez[-1] += 1
		else:
			rez.append(c)
			rez.append(1)
			curr_dev = c
		while x < width_bound:
			t = [l1[x - 1], l1[x + 1], l0[x - 1], l0[x], l0[x + 1], l2[x - 1], l2[x], l2[x + 1]]
			c = max(abs(min(t) - l1[x]), abs(max(t) - l1[x]))
			if curr_dev == c:
				rez[-1] += 1
			else:
				rez.append(c)
				rez.append(1)
				curr_dev = c
			x += 1
		t = [l1[-2], l0[-2], l0[-1], l2[-2], l2[-1]]
		c = max(abs(min(t) - l1[-1]), abs(max(t) - l1[-1]))
		if curr_dev == c:
			rez[-1] += 1
		else:
			rez.append(c)
			rez.append(1)
			curr_dev = c
		y += 1
		if one_color_flag > 2:
			n_str = rle[1] // width - 1
			one_color_flag = 0
			if n_str > 0:
				ls = n_str * width
				if curr_dev == 0:
					rez[-1] += ls
				else:
					rez.append(0)
					rez.append(ls)
					curr_dev = 0
				rle[1] -= ls
				y += n_str
	return str(rez).replace(',', '').replace('[', '').replace(']', '')


DEBUG = False

class RLE:

	def __init__(self):
		self.c = 0
		self.count = 0
		self.result = ''

	def add(self, c, count):
		if self.count > 0 and self.c == c:
			self.count += count
		else:
			if self.count > 0:
				self.result += ' ' + str(self.c) + ' ' + str(self.count)
			self.c = c
			self.count = count

	def display(self):
		if self.count > 0:
			self.result += ' ' + str(self.c) + ' ' + str(self.count)
			self.count = 0
			self.c = 0
		return self.result[1:]

def get_line(w, src):
	nums = src
	(r, c) = (0, 0)
	line = []
	i = 0
	while i < len(nums) > 0:
		(n, count) = (nums[i], nums[i + 1])
		i += 2
		while c + count > w:
			if c == 0 and count > 3 * w:
				yield (None, [(n, w)])
				yield (count // w - 2, [(n, w)])
				yield (None, [(n, w)])
				(r, c) = (r + count // w, 0)
				count -= w * (count // w)
				line = []
				continue
			count -= w - c
			line.append((n, w - c))
			yield (None, line)
			(r, c) = (r + 1, 0)
			line = []
		if count > 0:
			line.append((n, count))
			c += count
			if c == w:
				yield (None, line)
				(r, c) = (r + 1, 0)
				line = []
	yield (None, None)

def edge_inline(w, line):
	extended_line = [(line[0][0], 1)] + line + [(line[-1][0], 1)]
	n_prev = line[0][0]
	r = []
	for i in range(1, len(extended_line) - 1):
		(n, count) = extended_line[i]
		n_next = extended_line[i + 1][0]
		d_l = abs(n - n_prev)
		d_r = abs(n - n_next)
		if count > 1:
			r.append((d_l, 1))
			if count > 2:
				r.append((0, count - 2))
			r.append((d_r, 1))
		else:
			r.append((max(d_l, d_r), 1))
		n_prev = n
	return r

def edge_twolines(w, line, other):
	if DEBUG:
		print(('twolines: ', line, other))

	def aa(line, other):
		(current, left, i, j, si, sj) = (0, 0, 0, 0, line[0][1], other[0][1])
		while left < w:
			while si <= left and i < len(line):
				i += 1
				si += line[i][1]
				current += 1
			while sj <= left and j < len(other):
				j += 1
				sj += other[j][1]
			right = min(si, sj)
			yield (line[current][0], right - left)
			left += right - left

	def bb(line, other):
		return [(line[0][0], 1)] + other + [(line[-1][0], 1)]
	extended_line = [(line[0][0], 1)] + other + [(line[-1][0], 1)]
	r = []
	m_prev = extended_line[0][0]
	(j, right, sj) = (1, 0, extended_line[1][1])
	for (n, count) in aa(line, other):
		dl = abs(n - m_prev)
		m = extended_line[j][0]
		dc = abs(n - m)
		if count > 1:
			r.append((max(dl, dc), 1))
			if count > 2:
				r.append((dc, count - 2))
			mr = m
			right += count
			if right >= sj:
				j += 1
				sj += extended_line[j][1]
				mr = extended_line[j][0]
			r.append((max(dc, abs(n - mr)), 1))
		else:
			mr = m
			right += 1
			if right >= sj:
				j += 1
				sj += extended_line[j][1]
				mr = extended_line[j][0]
			r.append((max(dl, dc, abs(n - mr)), 1))
		m_prev = m
	return r

def merge_edge_lines(w, line1, line2):
	(i, j, si, sj) = (0, 0, line1[0][1], line2[0][1])
	left = 0
	r = []
	while left < w:
		while si <= left and i < len(line1):
			i += 1
			si += line1[i][1]
		while sj <= left and j < len(line2):
			j += 1
			sj += line2[j][1]
		n = max(line1[i][0], line2[j][0])
		right = min(si, sj)
		r.append((n, right - left))
		left = right
	return r
import time

def edge_detection(image):
	imgs = [int(i) for i in image.split(' ')]
	(w, line) = (imgs[0], imgs[1:])
	line_iter = get_line(w, line)
	rle = RLE()
	(prev_line_info, cur_line_info, next_line_info) = ((None, None), (None, None), next(line_iter))
	while True:
		(prev_line_info, cur_line_info, next_line_info) = (cur_line_info, next_line_info, next(line_iter))
		(prev_line, cur_line, next_line, is_special) = (prev_line_info[1], cur_line_info[1], next_line_info[1], cur_line_info[0])
		if not is_special is None:
			rle.add(0, is_special * cur_line[0][1])
			continue
		cur_edge = edge_inline(w, cur_line)
		if not prev_line is None:
			prev_edge = edge_twolines(w, cur_line, prev_line)
			cur_edge = merge_edge_lines(w, prev_edge, cur_edge)
		if next_line is not None:
			next_edge = edge_twolines(w, cur_line, next_line)
			cur_edge = merge_edge_lines(w, cur_edge, next_edge)
		for (en, ec) in cur_edge:
			rle.add(en, ec)
		if next_line is None:
			break
	return ' '.join([str(w), rle.display()])


from itertools import chain

def parse_ascii(image_ascii):
	values = [int(v) for v in image_ascii.split()]
	width = values[0]
	pixel_runs = list(zip(values[1::2], values[2::2]))
	height = sum(values[2::2]) // width
	return (width, height, pixel_runs)

def get_intervals(pixel_runs):
	pos = 0
	for (pixel_value, run_length) in pixel_runs:
		yield (pos, pos + run_length, pixel_value)
		pos += run_length

def get_shifted_intervals(intervals, offset, width, height):
	if offset > 0:
		if offset % width == 1:
			yield (0, offset - 1, None)
		elif offset % width == width - 1:
			yield (0, offset + 1, None)
		else:
			yield (0, offset, None)
	for (start, end, pixel_value) in intervals:
		start += offset
		end += offset
		if end <= 0:
			continue
		if start < 0:
			start = 0
		if start >= width * height:
			continue
		if end > width * height:
			end = width * height
		if offset % width == 1 and start % width == 1:
			start -= 1
		if offset % width == 1 and end % width == 1:
			end -= 1
		if offset % width == width - 1 and start % width == width - 1:
			start += 1
		if offset % width == width - 1 and end % width == width - 1:
			end += 1
		if start == end:
			continue
		yield (start, end, pixel_value)
	if offset < 0:
		if (width * height + offset) % width == width - 1:
			yield (width * height + offset + 1, width * height, None)
		elif (width * height - offset) % width == 1:
			yield (width * height + offset - 1, width * height, None)
		else:
			yield (width * height + offset, width * height, None)

def intersect_intervals(interval_lists, width, height):
	ilists = [[iter(ilist), (0, 0, None)] for ilist in interval_lists]
	pos = 0
	while pos < width * height:
		for ilist in ilists:
			(iterator, current_interval) = ilist
			(_, end, _) = current_interval
			while end <= pos:
				ilist[1] = next(iterator)
				(_, end, _) = ilist[1]
		min_end = min((end for (_, (_, end, _)) in ilists))
		values = [value for (_, (_, _, value)) in ilists if value is not None]
		yield (pos, min_end, values)
		pos = min_end

def compose_intervals(intervals):
	cur_value = None
	cur_start = None
	cur_end = None
	for (start, end, value) in intervals:
		if value == cur_value:
			cur_end = end
			continue
		if cur_end is not None:
			yield (cur_start, cur_end, cur_value)
		(cur_start, cur_end, cur_value) = (start, end, value)
	yield (cur_start, cur_end, cur_value)

def get_lengths(intervals):
	return ((value, end - start) for (start, end, value) in intervals)

def generate_ascii(pairs, width):
	return ' '.join((str(n) for n in chain([width], *pairs)))

def edge_detection(image):
	(width, height, pixel_runs) = parse_ascii(image)
	intervals = list(get_intervals(pixel_runs))
	offsets = [-width - 1, -width, -width + 1, -1, 1, width - 1, width, width + 1]
	neighbours = [get_shifted_intervals(intervals, offset, width, height) for offset in offsets]
	intersected_neighbours = intersect_intervals(neighbours, width, height)
	intersected_all = intersect_intervals([intervals, intersected_neighbours], width, height)
	result = []
	for (start, end, (base_cell, neighbour_cells)) in intersected_all:
		result_cell = max((abs(base_cell - n) for n in neighbour_cells))
		result.append((start, end, result_cell))
	out_intervals = compose_intervals(result)
	out_lengths = get_lengths(out_intervals)
	return generate_ascii(out_lengths, width)


def edge_detection(image):
	image = [int(v) for v in image.split(' ')]
	width = image[0]
	(map, line, flat) = ([], [], [])
	(rest, f) = (width, 1)
	(current, result) = (['', width], [''])

	def apply(value):
		if current[0] == value:
			current[1] += 1
		else:
			result[0] += ' ' + str(current[0]) + ' ' + str(current[1])
			current[0] = value
			current[1] = 1

	def diff(R, C, r, c):
		r += R
		c += C
		return abs(flat[R][C] - flat[r][c]) if 0 <= r < len(flat) and 0 <= c < width else 0
	while f < len(image):
		line.append([image[f], min(rest, image[1 + f])])
		if image[1 + f] < rest:
			rest -= image[1 + f]
			f += 2
		else:
			image[1 + f] -= rest
			if image[1 + f] < 3 * width:
				if image[1 + f] < 1:
					f += 2
				map.append(line)
				line = []
				rest = width
			else:
				map.append(line)
				map.append([[image[f], width]])
				map.append([[image[f], width, image[1 + f] // width - 2]])
				map.append([[image[f], width]])
				line = []
				image[1 + f] %= width
				rest = width - image[1 + f]
				if image[1 + f]:
					line.append(image[f:2 + f])
				f += 2
	for v in map:
		t = f = 0
		line = []
		flat.append(line)
		for _ in range(width):
			line.append(v[f][0])
			t += 1
			if v[f][1] <= t:
				(t, f) = (0, 1 + f)
	for (r, row) in enumerate(map):
		if 2 < len(row[0]):
			apply(0)
			current[1] += width * row[0][2] - 1
		else:
			for f in range(width):
				apply(max(diff(r, f, -1, 0), diff(r, f, -1, 1), diff(r, f, 0, 1), diff(r, f, 1, 1), diff(r, f, 1, 0), diff(r, f, 1, -1), diff(r, f, 0, -1), diff(r, f, -1, -1)))
	apply(None)
	return result[0][2:]