Mercurial > hg > python

comparison nono.py @ 0:fee51ab07d09

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
blanket publication of all existing python files in lib/python on maritain
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Mon, 09 Mar 2020 14:58:04 +0000
parents
children a56d5285575b
comparison
equal deleted inserted replaced
-1:000000000000 0:fee51ab07d09
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=''
16 eRed=''
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.runs=runs
29 # compute the set of all possible layouts for runs
30 self.rn=len(self.runs)
31 rtot=sum(self.runs)
32 self.allRuns=list(self.seedList(0,0,0,
33 sum(1+self.runs[k] for k in range(self.rn))-1))
34 self.nar=len(self.allRuns)
35
36 def seedList(self,i,j,pos,runLen):
37 """
38 :param i: starting skip before next run
39 :type i: 0 if pos==0 else 1
40 :param j: next run number
41 :type j: int
42 :param pos: left margin
43 :type pos: int
44 """
45 bound=self.n-(pos+runLen)+1
46 #dprint('s',i,j,pos,runLen,bound)
47 if j==self.rn:
48 yield []
49 return
50 r=self.runs[j]
51 for v in range(i,bound):
52 for sub in self.seedList(1,j+1,pos+v+r,runLen-(r+1)):
53 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
61 def step(self):
62 scratch=[0 if c.val is None else c.val for c in self]
63 for k,runs in enumerate(self.allRuns):
64 dprint('=====pass %s======'%k)
65 self.onepass(0,self.n,scratch,runs.copy())
66 dprint(scratch)
67 for i in range(self.n):
68 if scratch[i]==self.nar:
69 # If blobby in _every_ pass, then must be a blob
70 if self[i].val is None:
71 self[i].setVal(True)
72 elif self[i].val is True:
73 # already there
74 pass
75 else:
76 print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr)
77 exit(101)
78
79 def onepass(self,i0,iBound,scratch,stack):
80 """note that stack is not a simple run, but one with _negative_ numbers between
81 and possibly before the positive ones, indicating obligatory skips
82 """
83 i=i0 # starting index into self/scratch/maybe
84 j=-1 # index into run
85 maybe=[0]*iBound
86 dprint('r: %s'%stack)
87 req=sum((-r if r<0 else r) for r in stack)
88 while stack and i<iBound:
89 r=rr=stack.pop(0)
90 dprint('pop:',r)
91 if r<1:
92 # obligatory skip
93 # (Above init of self.allRuns is easier if we allow a 0 to be ignored
94 i-=r
95 req+=r
96 r=rr=stack.pop(0)
97 # rr is run remaining -- how many we still need
98 j+=1 # index of current run in self.runs, we'll need to decorate that eventually
99 inOne=-1 # if non-neg, records the start point of a possible run
100 gapsFilled=0
101 # First, check if we can start here: 0 is OK, and n>0 iff n-1 is None or False
102 if i>0 and i<iBound:
103 while self[i-1].val:
104 i+=1
105 if (iBound-i)<req:
106 # Can't win, give up altogether
107 dprint('c0',i,iBound,req)
108 return
109 while i<iBound:
110 c=self[i].val
111 dprint('top',i,c,inOne,rr)
112 if c is None:
113 # we could add a blob here
114 dprint('c1')
115 gapsFilled+=1
116 rr-=1
117 if inOne<0:
118 dprint('c1a',i)
119 # starts here
120 inOne=i
121 # fall through to check for completion
122 else:
123 dprint('c2')
124 # c is a bool
125 if inOne<0:
126 dprint('c2a')
127 if c:
128 dprint('c2a1')
129 # a *, we can possible start something here
130 inOne=i
131 rr-=1
132 # fall through to check for completion
133 else:
134 dprint('c2a2')
135 # an x, can't start here, just move along
136 i+=1
137 continue
138 else:
139 dprint('c2b')
140 if c:
141 dprint('c2b1')
142 # a blob, extend or complete a partial
143 rr-=1
144 # fall through to check for completion
145 else:
146 # abandon a partial
147 dprint('c2b2')
148 inOne=-1
149 rr=r
150 i+=1
151 continue
152 if rr>0:
153 dprint('c3')
154 # we're not done, carry on
155 i+=1
156 continue
157 # Maybe a win?
158 # look ahead, can we stop here?
159 # NB _self_.n
160 if i+1<self.n and self[i+1].val:
161 dprint('c4')
162 # Nope
163 inOne=-1
164 rr=r
165 gapsFilled=0
166 i+=1
167 continue
168 elif gapsFilled==0:
169 dprint('c5')
170 # We must have crossed at least on gap...
171 print("Shouldn't happen: no gap! me:%s i:%s j:%s rr:%s inOne:%s"%(self,i, j, rr, inOne),file=sys.stderr)
172 exit(100)
173 # Victory!
174 dprint('c6',r,inOne,i)
175 for k in range(inOne,i+1):
176 maybe[k]+=1
177 i+=1
178 req-=r
179 break
180 # on to the next run
181 # end of inner loop, did we win?
182 if (not stack) or i==iBound:
183 # yes
184 dprint('win:',maybe)
185 for k in range(iBound):
186 scratch[k]+=maybe[k]
187
188 class Row(Vector):
189 def __init__(self,n,m,runs,pos,dprintWidth):
190 Vector.__init__(self,n,m,runs)
191 self.y=pos
192 self.dprintWidth=dprintWidth
193 self.fmt="%%%ss|"%dprintWidth
194
195 def __str__(self):
196 return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
197 Vector.__str__(self))
198
199 class Column(Vector):
200 def __init__(self,n,m,runs,pos,dprintHeight):
201 Vector.__init__(self,n,m,runs)
202 self.x=pos
203 self.dprintHeight=dprintHeight
204 self.fmt="%%%ss"%self.dprintHeight
205 self.updateHeader()
206
207 def updateHeader(self):
208 header=('-'.join(str(c) for c in self.runs))
209 self.header=self.fmt%header # pad to same 'height'
210
211 class Cell:
212 def __init__(self,row,y,column,x):
213 # At the intersection of row and column Vectors
214 self.row=row
215 self.column=column
216 self.x=x
217 self.y=y
218 self.val=None # three valued: None(unknown), True(filled), False(empty)
219 self.row[x]=self
220 self.column[y]=self
221
222 def __repr__(self):
223 return "C@(%s,%s):%s"%(self.x,self.y,self.val)
224
225 def __str__(self):
226 return ' ' if self.val is None else ('\u25A0' if self.val else 'x')
227
228 def setVal(self,v):
229 if v is True:
230 if self.val is False:
231 dprint("Warning: x -> * at %s,%s"%(self.x,self.y))
232 elif self.val is True:
233 # No-op
234 return
235 # @@ check row/col completed
236 else:
237 if self.val is not None:
238 dprint("Warning: %s -> %s at %s,%s"%(self.val,v,self.x,self.y))
239 self.val=v
240
241 class Nono(dict):
242 # 0,0 is upper left, so increasing y goes _downwards_, to match the standard layout
243 def __init__(self,rows,cols):
244 n=self.n=len(cols)
245 if n!=len(rows):
246 print("losing r:%s x c:%s"%(len(rows),n),sys.stderr)
247 exit(1)
248 self.rc=rows
249 rowDprintWidth=max(sum(len(str(r)) for r in row)+len(row)-1 for row in rows)
250 self.rowfmt="%s|%%s"%(' '*rowDprintWidth)
251 self.cc=cols
252 # dprint col nums>9 vertically :-(
253 self.colDprintHeight=max(sum(len(str(c)) for c in col)+len(col)-1 for col in cols)
254 self.columns=cc=[Column(n,self,cols[i],i,self.colDprintHeight) for i in range(20)]
255 self.rows=rr=[Row(n,self,rows[i],i,rowDprintWidth) for i in range(20)]
256 for x in range(20):
257 for y in range(20):
258 self[(x,y)]=Cell(rr[y],y,cc[x],x)
259
260 def __str__(self):
261 lines=[self.rowfmt%('|'.join([(self.columns[i]).header[j] for i in range(self.n)])) # 'rotate'
262 for j in range(self.colDprintHeight)]
263 lines+=[str(r) for r in self.rows]
264 return "\n".join(lines)
265
266 def dprint(*args):
267 pass
268
269 if __name__ == '__main__':
270 if len(sys.argv)>1:
271 f=open(sys.argv[1])
272 else:
273 f=sys.stdin
274
275 cols=[]
276
277 for l in f:
278 l=l.rstrip()
279 if l=='':
280 break
281 if 'x' in l:
282 vv=[int(s) for s in l.split('x')]
283 else:
284 vv=[int(c) for c in l]
285 cols.append(vv)
286
287 rows=[[int(s) for s in l.split()] for l in f]
288
289 solver=Nono(rows,cols)
290 print(solver)
291 for c in solver.columns:
292 c.step()
293 print()
294 print(solver)
295 for r in solver.rows:
296 r.step()
297 print()
298 print(solver)