Mercurial > hg > python

comparison nono.py @ 7:13f600be3a1b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implemented newBlob and found0, refactoring display
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Wed, 11 Mar 2020 17:13:05 +0000
parents a56d5285575b
children 3276cf6ee6df
comparison
equal deleted inserted replaced
6:a56d5285575b 7:13f600be3a1b
26 list.__init__(self,list(range(n))) 26 list.__init__(self,list(range(n)))
27 self.n=n 27 self.n=n
28 self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False 28 self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False
29 self.marginN=n-1 # a run can end here, so if <n-1 then self[mN+1].val ditto 29 self.marginN=n-1 # a run can end here, so if <n-1 then self[mN+1].val ditto
30 self.runs=self.origRuns=runs 30 self.runs=self.origRuns=runs
31 self.initialComplete=[] 31 self.initialComplete=""
32 self.finalComplete=[] 32 self.finalComplete=""
33 self.resetAllRuns() 33 self.resetAllRuns()
34 34
35 def __repr__(self): 35 def __repr__(self):
36 return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self)) 36 return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self))
37 37
38 def __str__(self): 38 def __str__(self):
39 return '%s|'%('|'.join(str(c) for c in self)) 39 return '%s|'%('|'.join(str(c) for c in self))
40
41 def myPrintSize(self):
42 return sum(len(str(run)) for run in self.runs)+len(self.runs)-1
40 43
41 def resetAllRuns(self): 44 def resetAllRuns(self):
42 # compute the set of all possible layouts for runs 45 # compute the set of all possible layouts for runs
43 self.rn=len(self.runs) 46 self.rn=len(self.runs)
44 rtot=sum(self.runs) 47 rtot=sum(self.runs)
69 scratch=[0 if c.val is None else c.val for c in self] 72 scratch=[0 if c.val is None else c.val for c in self]
70 for k,runs in enumerate(self.allRuns): 73 for k,runs in enumerate(self.allRuns):
71 dprint('=====pass %s======'%k) 74 dprint('=====pass %s======'%k)
72 self.onepass(0,self.n,scratch,runs.copy()) 75 self.onepass(0,self.n,scratch,runs.copy())
73 dprint(scratch) 76 dprint(scratch)
77 newSeq=False
78 inSeq=False
74 for i in range(self.n): 79 for i in range(self.n):
75 if scratch[i]==self.nar: 80 if scratch[i]==self.nar:
76 # If blobby in _every_ pass, then must be a blob 81 # If blobby in _every_ pass, then must be a blob
82 if inSeq:
83 newSeq=False
84 else:
85 inSeq=True
86 newSeq=True
77 if self[i].val is None: 87 if self[i].val is None:
78 self[i].setVal(True) 88 self.newBlob(i,newSeq)
79 elif self[i].val is True: 89 elif self[i].val is True:
80 # already there 90 # already there
81 pass 91 pass
82 else: 92 else:
83 print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr) 93 print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr)
84 exit(101) 94 exit(101)
95 else:
96 inSeq=newSeq=False
85 97
86 def onepass(self,i0,iBound,scratch,stack): 98 def onepass(self,i0,iBound,scratch,stack):
87 """note that stack is not a simple run, but one with _negative_ numbers between 99 """note that stack is not a simple run, but one with _negative_ numbers between
88 and possibly before the positive ones, indicating obligatory skips 100 and possibly before the positive ones, indicating obligatory skips
89 """ 101 """
197 # Assuming @@ FTTB that it's never possible to definitively complete a 209 # Assuming @@ FTTB that it's never possible to definitively complete a
198 # non-marginal run, which is wrong if the length is unique and it's bounded... 210 # non-marginal run, which is wrong if the length is unique and it's bounded...
199 changed=False 211 changed=False
200 # First, find our boundaries: 212 # First, find our boundaries:
201 s=pos # start index of our run 213 s=pos # start index of our run
202 while s>self.marginO and self[s-1].val is True: 214 while s>self.margin0 and self[s-1].val is True:
203 s-=1 215 s-=1
204 f=pos # finish index of our run 216 f=pos # finish index of our run
205 while f<self.marginN and self[f+1].val is True: 217 while f<self.marginN and self[f+1].val is True:
206 f+=1 218 f+=1
207 l=(f-s)+1 # our length 219 l=(f-s)+1 # our length
211 dprint('n0') 223 dprint('n0')
212 return 224 return
213 j=self.runs.index(l) 225 j=self.runs.index(l)
214 if j==0: 226 if j==0:
215 # is it safely left marginal, i.e. no blobs or big enough gaps before us? 227 # is it safely left marginal, i.e. no blobs or big enough gaps before us?
216 if marginal(range(self.margin0,s)): 228 if self.marginal(range(self.margin0,s),l):
217 changed=True 229 changed=True
218 # mark our margins 230 # mark our margins
219 for i in range(margin0+1,s): 231 for i in range(self.margin0+1,s):
220 if self[i].val is None: 232 if self[i].val is None:
221 self[i].setVal(False) 233 self[i].setVal(False)
222 if f<marginN-1: 234 if f<self.marginN-1:
223 if self[f+1].val is None: 235 if self[f+1].val is None:
224 self[f+1].setVal(False) 236 self[f+1].setVal(False)
225 if f<marginN-2 and self[f+2].val is True: 237 if f<self.marginN-2 and self[f+2].val is True:
226 dprint('n1') 238 dprint('n1')
227 self.checkNew(f+2) # I think@@ 239 self.checkNew(f+2) # I think@@
228 self.found0(f) # pull in the start margin at least to f+2 240 self.found0(f) # pull in the start margin at least to f+2
229 elif j==self.rn-1: 241 elif j==self.rn-1:
230 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us? 242 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
231 if self.marginal(range(self.marginN-1,r,-1),l): 243 if self.marginal(range(self.marginN-1,r,-1),l):
232 changed=True 244 changed=True
233 # mark our margins 245 # mark our margins
234 for i in range(marginN-1,f,-1): 246 for i in range(self.marginN-1,f,-1):
235 if self[i].val is None: 247 if self[i].val is None:
236 self[i].setVal(False) 248 self[i].setVal(False)
237 if s>margin0+1: 249 if s>self.margin0+1:
238 if self[s-1].val is None: 250 if self[s-1].val is None:
239 self[s-1].setVal(False) 251 self[s-1].setVal(False)
240 if s>margin0+2 and self[s-2].val is True: 252 if s>self.margin0+2 and self[s-2].val is True:
241 dprint('n2') 253 dprint('n2')
242 self.checkNew(s-2) # I think@@ 254 self.checkNew(s-2) # I think@@
243 self.foundN(s) # pull in the finish margin at least to s-2 255 self.foundN(s) # pull in the finish margin at least to s-2
244 if changed: 256 if changed:
245 self.resetAllRuns() 257 self.resetAllRuns()
256 g+=1 268 g+=1
257 if g==l: 269 if g==l:
258 return False 270 return False
259 return True 271 return True
260 272
273 def found0(self,i):
274 dprint('found0 called on %s at %s'%(self,i))
275 i=self.margin0
276 while self[i].val is False:
277 i+=1
278 if self[i].val is True:
279 r=self.runs.pop(0)
280 self.initialComplete+=(RedFmt%r)
281 self.margin0+=r+1
282
283 def foundN(self,i):
284 print('foundN called on %s at %s'%(self,i),file=sys.stderr)
285
261 class Row(Vector): 286 class Row(Vector):
262 def __init__(self,n,m,runs,pos,dprintWidth): 287 def __init__(self,n,m,runs,pos):
263 Vector.__init__(self,n,m,runs) 288 Vector.__init__(self,n,m,runs)
264 self.y=pos 289 self.y=pos
265 self.dprintWidth=dprintWidth 290 self.width=self.myPrintSize()
266 self.fmt="%%%ss|"%dprintWidth
267 291
268 def __str__(self): 292 def __str__(self):
269 return ((self.fmt%(' '.join(str(r) for r in self.runs)))+ 293 return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
270 Vector.__str__(self)) 294 Vector.__str__(self))
271 295
296 def updateHeader(self,maxWidth):
297 self.maxWidth=maxWidth
298 self.fmt="%s%%s|"%(' '*(maxWidth-self.width))
299
300 def newBlob(self,x,newSeq):
301 self[x].setVal(True)
302 self[x].column.checkNew(self.y)
303 if newSeq:
304 # We don't always check ourself, to avoid unnecessary duplication...
305 self.checkNew(x)
306
272 class Column(Vector): 307 class Column(Vector):
273 def __init__(self,n,m,runs,pos,dprintHeight): 308 def __init__(self,n,m,runs,pos):
274 Vector.__init__(self,n,m,runs) 309 Vector.__init__(self,n,m,runs)
275 self.x=pos 310 self.x=pos
276 self.dprintHeight=dprintHeight 311 self.height=self.myPrintSize()
277 self.fmt="%%%ss"%self.dprintHeight 312
278 self.updateHeader() 313 def updateHeader(self,maxHeight):
279 314 self.maxHeight=maxHeight
280 def updateHeader(self): 315 self.fmt="%s%%s"%(' '*(maxHeight - self.height))
281 header=('-'.join(str(c) for c in self.runs)) 316 header=('-'.join(str(c) for c in self.runs))
282 self.header=self.fmt%header # pad to same 'height' 317 self.header=self.fmt%header # pad to same 'height'
318
319 def newBlob(self,y,newSeq):
320 self[y].setVal(True)
321 self[y].row.checkNew(self.x)
322 if newSeq:
323 # We don't always check ourself, to avoid unnecessary duplication...
324 self.checkNew(y)
283 325
284 class Cell: 326 class Cell:
285 def __init__(self,row,y,column,x): 327 def __init__(self,row,y,column,x):
286 # At the intersection of row and column Vectors 328 # At the intersection of row and column Vectors
287 self.row=row 329 self.row=row
304 print("Warning: x -> * at %s,%s"%(self.x,self.y),file=sys.stderr) 346 print("Warning: x -> * at %s,%s"%(self.x,self.y),file=sys.stderr)
305 elif self.val is True: 347 elif self.val is True:
306 # No-op 348 # No-op
307 return 349 return
308 self.val=v 350 self.val=v
309 self.row.checkNew(self.x)
310 self.column.checkNew(self.y)
311 # @@ check row/col completed
312 else: 351 else:
313 if self.val is not None: 352 if self.val is not None:
314 print("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y),file=sys.stderr) 353 print("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y),file=sys.stderr)
315 self.val=v 354 self.val=v
316 355
317 class Nono(dict): 356 class Nono(dict):
318 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout 357 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
319 def __init__(self,rows,cols): 358 def __init__(self,runsPerRow,runsPerCol):
320 n=self.n=len(cols) 359 n=self.n=len(runsPerCol)
321 if n!=len(rows): 360 if n!=len(runsPerRow):
322 print("losing r:%s x c:%s"%(len(rows),n),sys.stderr) 361 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr)
323 exit(1) 362 exit(1)
324 self.rc=rows 363 self.rc=runsPerRow
325 rowDprintWidth=max(sum(len(str(r)) for r in row)+len(row)-1 for row in rows) 364 self.cc=runsPerCol
326 self.rowfmt="%s|%%s"%(' '*rowDprintWidth) 365 # print col nums>9 vertically :-(
327 self.cc=cols 366 self.columns=cc=[Column(n,self,runsPerCol[i],i) for i in range(20)]
328 # dprint col nums>9 vertically :-( 367 self.maxCRheight=maxCRheight=max(col.height for col in cc)
329 self.colDprintHeight=max(sum(len(str(c)) for c in col)+len(col)-1 for col in cols) 368 for c in cc:
330 self.columns=cc=[Column(n,self,cols[i],i,self.colDprintHeight) for i in range(20)] 369 c.updateHeader(maxCRheight)
331 self.rows=rr=[Row(n,self,rows[i],i,rowDprintWidth) for i in range(20)] 370 self.rows=rr=[Row(n,self,runsPerRow[i],i) for i in range(20)]
371 maxRRwidth=max(row.width for row in rr)
372 for r in rr:
373 r.updateHeader(maxRRwidth)
374 self.rowfmt="%s|%%s|"%(' '*maxRRwidth)
332 for x in range(20): 375 for x in range(20):
333 for y in range(20): 376 for y in range(20):
334 self[(x,y)]=Cell(rr[y],y,cc[x],x) 377 self[(x,y)]=Cell(rr[y],y,cc[x],x)
335 378
336 def __str__(self): 379 def __str__(self):
337 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate' 380 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
338 for j in range(self.colDprintHeight)] 381 for j in range(self.maxCRheight)]
339 lines+=[str(r) for r in self.rows] 382 lines+=[str(r) for r in self.rows]
340 return "\n".join(lines) 383 return "\n".join(lines)
341 384
342 def dprint(*args): 385 def dprint(*args):
343 pass 386 pass