Mercurial > hg > python
view nono.py @ 71:eea4bcb657bc simple
Pruned back to pass 0
| author | Henry Thompson <ht@markup.co.uk> |
|---|---|
| date | Fri, 18 Jul 2025 21:54:39 +0100 |
| parents | 578cb569d815 |
| children | 15e540c190d5 |
line wrap: on
line source
#!/usr/bin/python3 # 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 class Run: '''What we're looking for, converted eventually into what we've found. "left" and "right" make sense for Rows, for Columns read "above" and "below"''' def __init__(self,n,i,j): # A run of length n, starting within [i,j] self.n=n self.i=i self.j=j self.s=j-i self.done=False self.left=self.right=None def leftEdge(self): return self.i def rightEdge(self): if self.done: return self.i+self.n-1 return self.j+self.n-1 def __str__(self): return str(self.n) class Space: def __init__(self,n,i,j): # A space of length 1..n, starting within [i,j] # Once done, length == n # i and j don't change, but s, which is used by check0 # to decide where to look, is optimistic and may need to # be restricted if there is an overlap with the next (forward or backward) # run (see self.right and self.left, if any, respectively) assert n>0 self.n=n self.i=i self.j=j self.s=j-i self.done=False def __str__(self): return '' class Vector(list): # reads top-to-bottom or left-to-right def __init__(self,n,m): 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 def initRuns(self,runs): # Set runs to alternating list of Run and Skip self.rn=len(runs) self.runs=[] if self.rn==0: # No runs means a vector of x for c in self: c.setVal(False) else: need=sum(1+runs[k] for k in range(self.rn))-1 space=self.n-need pos=0 while runs: self.runs.append(Run(r:=runs.pop(0),pos,pos+space)) pos+=r if runs: self.runs.append(Space(space,pos,pos+space)) pos+=1 # Adjacent pairs mutually restrict possible starting points for i in range(0,self.rn-1): left=self.runs[2*i] right=self.runs[(2*i)+2] left.right=right right.left=left self.initDisp() def __str__(self): return '%s|'%('|'.join(str(c) for c in self)) def myPrintSize(self): return sum((len(str(run)) if isinstance(run,Run) else 1) for run in self.runs) def pass0(self): # simple first pass down/across a row for i in range(0,len(self.runs),2): run=self.runs[i] for p in range(run.i+run.s,run.i+run.n): self[p].setVal(True) def check0(self): # Check 1st and last not-done runs for completeness # Have to restrict lookahead/behind if there's overlap between runs... # Forwards # ****Assumes margin0 is 0***** and marginN is n for i in range(0,len(self.runs),2): run=self.runs[i] if not run.done: # look for first True cell for p in range(run.i,min(run.i+run.s+1, run.right.leftEdge()-run.n if (run.right and run.i>run.n) else 100)): if self[p].val: if p>0 and self[p-1].val==False: # We're pinned, force start here from now on self.i=p self.s=p+1 self.right=None #Maybe? l=self.trueRun(p,run.n) if l==run.n: if p!=0: self[p-1].setVal(False) e=p+l if e!=self.n: self[e].setVal(False) break break # and backwards m=len(self.runs)-1 # if isinstance(self,Column) and self.x==3: # breakpoint() for i in range(0,m+1,2): run=self.runs[m-i] if not run.done: # look for first True cell for p in range(run.i+run.s+(run.n-1), max(run.i-1,run.left.rightEdge()+run.n if (run.left and run.i<self.n-run.n) else 0),-1): if self[p].val: if p<self.n-1 and self[p+1]==False: self.i=p self.s=p+1 self.left=None # Maybe? l=self.trueRun(p,run.n,-1) if l==run.n: e=p-l if e!=0: self[e].setVal(False) if p+1!=self.n: self[p+1].setVal(False) break break def trueRun(self,p,n,delta=1): res=0 for i in range(p,p+(delta*n),delta): if self[i].val: res+=1 else: break return res class Row(Vector): cLet='R' def __init__(self,n,m,pos): Vector.__init__(self,n,m) self.y=pos def __repr__(self): return "R@%s%s:%s"%(self.y,self.runs,list.__repr__(self)) def initDisp(self): self.width=self.myPrintSize() def __str__(self): return ((self.fmt%(' '.join(str(r) for r in self.runs if isinstance(r,Run))))+ 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="" class Column(Vector): cLet='C' def __init__(self,n,m,pos): Vector.__init__(self,n,m) self.x=pos def __repr__(self): return "C@%s%s:%s"%(self.x,self.runs,list.__repr__(self)) def initDisp(self): 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 if isinstance(c,Run))) self.header=self.fmt%header dprint(self.header) 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): # Returns true iff old value was None assert v in (True, False) if v == self.val: return False if self.val is not None: eprint("Reset not allowed: %s -> %s at %s,%s"%(self.val, v, self.x,self.y),err=103) self.val=v return True class Nono(dict): # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout def __init__(self,runsPerRow,runsPerCol,debug): global SOLVER self.loop=0 self.dp='' # old depth hack self.debug = debug 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,i) for i in range(n)] self.rows=rr=[Row(n,self,i) for i in range(n)] for x in range(n): for y in range(n): self[(x,y)]=Cell(rr[y],y,cc[x],x) # Need cells in place for the following for row,runs in zip(rr,runsPerRow): row.initRuns(runs) for col,runs in zip(cc,runsPerCol): col.initRuns(runs) self.maxCRheight=maxCRheight=max(col.height for col in cc) for c in cc: c.updateHeader(maxHeight=maxCRheight) maxRRwidth=max(row.width for row in rr) for r in rr: r.updateHeader(maxWidth=maxRRwidth) self.rowfmt="%s|%%s|"%(' '*maxRRwidth) 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 pass0(self): # do columns of empty layout for c in self.columns: c.pass0() dprint('After Pass 0 for columns', self, sep = '\n') for r in self.rows: r.pass0() dprint('After Pass 0 for rows', self, sep = '\n') for c in self.columns: c.check0() dprint('After Check 0 for columns', self, sep = '\n') dprint(self) for r in self.rows: r.check0() dprint('After Check 0 for rows', self, sep = '\n') def solve(self): self.pass0() def dprint(*args, **kwargs): '''Debug print''' if SOLVER.debug: print(*args, **kwargs) sys.stdout.flush() def eprint(*args,**kw): '''error print''' print(*args,file=sys.stderr) sys.stderr.flush() print(SOLVER) breakpoint() exit(kw['err']) if __name__ == '__main__': if sys.argv[1] == '-d': sys.argv.pop(1) debug = True else: debug = False 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, debug) print(solver) print() solver.solve() print('Done',solver, sep = '\n')
