from os import mkdir
from random import *

seed('sherlocked')

MAXN_G2 = 50
MAXN = 1000

logger = lambda s : print (s)

class Printer:
    def __init__(self, path):
        self.path = "../" + path
        self.tests = 0
        try:
            logger("Creating directory %s"%self.path)
            mkdir(self.path)
        except:
            logger("...Directory already exists")

    def print(self, a):
        a = minimize_test(a)
        self.tests += 1
        p = self.path + "/" + "%02d"%self.tests
        logger("Printing test %s"%p)
        out = open(p, "w")
        n, m = len(a), len(a[0])
        print(n, m, file=out)
        for ax in a:
            print(' '.join(str(x) for x in ax), file=out)

def pack(s):
    d = {}
    i = 1
    for a in sorted(list(s)):
        d[a] = i
        if a + 1 in s:
            i += 1
        else:
            i += 2
    return d

def minimize_test(t):
    items = set([i for tx in t for i in tx])
    d = pack(items)
    return [[d[i] for i in tx] for tx in t]

def slow_voronoi(n, m, points):
    def dist(p1, p2):
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    return [[min(dist(p, (i, j)) for p in points) for j in range(m)] for i in range(n)]

def fast_voronoi(n, m, points):
    res = [[-1] * m for i in range(n)]
    from collections import deque
    q = deque(points)
    for x, y in points:
        res[x][y] = 0
    while q:
        x, y = q.popleft()
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            xTo, yTo = x + dx, y + dy
            if not (0 <= xTo < n and 0 <= yTo < m):
                continue
            if res[xTo][yTo] == -1:
                res[xTo][yTo] = res[x][y] + 1
                q.append((xTo, yTo))
    return res
            
#def voronoi(n, m, points):
#    assert fast_voronoi(n, m, points) == slow_voronoi(n, m, points)
#    return fast_voronoi(n, m, points)
voronoi = fast_voronoi

def snake(n, m):
    res, a = [], 1
    for i in range(n):
        b = [a + j for j in range(m)]
        a += m
        res.append(b if i % 2 == 0 else b[::-1])
    return res

def randtest(n, m, k):
    return [[randint(1, k) for j in range(m)] for i in range(n)]

prelim = Printer("preliminary")
prelim.print([[1,2,3], [6,5,4], [7,8,9]])
prelim.print([[1,1,1], [1,2,1], [1,1,1]])

tests = Printer("tests")
tests.print([[1]])
tests.print([list(range(10))])
tests.print([list(range(MAXN))[::-1]])
tests.print([[1,2,1]])
tests.print([[1,1,1]])
tests.print([[1,2,3,2,1]])
tests.print([[1,3,5,2,4]])
tests.print([list(range(1, MAXN, 2)) + list(range(2, MAXN, 2))])
tests.print(voronoi(1, 10, [(0, 2), (0, 5), (0, 9)]))
tests.print(voronoi(1, MAXN, [(0, MAXN // i) for i in range(2, 11)]))
tests.print(randtest(1, 10, 10))
tests.print(randtest(1, MAXN, MAXN))
tests.print(randtest(1, MAXN, 10))


for N in [MAXN_G2, MAXN]:
    tests.print([[1,1], [1,1]])
    tests.print([[1,1], [1,2]])
    tests.print([[1,2], [2,3]])
    for c in [3, 5, 10, N, N**2, 2 * N**2]:
        tests.print(randtest(N, N, c))
    tests.print(voronoi(N, N, [(N // 2, N // 2)]))
    for c in [3, 5, N // 10, N // 5]:
        tests.print(voronoi(N, N, [(randint(0, N - 1), randint(0, N - 1)) for i in range(c)]))
    tests.print(voronoi(N, N // 2, [(0, 0)]))
    tests.print(voronoi(N, N, [(0, 0)]))
    
tests.print(snake(MAXN, MAXN))
tests.print(snake(MAXN, MAXN)[::-1])
