Mercurial > hg > python
changeset 8:3276cf6ee6df
vastly simplified onePass, printing rows working
author | Henry S. Thompson <ht@inf.ed.ac.uk> |
---|---|
date | Wed, 11 Mar 2020 19:52:22 +0000 |
parents | 13f600be3a1b |
children | 28a7b0e992cb |
files | nono.py |
diffstat | 1 files changed, 59 insertions(+), 87 deletions(-) [+] |
line wrap: on
line diff
--- a/nono.py Wed Mar 11 17:13:05 2020 +0000 +++ b/nono.py Wed Mar 11 19:52:22 2020 +0000 @@ -14,7 +14,7 @@ Red='[31m' eRed='[39m' -RedFmt=Red+'%s'+eRed +RedFmt=Red+'%s '+eRed def interleave(*args): for vals in zip(*args): @@ -28,8 +28,8 @@ self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False self.marginN=n-1 # a run can end here, so if <n-1 then self[mN+1].val ditto self.runs=self.origRuns=runs - self.initialComplete="" - self.finalComplete="" + self.initialComplete=[] + self.finalComplete=[] self.resetAllRuns() def __repr__(self): @@ -70,14 +70,16 @@ def step(self): scratch=[0 if c.val is None else c.val for c in self] + wins=0 for k,runs in enumerate(self.allRuns): dprint('=====pass %s======'%k) - self.onepass(0,self.n,scratch,runs.copy()) - dprint(scratch) + if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()): + wins+=1 + dprint(wins, scratch) newSeq=False inSeq=False for i in range(self.n): - if scratch[i]==self.nar: + if scratch[i]==wins: # If blobby in _every_ pass, then must be a blob if inSeq: newSeq=False @@ -100,8 +102,7 @@ and possibly before the positive ones, indicating obligatory skips """ i=i0 # starting index into self/scratch/maybe - j=-1 # index into run - maybe=[0]*iBound + maybe=[0]*(iBound-i0) dprint('r: %s'%stack) req=sum((-r if r<0 else r) for r in stack) while stack and i<iBound: @@ -110,92 +111,52 @@ if r<1: # obligatory skip # (Above init of self.allRuns is easier if we allow a 0 to be ignored + for k in range(i,i-r): + if self[k] is True: + # has to be False or None to skip + dprint('x0',k) + return False i-=r req+=r r=rr=stack.pop(0) # rr is run remaining -- how many we still need - j+=1 # index of current run in self.runs, we'll need to decorate that eventually - inOne=-1 # if non-neg, records the start point of a possible run - gapsFilled=0 # First, check if we can start here: 0 is OK, and n>0 iff n-1 is None or False - if i>0 and i<iBound: - while self[i-1].val: - i+=1 + # if i>0 and self[i-1].val is True: + # dprint('x1',i) + # return if (iBound-i)<req: # Can't win, give up altogether - dprint('c0',i,iBound,req) - return - while i<iBound: + dprint('x2',i,iBound,req) + return False + j=i # start of run, if we find it + gapsFilled=0 + dprint('top:',j) + while rr>0: + # guaranteed by check above that we won't run over the far end c=self[i].val - dprint('top',i,c,inOne,rr) + if c is False: + dprint('x3',i) + return False if c is None: # we could add a blob here - dprint('c1') gapsFilled+=1 - rr-=1 - if inOne<0: - dprint('c1a',i) - # starts here - inOne=i - # fall through to check for completion - else: - dprint('c2') - # c is a bool - if inOne<0: - dprint('c2a') - if c: - dprint('c2a1') - # a *, we can possible start something here - inOne=i - rr-=1 - # fall through to check for completion - else: - dprint('c2a2') - # an x, can't start here, just move along - i+=1 - continue - else: - dprint('c2b') - if c: - dprint('c2b1') - # a blob, extend or complete a partial - rr-=1 - # fall through to check for completion - else: - # abandon a partial - dprint('c2b2') - inOne=-1 - rr=r - i+=1 - continue - if rr>0: - dprint('c3') - # we're not done, carry on - i+=1 - continue - # Maybe a win? - # look ahead, can we stop here? - # NB _self_.n - if i+1<self.n and self[i+1].val: - dprint('c4') - # Nope - inOne=-1 - rr=r - gapsFilled=0 - i+=1 - continue - elif gapsFilled==0: - dprint('c5') - # We must have crossed at least on gap... - print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s inOne:%s"%(self,i, j, rr, inOne),file=sys.stderr) - exit(100) - # Victory! - dprint('c6',r,inOne,i) - for k in range(inOne,i+1): - maybe[k]+=1 + # and a blob already present is OK + rr-=1 i+=1 - req-=r - break + # Maybe a win? + # look ahead, can we stop here? + if i<self.n and self[i].val is True: + dprint('x4',i) + return False + elif gapsFilled==0: + # We must have crossed at least one gap... + print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s"%(self,i, j, rr),file=sys.stderr) + raise Exception + # Victory! + dprint('c6',r,j,i) + for k in range(j,i): + maybe[k]+=1 + req-=r # on to the next run # end of inner loop, did we win? if (not stack) or i==iBound: @@ -203,6 +164,8 @@ dprint('win:',maybe) for k in range(iBound): scratch[k]+=maybe[k] + return True + print("Shouldn't happen? - fell through",stack,i,iBound) def checkNew(self,pos): # New blob at pos, can we complete anything? @@ -277,8 +240,9 @@ i+=1 if self[i].val is True: r=self.runs.pop(0) - self.initialComplete+=(RedFmt%r) + self.initialComplete.append(r) self.margin0+=r+1 + self.updateHeader(r=r) def foundN(self,i): print('foundN called on %s at %s'%(self,i),file=sys.stderr) @@ -293,9 +257,17 @@ return ((self.fmt%(' '.join(str(r) for r in self.runs)))+ Vector.__str__(self)) - def updateHeader(self,maxWidth): - self.maxWidth=maxWidth - self.fmt="%s%%s|"%(' '*(maxWidth-self.width)) + def updateHeader(self,maxWidth=None,r=None): + if maxWidth is None: + # update + self.infix+=RedFmt%r + self.fmt="%s%s%%s|"%(self.prespace,self.infix) + else: + # init + self.maxWidth=maxWidth + self.prespace=' '*(maxWidth-self.width) + self.fmt="%s%%s|"%self.prespace + self.infix="" def newBlob(self,x,newSeq): self[x].setVal(True) @@ -383,7 +355,7 @@ return "\n".join(lines) def dprint(*args): - pass + pass #print(*args) if __name__ == '__main__': if len(sys.argv)>1: