sequential search (cannot import string functions)

[Leonerd]

Hey I'm new to Python and taking a class on it.

To get started here is my homework specs

Sequential Letter Search

1.You will design and implement a program that will:
i.Accept as input a string of letters that will be looked up in another string.
ii.For each of the letters in the input string you will search the other string, called phonebook (this string is provided) starting from the first position and moving down the phonebook string until either the letter has been found, or the letter was determined not found. At which point, you will print the letter, whether it was found or not found, and the number of compares necessary to complete the search.
iii.After you have completed all searches you will provide statistics for both the success and failure rates (ie: number success = xx, total compares yy, average z.z / number failures = aa, total compares = bb, average c.c)
b.Save the code for this script/program in a file named: ssearch.py
c.Note: you are to write the search code yourself, do not use built-in string functions.
d.phonebook = ‘bcdfghjklmnpqrstvwxyz’
e.you may assume that phonebook will be in ascending order and will not contain duplicates.
f.Example:
i.input ‘ab’
ii.expected output:
‘a’ not found with 1 compares
‘b’ found with 1 compares
number success = 1; total compares = 1; average = 1.0
number failures = 1; total compares =1; average = 1.0
g.Example:
i.input ‘dog’
ii.expected output:
‘d’ found with 3 compares
‘o’ not found with 12 compares
‘g’ found with 5 compares
number success = 2; total compares = 8; average = 4.0
number failures = 1; total compares =12; average = 12.0

Now I'm also rather new to programming in general, so I'm not quite sure how to get this looping concept to work correctly.

Here's what I have (unsuccessfully) came up with:

inp = (raw_input('Input: '))

    phonebook = 'bcdfghjklmnpqrstvwxyz'

    count = 0

    for char in phonebook:
        if char == inp[count]:
            print inp[count] + ' found'
            count= count + 1
        else:
            print inp[count] + ' not found'
            count=count + 1

I keep recieving fatal errors, but it "works" if I change inp[count] to inp[0] (albeit it will only return results for the first string.

I don't even know where to begin with the rest of the output. I'm not trying to ask for the solution, but I really need someone who knows more about programming about how to structure my code.

Once I know how the structure should be I should be able to figure it all out.

Thanks for the help :I

[Leonerd]

inp = (raw_input('Input: '))

    phonebook = 'bcdfghjklmnpqrstvwxyz'

    count = 0
    compares = 0
    inpl = len(inp)
    found = 0

    while inpl > 0:
        for char in phonebook:
            if char == inp[0]:
                found = inp[0] + " found with " + str(compares) + " compares."
                count= count + 1
            else:
                compares=compares + 1
        if found:
            print found
        else:
            print inp[0] + " not found with " + str(compares) + " compares."

        inpl = inpl - 1

It's coming along, but it's still not working right... as you can see it works fine (so far kinda)

I have to use inp[0]... when I try to do inp[inpl] it doesnt work ( i think that's how I'm supposed to do it??)

I still don't know how I'm going to do the last part >.<

Argh I'm so lost :(

I'm wondering if I have to scrap the whole code and start fresh...

edit:

inp = (raw_input('Input: '))

    phonebook = 'bcdfghjklmnpqrstvwxyz'

    count = 0
    compares = 0
    inpl = len(inp)
    found = 0
    ltrinp = 0

    while ltrinp< inpl+1:
        while inpl > 0:
            for char in phonebook:
                if char == inp[ltrinp]:
                    found = inp[ltrinp] + " found with " + str(compares) + " compares."
                    count= count + 1
                else:
                    compares=compares + 1
                
            if found:
                print found
            else:
                print inp[stupid] + " not found with " + str(compares) + " compares."

            inpl = inpl - 1
        ltrinp = ltrinp + 1

Output:

>>>
Input: dog
d found with 2 compares.
d found with 22 compares.
d found with 42 compares.
>>>

Anyone know where I went wrong? Anyone at all!!

[jrcagle]

Well, a couple of things come to mind. This is a commendable start.

First of all, how would you solve this problem on paper? Suppose I gave you a string "dog" and said "find all of the letters in 'dog' in 'abcdefghijklmnopqrstuvwxyz' and tell me how many compares it takes you to find each one."

Describe that algorithm, and then I think your code can simplify. The good news is that your solution code will be *shorter* than what you've done already.

Regards,
Jeff

[Leonerd]

Coming along pretty good I suppose.

inp = (raw_input('Input: '))

    phonebook = 'bcdfghjklmnpqrstvwxyz'
    
    count = 0
    totalgoodcompares = 0
    success = 0
    totalfails = 0
    totalbadcompares = 0
    
    while count < len(inp):
        found = 0
        compares = 1
        for char in phonebook:
            if (char <= inp[count]):
                if (char == inp[count]): 
                    found = inp[count]+' found with '+ str(compares) +' compares'
                    totalgoodcompares = totalgoodcompares + compares
                    success = success + 1
                else:
                    compares = compares+1
                
        if (found):
            print found
        else:
            print inp[count]+' not found with '+str(compares)+' compares'
            totalfails = totalfails + 1
            totalbadcompares = totalbadcompares + compares
        count = count + 1
        
    failavg = totalbadcompares / totalfails * 1.0
    sucavg = totalgoodcompares / success * 1.0 
    print "number success = " + str(success) + "; total compares = " + str(totalgoodcompares) + "; average = " + str(sucavg)
    print "number fails = " + str(totalfails) + "; total compares = " + str(totalbadcompares) + "; average = " + str(failavg)

output:

>>>
Input: dog
d found with 3 compares
o not found with 12 compares
g found with 5 compares
number success = 2; total compares = 8; average = 4.0
number fails = 1; total compares = 12; average = 12.0
>>>

So it looks like (even though my code is messy), I have the right solution, aye?

[Leonerd]

Okay, now I have to do this:

Binary Search

1.Alter #3 above. Your first compare is the letter in phonebook at the halfway point. The second compare will be halfway above or below the first compare point.

>.<

Any clues?

[mark.woodson]

Coming along pretty good I suppose.

...
output:

>>>
Input: dog
d found with 3 compares
o not found with 12 compares
g found with 5 compares
number success = 2; total compares = 8; average = 4.0
number fails = 1; total compares = 12; average = 12.0
>>>

So it looks like (even though my code is messy), I have the right solution, aye?

Well, the number of compares for the fail is wrong. There are 21 characters to run through. Perhaps I read the assignment wrong though.

It looks like you are fighting the language a bit too. Iterating through lists, dictionaries, strings even can all be done the same way without the complex bounds checking kind of stuff. The suggestion to write it out on paper as something akin to a flow chart is a good one. It can be much simpler, much, much simpler.

-Mark

[woooee]

Take your first post and apply the same logic to both strings, phonebook and inp (for individual character in string). I think you can do the averages, etc.

inp = (raw_input('Input: '))
 
phonebook = 'bcdfghjklmnpqrstvwxyz'
 
for ip_char in inp:
     found = 0     ## reset these variables for each letter in inp
     count = 0
     for ph_char in phonebook:
          if ph_char <= ip_char:
               count += 1
               if ph_char == ip_char:
                    print "found", ph_char, ip_char, "in", count, "tries"
                    found = 1
     if not found:     ## Here we have processed the entire phonebook string
          print ip_char, "not found in", count, "tries"

[Leonerd]

Well, the number of compares for the fail is wrong. There are 21 characters to run through. Perhaps I read the assignment wrong though.

It looks like you are fighting the language a bit too. Iterating through lists, dictionaries, strings even can all be done the same way without the complex bounds checking kind of stuff. The suggestion to write it out on paper as something akin to a flow chart is a good one. It can be much simpler, much, much simpler.

-Mark

Yes, but the assignment is to "assume" that the phonebook string is in alphabetical order, and to stop once you get past that letter in the string (as in the expected output).

I did flow it out, which is why I only have one while loop now instead of 3 in my original design. I understand it is a little messy, but I honestly don't know how to simplify it anymore without breaking something.

[mark.woodson]

Yes, but the assignment is to "assume" that the phonebook string is in alphabetical order, and to stop once you get past that letter in the string (as in the expected output).

I did flow it out, which is why I only have one while loop now instead of 3 in my original design. I understand it is a little messy, but I honestly don't know how to simplify it anymore without breaking something.

Well, you can always break out of loops and let python handle the iterations itself.

for x in inp:
    for y in phonebook:
        if something:
            break

You do need to keep the stats, and keep track of where you are in the phonebook. But that is just a count += 1 . I see someone else has posted actual code that more follows this track.

[woooee]

1.Alter #3 above. Your first compare is the letter in phonebook at the halfway point. The second compare will be halfway above or below the first compare point.

You have to convert phonebook to a list, then you can compare the_list[len_list/2] to the letter. Depending on the result, you either split the first half in two and compare, or the last half, and then continue until you get an equal condition. Break it down into simple parts. It's not as difficult as it sounds.

[woooee]

Pardon me for over-posting. This is likely the final post. The problem gets easier if you use functions IMHO because you don't have loops within loops, and you break it into logical thought parts
1. get the input string
2. break the string into letters
3. test each letter against the phonebook

def letter_test(letter):
     phonebook = 'bcdfghjklmnpqrstvwxyz'
     count = 0
     for ph_char in phonebook:
          count += 1
          if ph_char > letter:     ## phonebook letter is greater
               return False, count
          elif ph_char == letter:
               return True, count
     ##--- for oddball stuff like "{" > "z"
     return False, count

if __name__ == "__main__":
   inp=raw_input("Enter string ")
   print inp, "entered"
   for ip_char in inp:
      found, count = letter_test(ip_char)
      print ip_char, 
      if found:
           print "found in", count, "tries"
      else:
            print "NOT found in", count, "tries"

That same "break it into functions=logical parts" is true for the "test the middle letter of phonebook" problem. So you should post your parts and any problems you have implementing an individual part.