import argparse
import random
import math
import sys
import subprocess

import cspuz
from cspuz import Solver, BoolGridFrame, graph
from cspuz.constraints import count_true, fold_or
from cspuz.puzzle import util

def solve_curve_data(height, width, *problem):
    solver = Solver()
    grid_frame = BoolGridFrame(solver, height - 1, width - 1)
    solver.add_answer_key(grid_frame)
    clue = problem[0]
    border = problem[1]
    for p in border:
        solver.ensure(~grid_frame[p[0][0]+p[1][0],p[0][1]+p[1][1]])
    is_sat = solver.solve()
    cnthor=0
    cntver=0
    for i in range(height):
        for j in range(width):
            adj = []
            if i > 0: adj.append(grid_frame[i*2-1,j*2])
            if j > 0: adj.append(grid_frame[i*2,j*2-1])
            if i + 1 < height: adj.append(grid_frame[i*2+1,j*2])
            if j +1  < width : adj.append(grid_frame[i*2,j*2+1])
            if clue[i][j]!=(-1,):
                solver.ensure(fold_or(adj))
                if clue[i][j]!=None:
                    for c in clue[i][j][1]:
                        if c[0]==0:
                            cnthor+=1
                        else:
                            cntver+=1
            else:
                solver.ensure(~fold_or(adj))
    horid=solver.int_array((height, width-1), 0,cnthor)
    verid=solver.int_array((height-1, width), 0,cntver)
    for i in range(height):
        for j in range(width):
            if i+1<height:
                solver.ensure(grid_frame[2*i+1,2*j] == (verid[i,j]!=0))
            if j+1<width:
                solver.ensure(grid_frame[2*i,2*j+1] == (horid[i,j]!=0))
    phor=0
    pver=0
    bs=[]
    def addmatch(x,y,ps):
        ee=[0,0,0,0]
        if y+1<width:
            ee[0]=horid[x][y]
        if x+1<height:
            ee[1]=verid[x][y]
        if y>0:
            ee[2]=horid[x][y-1]
        if x>0:
            ee[3]=verid[x-1][y]
        cond=[]
        for ff in ps:
            cond.append((ee[0]==ff[0])&(ee[1]==ff[1])&(ee[2]==ff[2])&(ee[3]==ff[3]))
        solver.ensure(fold_or(cond))
    for i in range(height):
        for j in range(width):
            if clue[i][j]!=(-1,) and clue[i][j]!=None:
                qs=[]
                n=clue[i][j][0]
                seg=clue[i][j][1]
                segid=[-1]*(len(seg))
                chor=0
                cver=0
                for (k,c) in enumerate(seg):
                    if c[0]==0:
                        chor+=1
                        segid[k]=chor+phor
                        bs.append((segid[k],0,segid[k],0))
                        qs.append((segid[k],0,segid[k],0))
                    else:
                        cver+=1
                        segid[k]=cver+pver
                        bs.append((0,segid[k],0,segid[k]))
                        qs.append((0,segid[k],0,segid[k]))
                for z in range(n):
                    ss=[0,0,0,0]
                    for (k,c) in enumerate(seg):
                        if c[0]==0 and c[1]==z:
                            ss[0]=segid[k]
                        if c[0]==0 and c[2]==z:
                            ss[2]=segid[k]
                        if c[0]==1 and c[1]==z:
                            ss[1]=segid[k]
                        if c[0]==1 and c[2]==z:
                            ss[3]=segid[k]
                    bs.append(ss)
                    qs.append(ss)
                gs = BoolGridFrame(solver, height - 1, width - 1)
                for y in range(height):
                    for x in range(width):
                        if y + 1 < height:
                            solver.ensure(gs[2 * y + 1, 2 * x] == ((verid[y, x]>pver) & (verid[y, x]<=pver+cver)))
                        if x + 1 < width:
                            solver.ensure(gs[2 * y, 2 * x + 1] == ((horid[y, x]>phor) & (horid[y, x]<=phor+chor)))
                graph.active_edges_connected(solver, gs)
                phor+=chor
                pver+=cver
                addmatch(i,j,qs)

    for i in range(height):
        for j in range(width):
            if clue[i][j]==None:
                addmatch(i,j,bs)
    is_sat = solver.solve()
    return is_sat, grid_frame



def convertborder(border, height, width):
    banpair=[]
    if border!=None:
        vb=[]
        for i in range(height):
            for j in range(1,width):
                vb.append((i,j))
        while len(vb)%5!=0:
            vb.append((-1,-1))
        t=0
        for i in range(0,len(vb),5):
            ch=border[t]
            num=0
            if ord(ch)<=ord('9'):
                num=ord(ch)-ord('0')
            else:
                num=ord(ch)-ord('a')+10
            for k in range(5):
                if vb[i+k]!=(-1,-1) and (num>>(4-k))&1:
                    banpair.append([(vb[i+k][0],vb[i+k][1]-1),(vb[i+k][0],vb[i+k][1])])
            t+=1
        vb=[]
        for i in range(1,height):
            for j in range(width):
                vb.append((i,j))
        while len(vb)%5!=0:
            vb.append((-1,-1))
        for i in range(0,len(vb),5):
            ch=border[t]
            num=0
            if ord(ch)<=ord('9'):
                num=ord(ch)-ord('0')
            else:
                num=ord(ch)-ord('a')+10
            for k in range(5):
                if vb[i+k]!=(-1,-1) and (num>>(4-k))&1:
                    banpair.append([(vb[i+k][0]-1,vb[i+k][1]),(vb[i+k][0],vb[i+k][1])])
            t+=1
    return banpair

def tonum(w):
    if ord(w) <= ord('9') and ord(w)>=ord('0'):
        return ord(w) - ord('0')
    elif ord(w) <= ord('f') and ord(w) >= ord('a'):
        return ord(w) - ord('a') + 10
    else:
        assert False

def decodeshape(h,w,code):
    bits=[0]*(h*w)
    l=h*w
    for i in range(0,l-1,2):
        num=tonum(code[i//2])
        bits[i]=num&3
        bits[i+1]=(num&12)>>2
    for id in range(l):
        x=id%w
        y=id//w
        if x > 0 and (bits[y * w + x - 1] & 1):
            bits[id]|=4
        if y > 0 and (bits[(y - 1) * w + x] & 2):
            bits[id]|=8
    nid=[-1]*(h*w)
    seg=[]
    cnt=0
    for id in range(l):
        if not bits[id] in [0,5,10]:
            nid[id]=cnt
            cnt+=1
    for id in range(l):
        if nid[id]==-1:
            continue
        if bits[id]&1:
            y=id+1
            while nid[y]==-1:
                y+=1
            seg.append((0,nid[id],nid[y]))
        if bits[id]&2:
            y=id+w
            while nid[y]==-1:
                y+=w
            seg.append((1,nid[id],nid[y]))
    return (cnt,seg)

def convert(url):
    part = url.split("curvedata")[1].split("/")[1:]
    if part[0]=="v:":
        part=part[1:]
    width = int(part[0])
    height = int(part[1])
    code = part[2]
    part = part[3:]
    border=[]
    while len(part)!=0 and part[0]=="":
        part = part[1:]
    if len(part)>0 and part[0][0]=='b':
        border = convertborder(part[0][1:], height, width)
        part=part[1:]
    assert(len(part)%3==0)
    pclue =[]
    for i in range(0,len(part),3):
        w = int(part[i])
        h = int(part[i+1])
        pclue.append(decodeshape(h, w, part[i+2]))

    clue = [[None for j in range(width)] for i in range(height)]
    def nextpos(px, py):
        return px + (py + 1) // width , (py + 1) % width
    l = 0
    px = 0
    py = 0
    while l < len(code):
        if ord(code[l])>=ord('g') and ord(code[l])<=ord('z'):
            for k in range(ord(code[l])-ord('g')):
                px, py = nextpos(px, py)
        elif code[l]=='=':
            clue[px][py] = (-1, )
        elif code[l]=='.':
            return 0,0,[],[]
        elif code[l]=='-':
            d=tonum(code[l+1])*16+tonum(code[l+2])
            clue[px][py]=pclue[d]
            l+=2
        else:
            d=tonum(code[l])
            clue[px][py]=pclue[d]
        l+=1
        px, py = nextpos(px, py)
    return height, width, clue,border

def solve_curve_data_url(url):
    height, width, clue, border = convert(url)
    if height == 0 or width == 0:
        return False, "not supported"
    is_sat, is_line = solve_curve_data(height, width, clue, border)
    return is_sat, is_line

def _main():
    if len(sys.argv) == 1:
        url = "https://puzz.link/p?curvedata/14/14/0g1g0g2zn3t4g5g6t7l8n9m4n2man2mcgbgdzzx01h02/3/3/9024/2/3/ba1/1/3/a/3/3/2aa5/3/3/c021/3/3/8430/2/3/b30/2/3/321/2/3/ba0/2/3/330/2/3/2b0/3/3/2630/3/3/bc95/3/3/7c05"
        is_sat, is_line = solve_curve_data_url(url)
        print('has answer:', is_sat)
        if is_sat:
            print(util.stringify_grid_frame(is_line))
            util.draw_grid_frame(is_line)

if __name__ == '__main__':
    _main()