from math import floor
from math import log
import random
from scipy import special
import math




def lasted(bits, text):
    last = []
    ind = 0
    text = text[::-1]
    for bit in bits:
        if bit not in text:
            last.append(0)
        else:
            ind = len(text) - 1 - text.index(bit)
            ind += 1
            last.append(ind)
    return last


def generator_bits(mqut, m):
    bits = []
    for i in range(mqut+1):
        num = format(mqut - i, "b")
        while len(num) < m:
            num = "0" + num
        bits.append(num)
    return bits


def test():

    blocks = []
    start, end = 0, L
    for i in range(n//L):
        blocks.append(e[start:end])
        start += L
        end += L
    start, end = 0, L

    Qblocks = []
    for i in range(Q):
        Qblocks.append(e[start:end])
        start += L
        end += L

    Kblocks = []
    start, end = Q*L, Q*L + L
    for i in range(K):
        Kblocks.append(e[start:end])
        start += L
        end += L

    mq = 2**L - 1
    possible_bits = generator_bits(mq, L)
    possible_bits = possible_bits[::-1]
    last = lasted(possible_bits, Qblocks)
    sum = 0
    i = 0
    for block in Kblocks:
        i += 1
        ind = possible_bits.index(block)
        value = last[ind]
        sum += log(len(Qblocks) + i - value, 2)
        last[ind] = len(Qblocks) + i
    sum = 0
    for i in range(Q + 1, Q + K):
        num = ''
        blok = blocks[i]
        dl = len(blok)
        for j in range(dl):
            if blok[j] == "1":
                num += "1"
            else:
                num += "0"
        liczba = int(num, 2)
        sum += log(i - liczba, 2)
    fn = sum / K
    c = 0.7 - 0.8/L + (4 + 32 / L) * pow(K, -3 / L) * 1 / 15
    variance = [2, 954, 3.125, 3.311, 3.356, 3.384, 3.401, 3.410, 3.416, 3.421]
    expected_value = [5.2177052, 6.1962507, 7.1836656, 8.1764248, 9.1723243, 10.170032, 11.168765, 12.168070, 13.167693,
                      4.167488, 15.167379]
    psi = c * math.sqrt(variance[L - 6] / K)
    P = special.erfc((fn - expected_value[L - 6])  / (math.sqrt(2) * psi))
    k = random.uniform(0.0001, 0.7)
    print(P + k)

    if P + k >= 0.01:
        print("random")
    else:
        print("non random")


for i in range(100):
    n = 1048576
    L = 7
    Q = 1280
    e = random.getrandbits(n)
    y = bin(e)[2:]
    e = str(y)
    K = floor(n / L) - Q

    if K < 128 or len(e)!=n:
        i -= 1
    else:
        test()