How to solve this complex recursive problem, pyramid point system

Question

Hi,

I'm trying to program a pyramid like score system for an ARG game and have come up with a problem. When users get into the game they start a new "pyramid" but if one start the game with a referer code from another player they become a child of this user and then kick points up the ladder.

The issue here is not the point calculation, I've gotten that right with some good help from you guys, but if a user gets more point that it parent, they should switch places in the ladder. So that a users parent becomes it's child and so on.

The python code I have now doesnt work proper, and I dont really know why.

def verify_parents(user):
    """
    This is a recursive function that checks to see if any of the parents
    should bump up because they got more points than its parent.

    """
    from rottenetter.accounts.models import get_score

    try:
        parent = user.parent
    except:
        return False
    else:
        # If this players score is greater than its parent
        if get_score(user) > get_score(parent):
            # change parent
            user.parent = parent.parent
            user.save()

            # change parent's parent to current profile
            parent.parent = user
            parent.save()
        verify_parents(parent)

In my mind this should work, if a user has a parent, check to see if the user got more points than its parent, if so, set the users parent to be the parents parent, and set the parents parent to be the user, and then they have switched places. And after that, call the same function with the parent as a target so that it can check it self, and then continue up the ladder.

But this doesnt always work, in some cases people aren't bumbed to the right position of some reason.

Edit:

When one users steps up or down a step in the ladder, it's childs move with him so they still relate to the same parent, unless they to get more points and step up. So it should be unecessary to anything with the parents shouldn't it?

Answer 1

I think your problem could be that you aren't setting the child(s) of profile to now have parent as it's/their parent, unless children with parents can't also be parents in your system (which I do not believe to be the case).

Alternatively (or possibly together with the previous), you may want to just do parent = profile.parent rather than parent = profile.parent.get_profile().

EDIT: And I see that you did indeed switch to something of that second form, though using user instead of profile.

Anyway, since each user can have multiple children (as you stated in a comment on another answer), you might want to keep track of each user's child from within that user's object. Something like...

parent = user.parent
user.parent = parent.parent
parent.parent = user

children = user.children

for child in children:
    child.parent = parent

user.children = parent.children

for child in user.children:
    if child is user:
        child = parent

    child.parent = user

parent.children = children

for child in user.parent.children:
    if child is parent:
        child = user

This probably needs refactoring, though, and I may have missed something.

Answer 2

[correction according to your comment]

If the result of the "move" never intends to change the topology of the tree(i.e. when X becomes the parent of its old parent Y, it gives all its children to Y), then the simplest might be to decouple the notion "pyramid nodes" from the "users", with one-to-one relationship. Then if the 'swap' operation does not change the topology of the tree, you would only need to swap the mapping between 'nodeA <=> userA' and 'nodeB <=> userB' so they become 'nodeA <=> userB' and 'nodeB <=> userA'.

Since the topology of the tree does not change, this would automagically take care of the children having a correct parent. The downside, of course, is that you no longer can directly find out the 'parent' from a user record and would need to go via the nodes.

No code as I am not sure of your application details - but hopefully if this is applicable it should be easy enough to turn into code.