import random
from string import ascii_lowercase

#parameters
N = 256 #universe of N 
d = 3 #distinct items
stream_size = 10000

#generate some random strings of size 10
U = []
for _ in range(N):
  U.append(''.join(random.choice(ascii_lowercase) for i in range(12)))

D = random.sample(U,k=d)

print(D)

import math
import random
from datetime import datetime

random.seed(datetime.now().timestamp())

def h(x,n):
  return hash(x)%n

#method for counting trailing 0s
def trailing_0(x):
  x1 = x
  t0 = 0
  while x1%2==0 and x1!=0:
    t0 += 1
    x1 //= 2
  return t0

#simulating the stream
R = 0
for _ in range(stream_size):
  #take a random string from the distinct pool
  s = random.choice(D)
  #check its hash value
  hv = h(s,2*N) #to allow more space for hash values
  r = trailing_0(hv)
  if r>R:  #we get the max number of trailing consecutive ceros  
    R=r

est = int(math.pow(2,R))

print('Estimation of distinct items: %d'%est)