Python Forum
Park-Miller Algorithm - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: Park-Miller Algorithm (/thread-2114.html)

Pages: 1 2

Park-Miller Algorithm - hughng92 - Feb-20-2017

Hello,

I am trying to pick up some projects online to practice coding and so far I have faced a challenge.



If we take a look at the US keypad on a standard keyboard, it has ten keys for the digits 0 through 9. Each key 2 through 9 has three letters of the alphabet, but the letters Q and Z are missing. The keys 0 and 1 have no letters. I am trying to construct a mnemonic word for a telephone number. It might choose letters purely at random. Suppose that the program must construct a word for 686–2377. The possible letters for 6 are MNO, so it might choose M first. The possible letters for 8 are TUV, so it might choose V next, etc. Continuing in this way, it might construct MVNBDPR. 



However, I want to create a word that is "pronounce-able", meaning it looks like an english word even though it has no meaning in any dictionary on earth. For example, suppose that the program must still construct a word for 686–2377. The possible letters for 6 are MNO, so it might choose M. The possible letters for 8 are TUV, but since U is more likely to follow M than T or V, it might choose U. Continuing in this way, choosing each letter based on how likely it is to follow the previous letter, the program might construct MUNCERS. This isn’t an English word, but it looks like one, so it’s easier to remember than the number. 



Here are my thoughts.

1. I created two classes: one is called Random which is used to generate a random number based on Park-Miller Algorithm and then use that number to generate a random character out of a string. My second class is called Mnenomic. Its methods will generate mnemonic words for telephone numbers.

2. In the Mnemonic, I will have a method called make:
make(self, number)
Here number is a telephone number, made up of digit characters. The method make tries to construct a mnemonic word from number. Let’s say the word it constructs is in the local variable mnemonic. 
      It starts by getting the first digit from number. Then it gets a string of letters for that digit, using letters. It picks one of the letters from the string using choose. This letter is the first letter of mnemonic. 
      After that, make gets the remaining digits from number, one at a time. Each time it gets a digit, it gets the last letter from mnemonic. It also gets a string of letters from follow that can follow the last letter. It temporarily removes from that string all letters which do not appear on the same key for digit, using letters. If the resulting string is empty, then make can’t continue, so it gives up and returns'', the empty string. However, if it is not empty, then make picks one of its letters using choose and concatenates that letter to the end of mnemonic. 
      The method make continues in this way until it has seen all the digits from number; then it returns the string in mnemonic.
Here is my code for the make function:

def make(self,number):
   self.num = number
   self.s1=''
   self.s2=''
   self.s3=''
   i = 0
   self.s1+=self.random.choose(self.letters[int(self.num[0])])

   while i < len(self.num):
       # self.s1 +=self.random.choose(self.letters[int(self.num)])
       self.s2 += self.follow[self.s1[-1]]
       i=+1
       j = 0
       while j < len(self.s2):
           found_char = True
           if self.s2[j]==self.s1:
               self.s3+=self.s2[j]
               found_char = True
           elif found_char == False:
               return ''
           j+=1
   self.s1 += self.random.choose(self.letters[self.s3])
   return self.s1
When I ran my code, I got an error message:
Error:
Traceback (most recent call last):

  File "/Users/Hieung92/Google Drive/Notability/CSCI 1913 Lab/nguy2952_Project1.py", line 313, in <module>

    print('"' + m.make('6862377') + '"')  #  "ounadrr"

  File "/Users/Hieung92/Google Drive/Notability/CSCI 1913 Lab/nguy2952_Project1.py", line 37, in make

    if self.s2[j]==self.s1[i]:
IndexError: string index out of range
Any tip will be greatly appreciated. Thank you.

RE: Park-Miller Algorithm - micseydel - Feb-20-2017

(Feb-20-2017, 05:45 AM)hughng92 Wrote: I am trying to pick up some projects online to practice coding
Really? It looks more like you're taking a course.

You provided some code and the error, which is good, but you should provide fully runnable code along with its input hard-coded so it's easy for us to reproduce the problem. If there's more than 5-10 lines of code, you can almost always remove code unrelated to the problem, and get it down to just a few lines that reproduce the issue. At that point, we'll be able to comment easier and there's the benefit that you might even figure it out yourself. (Learning to simplify my forum questions, years ago, was what I got most from this community.)

RE: Park-Miller Algorithm - hughng92 - Feb-20-2017

Thanks. I did not mean to put my whole code up here and asked people to look at my code and fix the errors for me. Here is my complete code.
class Random:
   def __init__(self,seed):
       self.n = seed
   def next(self,range):
       self.n = ((pow(7,5)*self.n)%(pow(2,31)-1))
       self.m = (self.n)%(int(range))
       return self.m
   def choose(self,letters):
       self.s = letters
       charak = self.s[self.next(len(self.s))]
       return charak
class Mnemonic:
   def __init__(self,seed):
       self.random = Random(seed)
       self.follow = {'a':'','b':'','c':'','d':'','e':'','f':'','g':'','h':'','i':'','j':'','k':'','l':'','m':'','n':'','o':'','p':'','q':'','r':'','s':'','t':'','u':'','v':'','w':'','x':'','y':''}
       self.letters = {0:'z',1:'q',2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'prs',8:'tuv',9:'wxy'}
   def add(self,word):
       self.w = word
       for i in range(0,len(self.w)-2):
           self.follow[self.w]+=self.w[i+1]

   def make(self,number):
       self.num = number
       self.s1=''
       self.s2=''
       self.s3=''
       i = 0
       self.s1+=self.random.choose(self.letters[int(self.num[0])])

       while i < len(self.num):
           # self.s1 +=self.random.choose(self.letters[int(self.num)])
           self.s2 += self.follow[self.s1[-1]]
           i=+1
           j = 0
           while j < len(self.s2):
               found_char = True
               if self.s2[j]==self.s1:
                   self.s3+=self.s2[j]
                   found_char = True
               elif found_char == False:
                   return ''
               j+=1
       self.s1 += self.random.choose(self.letters[self.s3])
       return self.s1
I am sorry but did I make a mistake by putting my whole code up here? I am sorry I did not mean to break the rules.

RE: Park-Miller Algorithm - micseydel - Feb-20-2017

Read my reply again. The code you've provided won't produce an error, and while full code is better than incomplete code, it is in your best interest (though not a requirement of the rules) to simplify your code if possible so that as little code as possible is reproducing the thing you're blocked on.

RE: Park-Miller Algorithm - hughng92 - Feb-20-2017

OK I am sorry about that. The problem I am having right now is string index out of range. I can explain how I came up with my function "make". I will take an example for a number "651 555 4"
1. First, I call a function which I made in one of my other class, Random, called "choose", which randomly choose a character out of a string. So according to the US key pad, number 6 has three letters: mno. Thus, this function random.choose will randomly choose a letter, say, O.
2. Next I will call the dictionary "follow", which was also made in my other class to create possible letters that can follow O. I will add these letters to my "s2" string.
3. Then I call the choose function again for the next number, which is 5, to get a string of letters "jkl" and then I compare every of these letters I got from above to the string "jkl". If the string of letters that is returned by the follow method does not contain any of "j", "k", or "l", then I return an empty string. If not, I concatenate every found j k l  to the new string I called "s3" and then call the "choose" method again to pick a letter that can possible follow "0" and also one of the three letters j k l obtained from number 5.
class Mnemonic:
   def __init__(self,seed):
       self.random = Random(seed)
       self.follow = {'a':'','b':'','c':'','d':'','e':'','f':'','g':'','h':'','i':'','j':'','k':'','l':'','m':'','n':'','o':'','p':'','q':'','r':'','s':'','t':'','u':'','v':'','w':'','x':'','y':''}
       self.letters = {0:'z',1:'q',2:'abc',3:'def',4:'ghi',5:'jkl',6:'mno',7:'prs',8:'tuv',9:'wxy'}
   def add(self,word):
       self.w = word
       for i in range(0,len(self.w)-2):
           self.follow[self.w]+=self.w[i+1]

   def make(self,number):
       self.num = number
       self.s1=''
       self.s2=''
       self.s3=''
       i = 0
       self.s1+=self.random.choose(self.letters[int(self.num[0])])

       while i < len(self.num):
           # self.s1 +=self.random.choose(self.letters[int(self.num)])
           self.s2 += self.follow[self.s1]
           i=+1
           j = 0
           while j < len(self.s2):
               found_char = True
               if self.s2[j]==self.s1:
                   self.s3+=self.s2[j]
                   found_char = True
               elif found_char == False:
                   return ''
               j+=1
       self.s1 += self.random.choose(self.letters[self.s3])
       return self.s1
Thank you. I don't know how to move forward since I got a string index out of range error.

RE: Park-Miller Algorithm - buran - Feb-20-2017

Most of the people here can read code and there is no need to explain what your code does.  What micseydel request is runnable code that reproduce the error. What you provide is the Mnemonic class definition, but not how you use it. Also, please use correct Python code tags, not icode tags.
All that said, the problem in your code is that you increase i by 1 before the while loop.
So in the first iteration of the loop i=1 and in the same time self.s1 is of length 1, so there is no index 1 and  that's why if self.s2[j]==self.s1[i]:rise an exception.

RE: Park-Miller Algorithm - hughng92 - Feb-20-2017

Thank you. How do I use the python code tag?

RE: Park-Miller Algorithm - nilamo - Feb-20-2017

Either click the python logo in the editor to create a code block, or type [python] your code here [/python ]

RE: Park-Miller Algorithm - hughng92 - Feb-20-2017

Thank you. My class "Mnemonic" is used to generate a name out of a given phone number. For example, if the input of phone number is 6862377, then some possible outputs are: 
print('"' + m.make('6862377') + '"')  #  "ounadrr"
print('"' + m.make('6862377') + '"')  #  "ounadrs"
print('"' + m.make('6862377') + '"')  #  "ntobers"
print('"' + m.make('6862377') + '"')  #  "ouncerr"
print('"' + m.make('6862377') + '"')  #  "ntoadrr"
print('"' + m.make('6862377') + '"')  #  "muncess"
print('"' + m.make('6862377') + '"')  #  "ounadrs"
print('"' + m.make('6862377') + '"')  #  "munadrs"
print('"' + m.make('6862377') + '"')  #  "ouncers"
print('"' + m.make('6862377') + '"')  #  "otoadrr"
I tried to make a few print statements in my code, and some print statements are not even showing in my terminal. I don't know why.
def make(self,number):
    self.num = number
    self.s1=''
    self.s3=''
    print("First number is", self.num[0])
    print("Letters associated with",self.num[0],"is",self.letters[int(self.num[0])][1])
    i = 0
    self.s1+=self.random.choose(self.letters[int(self.num[0])])
    print("String s1 is",self.s1)
    while i < len(self.num):
        # self.s4 +=self.random.choose(self.letters[int(self.num)])
        self.s2 = ''
        self.s2 += self.follow[self.s1]
        print("String s2 is", self.s2)
        print("Length of s2 is", len(self.s2))
        j = 0
        while j <= len(self.s2):
            found_char = False
            if self.s2[j]==self.letters[int(self.num[i+1])]:
                print("String next num is",self.letters[int(self.num[i+1])])

                self.s3+=self.s2[j]
                found_char = True
            j+=1
            print("String s3 is", self.s3)

        if found_char == False:
                return''
        i=+1

    self.s1 += self.random.choose(self.letters[self.s3])
    print("String s1 is now",self.s1)
    return self.s1
for instance, the last print statement does not show up in the terminal (I am using Intellij IDE now). I think my while loop with the counter j is messing up my code but I think my logic sounds reasonable. All I am trying to do is to check whether at each position in my string s2 contains a self.letters[int(self.num[i+1])][/python]. If it does, then I concatenate it to the new string s3. If none matches, I return an empty string. At then end, when I have a string s3 with all the matching letters in the string self.letters[int(self.num[i+1])], then I called the random.choose function again to pick a random letter out of that string and concatenate to string s1. Hmm I am having some thoughts about my while loop now, but I am working on them.

RE: Park-Miller Algorithm - merlem - Feb-20-2017

As far as I can see, with 
self.s2 += self.follow[self.s1]
you add an empty string to an empty string, right? The dictionary 'follow' contains only empty strings. But then s2 will always remain an emtpy string with a length of 0.