Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | tutorial_tests = """ |
2 | Let's try a simple generator: | |
3 | ||
4 | >>> def f(): | |
5 | ... yield 1 | |
6 | ... yield 2 | |
7 | ||
8 | >>> for i in f(): | |
9 | ... print i | |
10 | 1 | |
11 | 2 | |
12 | >>> g = f() | |
13 | >>> g.next() | |
14 | 1 | |
15 | >>> g.next() | |
16 | 2 | |
17 | ||
18 | "Falling off the end" stops the generator: | |
19 | ||
20 | >>> g.next() | |
21 | Traceback (most recent call last): | |
22 | File "<stdin>", line 1, in ? | |
23 | File "<stdin>", line 2, in g | |
24 | StopIteration | |
25 | ||
26 | "return" also stops the generator: | |
27 | ||
28 | >>> def f(): | |
29 | ... yield 1 | |
30 | ... return | |
31 | ... yield 2 # never reached | |
32 | ... | |
33 | >>> g = f() | |
34 | >>> g.next() | |
35 | 1 | |
36 | >>> g.next() | |
37 | Traceback (most recent call last): | |
38 | File "<stdin>", line 1, in ? | |
39 | File "<stdin>", line 3, in f | |
40 | StopIteration | |
41 | >>> g.next() # once stopped, can't be resumed | |
42 | Traceback (most recent call last): | |
43 | File "<stdin>", line 1, in ? | |
44 | StopIteration | |
45 | ||
46 | "raise StopIteration" stops the generator too: | |
47 | ||
48 | >>> def f(): | |
49 | ... yield 1 | |
50 | ... raise StopIteration | |
51 | ... yield 2 # never reached | |
52 | ... | |
53 | >>> g = f() | |
54 | >>> g.next() | |
55 | 1 | |
56 | >>> g.next() | |
57 | Traceback (most recent call last): | |
58 | File "<stdin>", line 1, in ? | |
59 | StopIteration | |
60 | >>> g.next() | |
61 | Traceback (most recent call last): | |
62 | File "<stdin>", line 1, in ? | |
63 | StopIteration | |
64 | ||
65 | However, they are not exactly equivalent: | |
66 | ||
67 | >>> def g1(): | |
68 | ... try: | |
69 | ... return | |
70 | ... except: | |
71 | ... yield 1 | |
72 | ... | |
73 | >>> list(g1()) | |
74 | [] | |
75 | ||
76 | >>> def g2(): | |
77 | ... try: | |
78 | ... raise StopIteration | |
79 | ... except: | |
80 | ... yield 42 | |
81 | >>> print list(g2()) | |
82 | [42] | |
83 | ||
84 | This may be surprising at first: | |
85 | ||
86 | >>> def g3(): | |
87 | ... try: | |
88 | ... return | |
89 | ... finally: | |
90 | ... yield 1 | |
91 | ... | |
92 | >>> list(g3()) | |
93 | [1] | |
94 | ||
95 | Let's create an alternate range() function implemented as a generator: | |
96 | ||
97 | >>> def yrange(n): | |
98 | ... for i in range(n): | |
99 | ... yield i | |
100 | ... | |
101 | >>> list(yrange(5)) | |
102 | [0, 1, 2, 3, 4] | |
103 | ||
104 | Generators always return to the most recent caller: | |
105 | ||
106 | >>> def creator(): | |
107 | ... r = yrange(5) | |
108 | ... print "creator", r.next() | |
109 | ... return r | |
110 | ... | |
111 | >>> def caller(): | |
112 | ... r = creator() | |
113 | ... for i in r: | |
114 | ... print "caller", i | |
115 | ... | |
116 | >>> caller() | |
117 | creator 0 | |
118 | caller 1 | |
119 | caller 2 | |
120 | caller 3 | |
121 | caller 4 | |
122 | ||
123 | Generators can call other generators: | |
124 | ||
125 | >>> def zrange(n): | |
126 | ... for i in yrange(n): | |
127 | ... yield i | |
128 | ... | |
129 | >>> list(zrange(5)) | |
130 | [0, 1, 2, 3, 4] | |
131 | ||
132 | """ | |
133 | ||
134 | # The examples from PEP 255. | |
135 | ||
136 | pep_tests = """ | |
137 | ||
138 | Specification: Yield | |
139 | ||
140 | Restriction: A generator cannot be resumed while it is actively | |
141 | running: | |
142 | ||
143 | >>> def g(): | |
144 | ... i = me.next() | |
145 | ... yield i | |
146 | >>> me = g() | |
147 | >>> me.next() | |
148 | Traceback (most recent call last): | |
149 | ... | |
150 | File "<string>", line 2, in g | |
151 | ValueError: generator already executing | |
152 | ||
153 | Specification: Return | |
154 | ||
155 | Note that return isn't always equivalent to raising StopIteration: the | |
156 | difference lies in how enclosing try/except constructs are treated. | |
157 | For example, | |
158 | ||
159 | >>> def f1(): | |
160 | ... try: | |
161 | ... return | |
162 | ... except: | |
163 | ... yield 1 | |
164 | >>> print list(f1()) | |
165 | [] | |
166 | ||
167 | because, as in any function, return simply exits, but | |
168 | ||
169 | >>> def f2(): | |
170 | ... try: | |
171 | ... raise StopIteration | |
172 | ... except: | |
173 | ... yield 42 | |
174 | >>> print list(f2()) | |
175 | [42] | |
176 | ||
177 | because StopIteration is captured by a bare "except", as is any | |
178 | exception. | |
179 | ||
180 | Specification: Generators and Exception Propagation | |
181 | ||
182 | >>> def f(): | |
183 | ... return 1//0 | |
184 | >>> def g(): | |
185 | ... yield f() # the zero division exception propagates | |
186 | ... yield 42 # and we'll never get here | |
187 | >>> k = g() | |
188 | >>> k.next() | |
189 | Traceback (most recent call last): | |
190 | File "<stdin>", line 1, in ? | |
191 | File "<stdin>", line 2, in g | |
192 | File "<stdin>", line 2, in f | |
193 | ZeroDivisionError: integer division or modulo by zero | |
194 | >>> k.next() # and the generator cannot be resumed | |
195 | Traceback (most recent call last): | |
196 | File "<stdin>", line 1, in ? | |
197 | StopIteration | |
198 | >>> | |
199 | ||
200 | Specification: Try/Except/Finally | |
201 | ||
202 | >>> def f(): | |
203 | ... try: | |
204 | ... yield 1 | |
205 | ... try: | |
206 | ... yield 2 | |
207 | ... 1//0 | |
208 | ... yield 3 # never get here | |
209 | ... except ZeroDivisionError: | |
210 | ... yield 4 | |
211 | ... yield 5 | |
212 | ... raise | |
213 | ... except: | |
214 | ... yield 6 | |
215 | ... yield 7 # the "raise" above stops this | |
216 | ... except: | |
217 | ... yield 8 | |
218 | ... yield 9 | |
219 | ... try: | |
220 | ... x = 12 | |
221 | ... finally: | |
222 | ... yield 10 | |
223 | ... yield 11 | |
224 | >>> print list(f()) | |
225 | [1, 2, 4, 5, 8, 9, 10, 11] | |
226 | >>> | |
227 | ||
228 | Guido's binary tree example. | |
229 | ||
230 | >>> # A binary tree class. | |
231 | >>> class Tree: | |
232 | ... | |
233 | ... def __init__(self, label, left=None, right=None): | |
234 | ... self.label = label | |
235 | ... self.left = left | |
236 | ... self.right = right | |
237 | ... | |
238 | ... def __repr__(self, level=0, indent=" "): | |
239 | ... s = level*indent + repr(self.label) | |
240 | ... if self.left: | |
241 | ... s = s + "\\n" + self.left.__repr__(level+1, indent) | |
242 | ... if self.right: | |
243 | ... s = s + "\\n" + self.right.__repr__(level+1, indent) | |
244 | ... return s | |
245 | ... | |
246 | ... def __iter__(self): | |
247 | ... return inorder(self) | |
248 | ||
249 | >>> # Create a Tree from a list. | |
250 | >>> def tree(list): | |
251 | ... n = len(list) | |
252 | ... if n == 0: | |
253 | ... return [] | |
254 | ... i = n // 2 | |
255 | ... return Tree(list[i], tree(list[:i]), tree(list[i+1:])) | |
256 | ||
257 | >>> # Show it off: create a tree. | |
258 | >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") | |
259 | ||
260 | >>> # A recursive generator that generates Tree labels in in-order. | |
261 | >>> def inorder(t): | |
262 | ... if t: | |
263 | ... for x in inorder(t.left): | |
264 | ... yield x | |
265 | ... yield t.label | |
266 | ... for x in inorder(t.right): | |
267 | ... yield x | |
268 | ||
269 | >>> # Show it off: create a tree. | |
270 | >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") | |
271 | >>> # Print the nodes of the tree in in-order. | |
272 | >>> for x in t: | |
273 | ... print x, | |
274 | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z | |
275 | ||
276 | >>> # A non-recursive generator. | |
277 | >>> def inorder(node): | |
278 | ... stack = [] | |
279 | ... while node: | |
280 | ... while node.left: | |
281 | ... stack.append(node) | |
282 | ... node = node.left | |
283 | ... yield node.label | |
284 | ... while not node.right: | |
285 | ... try: | |
286 | ... node = stack.pop() | |
287 | ... except IndexError: | |
288 | ... return | |
289 | ... yield node.label | |
290 | ... node = node.right | |
291 | ||
292 | >>> # Exercise the non-recursive generator. | |
293 | >>> for x in t: | |
294 | ... print x, | |
295 | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z | |
296 | ||
297 | """ | |
298 | ||
299 | # Examples from Iterator-List and Python-Dev and c.l.py. | |
300 | ||
301 | email_tests = """ | |
302 | ||
303 | The difference between yielding None and returning it. | |
304 | ||
305 | >>> def g(): | |
306 | ... for i in range(3): | |
307 | ... yield None | |
308 | ... yield None | |
309 | ... return | |
310 | >>> list(g()) | |
311 | [None, None, None, None] | |
312 | ||
313 | Ensure that explicitly raising StopIteration acts like any other exception | |
314 | in try/except, not like a return. | |
315 | ||
316 | >>> def g(): | |
317 | ... yield 1 | |
318 | ... try: | |
319 | ... raise StopIteration | |
320 | ... except: | |
321 | ... yield 2 | |
322 | ... yield 3 | |
323 | >>> list(g()) | |
324 | [1, 2, 3] | |
325 | ||
326 | Next one was posted to c.l.py. | |
327 | ||
328 | >>> def gcomb(x, k): | |
329 | ... "Generate all combinations of k elements from list x." | |
330 | ... | |
331 | ... if k > len(x): | |
332 | ... return | |
333 | ... if k == 0: | |
334 | ... yield [] | |
335 | ... else: | |
336 | ... first, rest = x[0], x[1:] | |
337 | ... # A combination does or doesn't contain first. | |
338 | ... # If it does, the remainder is a k-1 comb of rest. | |
339 | ... for c in gcomb(rest, k-1): | |
340 | ... c.insert(0, first) | |
341 | ... yield c | |
342 | ... # If it doesn't contain first, it's a k comb of rest. | |
343 | ... for c in gcomb(rest, k): | |
344 | ... yield c | |
345 | ||
346 | >>> seq = range(1, 5) | |
347 | >>> for k in range(len(seq) + 2): | |
348 | ... print "%d-combs of %s:" % (k, seq) | |
349 | ... for c in gcomb(seq, k): | |
350 | ... print " ", c | |
351 | 0-combs of [1, 2, 3, 4]: | |
352 | [] | |
353 | 1-combs of [1, 2, 3, 4]: | |
354 | [1] | |
355 | [2] | |
356 | [3] | |
357 | [4] | |
358 | 2-combs of [1, 2, 3, 4]: | |
359 | [1, 2] | |
360 | [1, 3] | |
361 | [1, 4] | |
362 | [2, 3] | |
363 | [2, 4] | |
364 | [3, 4] | |
365 | 3-combs of [1, 2, 3, 4]: | |
366 | [1, 2, 3] | |
367 | [1, 2, 4] | |
368 | [1, 3, 4] | |
369 | [2, 3, 4] | |
370 | 4-combs of [1, 2, 3, 4]: | |
371 | [1, 2, 3, 4] | |
372 | 5-combs of [1, 2, 3, 4]: | |
373 | ||
374 | From the Iterators list, about the types of these things. | |
375 | ||
376 | >>> def g(): | |
377 | ... yield 1 | |
378 | ... | |
379 | >>> type(g) | |
380 | <type 'function'> | |
381 | >>> i = g() | |
382 | >>> type(i) | |
383 | <type 'generator'> | |
384 | >>> [s for s in dir(i) if not s.startswith('_')] | |
385 | ['gi_frame', 'gi_running', 'next'] | |
386 | >>> print i.next.__doc__ | |
387 | x.next() -> the next value, or raise StopIteration | |
388 | >>> iter(i) is i | |
389 | True | |
390 | >>> import types | |
391 | >>> isinstance(i, types.GeneratorType) | |
392 | True | |
393 | ||
394 | And more, added later. | |
395 | ||
396 | >>> i.gi_running | |
397 | 0 | |
398 | >>> type(i.gi_frame) | |
399 | <type 'frame'> | |
400 | >>> i.gi_running = 42 | |
401 | Traceback (most recent call last): | |
402 | ... | |
403 | TypeError: readonly attribute | |
404 | >>> def g(): | |
405 | ... yield me.gi_running | |
406 | >>> me = g() | |
407 | >>> me.gi_running | |
408 | 0 | |
409 | >>> me.next() | |
410 | 1 | |
411 | >>> me.gi_running | |
412 | 0 | |
413 | ||
414 | A clever union-find implementation from c.l.py, due to David Eppstein. | |
415 | Sent: Friday, June 29, 2001 12:16 PM | |
416 | To: python-list@python.org | |
417 | Subject: Re: PEP 255: Simple Generators | |
418 | ||
419 | >>> class disjointSet: | |
420 | ... def __init__(self, name): | |
421 | ... self.name = name | |
422 | ... self.parent = None | |
423 | ... self.generator = self.generate() | |
424 | ... | |
425 | ... def generate(self): | |
426 | ... while not self.parent: | |
427 | ... yield self | |
428 | ... for x in self.parent.generator: | |
429 | ... yield x | |
430 | ... | |
431 | ... def find(self): | |
432 | ... return self.generator.next() | |
433 | ... | |
434 | ... def union(self, parent): | |
435 | ... if self.parent: | |
436 | ... raise ValueError("Sorry, I'm not a root!") | |
437 | ... self.parent = parent | |
438 | ... | |
439 | ... def __str__(self): | |
440 | ... return self.name | |
441 | ||
442 | >>> names = "ABCDEFGHIJKLM" | |
443 | >>> sets = [disjointSet(name) for name in names] | |
444 | >>> roots = sets[:] | |
445 | ||
446 | >>> import random | |
447 | >>> gen = random.WichmannHill(42) | |
448 | >>> while 1: | |
449 | ... for s in sets: | |
450 | ... print "%s->%s" % (s, s.find()), | |
451 | ||
452 | ... if len(roots) > 1: | |
453 | ... s1 = gen.choice(roots) | |
454 | ... roots.remove(s1) | |
455 | ... s2 = gen.choice(roots) | |
456 | ... s1.union(s2) | |
457 | ... print "merged", s1, "into", s2 | |
458 | ... else: | |
459 | ... break | |
460 | A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M | |
461 | merged D into G | |
462 | A->A B->B C->C D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M | |
463 | merged C into F | |
464 | A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->L M->M | |
465 | merged L into A | |
466 | A->A B->B C->F D->G E->E F->F G->G H->H I->I J->J K->K L->A M->M | |
467 | merged H into E | |
468 | A->A B->B C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M | |
469 | merged B into E | |
470 | A->A B->E C->F D->G E->E F->F G->G H->E I->I J->J K->K L->A M->M | |
471 | merged J into G | |
472 | A->A B->E C->F D->G E->E F->F G->G H->E I->I J->G K->K L->A M->M | |
473 | merged E into G | |
474 | A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->M | |
475 | merged M into G | |
476 | A->A B->G C->F D->G E->G F->F G->G H->G I->I J->G K->K L->A M->G | |
477 | merged I into K | |
478 | A->A B->G C->F D->G E->G F->F G->G H->G I->K J->G K->K L->A M->G | |
479 | merged K into A | |
480 | A->A B->G C->F D->G E->G F->F G->G H->G I->A J->G K->A L->A M->G | |
481 | merged F into A | |
482 | A->A B->G C->A D->G E->G F->A G->G H->G I->A J->G K->A L->A M->G | |
483 | merged A into G | |
484 | A->G B->G C->G D->G E->G F->G G->G H->G I->G J->G K->G L->G M->G | |
485 | """ | |
486 | # Emacs turd ' | |
487 | ||
488 | # Fun tests (for sufficiently warped notions of "fun"). | |
489 | ||
490 | fun_tests = """ | |
491 | ||
492 | Build up to a recursive Sieve of Eratosthenes generator. | |
493 | ||
494 | >>> def firstn(g, n): | |
495 | ... return [g.next() for i in range(n)] | |
496 | ||
497 | >>> def intsfrom(i): | |
498 | ... while 1: | |
499 | ... yield i | |
500 | ... i += 1 | |
501 | ||
502 | >>> firstn(intsfrom(5), 7) | |
503 | [5, 6, 7, 8, 9, 10, 11] | |
504 | ||
505 | >>> def exclude_multiples(n, ints): | |
506 | ... for i in ints: | |
507 | ... if i % n: | |
508 | ... yield i | |
509 | ||
510 | >>> firstn(exclude_multiples(3, intsfrom(1)), 6) | |
511 | [1, 2, 4, 5, 7, 8] | |
512 | ||
513 | >>> def sieve(ints): | |
514 | ... prime = ints.next() | |
515 | ... yield prime | |
516 | ... not_divisible_by_prime = exclude_multiples(prime, ints) | |
517 | ... for p in sieve(not_divisible_by_prime): | |
518 | ... yield p | |
519 | ||
520 | >>> primes = sieve(intsfrom(2)) | |
521 | >>> firstn(primes, 20) | |
522 | [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] | |
523 | ||
524 | ||
525 | Another famous problem: generate all integers of the form | |
526 | 2**i * 3**j * 5**k | |
527 | in increasing order, where i,j,k >= 0. Trickier than it may look at first! | |
528 | Try writing it without generators, and correctly, and without generating | |
529 | 3 internal results for each result output. | |
530 | ||
531 | >>> def times(n, g): | |
532 | ... for i in g: | |
533 | ... yield n * i | |
534 | >>> firstn(times(10, intsfrom(1)), 10) | |
535 | [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] | |
536 | ||
537 | >>> def merge(g, h): | |
538 | ... ng = g.next() | |
539 | ... nh = h.next() | |
540 | ... while 1: | |
541 | ... if ng < nh: | |
542 | ... yield ng | |
543 | ... ng = g.next() | |
544 | ... elif ng > nh: | |
545 | ... yield nh | |
546 | ... nh = h.next() | |
547 | ... else: | |
548 | ... yield ng | |
549 | ... ng = g.next() | |
550 | ... nh = h.next() | |
551 | ||
552 | The following works, but is doing a whale of a lot of redundant work -- | |
553 | it's not clear how to get the internal uses of m235 to share a single | |
554 | generator. Note that me_times2 (etc) each need to see every element in the | |
555 | result sequence. So this is an example where lazy lists are more natural | |
556 | (you can look at the head of a lazy list any number of times). | |
557 | ||
558 | >>> def m235(): | |
559 | ... yield 1 | |
560 | ... me_times2 = times(2, m235()) | |
561 | ... me_times3 = times(3, m235()) | |
562 | ... me_times5 = times(5, m235()) | |
563 | ... for i in merge(merge(me_times2, | |
564 | ... me_times3), | |
565 | ... me_times5): | |
566 | ... yield i | |
567 | ||
568 | Don't print "too many" of these -- the implementation above is extremely | |
569 | inefficient: each call of m235() leads to 3 recursive calls, and in | |
570 | turn each of those 3 more, and so on, and so on, until we've descended | |
571 | enough levels to satisfy the print stmts. Very odd: when I printed 5 | |
572 | lines of results below, this managed to screw up Win98's malloc in "the | |
573 | usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting | |
574 | address space, and it *looked* like a very slow leak. | |
575 | ||
576 | >>> result = m235() | |
577 | >>> for i in range(3): | |
578 | ... print firstn(result, 15) | |
579 | [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24] | |
580 | [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80] | |
581 | [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192] | |
582 | ||
583 | Heh. Here's one way to get a shared list, complete with an excruciating | |
584 | namespace renaming trick. The *pretty* part is that the times() and merge() | |
585 | functions can be reused as-is, because they only assume their stream | |
586 | arguments are iterable -- a LazyList is the same as a generator to times(). | |
587 | ||
588 | >>> class LazyList: | |
589 | ... def __init__(self, g): | |
590 | ... self.sofar = [] | |
591 | ... self.fetch = g.next | |
592 | ... | |
593 | ... def __getitem__(self, i): | |
594 | ... sofar, fetch = self.sofar, self.fetch | |
595 | ... while i >= len(sofar): | |
596 | ... sofar.append(fetch()) | |
597 | ... return sofar[i] | |
598 | ||
599 | >>> def m235(): | |
600 | ... yield 1 | |
601 | ... # Gack: m235 below actually refers to a LazyList. | |
602 | ... me_times2 = times(2, m235) | |
603 | ... me_times3 = times(3, m235) | |
604 | ... me_times5 = times(5, m235) | |
605 | ... for i in merge(merge(me_times2, | |
606 | ... me_times3), | |
607 | ... me_times5): | |
608 | ... yield i | |
609 | ||
610 | Print as many of these as you like -- *this* implementation is memory- | |
611 | efficient. | |
612 | ||
613 | >>> m235 = LazyList(m235()) | |
614 | >>> for i in range(5): | |
615 | ... print [m235[j] for j in range(15*i, 15*(i+1))] | |
616 | [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24] | |
617 | [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80] | |
618 | [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192] | |
619 | [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384] | |
620 | [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675] | |
621 | ||
622 | ||
623 | Ye olde Fibonacci generator, LazyList style. | |
624 | ||
625 | >>> def fibgen(a, b): | |
626 | ... | |
627 | ... def sum(g, h): | |
628 | ... while 1: | |
629 | ... yield g.next() + h.next() | |
630 | ... | |
631 | ... def tail(g): | |
632 | ... g.next() # throw first away | |
633 | ... for x in g: | |
634 | ... yield x | |
635 | ... | |
636 | ... yield a | |
637 | ... yield b | |
638 | ... for s in sum(iter(fib), | |
639 | ... tail(iter(fib))): | |
640 | ... yield s | |
641 | ||
642 | >>> fib = LazyList(fibgen(1, 2)) | |
643 | >>> firstn(iter(fib), 17) | |
644 | [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584] | |
645 | """ | |
646 | ||
647 | # syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0 | |
648 | # hackery. | |
649 | ||
650 | syntax_tests = """ | |
651 | ||
652 | >>> def f(): | |
653 | ... return 22 | |
654 | ... yield 1 | |
655 | Traceback (most recent call last): | |
656 | .. | |
657 | SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[0]>, line 2) | |
658 | ||
659 | >>> def f(): | |
660 | ... yield 1 | |
661 | ... return 22 | |
662 | Traceback (most recent call last): | |
663 | .. | |
664 | SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[1]>, line 3) | |
665 | ||
666 | "return None" is not the same as "return" in a generator: | |
667 | ||
668 | >>> def f(): | |
669 | ... yield 1 | |
670 | ... return None | |
671 | Traceback (most recent call last): | |
672 | .. | |
673 | SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[2]>, line 3) | |
674 | ||
675 | This one is fine: | |
676 | ||
677 | >>> def f(): | |
678 | ... yield 1 | |
679 | ... return | |
680 | ||
681 | >>> def f(): | |
682 | ... try: | |
683 | ... yield 1 | |
684 | ... finally: | |
685 | ... pass | |
686 | Traceback (most recent call last): | |
687 | .. | |
688 | SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[4]>, line 3) | |
689 | ||
690 | >>> def f(): | |
691 | ... try: | |
692 | ... try: | |
693 | ... 1//0 | |
694 | ... except ZeroDivisionError: | |
695 | ... yield 666 # bad because *outer* try has finally | |
696 | ... except: | |
697 | ... pass | |
698 | ... finally: | |
699 | ... pass | |
700 | Traceback (most recent call last): | |
701 | ... | |
702 | SyntaxError: 'yield' not allowed in a 'try' block with a 'finally' clause (<doctest test.test_generators.__test__.syntax[5]>, line 6) | |
703 | ||
704 | But this is fine: | |
705 | ||
706 | >>> def f(): | |
707 | ... try: | |
708 | ... try: | |
709 | ... yield 12 | |
710 | ... 1//0 | |
711 | ... except ZeroDivisionError: | |
712 | ... yield 666 | |
713 | ... except: | |
714 | ... try: | |
715 | ... x = 12 | |
716 | ... finally: | |
717 | ... yield 12 | |
718 | ... except: | |
719 | ... return | |
720 | >>> list(f()) | |
721 | [12, 666] | |
722 | ||
723 | >>> def f(): | |
724 | ... yield | |
725 | Traceback (most recent call last): | |
726 | SyntaxError: invalid syntax | |
727 | ||
728 | >>> def f(): | |
729 | ... if 0: | |
730 | ... yield | |
731 | Traceback (most recent call last): | |
732 | SyntaxError: invalid syntax | |
733 | ||
734 | >>> def f(): | |
735 | ... if 0: | |
736 | ... yield 1 | |
737 | >>> type(f()) | |
738 | <type 'generator'> | |
739 | ||
740 | >>> def f(): | |
741 | ... if "": | |
742 | ... yield None | |
743 | >>> type(f()) | |
744 | <type 'generator'> | |
745 | ||
746 | >>> def f(): | |
747 | ... return | |
748 | ... try: | |
749 | ... if x==4: | |
750 | ... pass | |
751 | ... elif 0: | |
752 | ... try: | |
753 | ... 1//0 | |
754 | ... except SyntaxError: | |
755 | ... pass | |
756 | ... else: | |
757 | ... if 0: | |
758 | ... while 12: | |
759 | ... x += 1 | |
760 | ... yield 2 # don't blink | |
761 | ... f(a, b, c, d, e) | |
762 | ... else: | |
763 | ... pass | |
764 | ... except: | |
765 | ... x = 1 | |
766 | ... return | |
767 | >>> type(f()) | |
768 | <type 'generator'> | |
769 | ||
770 | >>> def f(): | |
771 | ... if 0: | |
772 | ... def g(): | |
773 | ... yield 1 | |
774 | ... | |
775 | >>> type(f()) | |
776 | <type 'NoneType'> | |
777 | ||
778 | >>> def f(): | |
779 | ... if 0: | |
780 | ... class C: | |
781 | ... def __init__(self): | |
782 | ... yield 1 | |
783 | ... def f(self): | |
784 | ... yield 2 | |
785 | >>> type(f()) | |
786 | <type 'NoneType'> | |
787 | ||
788 | >>> def f(): | |
789 | ... if 0: | |
790 | ... return | |
791 | ... if 0: | |
792 | ... yield 2 | |
793 | >>> type(f()) | |
794 | <type 'generator'> | |
795 | ||
796 | ||
797 | >>> def f(): | |
798 | ... if 0: | |
799 | ... lambda x: x # shouldn't trigger here | |
800 | ... return # or here | |
801 | ... def f(i): | |
802 | ... return 2*i # or here | |
803 | ... if 0: | |
804 | ... return 3 # but *this* sucks (line 8) | |
805 | ... if 0: | |
806 | ... yield 2 # because it's a generator | |
807 | Traceback (most recent call last): | |
808 | SyntaxError: 'return' with argument inside generator (<doctest test.test_generators.__test__.syntax[22]>, line 8) | |
809 | ||
810 | This one caused a crash (see SF bug 567538): | |
811 | ||
812 | >>> def f(): | |
813 | ... for i in range(3): | |
814 | ... try: | |
815 | ... continue | |
816 | ... finally: | |
817 | ... yield i | |
818 | ... | |
819 | >>> g = f() | |
820 | >>> print g.next() | |
821 | 0 | |
822 | >>> print g.next() | |
823 | 1 | |
824 | >>> print g.next() | |
825 | 2 | |
826 | >>> print g.next() | |
827 | Traceback (most recent call last): | |
828 | StopIteration | |
829 | """ | |
830 | ||
831 | # conjoin is a simple backtracking generator, named in honor of Icon's | |
832 | # "conjunction" control structure. Pass a list of no-argument functions | |
833 | # that return iterable objects. Easiest to explain by example: assume the | |
834 | # function list [x, y, z] is passed. Then conjoin acts like: | |
835 | # | |
836 | # def g(): | |
837 | # values = [None] * 3 | |
838 | # for values[0] in x(): | |
839 | # for values[1] in y(): | |
840 | # for values[2] in z(): | |
841 | # yield values | |
842 | # | |
843 | # So some 3-lists of values *may* be generated, each time we successfully | |
844 | # get into the innermost loop. If an iterator fails (is exhausted) before | |
845 | # then, it "backtracks" to get the next value from the nearest enclosing | |
846 | # iterator (the one "to the left"), and starts all over again at the next | |
847 | # slot (pumps a fresh iterator). Of course this is most useful when the | |
848 | # iterators have side-effects, so that which values *can* be generated at | |
849 | # each slot depend on the values iterated at previous slots. | |
850 | ||
851 | def conjoin(gs): | |
852 | ||
853 | values = [None] * len(gs) | |
854 | ||
855 | def gen(i, values=values): | |
856 | if i >= len(gs): | |
857 | yield values | |
858 | else: | |
859 | for values[i] in gs[i](): | |
860 | for x in gen(i+1): | |
861 | yield x | |
862 | ||
863 | for x in gen(0): | |
864 | yield x | |
865 | ||
866 | # That works fine, but recursing a level and checking i against len(gs) for | |
867 | # each item produced is inefficient. By doing manual loop unrolling across | |
868 | # generator boundaries, it's possible to eliminate most of that overhead. | |
869 | # This isn't worth the bother *in general* for generators, but conjoin() is | |
870 | # a core building block for some CPU-intensive generator applications. | |
871 | ||
872 | def conjoin(gs): | |
873 | ||
874 | n = len(gs) | |
875 | values = [None] * n | |
876 | ||
877 | # Do one loop nest at time recursively, until the # of loop nests | |
878 | # remaining is divisible by 3. | |
879 | ||
880 | def gen(i, values=values): | |
881 | if i >= n: | |
882 | yield values | |
883 | ||
884 | elif (n-i) % 3: | |
885 | ip1 = i+1 | |
886 | for values[i] in gs[i](): | |
887 | for x in gen(ip1): | |
888 | yield x | |
889 | ||
890 | else: | |
891 | for x in _gen3(i): | |
892 | yield x | |
893 | ||
894 | # Do three loop nests at a time, recursing only if at least three more | |
895 | # remain. Don't call directly: this is an internal optimization for | |
896 | # gen's use. | |
897 | ||
898 | def _gen3(i, values=values): | |
899 | assert i < n and (n-i) % 3 == 0 | |
900 | ip1, ip2, ip3 = i+1, i+2, i+3 | |
901 | g, g1, g2 = gs[i : ip3] | |
902 | ||
903 | if ip3 >= n: | |
904 | # These are the last three, so we can yield values directly. | |
905 | for values[i] in g(): | |
906 | for values[ip1] in g1(): | |
907 | for values[ip2] in g2(): | |
908 | yield values | |
909 | ||
910 | else: | |
911 | # At least 6 loop nests remain; peel off 3 and recurse for the | |
912 | # rest. | |
913 | for values[i] in g(): | |
914 | for values[ip1] in g1(): | |
915 | for values[ip2] in g2(): | |
916 | for x in _gen3(ip3): | |
917 | yield x | |
918 | ||
919 | for x in gen(0): | |
920 | yield x | |
921 | ||
922 | # And one more approach: For backtracking apps like the Knight's Tour | |
923 | # solver below, the number of backtracking levels can be enormous (one | |
924 | # level per square, for the Knight's Tour, so that e.g. a 100x100 board | |
925 | # needs 10,000 levels). In such cases Python is likely to run out of | |
926 | # stack space due to recursion. So here's a recursion-free version of | |
927 | # conjoin too. | |
928 | # NOTE WELL: This allows large problems to be solved with only trivial | |
929 | # demands on stack space. Without explicitly resumable generators, this is | |
930 | # much harder to achieve. OTOH, this is much slower (up to a factor of 2) | |
931 | # than the fancy unrolled recursive conjoin. | |
932 | ||
933 | def flat_conjoin(gs): # rename to conjoin to run tests with this instead | |
934 | n = len(gs) | |
935 | values = [None] * n | |
936 | iters = [None] * n | |
937 | _StopIteration = StopIteration # make local because caught a *lot* | |
938 | i = 0 | |
939 | while 1: | |
940 | # Descend. | |
941 | try: | |
942 | while i < n: | |
943 | it = iters[i] = gs[i]().next | |
944 | values[i] = it() | |
945 | i += 1 | |
946 | except _StopIteration: | |
947 | pass | |
948 | else: | |
949 | assert i == n | |
950 | yield values | |
951 | ||
952 | # Backtrack until an older iterator can be resumed. | |
953 | i -= 1 | |
954 | while i >= 0: | |
955 | try: | |
956 | values[i] = iters[i]() | |
957 | # Success! Start fresh at next level. | |
958 | i += 1 | |
959 | break | |
960 | except _StopIteration: | |
961 | # Continue backtracking. | |
962 | i -= 1 | |
963 | else: | |
964 | assert i < 0 | |
965 | break | |
966 | ||
967 | # A conjoin-based N-Queens solver. | |
968 | ||
969 | class Queens: | |
970 | def __init__(self, n): | |
971 | self.n = n | |
972 | rangen = range(n) | |
973 | ||
974 | # Assign a unique int to each column and diagonal. | |
975 | # columns: n of those, range(n). | |
976 | # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along | |
977 | # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0- | |
978 | # based. | |
979 | # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along | |
980 | # each, smallest i+j is 0, largest is 2n-2. | |
981 | ||
982 | # For each square, compute a bit vector of the columns and | |
983 | # diagonals it covers, and for each row compute a function that | |
984 | # generates the possiblities for the columns in that row. | |
985 | self.rowgenerators = [] | |
986 | for i in rangen: | |
987 | rowuses = [(1L << j) | # column ordinal | |
988 | (1L << (n + i-j + n-1)) | # NW-SE ordinal | |
989 | (1L << (n + 2*n-1 + i+j)) # NE-SW ordinal | |
990 | for j in rangen] | |
991 | ||
992 | def rowgen(rowuses=rowuses): | |
993 | for j in rangen: | |
994 | uses = rowuses[j] | |
995 | if uses & self.used == 0: | |
996 | self.used |= uses | |
997 | yield j | |
998 | self.used &= ~uses | |
999 | ||
1000 | self.rowgenerators.append(rowgen) | |
1001 | ||
1002 | # Generate solutions. | |
1003 | def solve(self): | |
1004 | self.used = 0 | |
1005 | for row2col in conjoin(self.rowgenerators): | |
1006 | yield row2col | |
1007 | ||
1008 | def printsolution(self, row2col): | |
1009 | n = self.n | |
1010 | assert n == len(row2col) | |
1011 | sep = "+" + "-+" * n | |
1012 | print sep | |
1013 | for i in range(n): | |
1014 | squares = [" " for j in range(n)] | |
1015 | squares[row2col[i]] = "Q" | |
1016 | print "|" + "|".join(squares) + "|" | |
1017 | print sep | |
1018 | ||
1019 | # A conjoin-based Knight's Tour solver. This is pretty sophisticated | |
1020 | # (e.g., when used with flat_conjoin above, and passing hard=1 to the | |
1021 | # constructor, a 200x200 Knight's Tour was found quickly -- note that we're | |
1022 | # creating 10s of thousands of generators then!), and is lengthy. | |
1023 | ||
1024 | class Knights: | |
1025 | def __init__(self, m, n, hard=0): | |
1026 | self.m, self.n = m, n | |
1027 | ||
1028 | # solve() will set up succs[i] to be a list of square #i's | |
1029 | # successors. | |
1030 | succs = self.succs = [] | |
1031 | ||
1032 | # Remove i0 from each of its successor's successor lists, i.e. | |
1033 | # successors can't go back to i0 again. Return 0 if we can | |
1034 | # detect this makes a solution impossible, else return 1. | |
1035 | ||
1036 | def remove_from_successors(i0, len=len): | |
1037 | # If we remove all exits from a free square, we're dead: | |
1038 | # even if we move to it next, we can't leave it again. | |
1039 | # If we create a square with one exit, we must visit it next; | |
1040 | # else somebody else will have to visit it, and since there's | |
1041 | # only one adjacent, there won't be a way to leave it again. | |
1042 | # Finelly, if we create more than one free square with a | |
1043 | # single exit, we can only move to one of them next, leaving | |
1044 | # the other one a dead end. | |
1045 | ne0 = ne1 = 0 | |
1046 | for i in succs[i0]: | |
1047 | s = succs[i] | |
1048 | s.remove(i0) | |
1049 | e = len(s) | |
1050 | if e == 0: | |
1051 | ne0 += 1 | |
1052 | elif e == 1: | |
1053 | ne1 += 1 | |
1054 | return ne0 == 0 and ne1 < 2 | |
1055 | ||
1056 | # Put i0 back in each of its successor's successor lists. | |
1057 | ||
1058 | def add_to_successors(i0): | |
1059 | for i in succs[i0]: | |
1060 | succs[i].append(i0) | |
1061 | ||
1062 | # Generate the first move. | |
1063 | def first(): | |
1064 | if m < 1 or n < 1: | |
1065 | return | |
1066 | ||
1067 | # Since we're looking for a cycle, it doesn't matter where we | |
1068 | # start. Starting in a corner makes the 2nd move easy. | |
1069 | corner = self.coords2index(0, 0) | |
1070 | remove_from_successors(corner) | |
1071 | self.lastij = corner | |
1072 | yield corner | |
1073 | add_to_successors(corner) | |
1074 | ||
1075 | # Generate the second moves. | |
1076 | def second(): | |
1077 | corner = self.coords2index(0, 0) | |
1078 | assert self.lastij == corner # i.e., we started in the corner | |
1079 | if m < 3 or n < 3: | |
1080 | return | |
1081 | assert len(succs[corner]) == 2 | |
1082 | assert self.coords2index(1, 2) in succs[corner] | |
1083 | assert self.coords2index(2, 1) in succs[corner] | |
1084 | # Only two choices. Whichever we pick, the other must be the | |
1085 | # square picked on move m*n, as it's the only way to get back | |
1086 | # to (0, 0). Save its index in self.final so that moves before | |
1087 | # the last know it must be kept free. | |
1088 | for i, j in (1, 2), (2, 1): | |
1089 | this = self.coords2index(i, j) | |
1090 | final = self.coords2index(3-i, 3-j) | |
1091 | self.final = final | |
1092 | ||
1093 | remove_from_successors(this) | |
1094 | succs[final].append(corner) | |
1095 | self.lastij = this | |
1096 | yield this | |
1097 | succs[final].remove(corner) | |
1098 | add_to_successors(this) | |
1099 | ||
1100 | # Generate moves 3 thru m*n-1. | |
1101 | def advance(len=len): | |
1102 | # If some successor has only one exit, must take it. | |
1103 | # Else favor successors with fewer exits. | |
1104 | candidates = [] | |
1105 | for i in succs[self.lastij]: | |
1106 | e = len(succs[i]) | |
1107 | assert e > 0, "else remove_from_successors() pruning flawed" | |
1108 | if e == 1: | |
1109 | candidates = [(e, i)] | |
1110 | break | |
1111 | candidates.append((e, i)) | |
1112 | else: | |
1113 | candidates.sort() | |
1114 | ||
1115 | for e, i in candidates: | |
1116 | if i != self.final: | |
1117 | if remove_from_successors(i): | |
1118 | self.lastij = i | |
1119 | yield i | |
1120 | add_to_successors(i) | |
1121 | ||
1122 | # Generate moves 3 thru m*n-1. Alternative version using a | |
1123 | # stronger (but more expensive) heuristic to order successors. | |
1124 | # Since the # of backtracking levels is m*n, a poor move early on | |
1125 | # can take eons to undo. Smallest square board for which this | |
1126 | # matters a lot is 52x52. | |
1127 | def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len): | |
1128 | # If some successor has only one exit, must take it. | |
1129 | # Else favor successors with fewer exits. | |
1130 | # Break ties via max distance from board centerpoint (favor | |
1131 | # corners and edges whenever possible). | |
1132 | candidates = [] | |
1133 | for i in succs[self.lastij]: | |
1134 | e = len(succs[i]) | |
1135 | assert e > 0, "else remove_from_successors() pruning flawed" | |
1136 | if e == 1: | |
1137 | candidates = [(e, 0, i)] | |
1138 | break | |
1139 | i1, j1 = self.index2coords(i) | |
1140 | d = (i1 - vmid)**2 + (j1 - hmid)**2 | |
1141 | candidates.append((e, -d, i)) | |
1142 | else: | |
1143 | candidates.sort() | |
1144 | ||
1145 | for e, d, i in candidates: | |
1146 | if i != self.final: | |
1147 | if remove_from_successors(i): | |
1148 | self.lastij = i | |
1149 | yield i | |
1150 | add_to_successors(i) | |
1151 | ||
1152 | # Generate the last move. | |
1153 | def last(): | |
1154 | assert self.final in succs[self.lastij] | |
1155 | yield self.final | |
1156 | ||
1157 | if m*n < 4: | |
1158 | self.squaregenerators = [first] | |
1159 | else: | |
1160 | self.squaregenerators = [first, second] + \ | |
1161 | [hard and advance_hard or advance] * (m*n - 3) + \ | |
1162 | [last] | |
1163 | ||
1164 | def coords2index(self, i, j): | |
1165 | assert 0 <= i < self.m | |
1166 | assert 0 <= j < self.n | |
1167 | return i * self.n + j | |
1168 | ||
1169 | def index2coords(self, index): | |
1170 | assert 0 <= index < self.m * self.n | |
1171 | return divmod(index, self.n) | |
1172 | ||
1173 | def _init_board(self): | |
1174 | succs = self.succs | |
1175 | del succs[:] | |
1176 | m, n = self.m, self.n | |
1177 | c2i = self.coords2index | |
1178 | ||
1179 | offsets = [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2), | |
1180 | (-1, -2), (-2, -1), (-2, 1), (-1, 2)] | |
1181 | rangen = range(n) | |
1182 | for i in range(m): | |
1183 | for j in rangen: | |
1184 | s = [c2i(i+io, j+jo) for io, jo in offsets | |
1185 | if 0 <= i+io < m and | |
1186 | 0 <= j+jo < n] | |
1187 | succs.append(s) | |
1188 | ||
1189 | # Generate solutions. | |
1190 | def solve(self): | |
1191 | self._init_board() | |
1192 | for x in conjoin(self.squaregenerators): | |
1193 | yield x | |
1194 | ||
1195 | def printsolution(self, x): | |
1196 | m, n = self.m, self.n | |
1197 | assert len(x) == m*n | |
1198 | w = len(str(m*n)) | |
1199 | format = "%" + str(w) + "d" | |
1200 | ||
1201 | squares = [[None] * n for i in range(m)] | |
1202 | k = 1 | |
1203 | for i in x: | |
1204 | i1, j1 = self.index2coords(i) | |
1205 | squares[i1][j1] = format % k | |
1206 | k += 1 | |
1207 | ||
1208 | sep = "+" + ("-" * w + "+") * n | |
1209 | print sep | |
1210 | for i in range(m): | |
1211 | row = squares[i] | |
1212 | print "|" + "|".join(row) + "|" | |
1213 | print sep | |
1214 | ||
1215 | conjoin_tests = """ | |
1216 | ||
1217 | Generate the 3-bit binary numbers in order. This illustrates dumbest- | |
1218 | possible use of conjoin, just to generate the full cross-product. | |
1219 | ||
1220 | >>> for c in conjoin([lambda: iter((0, 1))] * 3): | |
1221 | ... print c | |
1222 | [0, 0, 0] | |
1223 | [0, 0, 1] | |
1224 | [0, 1, 0] | |
1225 | [0, 1, 1] | |
1226 | [1, 0, 0] | |
1227 | [1, 0, 1] | |
1228 | [1, 1, 0] | |
1229 | [1, 1, 1] | |
1230 | ||
1231 | For efficiency in typical backtracking apps, conjoin() yields the same list | |
1232 | object each time. So if you want to save away a full account of its | |
1233 | generated sequence, you need to copy its results. | |
1234 | ||
1235 | >>> def gencopy(iterator): | |
1236 | ... for x in iterator: | |
1237 | ... yield x[:] | |
1238 | ||
1239 | >>> for n in range(10): | |
1240 | ... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n))) | |
1241 | ... print n, len(all), all[0] == [0] * n, all[-1] == [1] * n | |
1242 | 0 1 True True | |
1243 | 1 2 True True | |
1244 | 2 4 True True | |
1245 | 3 8 True True | |
1246 | 4 16 True True | |
1247 | 5 32 True True | |
1248 | 6 64 True True | |
1249 | 7 128 True True | |
1250 | 8 256 True True | |
1251 | 9 512 True True | |
1252 | ||
1253 | And run an 8-queens solver. | |
1254 | ||
1255 | >>> q = Queens(8) | |
1256 | >>> LIMIT = 2 | |
1257 | >>> count = 0 | |
1258 | >>> for row2col in q.solve(): | |
1259 | ... count += 1 | |
1260 | ... if count <= LIMIT: | |
1261 | ... print "Solution", count | |
1262 | ... q.printsolution(row2col) | |
1263 | Solution 1 | |
1264 | +-+-+-+-+-+-+-+-+ | |
1265 | |Q| | | | | | | | | |
1266 | +-+-+-+-+-+-+-+-+ | |
1267 | | | | | |Q| | | | | |
1268 | +-+-+-+-+-+-+-+-+ | |
1269 | | | | | | | | |Q| | |
1270 | +-+-+-+-+-+-+-+-+ | |
1271 | | | | | | |Q| | | | |
1272 | +-+-+-+-+-+-+-+-+ | |
1273 | | | |Q| | | | | | | |
1274 | +-+-+-+-+-+-+-+-+ | |
1275 | | | | | | | |Q| | | |
1276 | +-+-+-+-+-+-+-+-+ | |
1277 | | |Q| | | | | | | | |
1278 | +-+-+-+-+-+-+-+-+ | |
1279 | | | | |Q| | | | | | |
1280 | +-+-+-+-+-+-+-+-+ | |
1281 | Solution 2 | |
1282 | +-+-+-+-+-+-+-+-+ | |
1283 | |Q| | | | | | | | | |
1284 | +-+-+-+-+-+-+-+-+ | |
1285 | | | | | | |Q| | | | |
1286 | +-+-+-+-+-+-+-+-+ | |
1287 | | | | | | | | |Q| | |
1288 | +-+-+-+-+-+-+-+-+ | |
1289 | | | |Q| | | | | | | |
1290 | +-+-+-+-+-+-+-+-+ | |
1291 | | | | | | | |Q| | | |
1292 | +-+-+-+-+-+-+-+-+ | |
1293 | | | | |Q| | | | | | |
1294 | +-+-+-+-+-+-+-+-+ | |
1295 | | |Q| | | | | | | | |
1296 | +-+-+-+-+-+-+-+-+ | |
1297 | | | | | |Q| | | | | |
1298 | +-+-+-+-+-+-+-+-+ | |
1299 | ||
1300 | >>> print count, "solutions in all." | |
1301 | 92 solutions in all. | |
1302 | ||
1303 | And run a Knight's Tour on a 10x10 board. Note that there are about | |
1304 | 20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion. | |
1305 | ||
1306 | >>> k = Knights(10, 10) | |
1307 | >>> LIMIT = 2 | |
1308 | >>> count = 0 | |
1309 | >>> for x in k.solve(): | |
1310 | ... count += 1 | |
1311 | ... if count <= LIMIT: | |
1312 | ... print "Solution", count | |
1313 | ... k.printsolution(x) | |
1314 | ... else: | |
1315 | ... break | |
1316 | Solution 1 | |
1317 | +---+---+---+---+---+---+---+---+---+---+ | |
1318 | | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8| | |
1319 | +---+---+---+---+---+---+---+---+---+---+ | |
1320 | | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11| | |
1321 | +---+---+---+---+---+---+---+---+---+---+ | |
1322 | | 59|100| 73| 36| 41| 56| 39| 32| 9| 6| | |
1323 | +---+---+---+---+---+---+---+---+---+---+ | |
1324 | | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31| | |
1325 | +---+---+---+---+---+---+---+---+---+---+ | |
1326 | | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50| | |
1327 | +---+---+---+---+---+---+---+---+---+---+ | |
1328 | | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13| | |
1329 | +---+---+---+---+---+---+---+---+---+---+ | |
1330 | | 87| 98| 91| 80| 77| 84| 53| 46| 65| 44| | |
1331 | +---+---+---+---+---+---+---+---+---+---+ | |
1332 | | 90| 23| 88| 95| 70| 79| 68| 83| 14| 17| | |
1333 | +---+---+---+---+---+---+---+---+---+---+ | |
1334 | | 97| 92| 21| 78| 81| 94| 19| 16| 45| 66| | |
1335 | +---+---+---+---+---+---+---+---+---+---+ | |
1336 | | 22| 89| 96| 93| 20| 69| 82| 67| 18| 15| | |
1337 | +---+---+---+---+---+---+---+---+---+---+ | |
1338 | Solution 2 | |
1339 | +---+---+---+---+---+---+---+---+---+---+ | |
1340 | | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8| | |
1341 | +---+---+---+---+---+---+---+---+---+---+ | |
1342 | | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11| | |
1343 | +---+---+---+---+---+---+---+---+---+---+ | |
1344 | | 59|100| 73| 36| 41| 56| 39| 32| 9| 6| | |
1345 | +---+---+---+---+---+---+---+---+---+---+ | |
1346 | | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31| | |
1347 | +---+---+---+---+---+---+---+---+---+---+ | |
1348 | | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50| | |
1349 | +---+---+---+---+---+---+---+---+---+---+ | |
1350 | | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13| | |
1351 | +---+---+---+---+---+---+---+---+---+---+ | |
1352 | | 87| 98| 89| 80| 77| 84| 53| 46| 65| 44| | |
1353 | +---+---+---+---+---+---+---+---+---+---+ | |
1354 | | 90| 23| 92| 95| 70| 79| 68| 83| 14| 17| | |
1355 | +---+---+---+---+---+---+---+---+---+---+ | |
1356 | | 97| 88| 21| 78| 81| 94| 19| 16| 45| 66| | |
1357 | +---+---+---+---+---+---+---+---+---+---+ | |
1358 | | 22| 91| 96| 93| 20| 69| 82| 67| 18| 15| | |
1359 | +---+---+---+---+---+---+---+---+---+---+ | |
1360 | """ | |
1361 | ||
1362 | weakref_tests = """\ | |
1363 | Generators are weakly referencable: | |
1364 | ||
1365 | >>> import weakref | |
1366 | >>> def gen(): | |
1367 | ... yield 'foo!' | |
1368 | ... | |
1369 | >>> wr = weakref.ref(gen) | |
1370 | >>> wr() is gen | |
1371 | True | |
1372 | >>> p = weakref.proxy(gen) | |
1373 | ||
1374 | Generator-iterators are weakly referencable as well: | |
1375 | ||
1376 | >>> gi = gen() | |
1377 | >>> wr = weakref.ref(gi) | |
1378 | >>> wr() is gi | |
1379 | True | |
1380 | >>> p = weakref.proxy(gi) | |
1381 | >>> list(p) | |
1382 | ['foo!'] | |
1383 | ||
1384 | """ | |
1385 | ||
1386 | __test__ = {"tut": tutorial_tests, | |
1387 | "pep": pep_tests, | |
1388 | "email": email_tests, | |
1389 | "fun": fun_tests, | |
1390 | "syntax": syntax_tests, | |
1391 | "conjoin": conjoin_tests, | |
1392 | "weakref": weakref_tests, | |
1393 | } | |
1394 | ||
1395 | # Magic test name that regrtest.py invokes *after* importing this module. | |
1396 | # This worms around a bootstrap problem. | |
1397 | # Note that doctest and regrtest both look in sys.argv for a "-v" argument, | |
1398 | # so this works as expected in both ways of running regrtest. | |
1399 | def test_main(verbose=None): | |
1400 | from test import test_support, test_generators | |
1401 | test_support.run_doctest(test_generators, verbose) | |
1402 | ||
1403 | # This part isn't needed for regrtest, but for running the test directly. | |
1404 | if __name__ == "__main__": | |
1405 | test_main(1) |