Mercurial > hg > python

comparison nono.py @ 13:70993b538ddb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
works on 5a
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Fri, 20 Mar 2020 19:15:42 +0000
parents ede2551ae7d9
children 1e961cf10f88
comparison
equal deleted inserted replaced
12:ede2551ae7d9 13:70993b538ddb
23 class Vector(list): 23 class Vector(list):
24 # reads top-to-bottom or left-to-right 24 # reads top-to-bottom or left-to-right
25 def __init__(self,n,m,runs): 25 def __init__(self,n,m,runs):
26 list.__init__(self,list(range(n))) 26 list.__init__(self,list(range(n)))
27 self.n=n 27 self.n=n
28 self.m=m
28 self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False 29 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 30 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 31 self.runs=self.origRuns=runs
31 self.initialComplete=[] 32 self.initialComplete=[]
32 self.finalComplete=[] 33 self.finalComplete=[]
68 r=self.runs[j] 69 r=self.runs[j]
69 for v in range(i,bound): 70 for v in range(i,bound):
70 for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)): 71 for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)):
71 yield [-v,r]+sub 72 yield [-v,r]+sub
72 73
73 def step(self): 74 def step(self,pos):
74 if self.runs==[]: 75 if self.runs==[]:
75 return 0 76 return 0
76 scratch=[0 if c.val is None else c.val for c in self] 77 scratch=[0 if c.val is None else c.val for c in self]
77 wins=0 78 wins=0
78 changed=0 79 changed=0
79 for k,runs in enumerate(self.allRuns): 80 for k,runs in enumerate(self.allRuns):
80 dprint('=====pass %s======'%k) 81 dprint('=====pass %s.%s.%s.%s======'%(self.m.loop,self.cLet,pos,k))
81 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()): 82 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
82 wins+=1 83 wins+=1
83 dprint(wins, scratch) 84 dprint(wins, scratch)
85 dprint('r40',self.m.rows[4])
84 maybeSeq=None 86 maybeSeq=None
85 inSeq=None 87 inSeq=None
86 for i in range(self.n): 88 for i in range(self.n):
87 if scratch[i]==wins: 89 if scratch[i]>=wins:
88 # If blobby in _every_ pass, then must be a blob 90 # If blobby in _every_ pass, then must be a blob
89 if inSeq is None: 91 if inSeq is None:
90 inSeq=i if maybeSeq is None else maybeSeq 92 inSeq=i if maybeSeq is None else maybeSeq
91 dprint('s1',inSeq) 93 dprint('s1',inSeq)
92 maybeSeq=None 94 maybeSeq=None
109 dprint('s3',i) 111 dprint('s3',i)
110 maybeSeq=i 112 maybeSeq=i
111 dprint('s4',inSeq,i) 113 dprint('s4',inSeq,i)
112 if inSeq is not None: 114 if inSeq is not None:
113 self.checkNew(i) 115 self.checkNew(i)
116 dprint('r41',self.m.rows[4])
114 return changed 117 return changed
115 118
116 def onepass(self,i0,iBound,scratch,stack): 119 def onepass(self,i0,iBound,scratch,stack):
117 """note that stack is not a simple run, but one with _negative_ numbers between 120 """note that stack is not a simple run, but one with _negative_ numbers between
118 and possibly before the positive ones, indicating obligatory skips 121 and possibly before the positive ones, indicating obligatory skips
181 for k in range(iBound): 184 for k in range(iBound):
182 scratch[k]+=maybe[k] 185 scratch[k]+=maybe[k]
183 return True 186 return True
184 print("Shouldn't happen? - fell through",stack,i,iBound) 187 print("Shouldn't happen? - fell through",stack,i,iBound)
185 188
189 def checkX(self,pos,crosspos):
190 # New x at pos, are there others that can be xed out now?
191 # Overkill as is?
192 dprint('cx',self.cLet+str(crosspos),pos)
193 dprint('cxr1',self.m.rows[4])
194 if self.runs:
195 start0=0 if self.margin0==0 else self.margin0+1
196 if self.marginal(range(start0,pos+1),self.runs[0]):
197 dprint('cx1a')
198 else:
199 dprint('cx1b')
200 # if len(self.runs)>1:
201 startN=self.marginN if (self.marginN==self.n-1) else self.marginN-1
202 if self.marginal(range(startN,pos,-1),self.runs[-1]):
203 dprint('cx2a')
204 else:
205 dprint('cx2b')
206 dprint('cxr2',self.m.rows[4])
207
186 def checkNew(self,pos): 208 def checkNew(self,pos):
187 # New blob at pos, can we complete anything? 209 # New blob at pos, can we complete anything?
188 # Assuming @@ FTTB that it's never possible to definitively complete a 210 # Assuming @@ FTTB that it's never possible to definitively complete a
189 # non-marginal run, which is wrong if the length is unique and it's bounded... 211 # non-marginal run, which is wrong if the length is unique and it's bounded...
190 start0=0 if self.margin0==0 else self.margin0+1 212 start0=self.margin0 #0 if self.margin0==0 else self.margin0+1
191 startN=self.marginN if (self.marginN==self.n-1) else self.marginN-1 213 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
214 dprint('cn',start0,pos,startN)
192 changed=False 215 changed=False
193 # First, find our boundaries: 216 # First, find our boundaries:
194 s=pos # start index of our run 217 s=pos # start index of our run
195 while s>start0 and self[s-1].val is True: 218 if s>start0:
196 s-=1 219 while s>start0 and self[s-1].val is True:
220 s-=1
197 f=pos # finish index of our run 221 f=pos # finish index of our run
198 while f<startN and self[f+1].val is True: 222 if f<startN:
199 f+=1 223 while f<startN and self[f+1].val is True:
224 f+=1
200 l=(f-s)+1 # our length 225 l=(f-s)+1 # our length
201 print('%s:%s,%s,%s,%s:<%s>'%(str(self.__class__.__name__)[0],s,f,l,self.runs,self)) 226 dprint('%s:%s,%s,%s,%s:<%s>'%(self.cLet,s,f,l,self.runs,self))
202 c=self.runs.count(l) 227 c=self.runs.count(l)
203 if c==0: 228 if c==0:
204 # not big enough yet 229 # not big enough yet
205 dprint('x0') 230 dprint('x0')
206 return 231 return
208 # is it safely left marginal, i.e. no blobs or big enough gaps before us? 233 # is it safely left marginal, i.e. no blobs or big enough gaps before us?
209 if self.marginal(range(start0,s),l): 234 if self.marginal(range(start0,s),l):
210 changed=True 235 changed=True
211 dprint('n1') 236 dprint('n1')
212 # mark our margins 237 # mark our margins
213 for i in range(start0,s): 238 for i in range(start0,s): # not sure this is still needed since
239 # added gap-filling in self.marginal
214 if self[i].val is None: 240 if self[i].val is None:
215 self[i].setVal(False) 241 self.newX(i,False)
216 if f<startN: 242 if f<startN:
217 if self[f+1].val is None: 243 if self[f+1].val is None:
218 self[f+1].setVal(False) 244 self.newX(f+1,True)
219 self.found0(f) # pull in the start margin at least to f+2 245 self.found0(f) # pull in the start margin at least to f+2
220 else: 246 else:
221 dprint('x1a') 247 dprint('x1a')
222 if not changed: 248 if not changed:
223 if self.runs[-1]==l: 249 if self.runs[-1]==l:
224 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us? 250 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
225 if self.marginal(range(startN,f,-1),l): 251 if self.marginal(range(startN,f,-1),l):
226 changed=True 252 changed=True
227 dprint('n2') 253 dprint('n2')
228 # mark our margins 254 # mark our margins: still needed? see above
229 for i in range(startN,f,-1): 255 for i in range(startN,f,-1):
230 if self[i].val is None: 256 if self[i].val is None:
231 self[i].setVal(False) 257 self.newX(i,False)
232 if s>start0: 258 if s>start0:
233 if self[s-1].val is None: 259 if self[s-1].val is None:
234 self[s-1].setVal(False) 260 self.newX(s-1,True)
235 self.foundN(s) # pull in the finish margin at least to s-2 261 self.foundN(s) # pull in the finish margin at least to s-2
236 else: 262 else:
237 dprint('x2a') 263 dprint('x2a')
238 else: 264 else:
239 dprint('x2b') 265 dprint('x2b')
240 if changed: 266 if changed:
241 self.resetAllRuns() 267 self.resetAllRuns()
242 268
243 def marginal(self,rng,l): 269 def marginal(self,rng,l):
244 print('m',rng.start,rng.stop,rng.step) 270 dprint('m',rng.start,rng.stop,rng.step)
245 g=0 # length of a gap 271 g=0 # length of a gap
246 for i in rng: 272 for i in rng:
247 if self[i].val is True: 273 if self[i].val is True:
274 # Shouldn't be possible?
248 dprint('mx0') 275 dprint('mx0')
249 return False 276 return False
250 if self[i].val is False: 277 if self[i].val is False:
251 g=0 278 if g>0:
279 # Block a too-small gap
280 for i in (i-g,i):
281 self.newX(i,True)
282 g=0
252 else: 283 else:
253 # None 284 # None
254 g+=1 285 g+=1
255 if g==l: 286 if g==l:
256 dprint('mx1') 287 dprint('mx1')
257 return False 288 return False
289 if g>0:
290 # Block a too-small gap
291 for j in (i-g,i):
292 self.newX(j,True)
258 return True 293 return True
259 294
260 def found0(self,i): 295 def found0(self,i):
261 print('found0 called on %s at %s'%(self,i)) 296 dprint('found0 called on %s at %s'%(self,i))
262 i=self.margin0 297 i=self.margin0
263 while self[i].val is False: 298 while self[i].val is False:
264 i+=1 299 i+=1
265 if self[i].val is True: 300 if self[i].val is True:
266 r=self.runs.pop(0) 301 r=self.runs.pop(0)
267 self.initialComplete.append(r) 302 self.initialComplete.append(r)
268 self.margin0+=r+1 303 self.margin0+=r+1
269 self.updateHeader(r=r,pre=True) 304 self.updateHeader(r=r,pre=True)
270 305
271 def foundN(self,i): 306 def foundN(self,i):
272 print('foundN called on %s at %s'%(self,i)) 307 dprint('foundN called on %s at %s'%(self,i))
273 i=self.marginN 308 i=self.marginN
274 while self[i].val is False: 309 while self[i].val is False:
275 i-=1 310 i-=1
276 if self[i].val is True: 311 if self[i].val is True:
277 r=self.runs.pop() 312 r=self.runs.pop()
279 self.marginN-=r+1 314 self.marginN-=r+1
280 self.updateHeader(r=r,pre=False) 315 self.updateHeader(r=r,pre=False)
281 316
282 317
283 class Row(Vector): 318 class Row(Vector):
319 cLet='R'
284 def __init__(self,n,m,runs,pos): 320 def __init__(self,n,m,runs,pos):
285 Vector.__init__(self,n,m,runs) 321 Vector.__init__(self,n,m,runs)
286 self.y=pos 322 self.y=pos
287 self.width=self.myPrintSize() 323 self.width=self.myPrintSize()
288 324
291 Vector.__str__(self)) 327 Vector.__str__(self))
292 328
293 def updateHeader(self,*,maxWidth=None,r=None,pre=None): 329 def updateHeader(self,*,maxWidth=None,r=None,pre=None):
294 if maxWidth is None: 330 if maxWidth is None:
295 # update 331 # update
332 spacer=(" " if self.runs else "")
296 if pre: 333 if pre:
297 self.infix+=(RedFmt%r)+(" " if self.runs else "") 334 self.infix+=(RedFmt%r)+spacer
298 else: 335 else:
299 # post 336 # post
300 self.suffix=" "+RedFmt%r+self.suffix 337 self.suffix=spacer+RedFmt%r+self.suffix
301 self.fmt="%s%s%%s%s|"%(self.prespace,self.infix,self.suffix) 338 self.fmt="%s%s%%s%s|"%(self.prespace,self.infix,self.suffix)
302 else: 339 else:
303 # init 340 # init
304 self.maxWidth=maxWidth 341 self.maxWidth=maxWidth
305 self.prespace=' '*(maxWidth-self.width) 342 self.prespace=' '*(maxWidth-self.width)
310 def newBlob(self,x,crossCheck=False): 347 def newBlob(self,x,crossCheck=False):
311 self[x].setVal(True) 348 self[x].setVal(True)
312 if crossCheck: 349 if crossCheck:
313 self[x].column.checkNew(self.y) 350 self[x].column.checkNew(self.y)
314 351
352 def newX(self,x,crossCheck=False):
353 dprint('nx %s%s@%s'%('R',self.y,x))
354 self[x].setVal(False)
355 if crossCheck:
356 self[x].column.checkX(self.y,x)
357
315 class Column(Vector): 358 class Column(Vector):
359 cLet='C'
316 def __init__(self,n,m,runs,pos): 360 def __init__(self,n,m,runs,pos):
317 Vector.__init__(self,n,m,runs) 361 Vector.__init__(self,n,m,runs)
318 self.x=pos 362 self.x=pos
319 self.height=self.myPrintSize() 363 self.height=self.myPrintSize()
320 364
351 def newBlob(self,y,crossCheck=False): 395 def newBlob(self,y,crossCheck=False):
352 self[y].setVal(True) 396 self[y].setVal(True)
353 if crossCheck: 397 if crossCheck:
354 self[y].row.checkNew(self.x) 398 self[y].row.checkNew(self.x)
355 399
400 def newX(self,y,crossCheck=False):
401 dprint('nx %s%s@%s'%('C',self.x,y))
402 self[y].setVal(False)
403 if crossCheck:
404 self[y].row.checkX(self.x,y)
405
356 class Cell: 406 class Cell:
357 def __init__(self,row,y,column,x): 407 def __init__(self,row,y,column,x):
358 # At the intersection of row and column Vectors 408 # At the intersection of row and column Vectors
359 self.row=row 409 self.row=row
360 self.column=column 410 self.column=column
380 self.val=v 430 self.val=v
381 else: 431 else:
382 if self.val is not None: 432 if self.val is not None:
383 print("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y),file=sys.stderr) 433 print("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y),file=sys.stderr)
384 self.val=v 434 self.val=v
435
385 436
386 class Nono(dict): 437 class Nono(dict):
387 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout 438 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
388 def __init__(self,runsPerRow,runsPerCol): 439 def __init__(self,runsPerRow,runsPerCol):
440 self.loop=0
389 n=self.n=len(runsPerCol) 441 n=self.n=len(runsPerCol)
390 if n!=len(runsPerRow): 442 if n!=len(runsPerRow):
391 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr) 443 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr)
392 exit(1) 444 exit(1)
393 self.rc=runsPerRow 445 self.rc=runsPerRow
413 return "\n".join(lines) 465 return "\n".join(lines)
414 466
415 def solve(self): 467 def solve(self):
416 someChanged=1 468 someChanged=1
417 while someChanged>0: 469 while someChanged>0:
470 self.loop+=1
418 someChanged=0 471 someChanged=0
472 dprint("***Solve C %s***"%self.loop)
419 for c in self.columns: 473 for c in self.columns:
420 someChanged+=c.step() 474 someChanged+=c.step(c.x)
421 print(someChanged) 475 print(someChanged)
422 print(self) 476 print(self)
477 dprint("***Solve R %s***"%self.loop)
423 for r in self.rows: 478 for r in self.rows:
424 someChanged+=r.step() 479 someChanged+=r.step(r.y)
425 print(someChanged) 480 print(someChanged)
426 print(self) 481 print(self)
427 482
428 def dprint(*args): 483 def dprint(*args):
429 print(*args) 484 pass # print(*args)
430 485
431 if __name__ == '__main__': 486 if __name__ == '__main__':
432 if len(sys.argv)>1: 487 if len(sys.argv)>1:
433 f=open(sys.argv[1]) 488 f=open(sys.argv[1])
434 else: 489 else: