|
38
|
1 #!/usr/bin/python3
|
|
|
2 # Expects e.g. ^A copy from Nonograms dprint preview cols, then blank line, then rows
|
|
|
3 # rows are space-separated
|
|
|
4 # cols are one-digit-after-another, unless some 2-digit, in which case x is separator
|
|
|
5 # E.g.
|
|
|
6 # 13x1x2
|
|
|
7 # 19
|
|
|
8 # maps to
|
|
|
9 # 13
|
|
|
10 # 1 1
|
|
|
11 # 2 9
|
|
|
12
|
|
|
13 import sys
|
|
|
14
|
|
|
15 Red='[31m'
|
|
|
16 eRed='[39m'
|
|
|
17 RedFmt=Red+'%s'+eRed
|
|
|
18
|
|
|
19 def interleave(*args):
|
|
|
20 for vals in zip(*args):
|
|
|
21 yield from vals
|
|
|
22
|
|
|
23 class Vector(list):
|
|
|
24 # reads top-to-bottom or left-to-right
|
|
|
25 def __init__(self,n,m,runs):
|
|
|
26 list.__init__(self,list(range(n)))
|
|
|
27 self.n=n
|
|
|
28 self.m=m
|
|
|
29 self.margin0=0 # a run can start here, so if >0 then self[m0-1].val must be False
|
|
|
30 self.marginN=n-1 # a run can end here, so if <n-1 then self[mN+1].val ditto
|
|
|
31 self.runs=self.origRuns=runs
|
|
|
32 self.initialComplete=[]
|
|
|
33 self.finalComplete=[]
|
|
|
34 self.resetAllRuns()
|
|
|
35
|
|
|
36 def __repr__(self):
|
|
|
37 return "V@%s%s:%s"%(self.x,self.origRuns,list.__repr__(self))
|
|
|
38
|
|
|
39 def __str__(self):
|
|
|
40 return '%s|'%('|'.join(str(c) for c in self))
|
|
|
41
|
|
|
42 def myPrintSize(self):
|
|
|
43 return sum(len(str(run)) for run in self.runs)+len(self.runs)-1
|
|
|
44
|
|
|
45 def resetAllRuns(self):
|
|
|
46 # compute the set of all possible layouts for runs
|
|
|
47 self.rn=len(self.runs)
|
|
|
48 rtot=sum(self.runs)
|
|
|
49 self.allRuns=list(self.seedList(0,0,self.margin0,self.marginN+1,
|
|
|
50 sum(1+self.runs[k] for k in range(self.rn))-1))
|
|
|
51 self.nar=len(self.allRuns)
|
|
|
52
|
|
|
53 def seedList(self,i,j,pos0,posN,runLen):
|
|
|
54 """
|
|
|
55 :param i: starting skip before next run
|
|
|
56 :type i: 0 if pos==0 else 1
|
|
|
57 :param j: next run number
|
|
|
58 :type j: int
|
|
|
59 :param pos0: left margin
|
|
|
60 :type pos0: int
|
|
|
61 :param posN: right margin
|
|
|
62 :type posN: int
|
|
|
63 """
|
|
|
64 bound=posN-(pos0+runLen)+1
|
|
|
65 dprint('s',i,j,pos0,posN,runLen,bound)
|
|
|
66 if j==self.rn:
|
|
|
67 yield []
|
|
|
68 return
|
|
|
69 r=self.runs[j]
|
|
|
70 for v in range(i,bound):
|
|
|
71 for sub in self.seedList(1,j+1,pos0+v+r,posN,runLen-(r+1)):
|
|
|
72 yield [-v,r]+sub
|
|
|
73
|
|
|
74 def step(self,pos):
|
|
|
75 if self.runs==[]:
|
|
|
76 return 0
|
|
|
77 scratch=[0 if c.val is None else c.val for c in self]
|
|
|
78 wins=0
|
|
|
79 changed=0
|
|
|
80 for k,runs in enumerate(self.allRuns):
|
|
|
81 if (self.m.loop,self.cLet,pos,k)==(1,'R',7,5):
|
|
|
82 print(self.m)
|
|
|
83 dprint('=====pass %s.%s.%s.%s======'%(self.m.loop,self.cLet,pos,k))
|
|
|
84 if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
|
|
|
85 wins+=1
|
|
|
86 dprint(wins, scratch)
|
|
|
87 maybeSeq=None
|
|
|
88 inSeq=None
|
|
|
89 j=None
|
|
|
90 for i in range(self.n):
|
|
|
91 if scratch[i]>=wins:
|
|
|
92 # If blobby in _every_ pass, then must be a blob
|
|
|
93 if inSeq is None:
|
|
|
94 inSeq=i if maybeSeq is None else maybeSeq
|
|
|
95 dprint('s1',inSeq)
|
|
|
96 maybeSeq=None
|
|
|
97 if self[i].val is None:
|
|
|
98 dprint('s1a',i)
|
|
|
99 self.newBlob(i,True) # Check cross-vector
|
|
|
100 j=i
|
|
|
101 changed=1
|
|
|
102 elif self[i].val is True:
|
|
|
103 pass
|
|
|
104 else:
|
|
|
105 eprint("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),err=101)
|
|
|
106 elif inSeq is not None:
|
|
|
107 if self[i].val is not True:
|
|
|
108 inSeq=None
|
|
|
109 maybeSeq=None
|
|
|
110 dprint('s2',i-1,j)
|
|
|
111 if j is not None:
|
|
|
112 # Only if we actually added a blob at some point
|
|
|
113 dpush('b_s2')
|
|
|
114 self.checkNew(i-1)
|
|
|
115 dpop('b_s2')
|
|
|
116 elif self[i].val is True and maybeSeq is None:
|
|
|
117 dprint('s3',i)
|
|
|
118 maybeSeq=i
|
|
|
119 dprint('s4',inSeq,i)
|
|
|
120 if inSeq is not None:
|
|
|
121 dpush('b_s4')
|
|
|
122 self.checkNew(i)
|
|
|
123 dpop('b_s4')
|
|
|
124 return changed
|
|
|
125
|
|
|
126 def onepass(self,i0,iBound,scratch,stack):
|
|
|
127 """note that stack is not a simple run, but one with _negative_ numbers between
|
|
|
128 and possibly before the positive ones, indicating obligatory skips
|
|
|
129 """
|
|
|
130 i=i0 # starting index into self/scratch/maybe
|
|
|
131 maybe=[0]*self.n
|
|
|
132 dprint('r: %s'%stack,i0,iBound)
|
|
|
133 req=sum((-r if r<0 else r) for r in stack)
|
|
|
134 while stack and i<iBound:
|
|
|
135 r=rr=stack.pop(0)
|
|
|
136 dprint('pop:',r)
|
|
|
137 if r<1:
|
|
|
138 # obligatory skip
|
|
|
139 # (Above init of self.allRuns is easier if we allow a 0 to be ignored
|
|
|
140 for k in range(i,i-r):
|
|
|
141 if self[k] is True:
|
|
|
142 # has to be False or None to skip
|
|
|
143 dprint('x0',k)
|
|
|
144 return False
|
|
|
145 i-=r
|
|
|
146 req+=r
|
|
|
147 r=rr=stack.pop(0)
|
|
|
148 # rr is run remaining -- how many we still need
|
|
|
149 # First, check if we can start here: 0 is OK, and n>0 iff n-1 is None or False
|
|
|
150 # if i>0 and self[i-1].val is True:
|
|
|
151 # dprint('x1',i)
|
|
|
152 # return
|
|
|
153 if (iBound-i)<req:
|
|
|
154 # Can't win, give up altogether
|
|
|
155 dprint('x2',i,iBound,req)
|
|
|
156 return False
|
|
|
157 j=i # start of run, if we find it
|
|
|
158 gapsFilled=0
|
|
|
159 dprint('top:',j)
|
|
|
160 while rr>0:
|
|
|
161 # guaranteed by check above that we won't run over the far end
|
|
|
162 c=self[i].val
|
|
|
163 if c is False:
|
|
|
164 dprint('x3',i)
|
|
|
165 return False
|
|
|
166 if c is None:
|
|
|
167 # we could add a blob here
|
|
|
168 gapsFilled+=1
|
|
|
169 # and a blob already present is OK
|
|
|
170 rr-=1
|
|
|
171 i+=1
|
|
|
172 # Maybe a win?
|
|
|
173 # look ahead, can we stop here?
|
|
|
174 if i<self.n and self[i].val is True:
|
|
|
175 dprint('x4',i)
|
|
|
176 return False
|
|
|
177 # elif gapsFilled==0:
|
|
|
178 # # We must have crossed at least one gap...
|
|
|
179 # print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s"%(self,i, j, rr),file=sys.stderr)
|
|
|
180 # raise Exception
|
|
|
181 # Victory!
|
|
|
182 dprint('c6',r,j,i)
|
|
|
183 for k in range(j,i):
|
|
|
184 maybe[k]+=1
|
|
|
185 req-=r
|
|
|
186 # on to the next run
|
|
|
187 # end of inner loop, did we win?
|
|
|
188 if (not stack) or i==iBound:
|
|
|
189 # yes
|
|
|
190 dprint('win:',maybe)
|
|
|
191 for k in range(iBound):
|
|
|
192 scratch[k]+=maybe[k]
|
|
|
193 return True
|
|
|
194 eprint("Shouldn't happen? - fell through",stack,i,iBound,err=102)
|
|
|
195
|
|
|
196 def checkX(self,pos,crosspos):
|
|
|
197 # New x at pos, are there others that can be xed out now?
|
|
|
198 # Overkill as is?
|
|
|
199 dprint('cx',self.cLet+str(crosspos),pos)
|
|
|
200 if self.runs:
|
|
|
201 start0=self.margin0 # 0 if self.margin0==0 else self.margin0+1
|
|
|
202 if self.marginal(range(start0,pos),self.runs[0]):
|
|
|
203 dprint('cx1a')
|
|
|
204 else:
|
|
|
205 dprint('cx1b')
|
|
|
206 # if len(self.runs)>1:
|
|
|
207 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
|
|
|
208 if self.marginal(range(startN,pos,-1),self.runs[-1]):
|
|
|
209 dprint('cx2a')
|
|
|
210 else:
|
|
|
211 dprint('cx2b')
|
|
|
212
|
|
|
213 def checkNew(self,pos):
|
|
|
214 # New blob at pos, can we complete anything?
|
|
|
215 # Assuming @@ FTTB that it's never possible to definitively complete a
|
|
|
216 # non-marginal run, which is wrong if the length is unique and it's bounded...
|
|
|
217 start0=self.margin0 #0 if self.margin0==0 else self.margin0+1
|
|
|
218 startN=self.marginN # self.marginN if (self.marginN==self.n-1) else self.marginN-1
|
|
|
219 dprint('cn',start0,pos,startN)
|
|
|
220 changed=False
|
|
|
221 # First, find our boundaries:
|
|
|
222 s=pos # start index of our run
|
|
|
223 if s>start0:
|
|
|
224 while s>start0 and self[s-1].val is True:
|
|
|
225 s-=1
|
|
|
226 f=pos # finish index of our run
|
|
|
227 if f<startN:
|
|
|
228 while f<startN and self[f+1].val is True:
|
|
|
229 f+=1
|
|
|
230 l=(f-s)+1 # our length
|
|
|
231 dprint('%s:%s,%s,%s,%s:<%s>'%(self.cLet,s,f,l,self.runs,self))
|
|
|
232 c=self.runs.count(l)
|
|
|
233 if c==0:
|
|
|
234 # not big enough yet
|
|
|
235 dprint('x0')
|
|
|
236 return
|
|
|
237 if self.runs[0]==l:
|
|
|
238 # is it safely left marginal, i.e. no blobs or big enough gaps before us?
|
|
|
239 if self.marginal(range(start0,s),l):
|
|
|
240 changed=True
|
|
|
241 dprint('n1')
|
|
|
242 # mark our margins
|
|
|
243 for i in range(start0,s): # not sure this is still needed since
|
|
|
244 # added gap-filling in self.marginal
|
|
|
245 if self[i].val is None:
|
|
|
246 self.newX(i,False)
|
|
|
247 if f<startN:
|
|
|
248 if self[f+1].val is None:
|
|
|
249 self.newX(f+1,True)
|
|
|
250 self.found0(f) # pull in the start margin at least to f+2
|
|
|
251 else:
|
|
|
252 dprint('x1a')
|
|
|
253 if not changed:
|
|
|
254 if self.runs[-1]==l:
|
|
|
255 # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
|
|
|
256 if self.marginal(range(startN,f,-1),l):
|
|
|
257 changed=True
|
|
|
258 dprint('n2')
|
|
|
259 # mark our margins: still needed? see above
|
|
|
260 for i in range(startN,f,-1):
|
|
|
261 if self[i].val is None:
|
|
|
262 self.newX(i,False)
|
|
|
263 if s>start0:
|
|
|
264 if self[s-1].val is None:
|
|
|
265 self.newX(s-1,True)
|
|
|
266 self.foundN(s) # pull in the finish margin at least to s-2
|
|
|
267 else:
|
|
|
268 dprint('x2a')
|
|
|
269 else:
|
|
|
270 dprint('x2b')
|
|
|
271 if changed:
|
|
|
272 self.resetAllRuns()
|
|
|
273
|
|
|
274 def marginal(self,rng,l):
|
|
|
275 dprint('m%s'%self.cLet,rng.start,rng.stop,rng.step,l)
|
|
|
276 g=0 # length of a gap
|
|
|
277 for i in rng:
|
|
|
278 if self[i].val is True:
|
|
|
279 # Shouldn't be possible?
|
|
|
280 dprint('mx0')
|
|
|
281 return False
|
|
|
282 if self[i].val is False:
|
|
|
283 if g>0:
|
|
|
284 # Block a too-small gap
|
|
|
285 dprint('m1',i-g,i)
|
|
|
286 for j in range(i-g,i):
|
|
|
287 self.newX(j,True)
|
|
|
288 g=0
|
|
|
289 else:
|
|
|
290 # None
|
|
|
291 g+=1
|
|
|
292 if g==l:
|
|
|
293 # run could fit here, so no go
|
|
|
294 dprint('mx1')
|
|
|
295 return False
|
|
|
296 if g>0:
|
|
|
297 # Block a too-small gap
|
|
|
298 if rng.step==1:
|
|
|
299 # forward
|
|
|
300 dprint('m2f',i-g,i)
|
|
|
301 for j in range(i+1-g,i+1):
|
|
|
302 self.newX(j,True)
|
|
|
303 else:
|
|
|
304 # backward
|
|
|
305 dprint('m2b',i+g,i)
|
|
|
306 for j in range(i+g-1,i-1,-1):
|
|
|
307 self.newX(j,True)
|
|
|
308 return True
|
|
|
309
|
|
|
310 def found0(self,i):
|
|
|
311 dprint('found0 called on %s at %s'%(self,i))
|
|
|
312 i=self.margin0
|
|
|
313 while self[i].val is False:
|
|
|
314 i+=1
|
|
|
315 if self[i].val is True:
|
|
|
316 r=self.runs.pop(0)
|
|
|
317 self.initialComplete.append(r)
|
|
|
318 self.margin0+=r+1
|
|
|
319 self.updateHeader(r=r,pre=True)
|
|
|
320
|
|
|
321 def foundN(self,i):
|
|
|
322 dprint('foundN called on %s at %s'%(self,i))
|
|
|
323 i=self.marginN
|
|
|
324 while self[i].val is False:
|
|
|
325 i-=1
|
|
|
326 if self[i].val is True:
|
|
|
327 r=self.runs.pop()
|
|
|
328 self.finalComplete=[r]+self.finalComplete
|
|
|
329 self.marginN-=r+1
|
|
|
330 self.updateHeader(r=r,pre=False)
|
|
|
331
|
|
|
332
|
|
|
333 class Row(Vector):
|
|
|
334 cLet='R'
|
|
|
335 def __init__(self,n,m,runs,pos):
|
|
|
336 Vector.__init__(self,n,m,runs)
|
|
|
337 self.y=pos
|
|
|
338 self.width=self.myPrintSize()
|
|
|
339
|
|
|
340 def __str__(self):
|
|
|
341 return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
|
|
|
342 Vector.__str__(self))
|
|
|
343
|
|
|
344 def updateHeader(self,*,maxWidth=None,r=None,pre=None):
|
|
|
345 if maxWidth is None:
|
|
|
346 # update
|
|
|
347 spacer=(" " if self.runs else "")
|
|
|
348 if pre:
|
|
|
349 self.infix+=(RedFmt%r)+spacer
|
|
|
350 else:
|
|
|
351 # post
|
|
|
352 self.suffix=spacer+RedFmt%r+self.suffix
|
|
|
353 self.fmt="%s%s%%s%s|"%(self.prespace,self.infix,self.suffix)
|
|
|
354 else:
|
|
|
355 # init
|
|
|
356 self.maxWidth=maxWidth
|
|
|
357 self.prespace=' '*(maxWidth-self.width)
|
|
|
358 self.fmt="%s%%s|"%self.prespace
|
|
|
359 self.infix=""
|
|
|
360 self.suffix=""
|
|
|
361
|
|
|
362 def newBlob(self,x,crossCheck=False):
|
|
|
363 self[x].setVal(True)
|
|
|
364 if crossCheck:
|
|
|
365 dpush('b_cc')
|
|
|
366 self[x].column.checkNew(self.y)
|
|
|
367 dpop('b_cc')
|
|
|
368
|
|
|
369 def newX(self,x,crossCheck=False):
|
|
|
370 dprint('nx %s%s@%s'%('R',self.y,x))
|
|
|
371 self[x].setVal(False)
|
|
|
372 if crossCheck:
|
|
|
373 dpush('x_cc')
|
|
|
374 self[x].column.checkX(self.y,x)
|
|
|
375 dpop('x_cc')
|
|
|
376
|
|
|
377 class Column(Vector):
|
|
|
378 cLet='C'
|
|
|
379 def __init__(self,n,m,runs,pos):
|
|
|
380 Vector.__init__(self,n,m,runs)
|
|
|
381 self.x=pos
|
|
|
382 self.height=self.myPrintSize()
|
|
|
383
|
|
|
384 def updateHeader(self,*,maxHeight=None,r=None,pre=None):
|
|
|
385 dprint('CuH',r,pre)
|
|
|
386 if maxHeight is None:
|
|
|
387 # update
|
|
|
388 if pre:
|
|
|
389 for rc in str(r):
|
|
|
390 self.infix.append(RedFmt%rc)
|
|
|
391 if self.runs:
|
|
|
392 self.infix.append('-')
|
|
|
393 else:
|
|
|
394 # post
|
|
|
395 ins=["-"] if self.runs else []
|
|
|
396 for rc in str(r):
|
|
|
397 ins.append(RedFmt%r)
|
|
|
398 self.suffix=ins+self.suffix
|
|
|
399 dprint('CuH1: |%s|,%s,%s,%s'%(self.prespace,self.infix,self.suffix,self.runs))
|
|
|
400 self.header=([" "]*self.prespace)+\
|
|
|
401 self.infix+\
|
|
|
402 (['-'.join(str(c) for c in self.runs)] if self.runs else [])+\
|
|
|
403 self.suffix
|
|
|
404 else:
|
|
|
405 # init
|
|
|
406 self.maxHeight=maxHeight
|
|
|
407 self.infix=[]
|
|
|
408 self.suffix=[]
|
|
|
409 self.prespace=maxHeight - self.height # pad to same 'height'
|
|
|
410 self.fmt="%s%%s"%(' '*self.prespace)
|
|
|
411 header=('-'.join(str(c) for c in self.runs))
|
|
|
412 self.header=self.fmt%header
|
|
|
413 dprint(self.header)
|
|
|
414
|
|
|
415 def newBlob(self,y,crossCheck=False):
|
|
|
416 self[y].setVal(True)
|
|
|
417 if crossCheck:
|
|
|
418 dpush('b_cc')
|
|
|
419 self[y].row.checkNew(self.x)
|
|
|
420 dpop('b_cc')
|
|
|
421
|
|
|
422 def newX(self,y,crossCheck=False):
|
|
|
423 dprint('nx %s%s@%s'%('C',self.x,y))
|
|
|
424 self[y].setVal(False)
|
|
|
425 if crossCheck:
|
|
|
426 dpush('x_cc')
|
|
|
427 self[y].row.checkX(self.x,y)
|
|
|
428 dpop('x_cc')
|
|
|
429
|
|
|
430 class Cell:
|
|
|
431 def __init__(self,row,y,column,x):
|
|
|
432 # At the intersection of row and column Vectors
|
|
|
433 self.row=row
|
|
|
434 self.column=column
|
|
|
435 self.x=x
|
|
|
436 self.y=y
|
|
|
437 self.val=None # three valued: None(unknown), True(filled), False(empty)
|
|
|
438 self.row[x]=self
|
|
|
439 self.column[y]=self
|
|
|
440
|
|
|
441 def __repr__(self):
|
|
|
442 return "C@(%s,%s):%s"%(self.x,self.y,self.val)
|
|
|
443
|
|
|
444 def __str__(self):
|
|
|
445 return ' ' if self.val is None else ('\u25A0' if self.val else 'x')
|
|
|
446
|
|
|
447 def setVal(self,v):
|
|
|
448 if v is True:
|
|
|
449 if self.val is False:
|
|
|
450 wprint("Warning: x -> * at %s,%s"%(self.x,self.y))
|
|
|
451 elif self.val is True:
|
|
|
452 # No-op
|
|
|
453 return
|
|
|
454 self.val=v
|
|
|
455 else:
|
|
|
456 if self.val is not None:
|
|
|
457 wprint("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y))
|
|
|
458 self.val=v
|
|
|
459
|
|
|
460
|
|
|
461 class Nono(dict):
|
|
|
462 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
|
|
|
463 def __init__(self,runsPerRow,runsPerCol):
|
|
|
464 global SOLVER
|
|
|
465 self.loop=0
|
|
|
466 self.dp=''
|
|
|
467 self.dstate=[]
|
|
|
468 SOLVER=self
|
|
|
469 n=self.n=len(runsPerCol)
|
|
|
470 if n!=len(runsPerRow):
|
|
|
471 print("losing r:%s x c:%s"%(len(runsPerRow),n),sys.stderr)
|
|
|
472 exit(1)
|
|
|
473 self.rc=runsPerRow
|
|
|
474 self.cc=runsPerCol
|
|
|
475 # print col nums>9 vertically :-(
|
|
|
476 self.columns=cc=[Column(n,self,runsPerCol[i],i) for i in range(n)]
|
|
|
477 self.maxCRheight=maxCRheight=max(col.height for col in cc)
|
|
|
478 for c in cc:
|
|
|
479 c.updateHeader(maxHeight=maxCRheight)
|
|
|
480 self.rows=rr=[Row(n,self,runsPerRow[i],i) for i in range(n)]
|
|
|
481 maxRRwidth=max(row.width for row in rr)
|
|
|
482 for r in rr:
|
|
|
483 r.updateHeader(maxWidth=maxRRwidth)
|
|
|
484 self.rowfmt="%s|%%s|"%(' '*maxRRwidth)
|
|
|
485 for x in range(n):
|
|
|
486 for y in range(n):
|
|
|
487 self[(x,y)]=Cell(rr[y],y,cc[x],x)
|
|
|
488
|
|
|
489 def __str__(self):
|
|
|
490 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
|
|
|
491 for j in range(self.maxCRheight)]
|
|
|
492 lines+=[str(r) for r in self.rows]
|
|
|
493 return "\n".join(lines)
|
|
|
494
|
|
|
495 def solve(self):
|
|
|
496 someChanged=1
|
|
|
497 while someChanged>0:
|
|
|
498 self.loop+=1
|
|
|
499 someChanged=0
|
|
|
500 dprint("***Solve C %s***"%self.loop)
|
|
|
501 for c in self.columns:
|
|
|
502 someChanged+=c.step(c.x)
|
|
|
503 print(someChanged)
|
|
|
504 print(self)
|
|
|
505 dprint("***Solve R %s***"%self.loop)
|
|
|
506 for r in self.rows:
|
|
|
507 someChanged+=r.step(r.y)
|
|
|
508 print(someChanged)
|
|
|
509 print(self)
|
|
|
510
|
|
|
511 def dpush(s):
|
|
|
512 SOLVER.dp+=' '
|
|
|
513 SOLVER.dstate.append(s)
|
|
|
514
|
|
|
515 def dpop(s):
|
|
|
516 assert(SOLVER.dstate.pop()==s)
|
|
|
517 SOLVER.dp=SOLVER.dp[1:]
|
|
|
518
|
|
|
519 def dprint(*args):
|
|
|
520 print(SOLVER.dp,end='')
|
|
|
521 print(*args)
|
|
|
522 sys.stdout.flush()
|
|
|
523
|
|
|
524 def eprint(*args,**kw):
|
|
|
525 print(*args,file=sys.stderr)
|
|
|
526 sys.stderr.flush()
|
|
|
527 exit(kw['err'])
|
|
|
528
|
|
|
529 def wprint(*args):
|
|
|
530 print(*args,file=sys.stderr)
|
|
|
531 sys.stderr.flush()
|
|
|
532
|
|
|
533 if __name__ == '__main__':
|
|
|
534 if len(sys.argv)>1:
|
|
|
535 f=open(sys.argv[1])
|
|
|
536 else:
|
|
|
537 f=sys.stdin
|
|
|
538
|
|
|
539 cols=[]
|
|
|
540
|
|
|
541 for l in f:
|
|
|
542 l=l.rstrip()
|
|
|
543 if l=='':
|
|
|
544 break
|
|
|
545 if 'x' in l:
|
|
|
546 vv=[int(s) for s in l.split('x')]
|
|
|
547 else:
|
|
|
548 vv=[int(c) for c in l]
|
|
|
549 cols.append(vv)
|
|
|
550
|
|
|
551 rows=[[int(s) for s in l.split()] for l in f]
|
|
|
552
|
|
|
553 solver=Nono(rows,cols)
|
|
|
554 solver.solve()
|
