Mercurial > hg > python

comparison nono.py @ 6:a56d5285575b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
drafted Vector.checkNew, still need found0 and foundN
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Tue, 10 Mar 2020 19:56:07 +0000
parents fee51ab07d09
children 13f600be3a1b
comparison
equal deleted inserted replaced
5:bd1db1ed4c25 6:a56d5285575b
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.runs=runs 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
30 self.runs=self.origRuns=runs
31 self.initialComplete=[]
32 self.finalComplete=[]
33 self.resetAllRuns()
34
35 def __repr__(self):
36 return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self))
37
38 def __str__(self):
39 return '%s|'%('|'.join(str(c) for c in self))
40
41 def resetAllRuns(self):
29 # compute the set of all possible layouts for runs 42 # compute the set of all possible layouts for runs
30 self.rn=len(self.runs) 43 self.rn=len(self.runs)
31 rtot=sum(self.runs) 44 rtot=sum(self.runs)
32 self.allRuns=list(self.seedList(0,0,0, 45 self.allRuns=list(self.seedList(0,0,0,
33 sum(1+self.runs[k] for k in range(self.rn))-1)) 46 sum(1+self.runs[k] for k in range(self.rn))-1))
49 return 62 return
50 r=self.runs[j] 63 r=self.runs[j]
51 for v in range(i,bound): 64 for v in range(i,bound):
52 for sub in self.seedList(1,j+1,pos+v+r,runLen-(r+1)): 65 for sub in self.seedList(1,j+1,pos+v+r,runLen-(r+1)):
53 yield [-v,r]+sub 66 yield [-v,r]+sub
54
55 def __repr__(self):
56 return "V@%s%s:%s"%(self.x,self.runs,list.__repr__(self))
57
58 def __str__(self):
59 return '%s|'%('|'.join(str(c) for c in self))
60 67
61 def step(self): 68 def step(self):
62 scratch=[0 if c.val is None else c.val for c in self] 69 scratch=[0 if c.val is None else c.val for c in self]
63 for k,runs in enumerate(self.allRuns): 70 for k,runs in enumerate(self.allRuns):
64 dprint('=====pass %s======'%k) 71 dprint('=====pass %s======'%k)
183 # yes 190 # yes
184 dprint('win:',maybe) 191 dprint('win:',maybe)
185 for k in range(iBound): 192 for k in range(iBound):
186 scratch[k]+=maybe[k] 193 scratch[k]+=maybe[k]
187 194
195 def checkNew(self,pos):
196 # New blob at pos, can we complete anything?
197 # 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...
199 changed=False
200 # First, find our boundaries:
201 s=pos # start index of our run
202 while s>self.marginO and self[s-1].val is True:
203 s-=1
204 f=pos # finish index of our run
205 while f<self.marginN and self[f+1].val is True:
206 f+=1
207 l=(f-s)+1 # our length
208 c=self.runs.count(l)
209 if c==0:
210 # not big enough yet
211 dprint('n0')
212 return
213 j=self.runs.index(l)
214 if j==0:
215 # is it safely left marginal, i.e. no blobs or big enough gaps before us?
216 if marginal(range(self.margin0,s)):
217 changed=True
218 # mark our margins
219 for i in range(margin0+1,s):
220 if self[i].val is None:
221 self[i].setVal(False)
222 if f<marginN-1:
223 if self[f+1].val is None:
224 self[f+1].setVal(False)
225 if f<marginN-2 and self[f+2].val is True:
226 dprint('n1')
227 self.checkNew(f+2) # I think@@
228 self.found0(f) # pull in the start margin at least to f+2
229 elif j==self.rn-1:
230 # 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):
232 changed=True
233 # mark our margins
234 for i in range(marginN-1,f,-1):
235 if self[i].val is None:
236 self[i].setVal(False)
237 if s>margin0+1:
238 if self[s-1].val is None:
239 self[s-1].setVal(False)
240 if s>margin0+2 and self[s-2].val is True:
241 dprint('n2')
242 self.checkNew(s-2) # I think@@
243 self.foundN(s) # pull in the finish margin at least to s-2
244 if changed:
245 self.resetAllRuns()
246
247 def marginal(self,rng,l):
248 g=0 # length of a gap
249 for i in rng:
250 if self[i].val is True:
251 return False
252 if self[i].val is False:
253 g=0
254 else:
255 # None
256 g+=1
257 if g==l:
258 return False
259 return True
260
188 class Row(Vector): 261 class Row(Vector):
189 def __init__(self,n,m,runs,pos,dprintWidth): 262 def __init__(self,n,m,runs,pos,dprintWidth):
190 Vector.__init__(self,n,m,runs) 263 Vector.__init__(self,n,m,runs)
191 self.y=pos 264 self.y=pos
192 self.dprintWidth=dprintWidth 265 self.dprintWidth=dprintWidth
226 return ' ' if self.val is None else ('\u25A0' if self.val else 'x') 299 return ' ' if self.val is None else ('\u25A0' if self.val else 'x')
227 300
228 def setVal(self,v): 301 def setVal(self,v):
229 if v is True: 302 if v is True:
230 if self.val is False: 303 if self.val is False:
231 dprint("Warning: x -> * at %s,%s"%(self.x,self.y)) 304 print("Warning: x -> * at %s,%s"%(self.x,self.y),file=sys.stderr)
232 elif self.val is True: 305 elif self.val is True:
233 # No-op 306 # No-op
234 return 307 return
308 self.val=v
309 self.row.checkNew(self.x)
310 self.column.checkNew(self.y)
235 # @@ check row/col completed 311 # @@ check row/col completed
236 else: 312 else:
237 if self.val is not None: 313 if self.val is not None:
238 dprint("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y)) 314 print("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y),file=sys.stderr)
239 self.val=v 315 self.val=v
240 316
241 class Nono(dict): 317 class Nono(dict):
242 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout 318 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
243 def __init__(self,rows,cols): 319 def __init__(self,rows,cols):
244 n=self.n=len(cols) 320 n=self.n=len(cols)