fork download
copy 
  1. from time import*
  2. from fractions import*
  3. from collections import*
  4. from itertools import*
  5.  
  6. def solve1a():
  7. 	dotprod = lambda A,B: sum(a*b for a,b in zip(A,B))
  8.  
  9. 	for n in xrange(1,7):
  10. 		numer=0
  11. 		for A in product([1,-1],repeat=n):
  12. 			for B in product([1,0,0,-1],repeat=n):
  13. 				if not dotprod(A,B):
  14. 					if not dotprod(A[1:]+A[:1],B):
  15. 						numer+=1
  16. 		denom=8**n
  17. 		print n,Fraction(numer,denom)
  18.  
  19. solve1a()
  20. print '----'
  21.  
  22. def solve1b():
  23. 	for n in xrange(1,8):
  24. 		def f(i,a,b,s,t):
  25. 			if i==n:
  26. 				return not s and not t+a*b
  27.  
  28. 			res=0
  29.  
  30. 			for A in 1,-1:
  31. 				for B in 1,0,0,-1:
  32. 					res+=f(i+1,a,B,s+A*B,t+A*b)
  33.  
  34. 			return res
  35.  
  36. 		numer=0
  37.  
  38. 		for a in 1,-1:
  39. 			for b in 1,0,0,-1:
  40. 				numer+=f(1,a,b,a*b,0)
  41.  
  42. 		denom=8**n
  43.  
  44. 		print n,Fraction(numer,denom)
  45.  
  46. solve1b()
  47. print '----'
  48.  
  49. def solve2a():
  50. 	dotprod = lambda A,B: sum(a*b for a,b in zip(A,B))
  51.  
  52. 	for n in xrange(2,7):
  53. 		numer=0
  54. 		for A in product([1,-1],repeat=n):
  55. 			for B in product([1,0,0,-1],repeat=n):
  56. 				if not dotprod(A,B):
  57. 					if not dotprod(A[1:]+A[:1],B):
  58. 						if not dotprod(A[2:]+A[:2],B):
  59. 							numer+=1
  60. 		denom=8**n
  61. 		print n,Fraction(numer,denom)
  62.  
  63. solve2a()
  64. print '----'
  65.  
  66. def solve2b():
  67. 	for n in xrange(2,8):
  68. 		def f(i,a1,a2,b1,b2,s,t,u):
  69. 			if i==n:
  70. 				return not s and not t+a1*b2 and not u+a1*b1+a2*b2
  71.  
  72. 			res=0
  73.  
  74. 			for A in 1,-1:
  75. 				for B in 1,0,0,-1:
  76. 					res+=f(i+1,a1,a2,b2,B,s+A*B,t+A*b2,u+A*b1)
  77.  
  78. 			return res
  79.  
  80. 		numer=0
  81.  
  82. 		for a1 in 1,-1:
  83. 			for b1 in 1,0,0,-1:
  84. 				for a2 in 1,-1:
  85. 					for b2 in 1,0,0,-1:
  86. 						numer+=f(2,a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)
  87.  
  88. 		denom=8**n
  89.  
  90. 		print n,Fraction(numer,denom)
  91.  
  92. solve2b()
  93. print '----'
  94.  
  95. def solve2c():
  96. 	X=defaultdict(lambda:0)
  97.  
  98. 	numer=0
  99.  
  100. 	for a1 in 1,-1:
  101. 		for b1 in 1,0,0,-1:
  102. 			for a2 in 1,-1:
  103. 				for b2 in 1,0,0,-1:
  104. 					if not a1*b1+a2*b2 and not a2*b1+a1*b2:
  105. 						numer+=1
  106. 					X[(a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)]+=1
  107.  
  108. 	denom=8**2
  109. 	print 2,Fraction(numer,denom)
  110.  
  111. 	for n in xrange(3,17):
  112. 		Y=defaultdict(lambda:0)
  113. 		numer=0
  114. 		for a1,a2,b1,b2,s,t,u in X:
  115. 			c=X[(a1,a2,b1,b2,s,t,u)]
  116. 			for A in 1,-1:
  117. 				for B in 1,0,0,-1:
  118. 					if not s+A*B and not t+A*b2+a1*B and not u+A*b1+a1*b2+a2*B:
  119. 						numer+=c
  120. 					Y[(a1,a2,b2,B,s+A*B,t+A*b2,u+A*b1)]+=c
  121. 		denom=8**n
  122. 		print n,Fraction(numer,denom)
  123. 		X=Y
  124.  
  125. solve2c()
  126. print '----'
  127.  
  128. def solve2d():
  129. 	N_MAX=28
  130.  
  131. 	T=time()
  132.  
  133. 	n=2
  134. 	Y=defaultdict(lambda:0)
  135. 	numer=0
  136.  
  137. 	for a1 in [1]:
  138. 		for b1 in (1,0):
  139. 			for a2 in (1,-1):
  140. 				for b2 in (1,0,0,-1):
  141. 					if not a1*b1+a2*b2 and not a2*b1+a1*b2:
  142. 						numer+=1
  143. 					Y[(a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)]+=1
  144.  
  145. 	thresh=N_MAX-1
  146.  
  147. 	while time() <= T+10:
  148. 		print('%d %s'%(n,Fraction(numer,8**n/4)))
  149.  
  150. 		n+=1
  151. 		X=Y
  152. 		Y=defaultdict(lambda:0)
  153. 		numer=0
  154.  
  155. 		if thresh<2:
  156. 			print('reached MAX_N with %.2f seconds remaining'%(T+10-time()))
  157. 			return
  158.  
  159. 		for a1,a2,b1,b2,s,t,u in X:
  160. 			if not ( abs(s)<thresh and abs(t)<thresh+1 and abs(u)<thresh+2 ):
  161. 				continue
  162.  
  163. 			c=X[(a1,a2,b1,b2,s,t,u)]
  164.  
  165. 			# 1,1
  166.  
  167. 			if not s+1 and not t+b2+a1 and not u+b1+a1*b2+a2: numer+=c
  168. 			Y[(a1,a2,b2,1,s+1,t+b2,u+b1)]+=c
  169.  
  170. 			# -1,1
  171.  
  172. 			if not s-1 and not t-b2+a1 and not u-b1+a1*b2+a2: numer+=c
  173. 			Y[(a1,a2,b2,1,s-1,t-b2,u-b1)]+=c
  174.  
  175. 			# 1,-1
  176.  
  177. 			if not s-1 and not t+b2-a1 and not u+b1+a1*b2-a2: numer+=c
  178. 			Y[(a1,a2,b2,-1,s-1,t+b2,u+b1)]+=c
  179.  
  180. 			# -1,-1
  181.  
  182. 			if not s+1 and not t-b2-a1 and not u-b1+a1*b2-a2: numer+=c
  183. 			Y[(a1,a2,b2,-1,s+1,t-b2,u-b1)]+=c
  184.  
  185. 			# 1,0
  186.  
  187. 			c+=c
  188.  
  189. 			if not s and not t+b2 and not u+b1+a1*b2: numer+=c
  190. 			Y[(a1,a2,b2,0,s,t+b2,u+b1)]+=c
  191.  
  192. 			# -1,0
  193.  
  194. 			if not s and not t-b2 and not u-b1+a1*b2: numer+=c
  195. 			Y[(a1,a2,b2,0,s,t-b2,u-b1)]+=c
  196.  
  197. 		thresh-=1
  198.  
  199. solve2d()
Time limit exceeded #stdin #stdout 5s 8616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qgjrTt
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!