add_binTrie.py

[MohamedHamed12]

Thank you for your last valuable feedback. I have made improvements to the code, 1-edit time complexity, in max_and and max_or 2-I have also focused on enhancing its overall cleanliness. 3-I have renamed variables to improve readability.

I appreciate your support and suggestions, and I hope the updated version meets your expectations. If you have any further feedback , please feel free to let me know.

[cheran-senthil]

I don't like this code

[MohamedHamed12]

I don't like this code

Thank you for your feedback. I appreciate you taking the time to review my code.

I understand that you don't like the code. Can you please clarify what you don't like about it? I'm happy to make changes if you have any specific suggestions.

[bjorn-martinsson]

Your code is a standard binary trie implementation in Python. But it is not the kind of implementation that we would like to add to Pyrival. Pyrival is a competitive programming library with relatively short/simple and fast running Python implementations. The good thing about your code is that it is easy to understand what it is doing, but your implementation is not short and it is probably pretty slow.

So what kind of implementation are we looking for? For solving max_xor I've personally been a big fan of implementations like this:

count = [0, 0]
left_child_index = [-1, -1]
max_len = 30

def add(x):
    node = 0
    for i in range(max_len)[::-1]:
        if left_child_index[node] == -1:
            left_child_index[node] = len(count)
            count.extend([0,0])
            left_child_index.extend([-1,-1])
        node = left_child_index[node] ^ (1 & (x >> i))
        count[node] += 1

def remove(x):
    node = 0
    for i in range(max_len)[::-1]:
        node = left_child_index[node] ^ (1 & (x >> i))
        count[node] -= 1

def max_xor(x):
    assert len(count) > 2
    node = 0
    for i in range(max_len)[::-1]:
        node = left_child_index[node] ^ (1 & (x >> i)) ^ 1
        node ^= count[node] == 0
        x ^= (node & 1) << i
    return x

This implementation is pretty short and probably runs really fast since it just uses a couple of lists and a for loop. The reason why I haven't added it to Pyrival is that it is kind of complicated and not that nice. Still, I think that something like this fits Pyrival a lot better than your implementation.

[MohamedHamed12]

Your code is a standard binary trie implementation in Python. But it is not the kind of implementation that we would like to add to Pyrival. Pyrival is a competitive programming library with relatively short/simple and fast running Python implementations. The good thing about your code is that it is easy to understand what it is doing, but your implementation is not short and it is probably pretty slow.

So what kind of implementation are we looking for? For solving max_xor I've personally been a big fan of implementations like this:

count = [0, 0]
left_child_index = [-1, -1]
max_len = 30

def add(x):
    node = 0
    for i in range(max_len)[::-1]:
        if left_child_index[node] == -1:
            left_child_index[node] = len(count)
            count.extend([0,0])
            left_child_index.extend([-1,-1])
        node = left_child_index[node] ^ (1 & (x >> i))
        count[node] += 1

def remove(x):
    node = 0
    for i in range(max_len)[::-1]:
        node = left_child_index[node] ^ (1 & (x >> i))
        count[node] -= 1

def max_xor(x):
    assert len(count) > 2
    node = 0
    for i in range(max_len)[::-1]:
        node = left_child_index[node] ^ (1 & (x >> i)) ^ 1
        node ^= count[node] == 0
        x ^= (node & 1) << i
    return x

This implementation is pretty short and probably runs really fast since it just uses a couple of lists and a for loop. The reason why I haven't added it to Pyrival is that it is kind of complicated and not that nice. Still, I think that something like this fits Pyrival a lot better than your implementation.

I am deeply grateful to you for your invaluable help and guidance. Your explanation and your code were incredibly valuable, and I learned a lot from your insights.

I'm looking forward to applying the lessons I've learned in future. Thank you once again