← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to lib-python/2.4.1/test/test_generators.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib-python/2.4.1/test/test_generators.py
 
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
...     print
 
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)