#!/opt/local/bin/python

import random, collections, string, copy

probname = "spiesvsspies"

tcount = {}
total_secret = 0

# bounds like MAXN here
MAXN = 300000
MAXI = 300000
MAXC = 10**6

def gen(loc, ins, intype = probname):
    global total_secret

    assert type(loc) == list and len(loc) in range(1, MAXN+1)
    assert type(ins) == list and len(ins) in range(1, MAXI+1)

    hor, ver, inits = {}, {}, set()
    
    for l in loc:
        assert type(l) == tuple and len(l) == 2
        x, y = l
        assert x in range(-MAXC, MAXC+1) and y in range(-MAXC, MAXC+1)
        assert (x, y) not in inits
        inits.add((x, y))
    
    for x in ins:
        assert type(x) == tuple and len(x) == 2
        i, d = x
        assert i in range(1, len(loc)+1) and d in "NSEW"

    path = "../data"

    if intype not in tcount: tcount[intype] = 0
    tcount[intype] += 1

    if intype == "sample":
        filename = "{0}/sample/{1}.in".format(path, tcount[intype])
    else:
        filename = "{0}/secret/{3:02}-{1}-{2}.in".format(path, intype, tcount[intype], total_secret)
        total_secret += 1

    print("Generating:", filename)

    out = open(filename, "w")

    # print the test case here, remember to print to file=out
    print(len(loc), len(ins), file=out)
    for l in loc: print(*l, file=out)
    for i in ins: print(*i, file=out)

    out.close()

def gensample():
    gen([(0,0), (1,2), (1,0)], [(1,"N"), (3,"W"), (1,"E"), (2,"S"), (2,"E"), (3,"N")], "sample")
    gen([(0,0), (1,0), (2, 0), (3, 0), (4, 0)], [(5,"N"), (4,"E"), (3, "W"), (4, "W")], "sample")

def randins(N):
    return (random.randint(1,N), random.choice("NSEW"))

def gencorner():
    gen([(0,0)], [(1,"N"), (1, "S"), (1, "E"), (1, "W")], "corner")
    gen([(0,0), (1,0), (0,1), (-1,0), (0,-1)], [(1,"N"), (1, "S"), (1, "E"), (1, "W")], "corner")
    gen([(0,0), (1,0), (1,1)], [(1,"E"), (3,"S")], "corner")

    seq = [(0,i) for i in range(MAXN)]
    ins = [(i,"N") for i in range(1,MAXN+1)]
    gen(seq, ins, "corner")
    gen(seq, ins[::-1], "corner")

    seq = [(0,i) for i in range(MAXN)]
    ins = [(i,"S") for i in range(1,MAXN+1)]
    gen(seq, ins, "corner")
    gen(seq, ins[::-1], "corner")

    seq = [(i,0) for i in range(MAXN)]
    ins = [(i,"E") for i in range(1,MAXN+1)]
    gen(seq, ins, "corner")
    gen(seq, ins[::-1], "corner")

    seq = [(i,0) for i in range(MAXN)]
    ins = [(i,"W") for i in range(1,MAXN+1)]
    gen(seq, ins, "corner")
    gen(seq, ins[::-1], "corner")


def genrandline(N):
    locs = list({(random.randint(-MAXC, MAXC), 17) for _ in range(N)})
    ins = [randins(len(locs)) for _ in range(len(locs))]
    gen(locs, ins, "randline")

    locs = list({(42, random.randint(-MAXC, MAXC)) for _ in range(N)})
    ins = [randins(len(locs)) for _ in range(len(locs))]
    gen(locs, ins, "randline")

def genspiral(N):
    prev = (0,0)
    locs = set()
    while len(locs) < N:
        rnd = random.randint(-MAXC,MAXC)
        nx, ny = prev
        if len(locs)%2: nx = rnd
        else: ny = rnd
        nxt = (nx, ny)
        if nxt not in locs:
            locs.add(nxt)
            prev = nxt
    locs = list(locs)
    random.shuffle(locs)
    gen(locs, [randins(len(locs)) for i in range(N)], "spiral")
        
def gengrid(R, C, N):
    xv = set()
    while len(xv) < R: xv.add(random.randint(-MAXC, MAXC))
    yv = set()
    while len(yv) < C: yv.add(random.randint(-MAXC, MAXC))

    xv = list(xv)
    yv = list(yv)

    assert R*C >= 2*N
    loc = set()
    while len(loc) < N:
        loc.add((random.choice(xv), random.choice(yv)))
    loc = list(loc)

    gen(loc, [randins(len(loc)) for _ in range(N)], "grid")

if __name__ == "__main__":
    random.seed(0)

    gensample()

    gencorner()

    genrandline(100)
    genspiral(100)
    gengrid(2,100,100)
    gengrid(10,20,100)
    gengrid(100,100,100)
    gengrid(100,100,1000)
    
    genrandline(MAXN)
    genspiral(MAXN)

    rt = int((2*MAXN)**0.5)+1
    gengrid(rt, rt, MAXN)
    gengrid(20,MAXN//10, MAXN)
    gengrid(10,MAXN//5, MAXN)
    gengrid(40,MAXN//20, MAXN)
    gengrid(rt, rt, MAXN)
    gengrid(rt, rt, MAXN)