<s> tutorial_tests = """<STR_LIT>""" <EOL> pep_tests = """<STR_LIT>""" <EOL> email_tests = """<STR_LIT>""" <EOL> fun_tests = """<STR_LIT>""" <EOL> syntax_tests = """<STR_LIT>""" <EOL> def conjoin ( gs ) : <EOL> values = [ None ] * len ( gs ) <EOL> def gen ( i , values = values ) : <EOL> if i >= len ( gs ) : <EOL> yield values <EOL> else : <EOL> for values [ i ] in gs [ i ] ( ) : <EOL> for x in gen ( i + <NUM_LIT:1> ) : <EOL> yield x <EOL> for x in gen ( <NUM_LIT:0> ) : <EOL> yield x <EOL> def conjoin ( gs ) : <EOL> n = len ( gs ) <EOL> values = [ None ] * n <EOL> def gen ( i , values = values ) : <EOL> if i >= n : <EOL> yield values <EOL> elif ( n - i ) % <NUM_LIT:3> : <EOL> ip1 = i + <NUM_LIT:1> <EOL> for values [ i ] in gs [ i ] ( ) : <EOL> for x in gen ( ip1 ) : <EOL> yield x <EOL> else : <EOL> for x in _gen3 ( i ) : <EOL> yield x <EOL> def _gen3 ( i , values = values ) : <EOL> assert i < n and ( n - i ) % <NUM_LIT:3> == <NUM_LIT:0> <EOL> ip1 , ip2 , ip3 = i + <NUM_LIT:1> , i + <NUM_LIT:2> , i + <NUM_LIT:3> <EOL> g , g1 , g2 = gs [ i : ip3 ] <EOL> if ip3 >= n : <EOL> for values [ i ] in g ( ) : <EOL> for values [ ip1 ] in g1 ( ) : <EOL> for values [ ip2 ] in g2 ( ) : <EOL> yield values <EOL> else : <EOL> for values [ i ] in g ( ) : <EOL> for values [ ip1 ] in g1 ( ) : <EOL> for values [ ip2 ] in g2 ( ) : <EOL> for x in _gen3 ( ip3 ) : <EOL> yield x <EOL> for x in gen ( <NUM_LIT:0> ) : <EOL> yield x <EOL> def flat_conjoin ( gs ) : <EOL> n = len ( gs ) <EOL> values = [ None ] * n <EOL> iters = [ None ] * n <EOL> _StopIteration = StopIteration <EOL> i = <NUM_LIT:0> <EOL> while <NUM_LIT:1> : <EOL> try : <EOL> while i < n : <EOL> it = iters [ i ] = gs [ i ] ( ) . next <EOL> values [ i ] = it ( ) <EOL> i += <NUM_LIT:1> <EOL> except _StopIteration : <EOL> pass <EOL> else : <EOL> assert i == n <EOL> yield values <EOL> i -= <NUM_LIT:1> <EOL> while i >= <NUM_LIT:0> : <EOL> try : <EOL> values [ i ] = iters [ i ] ( ) <EOL> i += <NUM_LIT:1> <EOL> break <EOL> except _StopIteration : <EOL> i -= <NUM_LIT:1> <EOL> else : <EOL> assert i < <NUM_LIT:0> <EOL> break <EOL> class Queens : <EOL> def __init__ ( self , n ) : <EOL> self . n = n <EOL> rangen = range ( n ) <EOL> self . rowgenerators = [ ] <EOL> for i in rangen : <EOL> rowuses = [ ( <NUM_LIT:1> L << j ) | <EOL> ( <NUM_LIT:1> L << ( n + i - j + n - <NUM_LIT:1> ) ) | <EOL> ( <NUM_LIT:1> L << ( n + <NUM_LIT:2> * n - <NUM_LIT:1> + i + j ) ) <EOL> for j in rangen ] <EOL> def rowgen ( rowuses = rowuses ) : <EOL> for j in rangen : <EOL> uses = rowuses [ j ] <EOL> if uses & self . used == <NUM_LIT:0> : <EOL> self . used |= uses <EOL> yield j <EOL> self . used &= ~ uses <EOL> self . rowgenerators . append ( rowgen ) <EOL> def solve ( self ) : <EOL> self . used = <NUM_LIT:0> <EOL> for row2col in conjoin ( self . rowgenerators ) : <EOL> yield row2col <EOL> def printsolution ( self , row2col ) : <EOL> n = self . n <EOL> assert n == len ( row2col ) <EOL> sep = "<STR_LIT:+>" + "<STR_LIT>" * n <EOL> print sep <EOL> for i in range ( n ) : <EOL> squares = [ "<STR_LIT:U+0020>" for j in range ( n ) ] <EOL> squares [ row2col [ i ] ] = "<STR_LIT>" <EOL> print "<STR_LIT:|>" + "<STR_LIT:|>" . join ( squares ) + "<STR_LIT:|>" <EOL> print sep <EOL> class Knights : <EOL> def __init__ ( self , m , n , hard = <NUM_LIT:0> ) : <EOL> self . m , self . n = m , n <EOL> succs = self . succs = [ ] <EOL> def remove_from_successors ( i0 , len = len ) : <EOL> ne0 = ne1 = <NUM_LIT:0> <EOL> for i in succs [ i0 ] : <EOL> s = succs [ i ] <EOL> s . remove ( i0 ) <EOL> e = len ( s ) <EOL> if e == <NUM_LIT:0> : <EOL> ne0 += <NUM_LIT:1> <EOL> elif e == <NUM_LIT:1> : <EOL> ne1 += <NUM_LIT:1> <EOL> return ne0 == <NUM_LIT:0> and ne1 < <NUM_LIT:2> <EOL> def add_to_successors ( i0 ) : <EOL> for i in succs [ i0 ] : <EOL> succs [ i ] . append ( i0 ) <EOL> def first ( ) : <EOL> if m < <NUM_LIT:1> or n < <NUM_LIT:1> : <EOL> return <EOL> corner = self . coords2index ( <NUM_LIT:0> , <NUM_LIT:0> ) <EOL> remove_from_successors ( corner ) <EOL> self . lastij = corner <EOL> yield corner <EOL> add_to_successors ( corner ) <EOL> def second ( ) : <EOL> corner = self . coords2index ( <NUM_LIT:0> , <NUM_LIT:0> ) <EOL> assert self . lastij == corner <EOL> if m < <NUM_LIT:3> or n < <NUM_LIT:3> : <EOL> return <EOL> assert len ( succs [ corner ] ) == <NUM_LIT:2> <EOL> assert self . coords2index ( <NUM_LIT:1> , <NUM_LIT:2> ) in succs [ corner ] <EOL> assert self . coords2index ( <NUM_LIT:2> , <NUM_LIT:1> ) in succs [ corner ] <EOL> for i , j in ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:1> ) : <EOL> this = self . coords2index ( i , j ) <EOL> final = self . coords2index ( <NUM_LIT:3> - i , <NUM_LIT:3> - j ) <EOL> self . final = final <EOL> remove_from_successors ( this ) <EOL> succs [ final ] . append ( corner ) <EOL> self . lastij = this <EOL> yield this <EOL> succs [ final ] . remove ( corner ) <EOL> add_to_successors ( this ) <EOL> def advance ( len = len ) : <EOL> candidates = [ ] <EOL> for i in succs [ self . lastij ] : <EOL> e = len ( succs [ i ] ) <EOL> assert e > <NUM_LIT:0> , "<STR_LIT>" <EOL> if e == <NUM_LIT:1> : <EOL> candidates = [ ( e , i ) ] <EOL> break <EOL> candidates . append ( ( e , i ) ) <EOL> else : <EOL> candidates . sort ( ) <EOL> for e , i in candidates : <EOL> if i != self . final : <EOL> if remove_from_successors ( i ) : <EOL> self . lastij = i <EOL> yield i <EOL> add_to_successors ( i ) <EOL> def advance_hard ( vmid = ( m - <NUM_LIT:1> ) / <NUM_LIT> , hmid = ( n - <NUM_LIT:1> ) / <NUM_LIT> , len = len ) : <EOL> candidates = [ ] <EOL> for i in succs [ self . lastij ] : <EOL> e = len ( succs [ i ] ) <EOL> assert e > <NUM_LIT:0> , "<STR_LIT>" <EOL> if e == <NUM_LIT:1> : <EOL> candidates = [ ( e , <NUM_LIT:0> , i ) ] <EOL> break <EOL> i1 , j1 = self . index2coords ( i ) <EOL> d = ( i1 - vmid ) ** <NUM_LIT:2> + ( j1 - hmid ) ** <NUM_LIT:2> <EOL> candidates . append ( ( e , - d , i ) ) <EOL> else : <EOL> candidates . sort ( ) <EOL> for e , d , i in candidates : <EOL> if i != self . final : <EOL> if remove_from_successors ( i ) : <EOL> self . lastij = i <EOL> yield i <EOL> add_to_successors ( i ) <EOL> def last ( ) : <EOL> assert self . final in succs [ self . lastij ] <EOL> yield self . final <EOL> if m * n < <NUM_LIT:4> : <EOL> self . squaregenerators = [ first ] <EOL> else : <EOL> self . squaregenerators = [ first , second ] + [ hard and advance_hard or advance ] * ( m * n - <NUM_LIT:3> ) + [ last ] <EOL> def coords2index ( self , i , j ) : <EOL> assert <NUM_LIT:0> <= i < self . m <EOL> assert <NUM_LIT:0> <= j < self . n <EOL> return i * self . n + j <EOL> def index2coords ( self , index ) : <EOL> assert <NUM_LIT:0> <= index < self . m * self . n <EOL> return divmod ( index , self . n ) <EOL> def _init_board ( self ) : <EOL> succs = self . succs <EOL> del succs [ : ] <EOL> m , n = self . m , self . n <EOL> c2i = self . coords2index <EOL> offsets = [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , - <NUM_LIT:1> ) , ( <NUM_LIT:1> , - <NUM_LIT:2> ) , <EOL> ( - <NUM_LIT:1> , - <NUM_LIT:2> ) , ( - <NUM_LIT:2> , - <NUM_LIT:1> ) , ( - <NUM_LIT:2> , <NUM_LIT:1> ) , ( - <NUM_LIT:1> , <NUM_LIT:2> ) ] <EOL> rangen = range ( n ) <EOL> for i in range ( m ) : <EOL> for j in rangen : <EOL> s = [ c2i ( i + io , j + jo ) for io , jo in offsets <EOL> if <NUM_LIT:0> <= i + io < m and <EOL> <NUM_LIT:0> <= j + jo < n ] <EOL> succs . append ( s ) <EOL> def solve ( self ) : <EOL> self . _init_board ( ) <EOL> for x in conjoin ( self . squaregenerators ) : <EOL> yield x <EOL> def printsolution ( self , x ) : <EOL> m , n = self . m , self . n <EOL> assert len ( x ) == m * n <EOL> w = len ( str ( m * n ) ) <EOL> format = "<STR_LIT:%>" + str ( w ) + "<STR_LIT:d>" <EOL> squares = [ [ None ] * n for i in range ( m ) ] <EOL> k = <NUM_LIT:1> <EOL> for i in x : <EOL> i1 , j1 = self . index2coords ( i ) <EOL> squares [ i1 ] [ j1 ] = format % k <EOL> k += <NUM_LIT:1> <EOL> sep = "<STR_LIT:+>" + ( "<STR_LIT:->" * w + "<STR_LIT:+>" ) * n <EOL> print sep <EOL> for i in range ( m ) : <EOL> row = squares [ i ] <EOL> print "<STR_LIT:|>" + "<STR_LIT:|>" . join ( row ) + "<STR_LIT:|>" <EOL> print sep <EOL> conjoin_tests = """<STR_LIT>""" <EOL> weakref_tests = """<STR_LIT>""" <EOL> coroutine_tests = """<STR_LIT>""" <EOL> refleaks_tests = """<STR_LIT>""" <EOL> __test__ = { "<STR_LIT>" : tutorial_tests , <EOL> "<STR_LIT>" : pep_tests , <EOL> "<STR_LIT:email>" : email_tests , <EOL> "<STR_LIT>" : fun_tests , <EOL> "<STR_LIT>" : syntax_tests , <EOL> "<STR_LIT>" : conjoin_tests , <EOL> "<STR_LIT>" : weakref_tests , <EOL> "<STR_LIT>" : coroutine_tests , <EOL> "<STR_LIT>" : refleaks_tests , <EOL> } <EOL> def test_main ( verbose = None ) : <EOL> from test import test_support , test_generators <EOL> test_support . run_doctest ( test_generators , verbose ) <EOL> def extra_collect ( ) : <EOL> import gc <EOL> from time import sleep <EOL> gc . collect ( ) ; sleep ( <NUM_LIT:1> ) ; gc . collect ( ) ; sleep ( <NUM_LIT:0.1> ) ; gc . collect ( ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> test_main ( <NUM_LIT:1> ) </s>
