Last active
July 14, 2017 07:17
-
-
Save unclecode/270f8d0a6eb52f6b78ae4ff3a56b6adc to your computer and use it in GitHub Desktop.
Algorithm to generate stupid soldier patterns
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import math | |
| def findAnomalyPosition(n): | |
| bit_length = int(math.ceil(math.log(n, 2))) | |
| #1010 & 0011 = 0010 It means and of any number to 33 << i is returning two consequitive bits at position i and i + 1 | |
| #XOR of n eith 2**i is toggling the bit at position i | |
| #so XOR n with 3 >> i is toggling bits at positions i and i + 1 and in our case | |
| #if bits in position i and i + 1 is 2 or 10 we want to make 01 which is this toggling with number 3 | |
| return [i for i in range(but_length) if ((x >> i) & 3) == 2 if ((x >> i) & 3) == 2] | |
| def generateNext(x): | |
| n = x | |
| for i in findAnomalyPosition(x): | |
| n = n ^ (3 << i) | |
| return n | |
| y = x = int('11100101001100110', 2) | |
| #y = x = int('1000101101011', 2) | |
| #y = x = int('110011010010', 2) | |
| #y = x = int('10101', 2) | |
| #y = x = int('101101011', 2) | |
| #y = x = int('100010101101011', 2) | |
| #y = x = int('10001', 2) | |
| #print first_length | |
| def genCount(x, debug = True): | |
| f = lambda x : reduce(lambda acc, i: acc ^ ( 3 << i ), [i for i in range(int(math.ceil(math.log(x, 2)))) if ((x >> i) & 3) == 2], x ) | |
| s = 0 | |
| first_length = int(math.floor(math.log(x, 2))) + 1 | |
| if debug: | |
| print bin(x)[2:].zfill(first_length), x | |
| while x != 2 ** (int(math.floor(math.log(x, 2)) + 1)) - 1: | |
| s+=1 | |
| x= f(x) | |
| if debug: | |
| print bin(x)[2:].zfill(first_length), x | |
| return s | |
| # y = x | |
| # while (x != (2 ** int(math.ceil(math.log(x, 2)))) - 1): | |
| # s+=1 | |
| # y = x | |
| # bitLength = int(math.ceil(math.log(x, 2))) | |
| # for i in range(bitLength): | |
| # if (y >> i) & 3 == 2: | |
| # x = x ^ (3 << i) | |
| # print bin(x)[2:].zfill(first_length), x | |
| # print s | |
| def countOnly(y, debug = True): | |
| oneCount = 0 | |
| action = 0 | |
| first_length = int(math.floor(math.log(y, 2))) + 1 | |
| if debug: | |
| print first_length | |
| for i in range(first_length)[::-1]: | |
| t = y & (1 << i) | |
| if t: oneCount+=1 | |
| else: | |
| action += oneCount - action if oneCount - action > 0 else 1 | |
| if debug: | |
| print y, i, 1 << i, t, oneCount, action | |
| return action | |
| res = [] | |
| for x in range(1, 100000): | |
| if genCount(x, False) != countOnly(x, False): | |
| res.append(x) | |
| print res | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment