fork download 
  1. def heuristic(n):
  2.     if n&3:
  3.         return 1,'0'*n
  4.  
  5.     if n==4:
  6.         return 4,'0001'
  7.  
  8.     for ones in xrange(1,n/2-1):
  9.         def recurse(i,x,onesleft):
  10.             if not onesleft:
  11.                 b=(x<<(n/2)) | (((1<<(n/2))-1)^x)
  12.                 for flip in xrange(n/2):
  13.                     x=y=b^(1<<flip)
  14.                     m=1
  15.                     while 1:
  16.                         y=((y&1)<<(n-1))|(y>>1)
  17.                         if bin(x^y).count('1')!=n/2:
  18.                             break
  19.                         m+=1
  20.                     if m==n/2:
  21.                         return m,bin((1<<n)|x)[3:]
  22.                 return
  23.  
  24.             for j in xrange(i,n/2-onesleft):
  25.                 r=recurse(j+1,x|(1<<j),onesleft-1)
  26.                 if r: return r
  27.  
  28.         r=recurse(0,0,ones)
  29.         if r: return r
  30.  
  31.     print 'failed'
  32.     1/0
  33.  
  34. def brute(n):
  35.     r=1
  36.     for x in xrange(3<<(n-2),1<<n):
  37.         c=1
  38.         y=x
  39.         while 1:
  40.             y=((y&1)<<(n-1))|(y>>1)
  41.             if bin(x^y).count('1')!=n/2:
  42.                 break
  43.             c+=1
  44.         if c>r:
  45.             r=c
  46.             X=x
  47.     return r,bin(X)[2:]
  48.  
  49. for n in xrange(4,32,4):
  50.     print n,heuristic(n)
Success #stdin #stdout 0.02s 8968KB
comments (?)
stdin 
Standard input is empty
stdout 
4 (4, '0001')
8 (4, '00011010')
12 (6, '000010111001')
16 (8, '0000010011101011')
20 (10, '00001000101111001101')
24 (12, '000001001000111010110111')
28 (14, '0001010000010011101001111011')
https://ideone.com/U1VqrC
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!