2
\$\begingroup\$

I am traversing two objects that may share a common ancestor. To make the code small enough to show here, I have changed it into two dictionaries with values. As you can see, a_d and b_d are the inverse of each other. The idea is to step into each dictionary step by step until we find an overlapping value for the two. At each step the 'distance' is increased.

For the example case get_distance('b', 'y'), the output will print (comments added):

# init
start= b
end= y

# both a and b changed value (dist +1 for both) but no overlap found
start= c
end= x

# both a and b changed value (dist +1 for both) and an overlap was found!
start= d
end= d

Found overlap d
connected True

I hope that it is clear what this code does and what I am trying to do. Please keep in mind that the actual code works with elaborate objects and their properties, but the idea is similar. The issue that I am having is that the code is very repetitive and probably not as efficient as it could be. But I am not sure how I can improve on it. Ideas welcome!

def get_distance(start, end):
    start_d = {
        'a': 'b',
        'b': 'c',
        'c': 'd',
        'd': 'x',
        'x': 'y',
        'y': 'z',
        'z': 'z'
    }

    end_d = {
        'z': 'y',
        'y': 'x',
        'x': 'd',
        'd': 'c',
        'c': 'b',
        'b': 'a',
        'a': 'a'
    }

    connected = False
    start_dist = 0
    end_dist = 0
    while True:
        print('start=', start)
        print('end=', end)
        print()

        # Check whether a and b are the same, if so break
        if start == end:
            print(f"Found overlap {end}")
            connected = True
            break
        # Check whether the next a value is the same as b, if so break and increase a_dist
        elif start_d[start] == end:
            print(f"Found overlap {end}")
            start_dist += 1
            connected = True
            break
        # Check whether the next b value is the same as a, if so break and increase b_dist
        elif end_d[end] == start:
            print(f"Found overlap {start}")
            end_dist += 1
            connected = True
            break

        # If for a and b all options are exhausted, break
        if start == start_d[start] and end == end_d[end]:
            break

        # If a is not exhausted, get its dict value and increase distance
        if start != start_d[start]:
            start_dist += 1
            start = start_d[start]

        # If b is not exhausted, get its dict value and increase distance
        if end != end_d[end]:
            end_dist += 1
            end = end_d[end]

    dist = start_dist + end_dist
    print('connected', connected)
    return dist


if __name__ == '__main__':
    dist = get_distance('b', 'y')

\$\endgroup\$
  • \$\begingroup\$ text a= and b= can be missleading when you have also nodes a and b. Maybe start=, end= could be more readable. \$\endgroup\$ – furas Jul 24 at 0:59
  • \$\begingroup\$ what if you have loops in data ? You will never exit from while. You should check how many steps you made - it can't be more then number of nodes. \$\endgroup\$ – furas Jul 24 at 1:01
  • \$\begingroup\$ Maybe traversing in two directions can be sometimes faster - if one direction checked data faster then other direction - but traversing in one direction would need shorter code. \$\endgroup\$ – furas Jul 24 at 1:07
  • \$\begingroup\$ Loops cannot occur (the actual, object-oriented data is on hierarchical data), so you don't have to think about that for now. \$\endgroup\$ – Bram Vanroy Jul 24 at 1:09
  • \$\begingroup\$ I think better names would help understanding. Especially, what's the d in start_d and end_d ? And you talk about a tree, but if start/end correspond to actual parent/child, then you probably need something different, for when a node has several children. If it's for a tree again, I wouldn't bother traversing in 2 directions, you can just start from one node (unless you have very particular complexity requirements and statistics). \$\endgroup\$ – Gnurfos Jul 24 at 5:48
2
\$\begingroup\$
  • Docstrings: You should include a docstring at the beginning of every method, class, and module you write. This will help documentation identify what your methods/classes/modules are supposed to accomplish.
  • Simplicity: Rather than dist = start_dist + end_dist then returning dist, you can simply return start_dist + end_dist. You can return the addition of the two values, rather than creating a variable to only use it once to return. This is a personal preference, but it helps reduce the number of variables in the program, which helps me; and may also help you.
  • Constants: Any constants in your program should be UPPERCASE. You only have one in your code, but you should keep in practice for when you write bigger programs.
  • Printing: You use print(..., ...) and print(f"...") interchangeably. You should stick to using only one for consistency sake. As my preference, I changed all of them to print(f"..."), but you change choose your preference.

Updated Code

"""
Traverses two objects that may share a common ancestor
"""

def get_distance(start, end):
    """
    Gets the distance from `start` to `end` in the trees
    """
    start_d = {
        'a': 'b',
        'b': 'c',
        'c': 'd',
        'd': 'x',
        'x': 'y',
        'y': 'z',
        'z': 'z'
    }

    end_d = {
        'z': 'y',
        'y': 'x',
        'x': 'd',
        'd': 'c',
        'c': 'b',
        'b': 'a',
        'a': 'a'
    }

    connected = False
    start_dist = 0
    end_dist = 0

    while True:
        print(f"Start: {start}")
        print(f"End: {end} \n")

        # Check whether a and b are the same, if so break
        if start == end:
            print(f"Found overlap: {end}")
            connected = True
            break

        # Check whether the next a value is the same as b, if so break and increase a_dist
        elif start_d[start] == end:
            print(f"Found overlap: {end}")
            start_dist += 1
            connected = True
            break

        # Check whether the next b value is the same as a, if so break and increase b_dist
        elif end_d[end] == start:
            print(f"Found overlap: {start}")
            end_dist += 1
            connected = True
            break

        # If for a and b all options are exhausted, break
        if start == start_d[start] and end == end_d[end]:
            break

        # If a is not exhausted, get its dict value and increase distance
        if start != start_d[start]:
            start_dist += 1
            start = start_d[start]

        # If b is not exhausted, get its dict value and increase distance
        if end != end_d[end]:
            end_dist += 1
            end = end_d[end]

    print(f"Connected: {connected}")
    return start_dist + end_dist

if __name__ == '__main__':
    DISTANCE = get_distance('b', 'y')
    print(f"Distance: {DISTANCE}")
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.