Mercurial > hg > python

comparison nono.py @ 71:eea4bcb657bc simple

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
70:578cb569d815 71:eea4bcb657bc
6 import sys 6 import sys
7 7
8 Red='' 8 Red=''
9 eRed='' 9 eRed=''
10 RedFmt=Red+'%s'+eRed 10 RedFmt=Red+'%s'+eRed
11
12 def interleave(*args):
13 for vals in zip(*args):
14 yield from vals
15 11
16 class Run: 12 class Run:
17 '''What we're looking for, converted eventually into what 13 '''What we're looking for, converted eventually into what
18 we've found. 14 we've found.
19 "left" and "right" make sense for Rows, for Columns read "above" and "below"''' 15 "left" and "right" make sense for Rows, for Columns read "above" and "below"'''
94 return '%s|'%('|'.join(str(c) for c in self)) 90 return '%s|'%('|'.join(str(c) for c in self))
95 91
96 def myPrintSize(self): 92 def myPrintSize(self):
97 return sum((len(str(run)) if isinstance(run,Run) else 1) for run in self.runs) 93 return sum((len(str(run)) if isinstance(run,Run) else 1) for run in self.runs)
98 94
99 #=========v-old-v============
100
101 def resetAllRuns(self):
102 # compute the set of all possible layouts for runs
103 self.rn=len(self.runs)
104 rtot=sum(self.runs)
105 self.allRuns=list(self.seedList(0,0,self.margin0,self.marginN+1,
106 sum(1+self.runs[k] for k in range(self.rn))-1))
107 self.nar=len(self.allRuns)
108
109 def seedList(self,i,j,pos0,posN,runLen):
110 """
111 :param i: starting skip before next run
112 :type i: 0 if pos==0 else 1
113 :param j: next run number
114 :type j: int
115 :param pos0: left margin
116 :type pos0: int
117 :param posN: right margin
118 :type posN: int
119 :return: list of runlens separated, possibly prefixed, with skips as negative integers
120 """
121 bound=posN-(pos0+runLen)+1
122 dprint('s',i,j,pos0,posN,runLen,bound)
123 if j==self.rn:
124 yield []
125 return
126 r=self.runs[j]
127 for v in range(i,bound):
128 for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)):
129 yield [-v,r]+sub
130
131 def step(self,pos):
132 if self.runs==[]:
133 return 0
134 scratch=[0 if c.val is None else c.val for c in self]
135 wins=0
136 changed=0
137 for k,runs in enumerate(self.allRuns):
138 if (self.m.loop,self.cLet,pos,k)==(1,'R',7,5):
139 print(self.m)
140 dprint('=====pass %s.%s.%s.%s======'%(self.m.loop,self.cLet,pos,k))
141 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
142 wins+=1
143 dprint(wins, scratch)
144 maybeSeq=None
145 inSeq=None
146 j=None
147 for i in range(self.n):
148 if scratch[i]>=wins:
149 # If blobby in _every_ pass, then must be a blob
150 if inSeq is None:
151 inSeq=i if maybeSeq is None else maybeSeq
152 dprint('s1',inSeq)
153 maybeSeq=None
154 if self[i].val is None:
155 dprint('s1a',i)
156 self.newBlob(i,True) # Check cross-vector
157 j=i
158 changed=1
159 elif self[i].val is True:
160 pass
161 else:
162 eprint("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),err=101)
163 elif inSeq is not None:
164 if self[i].val is not True:
165 inSeq=None
166 maybeSeq=None
167 dprint('s2',i-1,j)
168 if j is not None:
169 # Only if we actually added a blob at some point
170 dpush('b_s2')
171 self.checkNew(i-1)
172 dpop('b_s2')
173 elif self[i].val is True and maybeSeq is None:
174 dprint('s3',i)
175 maybeSeq=i
176 dprint('s4',inSeq,i)
177 if inSeq is not None:
178 dpush('b_s4')
179 self.checkNew(i)
180 dpop('b_s4')
181 return changed
182
183 def onepass(self,i0,iBound,scratch,stack):
184 """note that stack is not a simple run, but one with _negative_ numbers between
185 and possibly before the positive ones, indicating obligatory skips
186 """
187 i=i0 # starting index into self/scratch/maybe
188 maybe=[0]*self.n
189 dprint('r: %s'%stack,i0,iBound)
190 req=sum((-r if r<0 else r) for r in stack)
191 while stack and i<iBound:
192 r=rr=stack.pop(0)
193 dprint('pop:',r)
194 if r<1:
195 # obligatory skip
196 # (Above init of self.allRuns is easier if we allow a 0 to be ignored
197 for k in range(i,i-r):
198 if self[k] is True:
199 # has to be False or None to skip
200 dprint('x0',k)
201 return False
202 i-=r
203 req+=r
204 r=rr=stack.pop(0)
205 # rr is run remaining -- how many we still need
206 # First, check if we can start here: 0 is OK, and n>0 iff n-1 is None or False
207 # if i>0 and self[i-1].val is True:
208 # dprint('x1',i)
209 # return
210 if (iBound-i)<req:
211 # Can't win, give up altogether
212 dprint('x2',i,iBound,req)
213 return False
214 j=i # start of run, if we find it
215 gapsFilled=0
216 dprint('top:',j)
217 while rr>0:
218 # guaranteed by check above that we won't run over the far end
219 c=self[i].val
220 if c is False:
221 dprint('x3',i)
222 return False
223 if c is None:
224 # we could add a blob here
225 gapsFilled+=1
226 # and a blob already present is OK
227 rr-=1
228 i+=1
229 # Maybe a win?
230 # look ahead, can we stop here?
231 if i<self.n and self[i].val is True:
232 dprint('x4',i)
233 return False
234 # elif gapsFilled==0:
235 # # We must have crossed at least one gap...
236 # print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s"%(self,i, j, rr),file=sys.stderr)
237 # raise Exception
238 # Victory!
239 dprint('c6',r,j,i)
240 for k in range(j,i):
241 maybe[k]+=1
242 req-=r
243 # on to the next run
244 # end of inner loop, did we win?
245 if (not stack) or i==iBound:
246 # yes
247 dprint('win:',maybe)
248 for k in range(iBound):
249 scratch[k]+=maybe[k]
250 return True
251 eprint("Shouldn't happen? - fell through",stack,i,iBound,err=102)
252
253 def checkX(self,pos,crosspos):
254 # New x at pos, are there others that can be xed out now?
255 # Overkill as is?
256 dprint('cx',self.cLet+str(crosspos),pos)
257 if self.runs:
258 start0=self.margin0 # 0 if self.margin0==0 else self.margin0+1
259 if self.marginal(range(start0,pos),self.runs[0]):
260 dprint('cx1a')
261 else:
262 dprint('cx1b')
263 # if len(self.runs)>1:
264 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
265 if self.marginal(range(startN,pos,-1),self.runs[-1]):
266 dprint('cx2a')
267 else:
268 dprint('cx2b')
269
270 def checkNew(self,pos):
271 # New blob at pos, can we complete anything?
272 # Assuming @@ FTTB that it's never possible to definitively complete a
273 # non-marginal run, which is wrong if the length is unique and it's bounded...
274 start0=self.margin0 #0 if self.margin0==0 else self.margin0+1
275 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
276 dprint('cn',start0,pos,startN)
277 changed=False
278 # First, find our boundaries:
279 s=pos # start index of our run
280 if s>start0:
281 while s>start0 and self[s-1].val is True:
282 s-=1
283 f=pos # finish index of our run
284 if f<startN:
285 while f<startN and self[f+1].val is True:
286 f+=1
287 l=(f-s)+1 # our length
288 dprint('%s:%s,%s,%s,%s:<%s>'%(self.cLet,s,f,l,self.runs,self))
289 c=self.runs.count(l)
290 if c==0:
291 # not big enough yet
292 dprint('x0')
293 return
294 if self.runs[0]==l:
295 # is it safely left marginal, i.e. no blobs or big enough gaps before us?
296 if self.marginal(range(start0,s),l):
297 changed=True
298 dprint('n1')
299 # mark our margins
300 for i in range(start0,s): # not sure this is still needed since
301 # added gap-filling in self.marginal
302 if self[i].val is None:
303 self.newX(i,False)
304 if f<startN:
305 if self[f+1].val is None:
306 self.newX(f+1,True)
307 self.found0(f) # pull in the start margin at least to f+2
308 else:
309 dprint('x1a')
310 if not changed:
311 if self.runs[-1]==l:
312 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
313 if self.marginal(range(startN,f,-1),l):
314 changed=True
315 dprint('n2')
316 # mark our margins: still needed? see above
317 for i in range(startN,f,-1):
318 if self[i].val is None:
319 self.newX(i,False)
320 if s>start0:
321 if self[s-1].val is None:
322 self.newX(s-1,True)
323 self.foundN(s) # pull in the finish margin at least to s-2
324 else:
325 dprint('x2a')
326 else:
327 dprint('x2b')
328 if changed:
329 self.resetAllRuns()
330
331 def marginal(self,rng,l):
332 dprint('m%s'%self.cLet,rng.start,rng.stop,rng.step,l)
333 g=0 # length of a gap
334 for i in rng:
335 if self[i].val is True:
336 # Shouldn't be possible?
337 dprint('mx0')
338 return False
339 if self[i].val is False:
340 if g>0:
341 # Block a too-small gap
342 dprint('m1',i-g,i)
343 for j in range(i-g,i):
344 self.newX(j,True)
345 g=0
346 else:
347 # None
348 g+=1
349 if g==l:
350 # run could fit here, so no go
351 dprint('mx1')
352 return False
353 if g>0:
354 # Block a too-small gap
355 if rng.step==1:
356 # forward
357 dprint('m2f',i-g,i)
358 for j in range(i+1-g,i+1):
359 self.newX(j,True)
360 else:
361 # backward
362 dprint('m2b',i+g,i)
363 for j in range(i+g-1,i-1,-1):
364 self.newX(j,True)
365 return True
366
367 def found0(self,i):
368 dprint('found0 called on %s at %s'%(self,i))
369 i=self.margin0
370 while self[i].val is False:
371 i+=1
372 if self[i].val is True:
373 r=self.runs.pop(0)
374 self.initialComplete.append(r)
375 self.margin0+=r+1
376 self.updateHeader(r=r,pre=True)
377
378 def foundN(self,i):
379 dprint('foundN called on %s at %s'%(self,i))
380 i=self.marginN
381 while self[i].val is False:
382 i-=1
383 if self[i].val is True:
384 r=self.runs.pop()
385 self.finalComplete=[r]+self.finalComplete
386 self.marginN-=r+1
387 self.updateHeader(r=r,pre=False)
388
389 #=============new simple============
390 def pass0(self): 95 def pass0(self):
391 # simple first pass down/across a row 96 # simple first pass down/across a row
392 for i in range(0,len(self.runs),2): 97 for i in range(0,len(self.runs),2):
393 run=self.runs[i] 98 run=self.runs[i]
394 for p in range(run.i+run.s,run.i+run.n): 99 for p in range(run.i+run.s,run.i+run.n):
486 self.prespace=' '*(maxWidth-self.width) 191 self.prespace=' '*(maxWidth-self.width)
487 self.fmt="%s%%s|"%self.prespace 192 self.fmt="%s%%s|"%self.prespace
488 self.infix="" 193 self.infix=""
489 self.suffix="" 194 self.suffix=""
490 195
491 def newBlob(self,x,crossCheck=False):
492 self[x].setVal(True)
493 if crossCheck:
494 dpush('b_cc')
495 self[x].column.checkNew(self.y)
496 dpop('b_cc')
497
498 def newX(self,x,crossCheck=False):
499 dprint('nx %s%s@%s'%('R',self.y,x))
500 self[x].setVal(False)
501 if crossCheck:
502 dpush('x_cc')
503 self[x].column.checkX(self.y,x)
504 dpop('x_cc')
505
506 class Column(Vector): 196 class Column(Vector):
507 cLet='C' 197 cLet='C'
508 def __init__(self,n,m,pos): 198 def __init__(self,n,m,pos):
509 Vector.__init__(self,n,m) 199 Vector.__init__(self,n,m)
510 self.x=pos 200 self.x=pos
544 self.fmt="%s%%s"%(' '*self.prespace) 234 self.fmt="%s%%s"%(' '*self.prespace)
545 header=('-'.join(str(c) for c in self.runs if isinstance(c,Run))) 235 header=('-'.join(str(c) for c in self.runs if isinstance(c,Run)))
546 self.header=self.fmt%header 236 self.header=self.fmt%header
547 dprint(self.header) 237 dprint(self.header)
548 238
549 def newBlob(self,y,crossCheck=False):
550 self[y].setVal(True)
551 if crossCheck:
552 dpush('b_cc')
553 self[y].row.checkNew(self.x)
554 dpop('b_cc')
555
556 def newX(self,y,crossCheck=False):
557 dprint('nx %s%s@%s'%('C',self.x,y))
558 self[y].setVal(False)
559 if crossCheck:
560 dpush('x_cc')
561 self[y].row.checkX(self.x,y)
562 dpop('x_cc')
563
564 class Cell: 239 class Cell:
565 def __init__(self,row,y,column,x): 240 def __init__(self,row,y,column,x):
566 # At the intersection of row and column Vectors 241 # At the intersection of row and column Vectors
567 self.row=row 242 self.row=row
568 self.column=column 243 self.column=column
588 self.val=v 263 self.val=v
589 return True 264 return True
590 265
591 class Nono(dict): 266 class Nono(dict):
592 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout 267 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
593 def __init__(self,runsPerRow,runsPerCol): 268 def __init__(self,runsPerRow,runsPerCol,debug):
594 global SOLVER 269 global SOLVER
595 self.loop=0 270 self.loop=0
596 self.dp='' 271 self.dp='' # old depth hack
272 self.debug = debug
597 self.dstate=[] 273 self.dstate=[]
598 SOLVER=self 274 SOLVER=self
599 n=self.n=len(runsPerCol) 275 n=self.n=len(runsPerCol)
600 if n!=len(runsPerRow): 276 if n!=len(runsPerRow):
601 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr) 277 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr)
619 maxRRwidth=max(row.width for row in rr) 295 maxRRwidth=max(row.width for row in rr)
620 for r in rr: 296 for r in rr:
621 r.updateHeader(maxWidth=maxRRwidth) 297 r.updateHeader(maxWidth=maxRRwidth)
622 self.rowfmt="%s|%%s|"%(' '*maxRRwidth) 298 self.rowfmt="%s|%%s|"%(' '*maxRRwidth)
623 299
624
625 def __str__(self): 300 def __str__(self):
626 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate' 301 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
627 for j in range(self.maxCRheight)] 302 for j in range(self.maxCRheight)]
628 lines+=[str(r) for r in self.rows] 303 lines+=[str(r) for r in self.rows]
629 return "\n".join(lines) 304 return "\n".join(lines)
630 305
631 #=============new simple============
632 def pass0(self): # do columns of empty layout 306 def pass0(self): # do columns of empty layout
633 for c in self.columns: 307 for c in self.columns:
634 c.pass0() 308 c.pass0()
635 print(self) 309 dprint('After Pass 0 for columns', self, sep = '\n')
636 for r in self.rows: 310 for r in self.rows:
637 r.pass0() 311 r.pass0()
638 print(self) 312 dprint('After Pass 0 for rows', self, sep = '\n')
639 for c in self.columns: 313 for c in self.columns:
640 c.check0() 314 c.check0()
641 print(self) 315 dprint('After Check 0 for columns', self, sep = '\n')
316 dprint(self)
642 for r in self.rows: 317 for r in self.rows:
643 r.check0() 318 r.check0()
319 dprint('After Check 0 for rows', self, sep = '\n')
644 320
645 def solve(self): 321 def solve(self):
646 self.pass0() 322 self.pass0()
647 print(self) 323
648 return 324 def dprint(*args, **kwargs):
649 someChanged=1 325 '''Debug print'''
650 while someChanged>0: 326 if SOLVER.debug:
651 self.loop+=1 327 print(*args, **kwargs)
652 someChanged=0 328 sys.stdout.flush()
653 dprint("***Solve C %s***"%self.loop)
654 for c in self.columns:
655 someChanged+=c.step(c.x)
656 print(someChanged)
657 print(self)
658 dprint("***Solve R %s***"%self.loop)
659 for r in self.rows:
660 someChanged+=r.step(r.y)
661 print(someChanged)
662 print(self)
663
664 def dpush(s):
665 SOLVER.dp+=' '
666 SOLVER.dstate.append(s)
667
668 def dpop(s):
669 assert(SOLVER.dstate.pop()==s)
670 SOLVER.dp=SOLVER.dp[1:]
671
672 def dprint(*args):
673 print(SOLVER.dp,end='')
674 print(*args)
675 sys.stdout.flush()
676 329
677 def eprint(*args,**kw): 330 def eprint(*args,**kw):
331 '''error print'''
678 print(*args,file=sys.stderr) 332 print(*args,file=sys.stderr)
679 sys.stderr.flush() 333 sys.stderr.flush()
680 print(SOLVER) 334 print(SOLVER)
681 breakpoint() 335 breakpoint()
682 exit(kw['err']) 336 exit(kw['err'])
683 337
684 def wprint(*args):
685 print(*args,file=sys.stderr)
686 sys.stderr.flush()
687
688 if __name__ == '__main__': 338 if __name__ == '__main__':
339 if sys.argv[1] == '-d':
340 sys.argv.pop(1)
341 debug = True
342 else:
343 debug = False
689 if len(sys.argv)>1: 344 if len(sys.argv)>1:
690 f=open(sys.argv[1]) 345 f=open(sys.argv[1])
691 else: 346 else:
692 f=sys.stdin 347 f=sys.stdin
693 348
696 n=int(len(vv)/2) 351 n=int(len(vv)/2)
697 print('%sx%s puzzle'%(n,n),file=sys.stderr) 352 print('%sx%s puzzle'%(n,n),file=sys.stderr)
698 cols=[[int(i) for i in v.split('.')] for v in vv[:n]] 353 cols=[[int(i) for i in v.split('.')] for v in vv[:n]]
699 rows=[[int(i) for i in v.split('.')] for v in vv[n:]] 354 rows=[[int(i) for i in v.split('.')] for v in vv[n:]]
700 355
701 solver=Nono(rows,cols) 356 solver=Nono(rows, cols, debug)
357 print(solver)
358 print()
702 solver.solve() 359 solver.solve()
360 print('Done',solver, sep = '\n')
703 361
362
363