Mercurial > hg > python
view nono.py @ 55:68004ce55703
convert to newer source of Nonogram data
author | Henry Thompson <ht@markup.co.uk> |
---|---|
date | Mon, 29 May 2023 22:24:53 +0100 |
parents | 6c9e371b0325 |
children | 40273cb7c7fc |
line wrap: on
line source
#!/usr/bin/python3 # Expects e.g. ^A copy from Nonograms dprint preview cols, then blank line, then rows # rows are space-separated # cols are one-digit-after-another, unless some 2-digit, in which case x is separator # E.g. # 13x1x2 # 19 # maps to # 13 # 1 1 # 2 9 # New version, input taken from Nonograms Outer HTML plus # > fgrep 'task = ' nono10.xhtml|tr ';' '\n' | fgrep task\ = | sed 's/^.*= //'| tr -d \' # E.g. 8/5.1/2.3/2.1/4.3/3.4/2/1.1/3/5.2/2.2/2.2/1.3.2/5.1/3.1.1/2/2.3.1/7.1/1.1.2/3.2 import sys Red='[31m' eRed='[39m' RedFmt=Red+'%s'+eRed def interleave(*args): for vals in zip(*args): yield from vals class Vector(list): # reads top-to-bottom or left-to-right def __init__(self,n,m,runs): list.__init__(self,list(range(n))) self.n=n # size self.m=m # parent NoNo 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.resetAllRuns() def __repr__(self): return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self)) def __str__(self): return '%s|'%('|'.join(str(c) for c in self)) def myPrintSize(self): return sum(len(str(run)) for run in self.runs)+len(self.runs)-1 def resetAllRuns(self): # compute the set of all possible layouts for runs self.rn=len(self.runs) rtot=sum(self.runs) self.allRuns=list(self.seedList(0,0,self.margin0,self.marginN+1, sum(1+self.runs[k] for k in range(self.rn))-1)) self.nar=len(self.allRuns) def seedList(self,i,j,pos0,posN,runLen): """ :param i: starting skip before next run :type i: 0 if pos==0 else 1 :param j: next run number :type j: int :param pos0: left margin :type pos0: int :param posN: right margin :type posN: int :return: list of runlens separated, possibly prefixed, with skips as negative integers """ bound=posN-(pos0+runLen)+1 dprint('s',i,j,pos0,posN,runLen,bound) if j==self.rn: yield [] return r=self.runs[j] for v in range(i,bound): for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)): yield [-v,r]+sub def step(self,pos): if self.runs==[]: return 0 scratch=[0 if c.val is None else c.val for c in self] wins=0 changed=0 for k,runs in enumerate(self.allRuns): if (self.m.loop,self.cLet,pos,k)==(1,'R',7,5): print(self.m) dprint('=====pass %s.%s.%s.%s======'%(self.m.loop,self.cLet,pos,k)) if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()): wins+=1 dprint(wins, scratch) maybeSeq=None inSeq=None j=None for i in range(self.n): if scratch[i]>=wins: # If blobby in _every_ pass, then must be a blob if inSeq is None: inSeq=i if maybeSeq is None else maybeSeq dprint('s1',inSeq) maybeSeq=None if self[i].val is None: dprint('s1a',i) self.newBlob(i,True) # Check cross-vector j=i changed=1 elif self[i].val is True: pass else: eprint("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),err=101) elif inSeq is not None: if self[i].val is not True: inSeq=None maybeSeq=None dprint('s2',i-1,j) if j is not None: # Only if we actually added a blob at some point dpush('b_s2') self.checkNew(i-1) dpop('b_s2') elif self[i].val is True and maybeSeq is None: dprint('s3',i) maybeSeq=i dprint('s4',inSeq,i) if inSeq is not None: dpush('b_s4') self.checkNew(i) dpop('b_s4') return changed def onepass(self,i0,iBound,scratch,stack): """note that stack is not a simple run, but one with _negative_ numbers between and possibly before the positive ones, indicating obligatory skips """ i=i0 # starting index into self/scratch/maybe maybe=[0]*self.n dprint('r: %s'%stack,i0,iBound) req=sum((-r if r<0 else r) for r in stack) while stack and i<iBound: r=rr=stack.pop(0) dprint('pop:',r) 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 # First, check if we can start here: 0 is OK, and n>0 iff n-1 is None or False # 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('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 if c is False: dprint('x3',i) return False if c is None: # we could add a blob here gapsFilled+=1 # and a blob already present is OK rr-=1 i+=1 # 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: # yes dprint('win:',maybe) for k in range(iBound): scratch[k]+=maybe[k] return True eprint("Shouldn't happen? - fell through",stack,i,iBound,err=102) def checkX(self,pos,crosspos): # New x at pos, are there others that can be xed out now? # Overkill as is? dprint('cx',self.cLet+str(crosspos),pos) if self.runs: start0=self.margin0 # 0 if self.margin0==0 else self.margin0+1 if self.marginal(range(start0,pos),self.runs[0]): dprint('cx1a') else: dprint('cx1b') # if len(self.runs)>1: startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1 if self.marginal(range(startN,pos,-1),self.runs[-1]): dprint('cx2a') else: dprint('cx2b') def checkNew(self,pos): # New blob at pos, can we complete anything? # Assuming @@ FTTB that it's never possible to definitively complete a # non-marginal run, which is wrong if the length is unique and it's bounded... start0=self.margin0 #0 if self.margin0==0 else self.margin0+1 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1 dprint('cn',start0,pos,startN) changed=False # First, find our boundaries: s=pos # start index of our run if s>start0: while s>start0 and self[s-1].val is True: s-=1 f=pos # finish index of our run if f<startN: while f<startN and self[f+1].val is True: f+=1 l=(f-s)+1 # our length dprint('%s:%s,%s,%s,%s:<%s>'%(self.cLet,s,f,l,self.runs,self)) c=self.runs.count(l) if c==0: # not big enough yet dprint('x0') return if self.runs[0]==l: # is it safely left marginal, i.e. no blobs or big enough gaps before us? if self.marginal(range(start0,s),l): changed=True dprint('n1') # mark our margins for i in range(start0,s): # not sure this is still needed since # added gap-filling in self.marginal if self[i].val is None: self.newX(i,False) if f<startN: if self[f+1].val is None: self.newX(f+1,True) self.found0(f) # pull in the start margin at least to f+2 else: dprint('x1a') if not changed: if self.runs[-1]==l: # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us? if self.marginal(range(startN,f,-1),l): changed=True dprint('n2') # mark our margins: still needed? see above for i in range(startN,f,-1): if self[i].val is None: self.newX(i,False) if s>start0: if self[s-1].val is None: self.newX(s-1,True) self.foundN(s) # pull in the finish margin at least to s-2 else: dprint('x2a') else: dprint('x2b') if changed: self.resetAllRuns() def marginal(self,rng,l): dprint('m%s'%self.cLet,rng.start,rng.stop,rng.step,l) g=0 # length of a gap for i in rng: if self[i].val is True: # Shouldn't be possible? dprint('mx0') return False if self[i].val is False: if g>0: # Block a too-small gap dprint('m1',i-g,i) for j in range(i-g,i): self.newX(j,True) g=0 else: # None g+=1 if g==l: # run could fit here, so no go dprint('mx1') return False if g>0: # Block a too-small gap if rng.step==1: # forward dprint('m2f',i-g,i) for j in range(i+1-g,i+1): self.newX(j,True) else: # backward dprint('m2b',i+g,i) for j in range(i+g-1,i-1,-1): self.newX(j,True) return True def found0(self,i): dprint('found0 called on %s at %s'%(self,i)) i=self.margin0 while self[i].val is False: i+=1 if self[i].val is True: r=self.runs.pop(0) self.initialComplete.append(r) self.margin0+=r+1 self.updateHeader(r=r,pre=True) def foundN(self,i): dprint('foundN called on %s at %s'%(self,i)) i=self.marginN while self[i].val is False: i-=1 if self[i].val is True: r=self.runs.pop() self.finalComplete=[r]+self.finalComplete self.marginN-=r+1 self.updateHeader(r=r,pre=False) class Row(Vector): cLet='R' def __init__(self,n,m,runs,pos): Vector.__init__(self,n,m,runs) self.y=pos self.width=self.myPrintSize() def __str__(self): return ((self.fmt%(' '.join(str(r) for r in self.runs)))+ Vector.__str__(self)) def updateHeader(self,*,maxWidth=None,r=None,pre=None): if maxWidth is None: # update spacer=(" " if self.runs else "") if pre: self.infix+=(RedFmt%r)+spacer else: # post self.suffix=spacer+RedFmt%r+self.suffix self.fmt="%s%s%%s%s|"%(self.prespace,self.infix,self.suffix) else: # init self.maxWidth=maxWidth self.prespace=' '*(maxWidth-self.width) self.fmt="%s%%s|"%self.prespace self.infix="" self.suffix="" def newBlob(self,x,crossCheck=False): self[x].setVal(True) if crossCheck: dpush('b_cc') self[x].column.checkNew(self.y) dpop('b_cc') def newX(self,x,crossCheck=False): dprint('nx %s%s@%s'%('R',self.y,x)) self[x].setVal(False) if crossCheck: dpush('x_cc') self[x].column.checkX(self.y,x) dpop('x_cc') class Column(Vector): cLet='C' def __init__(self,n,m,runs,pos): Vector.__init__(self,n,m,runs) self.x=pos self.height=self.myPrintSize() def updateHeader(self,*,maxHeight=None,r=None,pre=None): dprint('CuH',r,pre) if maxHeight is None: # update if pre: for rc in str(r): self.infix.append(RedFmt%rc) if self.runs: self.infix.append('-') else: # post ins=["-"] if self.runs else [] for rc in str(r): ins.append(RedFmt%r) self.suffix=ins+self.suffix dprint('CuH1: |%s|,%s,%s,%s'%(self.prespace,self.infix,self.suffix,self.runs)) self.header=([" "]*self.prespace)+\ self.infix+\ (['-'.join(str(c) for c in self.runs)] if self.runs else [])+\ self.suffix else: # init self.maxHeight=maxHeight self.infix=[] self.suffix=[] self.prespace=maxHeight - self.height # pad to same 'height' self.fmt="%s%%s"%(' '*self.prespace) header=('-'.join(str(c) for c in self.runs)) self.header=self.fmt%header dprint(self.header) def newBlob(self,y,crossCheck=False): self[y].setVal(True) if crossCheck: dpush('b_cc') self[y].row.checkNew(self.x) dpop('b_cc') def newX(self,y,crossCheck=False): dprint('nx %s%s@%s'%('C',self.x,y)) self[y].setVal(False) if crossCheck: dpush('x_cc') self[y].row.checkX(self.x,y) dpop('x_cc') class Cell: def __init__(self,row,y,column,x): # At the intersection of row and column Vectors self.row=row self.column=column self.x=x self.y=y self.val=None # three valued: None(unknown), True(filled), False(empty) self.row[x]=self self.column[y]=self def __repr__(self): return "C@(%s,%s):%s"%(self.x,self.y,self.val) def __str__(self): return ' ' if self.val is None else ('\u25A0' if self.val else 'x') def setVal(self,v): if v is True: if self.val is False: wprint("Warning: x -> * at %s,%s"%(self.x,self.y)) elif self.val is True: # No-op return self.val=v else: if self.val is not None: wprint("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y)) self.val=v class Nono(dict): # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout def __init__(self,runsPerRow,runsPerCol): global SOLVER self.loop=0 self.dp='' self.dstate=[] SOLVER=self n=self.n=len(runsPerCol) if n!=len(runsPerRow): print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr) exit(1) self.rc=runsPerRow self.cc=runsPerCol # print col nums>9 vertically :-( self.columns=cc=[Column(n,self,runsPerCol[i],i) for i in range(n)] self.maxCRheight=maxCRheight=max(col.height for col in cc) for c in cc: c.updateHeader(maxHeight=maxCRheight) self.rows=rr=[Row(n,self,runsPerRow[i],i) for i in range(n)] maxRRwidth=max(row.width for row in rr) for r in rr: r.updateHeader(maxWidth=maxRRwidth) self.rowfmt="%s|%%s|"%(' '*maxRRwidth) for x in range(n): for y in range(n): self[(x,y)]=Cell(rr[y],y,cc[x],x) def __str__(self): lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate' for j in range(self.maxCRheight)] lines+=[str(r) for r in self.rows] return "\n".join(lines) def solve(self): someChanged=1 while someChanged>0: self.loop+=1 someChanged=0 dprint("***Solve C %s***"%self.loop) for c in self.columns: someChanged+=c.step(c.x) print(someChanged) print(self) dprint("***Solve R %s***"%self.loop) for r in self.rows: someChanged+=r.step(r.y) print(someChanged) print(self) def dpush(s): SOLVER.dp+=' ' SOLVER.dstate.append(s) def dpop(s): assert(SOLVER.dstate.pop()==s) SOLVER.dp=SOLVER.dp[1:] def dprint(*args): print(SOLVER.dp,end='') print(*args) sys.stdout.flush() def eprint(*args,**kw): print(*args,file=sys.stderr) sys.stderr.flush() exit(kw['err']) def wprint(*args): print(*args,file=sys.stderr) sys.stderr.flush() if __name__ == '__main__': if len(sys.argv)>1: f=open(sys.argv[1]) else: f=sys.stdin l = f.readline().rstrip() vv=l.split('/') n=int(len(vv)/2) print('%sx%s puzzle'%(n,n),file=sys.stderr) cols=[[int(i) for i in v.split('.')] for v in vv[:n]] rows=[[int(i) for i in v.split('.')] for v in vv[n:]] solver=Nono(rows,cols) solver.solve()