help with dictionaries in python

[audiopython]

hi i'm trying to elarn programming, but as of today i've been stuck at 2 challenges, i am to write the who's your daddy program if you are familiar with it, i need a dictionary to hold father/son name pairs, and i need the user to be able to search the dictionary by kids names,  and later on add the functionality of having grandfather/father pairs stored in a dictionary, and have it print the grandfather/father associated with the father/kid pair being printed.

my idea for how to make this program is i'd create a dictionary (fathers as keys, sons as values) then have the user search the dictionary by values, if a corresponding key is found it will print both key and value, and then have it print the corresponding grandfather/father key/value the problem seems to be i can't get a straight answer anywhere on how the *censored* i search a dictionary by value.
i've been stuck on this problem close to 10 hours by now and i can't let it go, so help would really be appreciated

[Salmon Trout]

Maybe this will help

http://stackoverflow.com/questions/8023306/get-key-by-value-in-dictionary

[DaveLembke]

My thoughts on this is that every object given a unique identity and then concatenate a string with lineage association. Such as:

object 1 = 001
object 2 = 002
object 3 = 003

If object 2 ( 002 ) makes another object its object 4 ( 004 ), but object 4 was created from object 2 and so the lineage string in a database for example would be ( 004 002 ) If object 2 makes another object 5 ( 005 ), the database would have a lineage string of ( 005 002 ) if object 5 makes an object 6 then it would be a lineage string associated with object 6 of ( 006 005 002 ).

Not sure if this is a lineage problem that you have, where you want to maintain which objects are created from each other or some other problem. You have father/son and grandfather and the father as a key and son as a value, what does that make the grandfather then... so I am thinking instead of apples to oranges of father as a key and son as a value that concatenating a lineage string might work out best to append to the string its origin to maintain a lineage.

Thing is that you dont have anything here referring to a database and maybe you are going to be doing this possibly within python itself. This will require maintaining a flat database writing to files and populating arrays and string variables to populate the info, and the file that is written to to store the lineage information is going to grow quickly as each object spawns off a new object and the lineage appended to the lineage string data for the new object, so do you really need to have lineage back to the beginning, or maybe just 6 deep etc.

Here is an example of how it will grow in size where each object entry will consume more storage memory than the other

object 12  has a lineage string of ( 012 011 010 009 008 007 006 005 004 003 002 001 ) assuming the initial object only had 1 offspring object and then each generation maintained the same spawning of a single object. All 12 objects still exist but object 12 has lineage going back to object 1 and so the string of 12 back to 1.

object 12 spawns off a son and so that son is object 13 so it then has a string of ( 013 012 011 010 009 008 007 006 005 004 003 002 001 )

Where info in bold is the father and grandfather and great , great great, great great great and so on down the line back to the lowest object value of its lineage.

*This numbering only for example purposes the 000 to 999 range of each object works for 1000 objects and so if you want greater than 1000 objects you could potentially have a lineage of ( 197387 167987 133290 121000 ....... a long string of lineage going back to the beginning of object 1 )

[BC_Programmer]

The answer is: You don't.

Well, not really. You CAN search a dictionary for a key given a value- but it's going to be a sequential search- you'd have to look through every item and find the one with the correct value. You would also have to decide what to do when more than one key has the same value. Fact is, this is slow and very poor design, because you are basically misusing the Dictionary.

As a solution, We can discount adding the reverse association to the dictionary- eg, the son key returns the father key as well, because this would mean that a son could not be a father which would obviously be no good for your required scalability to include grandfathers.

The solution, IMO, would be to maintain two Dictionaries. One that indexes the sons by their father, and one that indexes fathers by their sons (the one you already have). when you add one in you add the appropriate values to each dictionary; when you define that Bob is the Son of George, for example, you add Bob with the Key George to your existing dictionary, but you also add George with the key Bob to the second dictionary; then you use the correct dictionary based on how you are searching.

Of course, this means that any father can only ever have one son, which is implied somewhat anyway since your original dictionary couldn't have more than one son indexed by the father anyway.

Realistically if the desire is to create a more full "Family Tree" than you would want to explore the creation of an Actual Tree Data structure.

[Salmon Trout]

The answer is: You don't.

You beat me to it. This isn't how a dictionary is meant to be used. A dictionary is like a mapping in mathematics. A dict is a mapping of the set of keys to the values, but not the other way around.

[Squashman]

Amazing!  Not one mention of learning how to properly write a sentence, paragraph, capitalize or use punctuation.  Everybody must be in their happy place after a restful weekend.

[audiopython]

oh wow... this was waaaay more feedback then i was expecting in such short time

Maybe this will help

http://stackoverflow.com/questions/8023306/get-key-by-value-in-dictionary

i think i looked at that link earlier when searching around myself, but i didn't really understnad all of what was going on, there where functions i've never dealt with yet wich made it a bit too much for me to really grasp what they where doing.

DaveLembke, the challenge is to do it with a dictionary, but otherwise it sounds really smart and like something that's waaaaaaaay over the scale of my small python beginner challenge xD there is no file it's writing to it will just be a single file containing the program itself, i'm hardcoding the dictionary with some predefined values, and the user will be able to add/remove stuff but i won't be saving the changes or addittions anywhere, it's simply a code challenge to help me learn python

The answer is: You don't.

Well, not really. You CAN search a dictionary for a key given a value- but it's going to be a sequential search- you'd have to look through every item and find the one with the correct value. You would also have to decide what to do when more than one key has the same value. Fact is, this is slow and very poor design, because you are basically misusing the Dictionary.

As a solution, We can discount adding the reverse association to the dictionary- eg, the son key returns the father key as well, because this would mean that a son could not be a father which would obviously be no good for your required scalability to include grandfathers.

The solution, IMO, would be to maintain two Dictionaries. One that indexes the sons by their father, and one that indexes fathers by their sons (the one you already have). when you add one in you add the appropriate values to each dictionary; when you define that Bob is the Son of George, for example, you add Bob with the Key George to your existing dictionary, but you also add George with the key Bob to the second dictionary; then you use the correct dictionary based on how you are searching.

Of course, this means that any father can only ever have one son, which is implied somewhat anyway since your original dictionary couldn't have more than one son indexed by the father anyway.

Realistically if the desire is to create a more full "Family Tree" than you would want to explore the creation of an Actual Tree Data structure.

seems to be following the theme of tonight

while these answers have been rolling in i got some help from a friend on facebook, who's been going over this with me, and yes i understand that what i'm asking for help to do is breaking dictionaries and any real world applications xD

my friend also suggested doing 2 dictionaries, challenge with the grandfather part, says i have to do it inside one dictionary,

to give you a better idea i'll write out the entire challenge as it stands in the book i'm following

Write a Who's Your Daddy? program that lets the user enter the name of a male and produces the name of his father.
Allow the user to add, replace, and delete son-father pairs.

Improve the Who's Your Daddy? program by adding a choice that lets the user enter a name and get back a grandfather. Your program should still only use one dictionary of son-father pairs.
Make sure to include several generations in your dictionary so that a match can be found.

after talking to my friend i've been thinking about doing it as a dictionary where the son's name is gonna be the key, and the value will be a list containing his father and grandfather, it seems to be the way to go about making this work within the "rules" of the challenges

[BC_Programmer]

I see. the issue is that your original assessment was backwards. There is no reason to have sons indexed by fathers, because according to the question, you do not need to retrieve the sons given a father, but the opposite way. So you can do this with only one dictionary, one which indexes fathers based on sons.

Given a Dictionary named "Paternity" with sons as the key, and fathers as the value, and a name "n":

Code: [Select]

Father = Paternity[n]

would retrieve the father for the son named in variable n.

Now, At this point, you should be able to figure out how to get a grandfather as well; after all, a Grandfather is just a father's father, you have the father, and you have a way to get fathers based on sons, right? You just put those together.

[audiopython]

I see. the issue is that your original assessment was backwards. There is no reason to have sons indexed by fathers, because according to the question, you do not need to retrieve the sons given a father, but the opposite way. So you can do this with only one dictionary, one which indexes fathers based on sons.

Given a Dictionary named "Paternity" with sons as the key, and fathers as the value, and a name "n":

Code: [Select]

Father = Paternity[n]


would retrieve the father for the son named in variable n.

Now, At this point, you should be able to figure out how to get a grandfather as well; after all, a Grandfather is just a father's father, you have the father, and you have a way to get fathers based on sons, right? You just put those together.

ah i see, i understood it like i would need to do it the other way around yes

hmm yeah i think so, i'm assuming add new pairs of fathers/sons (grandfathers/fathers) and add a condition to make it print both the father/son and the grandfather/father pairs at the same time

by the way thank you very much for all the input, i totally forgot to write it yesturday but it's really appreciated