self_avoiding_polygon/sage/walk.py

class Walk:
    def __init__(self,str=None):
        if str!=None:
            self.__decompress__(str)

    def __decompress__(self,str):
        self.xmin=0
        self.xmax=0
        self.ymin=0
        self.ymax=0
        self.length=0
        x=0
        y=0
        self.steps=[]
        valid_steps=['l','r','u','b']
        i=0
        while i<len(str):
            s=str[i]
            if not s in valid_steps:
                raise AttributeError("Step '"+c+"' unkown")
            i+=1
            j=i
            if i<len(str):
                j=i
                v=0
                while i<len(str) and '0'<=str[i] and str[i]<='9':
                    v=v*10+ord(str[i])-ord('0')
                    i+=1
            if j==i:
                #No digits
                v=1
            self.length+=v
            for k in range(v):
                self.steps.append(s)
            if s=='l':
                x+=v
                self.xmax=max(self.xmax,x)
            elif s=='r':
                x-=v
                self.xmin=min(self.xmin,x)
            elif s=='u':
                y+=v
                self.ymax=max(self.ymax,y)
            else: # s=='b'
                y-=v
                self.ymin=min(self.ymin,y)

    def show(self):
        G=Graphics()
        for x in range(self.xmin-1,self.xmax+2):
            G+=line2d([(x,self.ymin-1),(x,self.ymax+1)],thickness=1,rgbcolor=(0.5,0.5,0.5))
        for y in range(self.ymin-1,self.ymax+2):
            G+=line2d([(self.xmin-1,y),(self.xmax+1,y)],thickness=1,rgbcolor=(0.5,0.5,0.5))
        P=[(0,0)]
        x=0
        y=0
        for s in self.steps:
            if s=='l':
                x+=1
            elif s=='r':
                x-=1
            elif s=='u':
                y+=1
            else:
                y-=1
            P.append((x,y))
        G+=line2d(P,thickness=3)
        G.show(axes=False,aspect_ratio=1)

    def is_self_avoiding_polygon(self):
        x=0
        y=0
        v=set([(0,0)])
        l=0
        for s in self.steps:
            l+=1
            if s=='r':
                x+=1
            elif s=='l':
                x-=1
            elif s=='u':
                y+=1
            else:
                y-=1
            if l<self.length and (x,y) in v:
                return False
            if l==self.length:
                return (x,y)==(0,0)

    def polygon(self):
        if not self.is_self_avoiding_polygon():
            raise RuntimeError("This walk is not a self avoiding polygon")
        print("Ok lets go")