# 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: interview

Starter code:

def edge_detection(image):
	

Solutions:
'''
Challenge Fun #20: Edge Detection
https://www.codewars.com/kata/58bfa40c43fadb4edb0000b5/train/python

For a rectangular image given in run-length encoding (RLE) as
described below, return a RLE of the image processed by replacing
each pixel by the maximum absolute value of the difference between
it and each neighboring pixel (a simple form of edge detection).

For a RLE encoding string "7 15 4 100 15 25 2 ...",
    7      ----> image width
    15 4   ----> a pair(color value + pixel count)
    100 15 ----> a pair(color value + pixel count)
    25 2   ----> a pair(color value + pixel count)
    ...          ...
where the image width is > 0 and the sum of all the pixel counts
is a multiple of the width.

--------------------
Design of solution

Read the rle-encoded values into a buffer of rows of the given width,
with an important optimization trick. In the case of long runs of the
same value, where three or more rows would be filled with identical
data, store just three rows of data, and remember (using another data
structure) which is the middle of the three rows, and how many copies
of it (the "row count") were in the original image. For example,
suppose the image width is 10, and the image has a run of 73 copies
of the value 7, and the run starts with the last two values in row 34.
The buffer would look like this:

        ...
    34  [ some previous data ...  7, 7 ]
    35  [ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 ]
    36  [ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 ]
    37  [ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 ]
    38  [ 7, ... start of new data ... ]
        ...

and elsewhere a note is made that row 36 has a row count of 5.

With long runs arranged this way, the edge-detection transformation
can be run on the buffer without having to worry about row counts.
Row counts are used later, when encoding the transformed values back
into a run-length encoding.
'''
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: rowcount

    row, row_ndx = [], 0
    while data:
        val, runlen = data.pop(0), data.pop(0)
        if row == [] and runlen > 3 * width:
            buf += [[val] * width] * 3
            # There's a top, middle, and bottom row; middle has a row count
            rowcounts[row_ndx + 1] = (runlen // width) - 2
            row_ndx += 3
            # Values from run that didn't fit in the above rows.
            row = [val] * (runlen % width)
            continue

        take = min(runlen, width - len(row))
        runlen -= take
        row += [val] * take
        if len(row) < width:
            continue

        # Here, row is full, with mixed values, and there may be some
        # (many!) values left over from the last (val, runlen) pair that
        # was read from data.
        buf.append(row)
        row_ndx += 1
        row = []

        if row == [] and runlen > 3 * width:
            buf += [[val] * width] * 3
            # There's a top, middle, and bottom row; middle has a row count
            rowcounts[row_ndx + 1] = (runlen // width) - 2
            row_ndx += 3
            # Values from run that didn't fit in the above rows.
            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):
    '''
    Yields iterable's elements in pairs. If iterable is exhausted after
    an odd number of elements, completes the last pair with fillvalue.
    '''
    # This is the 'grouper' recipe from the itertools documentation.
    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)]

    # Single pixel
    if 1 == width == length:
        return [[0]]

    # Single row
    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

    # Single column
    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

    # At least a 2 x 2 image. Unroll what we'd rather do in loops and
    # list comprehensions.

    BOT = length - 1        # convenience; last data row
    RT = width - 1          # convenience; last data column

    # Corners
    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]))

    # Top and bottom (except corners)
    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]))

    # Left edge (except corners)
    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]))

    # Finallly! The interior
    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]),
                                   )
    # Now wasn't that fun?
    return outbuf


def encode(buf, rowcounts):
    width = len(buf[0])

    # Initial list of (value, runlength) pairs. Not necessarily a
    # run-length encoding, as successive values might be equal.
    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()
    # Now condense val_rl into a true run-length encoding.
    (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
#@profile
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

        
#@profile
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) #fill all window lines first line from image
    l1 = l2
    #print(l2)
    curr_dev = -99999
    y = 0
    while y < height:
        l0 = l1
        l1 = l2
        if y < height_bound:
            l2 = getline(width) 
        #print(l2)
        x = 1

        # +++ first elem in line
        t = [l1[1], l0[0], l0[1], l2[0], l2[1]]
        #t.sort()
        #c = max(abs(t[0] - l1[0]),abs(t[-1] - l1[0]))
        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
        # --- first elem in line

        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]]
            #t.sort()
            #c = max(abs(t[0] - l1[x]),abs(t[-1] - l1[x]))
            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
        # +++ end elem in line
        t = [l1[-2], l0[-2], l0[-1], l2[-2], l2[-1]]
        #t.sort()
        #c = max(abs(t[0] - l1[-1]),abs(t[-1] - l1[-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
        # --- end elem in line
        y += 1

        #if rez[-1] > width3 and y < height_bound and l1[0] == rle[0] :
        if  one_color_flag > 2:
            n_str = (rle[1]//width) - 1
            one_color_flag = 0
            if n_str > 0:
                ls = n_str * width
                #rez[-1] += ls
                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(']','')

# Todo: performance boost for the special case: same number for many lines

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:]

# get next line iterator, extra one 'None' after last line
## Todo: special lines mark (same number for many lines)
# (None (normal), line) or ((Special line nums), line)
# special lines are     xxx, ooo, ooo2, ooo3, ooo(last), xxx,   ooo2~last-1 are special
def get_line(w, src):
    nums = src

    r, c = 0, 0 # index
    line = []
    i = 0
    while i < len(nums) > 0:
        n, count = nums[i], nums[i + 1]
        i += 2
        while c + count > w: # across line, split it
            # special case
            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: # could not be > w
                yield (None, line)
                r, c = r + 1, 0
                line = []
    # valid input should yields line and ends here
    # one None after last line
    yield (None, None)

# return RLE edge in one line (left/right)
def edge_inline(w, line):
    # patch on the left and right
    extended_line = [(line[0][0], 1)] + line + [(line[-1][0], 1)]

    n_prev = line[0][0]
    r = []
    # middle
    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

# return RLE edge compared from line to other line
def edge_twolines(w, line, other):
    if DEBUG: print(("twolines: ", line, other))
    # 2 pass, split this line in the shape of other
    def aa(line, other):
        current, left, i, j, si, sj = 0, 0, 0, 0, line[0][1], other[0][1]
        while left < w:
            # print(current, left, i, j, si, sj)
            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):
        # patch other line on the left and right
        return [(line[0][0], 1)] + other + [(line[-1][0], 1)]

    # line_splits = aa(line, other)
    # extended_line = bb(line, other)
    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):
    # for i in range(len(line_splits)):
        # (n, count) = line_splits[i]

        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
        # print(i, n, count, j, right, sj, m_prev, m, mr, dl, dc)
    return r


# merge RLE edges into one
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]

        # special case, same number across many lines
        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)
        # Todo: send cur_edge
        # print("cur edge: ", cur_edge, prev_line, cur_line, next_line)
        for en, ec in cur_edge:
            rle.add(en, ec)

        if next_line is None: # finishes
            break

    # Todo: send last edge line
    # print(cur_edge)
    # returns edges
    return ' '.join([str(w), rle.display()])





from itertools import chain


def parse_ascii(image_ascii):
    """ Parses the input string

    Returns a 3-tuple:
        - :width: - the width in pixels of the image
        - :height: - the height in pixels of the image
        - List of pairs (pixel_value, run_length)
            run_length is the number of successive pixels with the same value when scanning
            the row, including the following rows

    Assumes with no check:
        :run_length: > 0 for all cases
        Successive pairs have different :pixel_value:
        The sum of all pixels is a multiple of :width:

    >>> parse_ascii("3 43 4 24 2")
    (3, 2, [(43, 4), (24, 2)])
    """
    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):
    """ Denominates the pixel runs with an absolute position

    Given the pairs (pixel_value, run_length), returns triplets (start, end, pixel_value)

    The pixel positions are numbered successively starting with the first row from left
    to right and then the following rows. :start: and :end: are given as such positions.
    :start: points to the first pixel of the run with :pixel_value:
    :end: points to the position after the the pixel ending the run

    >>> list(get_intervals([(34,4),(98,5),(12,40)]))
    [(0, 4, 34), (4, 9, 98), (9, 49, 12)]
    """
    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):
    """ Shifts the intervals, and corrects for end of row

    Returns the intervals (start, end, pixel_value) with the variables :start: and :end:
    shifted :offset: positions.

    If :offset: is positive, fills the first positions with a new (0, :offset:, None) interval,
    and removes the intervals and interval parts correspoding to the last :offset: positions.
    Conversely for negative :offset:.

    If :offset: is positive, all endings and beginnings of interval falling in the first column
    past the end of a row are back-shifted one position, extending or contracting the interval as
    necessary. This is so to prevent an offset pixel to be neighbour of a pixel in a different row,
    as the use for this will be to assess neighbouring pixels. Conversely for negative :offset: and
    interval boundaries falling in the last column of a row.

    >>> list(get_shifted_intervals([(0, 3, 55), (3, 5, 78), (5, 11, 23), (11, 15, 99)], 6, 5, 3))
    [(0, 5, None), (5, 9, 55), (9, 10, 78), (10, 15, 23)]
    >>> list(get_shifted_intervals([(0, 3, 55), (3, 5, 78), (5, 11, 23), (11, 15, 99)], -6, 5, 3))
    [(0, 5, 23), (5, 10, 99), (10, 15, None)]
    """
    # Add empty interval at the beginning if shifted right
    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

        # Remove or contract an interval if shifted past the beginning
        if end <= 0:
            continue
        if start < 0:
            start = 0

        # Remove or contract and interval if shifted past the end
        if start >= width * height:
            continue
        if end > width * height:
            end = width * height

        # Correct for proximity of a row jump
        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

        # Remove if because of a contraction the length of the interval is zero
        if start == end:
            continue

        yield (start, end, pixel_value)

    # Add empty interval at the end if shifted left
    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):
    """ Fuse many lists of intervals into one

    Given many lists of intervals, returns a single list of intersected intervals.
    The intervals of the output list are of the form
    (start, end, [pixel_value_1, pixel_value_2, ...])
    Pixel values containing None are not included.

    >>> list(intersect_intervals([
    ...     [(0,4,23),(4,6,14),(6,25,88),(25,45,99)],
    ...     [(0,3,66),(3,9,33),(9,10,77),(10,25,43),(25,45,None)]
    ...     ], 9, 5))
    [(0, 3, [23, 66]), (3, 4, [23, 33]), (4, 6, [14, 33]), (6, 9, [88, 33]), (9, 10, [88, 77]), (10, 25, [88, 43]), (25, 45, [99])]
    """
    # List of pairs [iterator, interval], each iterator yields from a list of intervals
    # and the interval will be updated as the algorithm runs
    ilists = [[iter(ilist), (0, 0, None)] for ilist in interval_lists]
    pos = 0
    while pos < width * height:
        # Advance the iterators so that the associated interval contains :pos:
        for ilist in ilists:
            iterator, current_interval = ilist
            _, end, _ = current_interval
            while end <= pos:
                ilist[1] = next(iterator)
                _, end, _ = ilist[1]

        # Take the interval from :pos: to the closest end
        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):
    """ Merge successive intervals if they have the same value

    Input and output are lists of intervals (start, end, value)

    >>> list(compose_intervals([(0, 3, 7), (3, 5, 7), (5, 8, 7), (8, 9, 12), (9, 13, 7)]))
    [(0, 8, 7), (8, 9, 12), (9, 13, 7)]
    """
    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):
    """ Converts intervals to (value, length) format """
    return ((value, end - start) for (start, end, value) in intervals)


def generate_ascii(pairs, width):
    """ Converts to the required output format as a string """
    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:]