Mercurial > hg > python

comparison nono.py @ 11:1b9daa849b0f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
A bit further: red col working, finding middle of row 1, formatting off, outer loop in place, but fails overall after 3rd pass achieves nothing
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Sun, 15 Mar 2020 17:05:49 +0000
parents 0a24625b33fa
children ede2551ae7d9
comparison
equal deleted inserted replaced
10:0a24625b33fa 11:1b9daa849b0f
43 43
44 def resetAllRuns(self): 44 def resetAllRuns(self):
45 # compute the set of all possible layouts for runs 45 # compute the set of all possible layouts for runs
46 self.rn=len(self.runs) 46 self.rn=len(self.runs)
47 rtot=sum(self.runs) 47 rtot=sum(self.runs)
48 self.allRuns=list(self.seedList(0,0,0, 48 self.allRuns=list(self.seedList(0,0,self.margin0,self.marginN+1,
49 sum(1+self.runs[k] for k in range(self.rn))-1)) 49 sum(1+self.runs[k] for k in range(self.rn))-1))
50 self.nar=len(self.allRuns) 50 self.nar=len(self.allRuns)
51 51
52 def seedList(self,i,j,pos,runLen): 52 def seedList(self,i,j,pos0,posN,runLen):
53 """ 53 """
54 :param i: starting skip before next run 54 :param i: starting skip before next run
55 :type i: 0 if pos==0 else 1 55 :type i: 0 if pos==0 else 1
56 :param j: next run number 56 :param j: next run number
57 :type j: int 57 :type j: int
58 :param pos: left margin 58 :param pos0: left margin
59 :type pos: int 59 :type pos0: int
60 :param posN: right margin
61 :type posN: int
60 """ 62 """
61 bound=self.n-(pos+runLen)+1 63 bound=posN-(pos0+runLen)+1
62 #dprint('s',i,j,pos,runLen,bound) 64 dprint('s',i,j,pos0,posN,runLen,bound)
63 if j==self.rn: 65 if j==self.rn:
64 yield [] 66 yield []
65 return 67 return
66 r=self.runs[j] 68 r=self.runs[j]
67 for v in range(i,bound): 69 for v in range(i,bound):
68 for sub in self.seedList(1,j+1,pos+v+r,runLen-(r+1)): 70 for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)):
69 yield [-v,r]+sub 71 yield [-v,r]+sub
70 72
71 def step(self): 73 def step(self):
74 if self.runs==[]:
75 return 0
72 scratch=[0 if c.val is None else c.val for c in self] 76 scratch=[0 if c.val is None else c.val for c in self]
73 wins=0 77 wins=0
78 changed=0
74 for k,runs in enumerate(self.allRuns): 79 for k,runs in enumerate(self.allRuns):
75 dprint('=====pass %s======'%k) 80 dprint('=====pass %s======'%k)
76 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()): 81 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
77 wins+=1 82 wins+=1
78 dprint(wins, scratch) 83 dprint(wins, scratch)
85 inSeq=i if maybeSeq is None else maybeSeq 90 inSeq=i if maybeSeq is None else maybeSeq
86 dprint('s1',inSeq) 91 dprint('s1',inSeq)
87 maybeSeq=None 92 maybeSeq=None
88 if self[i].val is None: 93 if self[i].val is None:
89 self.newBlob(i,True) # Check cross-vector 94 self.newBlob(i,True) # Check cross-vector
95 changed=1
90 elif self[i].val is True: 96 elif self[i].val is True:
91 # already there 97 # already there
92 pass 98 pass
93 else: 99 else:
94 print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr) 100 print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr)
103 dprint('s3',i) 109 dprint('s3',i)
104 maybeSeq=i 110 maybeSeq=i
105 dprint('s4',inSeq,i) 111 dprint('s4',inSeq,i)
106 if inSeq is not None: 112 if inSeq is not None:
107 self.checkNew(i) 113 self.checkNew(i)
114 return changed
108 115
109 def onepass(self,i0,iBound,scratch,stack): 116 def onepass(self,i0,iBound,scratch,stack):
110 """note that stack is not a simple run, but one with _negative_ numbers between 117 """note that stack is not a simple run, but one with _negative_ numbers between
111 and possibly before the positive ones, indicating obligatory skips 118 and possibly before the positive ones, indicating obligatory skips
112 """ 119 """
113 i=i0 # starting index into self/scratch/maybe 120 i=i0 # starting index into self/scratch/maybe
114 maybe=[0]*(iBound-i0) 121 maybe=[0]*self.n
115 dprint('r: %s'%stack) 122 dprint('r: %s'%stack,i0,iBound)
116 req=sum((-r if r<0 else r) for r in stack) 123 req=sum((-r if r<0 else r) for r in stack)
117 while stack and i<iBound: 124 while stack and i<iBound:
118 r=rr=stack.pop(0) 125 r=rr=stack.pop(0)
119 dprint('pop:',r) 126 dprint('pop:',r)
120 if r<1: 127 if r<1:
206 self[i].setVal(False) 213 self[i].setVal(False)
207 if f<self.marginN-1: 214 if f<self.marginN-1:
208 if self[f+1].val is None: 215 if self[f+1].val is None:
209 self[f+1].setVal(False) 216 self[f+1].setVal(False)
210 self.found0(f) # pull in the start margin at least to f+2 217 self.found0(f) # pull in the start margin at least to f+2
211 if f<self.marginN-2 and self[f+2].val is True:
212 dprint('n1a')
213 self.checkNew(f+2) # I think@@
214 else: 218 else:
215 dprint('x1a') 219 dprint('x1a')
216 else: 220 if not changed:
217 dprint('x1b') 221 if self.runs[-1]==l:
218 if self.runs[-1]==l: 222 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
219 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us? 223 if self.marginal(range(self.marginN-1,f,-1),l):
220 if self.marginal(range(self.marginN-1,f,-1),l): 224 changed=True
221 changed=True 225 dprint('n2')
222 dprint('n2') 226 # mark our margins
223 # mark our margins 227 for i in range(self.marginN-1,f,-1):
224 for i in range(self.marginN-1,f,-1): 228 if self[i].val is None:
225 if self[i].val is None: 229 self[i].setVal(False)
226 self[i].setVal(False) 230 if s>self.margin0+1:
227 if s>self.margin0+1: 231 if self[s-1].val is None:
228 if self[s-1].val is None: 232 self[s-1].setVal(False)
229 self[s-1].setVal(False) 233 self.foundN(s) # pull in the finish margin at least to s-2
230 self.foundN(s) # pull in the finish margin at least to s-2 234 else:
231 if s>self.margin0+2 and self[s-2].val is True: 235 dprint('x2a')
232 dprint('n2a')
233 self.checkNew(s-2) # I think@@
234 else: 236 else:
235 dprint('x2a') 237 dprint('x2b')
236 else:
237 dprint('x2b')
238 if changed: 238 if changed:
239 self.resetAllRuns() 239 self.resetAllRuns()
240 240
241 def marginal(self,rng,l): 241 def marginal(self,rng,l):
242 print('m',rng.start,rng.stop,rng.step)
242 g=0 # length of a gap 243 g=0 # length of a gap
243 for i in rng: 244 for i in rng:
244 if self[i].val is True: 245 if self[i].val is True:
245 dprint('mx0') 246 dprint('mx0')
246 return False 247 return False
261 i+=1 262 i+=1
262 if self[i].val is True: 263 if self[i].val is True:
263 r=self.runs.pop(0) 264 r=self.runs.pop(0)
264 self.initialComplete.append(r) 265 self.initialComplete.append(r)
265 self.margin0+=r+1 266 self.margin0+=r+1
266 self.updateHeader(r=r) 267 self.updateHeader(r=r,pre=True)
267 268
268 def foundN(self,i): 269 def foundN(self,i):
269 print('foundN called on %s at %s'%(self,i)) 270 print('foundN called on %s at %s'%(self,i))
270 i=self.marginN 271 i=self.marginN
271 while self[i].val is False: 272 while self[i].val is False:
272 i-=1 273 i-=1
273 if self[i].val is True: 274 if self[i].val is True:
274 r=self.runs.pop() 275 r=self.runs.pop()
275 self.finalComplete=[r]+self.finalComplete 276 self.finalComplete=[r]+self.finalComplete
276 self.marginN-=r+1 277 self.marginN-=r+1
277 self.updateHeader(r=r) 278 self.updateHeader(r=r,pre=False)
278 279
279 280
280 class Row(Vector): 281 class Row(Vector):
281 def __init__(self,n,m,runs,pos): 282 def __init__(self,n,m,runs,pos):
282 Vector.__init__(self,n,m,runs) 283 Vector.__init__(self,n,m,runs)
314 Vector.__init__(self,n,m,runs) 315 Vector.__init__(self,n,m,runs)
315 self.x=pos 316 self.x=pos
316 self.height=self.myPrintSize() 317 self.height=self.myPrintSize()
317 318
318 def updateHeader(self,*,maxHeight=None,r=None,pre=None): 319 def updateHeader(self,*,maxHeight=None,r=None,pre=None):
320 dprint('CuH',r,pre)
319 if maxHeight is None: 321 if maxHeight is None:
320 # update 322 # update
321 if pre: 323 if pre:
322 self.infix+=(RedFmt%r)+" " 324 for rc in str(r):
325 self.infix.append(RedFmt%rc)
326 self.infix.append("-")
323 else: 327 else:
324 # post 328 # post
325 self.suffix=" "+RedFmt%r+self.suffix 329 ins=["-"]
326 self.fmt="%s%s%%s%s"%(self.prespace,self.infix,self.suffix) 330 for rc in str(r):
331 ins.append(RedFmt%r)
332 self.suffix=ins+self.suffix
333 dprint('CuH1: |%s|,%s,%s,%s'%(self.prespace,self.infix,self.suffix,self.runs))
334 self.header=(["-"]*self.prespace)+\
335 self.infix+\
336 ['-'.join(str(c) for c in self.runs)]+\
337 self.suffix
327 else: 338 else:
328 # init 339 # init
329 self.maxHeight=maxHeight 340 self.maxHeight=maxHeight
330 self.infix="" 341 self.infix=[]
331 self.suffix="" 342 self.suffix=[]
343 self.prespace=maxHeight - self.height # pad to same 'height'
344 self.fmt="%s%%s"%(' '*self.prespace)
332 header=('-'.join(str(c) for c in self.runs)) 345 header=('-'.join(str(c) for c in self.runs))
333 self.prespace=' '*(maxHeight - self.height) # pad to same 'height'
334 self.fmt="%s%%s"%self.prespace
335 self.header=self.fmt%header 346 self.header=self.fmt%header
347 dprint(self.header)
336 348
337 def newBlob(self,y,crossCheck=False): 349 def newBlob(self,y,crossCheck=False):
338 self[y].setVal(True) 350 self[y].setVal(True)
339 if crossCheck: 351 if crossCheck:
340 self[y].row.checkNew(self.x) 352 self[y].row.checkNew(self.x)
396 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate' 408 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
397 for j in range(self.maxCRheight)] 409 for j in range(self.maxCRheight)]
398 lines+=[str(r) for r in self.rows] 410 lines+=[str(r) for r in self.rows]
399 return "\n".join(lines) 411 return "\n".join(lines)
400 412
413 def solve(self):
414 someChanged=1
415 while someChanged>0:
416 someChanged=0
417 for c in self.columns:
418 someChanged+=c.step()
419 print(someChanged)
420 print(self)
421 for r in self.rows:
422 someChanged+=r.step()
423 print(someChanged)
424 print(self)
425
401 def dprint(*args): 426 def dprint(*args):
402 print(*args) 427 print(*args)
403 428
404 if __name__ == '__main__': 429 if __name__ == '__main__':
405 if len(sys.argv)>1: 430 if len(sys.argv)>1:
420 cols.append(vv) 445 cols.append(vv)
421 446
422 rows=[[int(s) for s in l.split()] for l in f] 447 rows=[[int(s) for s in l.split()] for l in f]
423 448
424 solver=Nono(rows,cols) 449 solver=Nono(rows,cols)
425 print(solver) 450 solver.solve()
426 for c in solver.columns:
427 c.step()
428 print()
429 print(solver)
430 for r in solver.rows:
431 r.step()
432 print()
433 print(solver)