Connect with us

Python programming course help

Discussion in 'Electronics Homework Help' started by chopnhack, Jan 21, 2015.

Scroll to continue with content
  1. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Problem 3: Alphabetical Substrings
    Assume s is a string of lower case characters.

    Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print



    Longest substring in alphabetical order is: beggh
    In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print



    Longest substring in alphabetical order is: abc
    For problems such as these, do not include raw_input statements or define the variable s in any way. Our automating testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.

    Note: This problem is fairly challenging. We encourage you to work smart. If you've spent more than a few hours on this problem, we suggest that you move on to a different part of the course. If you have time, come back to this problem after you've had a break and cleared your head.

    Code:
    curString = s[0]                 #I see curString and longest variable being set to zero initially. 
    longest = s[0]
    for i in range(1, len(s)):    #Contents of variable i while in range starting at 1 and ending at the length of variable 's'
      if s[i] >= curString[-1]:    #Loop if variable s[i]? is greater than curstring variable[-1]
           curString += s[i]        
           if len(curString) > len(longest):
                 longest = curString
      else:
            curString = s[i]
    print 'Longest substring in alphabetical order is:', longest
    
    CORRECT
    s = 'otaigtxslrmxhiuloiovxuhm'
    Output:
    Longest substring in alphabetical order is: iovx

    I like the last line about take a break and clear your head LOL I am having difficulty with these more abstracted arguments: for i in range (1, len(s)) - several functions are combined and I seem to lose my place.

    Can someone explain line by line what is going on?
    I also don't see where the computation is occurring to check for alphabetical order.
    Thank you in advance.
     
  2. KrisBlueNZ

    KrisBlueNZ Sadly passed away in 2015

    8,393
    1,270
    Nov 28, 2011
    Code:
    01  curString = s[0]            # Set curString to first character of input string s
    02  longest = s[0]              # Initially, the longest string is the same
    03  for i in range(1, len(s)):  # Step through s one character at a time, starting from second character
    04    if s[i] >= curString[-1]: # If current character in s is alphabetically the same or higher than last character in curString...
    05      curString += s[i]       # ... add it to the current string
    06      if len(curString) > len(longest):
    07        longest = curString   # Update longest if working string is longer
    08    else:
    09      curString = s[i]        # Character was out-of-order; restart curString here
    10  print 'Longest substring in alphabetical order is:', longest
    Where did you get this code from? It looks like it should work (with the correct indentation).

    Did you add the comments yourself?

    Start by looking at my modified comments. If you can't follow the code using those, I'll write up a more detailed explanation.
     
    chopnhack likes this.
  3. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Thanks Kris! The code was the solution to the problem set - I started the course a few days late and ran out of time to get the solution in. I did the comments as I tried to make sense of the functions. I will look through this in more detail late tonight, I am trying to get this last pset out and it looks like I only have another hour or so to go :(

    I am currently trying to get a loop setup that will correctly satisfy this question:

    Problem 2: Paying Debt Off In a Year
    (15 points possible)
    Now write a program that calculates the minimum fixed monthly payment needed in order pay off a credit card balance within 12 months. By a fixed monthly payment, we mean a single number which does not change each month, but instead is a constant amount that will be paid each month.

    In this problem, we will not be dealing with a minimum monthly payment rate.

    The following variables contain values as described below:

    1. balance - the outstanding balance on the credit card

    2. annualInterestRate - annual interest rate as a decimal
    The program should print out one line: the lowest monthly payment that will pay off all debt in under 1 year, for example:



    Lowest Payment: 180


    Code:
    month = 0
    MPR = annualInterestRate/12    #monthly percentage rate
    MMP = 10                       #monthly minimum payment
    tbalance = 0                   #temporary holder for balance for other operations to take place on it
    
    
    while month < 12:                #loop until 12
      tbalance = balance - MMP      #result is balance after min. monthly payment is made
      balance = tbalance * (1+MPR)  #new balance assigned after interest charges accrued
      month += 1                                #increase month
    
    
      if balance <= 0:                     #check to see if balance is zeroed out - course said ok to go negative, nearest increment of $10
        print 'Lowest payment: ', MMP      #if balance is low enough, Lowest payment will print out (last known MMP) and break out of loop
        break
      else:                                         #if the MMP was not enough to pay off balance after 12 go arounds, this should increment MMP by $10
      MMP = MMP + 10                   #and reset month to zero
      month = 0
    
    I was comparing my coding with the peers and boy, I don't think the same :confused::p:oops:
    I am just not familiar enough with the built in functions so I use very simplistic methods to get the answer. I won't make it much further unless I can grasp more of their uses.

    Thanks in advance if you can offer insight into my loop issue - I tested it out and it was close on most balances, but not quite right.
     
  4. Gryd3

    Gryd3

    4,098
    875
    Jun 25, 2014
    This may be overcomplicating or simplifying it...
    Is the interest compounded? (if so, is it compounded monthly?)

    If not, you could simply create a new total with the balance and interest and divide by 12.. could you not? Or did I miss something?
     
    chopnhack likes this.
  5. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Compounded monthly after the payment is made - my code is not going through a full 12 months before resetting to 0!!
     
  6. Gryd3

    Gryd3

    4,098
    875
    Jun 25, 2014
    How many loops is it doing?
    It looks like it will loop 12 times assuming the balance does not fall below 0 prior to the 11th iteration.

    (Your while loop will loop on month = 0 to 11, which is 12 iterations. You can try printing out the month value to see what it may be doing in the code)
     
    chopnhack likes this.
  7. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    I got this one, the code looks clunky, but it did the job:

    Code:
    bala = balance
    month = 0
    MPR = annualInterestRate/12 * bala
    MMP = 0
    
    
    while month < 12:
      bala -= MMP
      MPR = annualInterestRate/12 * bala
      bala += MPR
      month += 1
      if month == 12:
      if bala <= 0:
      print 'Lowest payment: ' , MMP
      break
      if bala > 0:
      MMP += 10
      month = 0
      bala = balance
     
    

    CORRECT Hide outputHide output
    Test Case 1
    balance = 3329; annualInterestRate = 0.2

    Output:
    Lowest payment: 310
     
  8. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    The next iteration of the above program was to use bisection to make it faster....
    I had made decent progress until I saw that my balance could overshoot some of my test cases, so I added the ability to check if the lo side needed to go lower (in other words after it was raised it might need to move back down - which if iterated correctly it probably wouldn't need this function, LOL)

    upload_2015-1-21_19-11-4.png

    I give up with fixing the indenting.....
     
  9. Laplace

    Laplace

    1,252
    184
    Apr 4, 2010
  10. Gryd3

    Gryd3

    4,098
    875
    Jun 25, 2014
  11. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Yes, lack of intelligence ROFL :D:p:oops:

    This will shock you Laplace, but I actually wrote a program in C++ close to two decades ago - I lament that I don't have the source code anymore, because at the time I was quite proud of how I was able to figure out the looping necessary to perform the calculation. It was a simple calculator for taking a starting investment, allowing for contributions, assuming a set interest rate and using inputted time period produced the future value. There is a link below if you want to check it out.

    https://drive.google.com/file/d/0B1P01SzcMubrSnVvb1k4b1NlZ2M/view?usp=sharing

    I will figure out loops and then the cleaner ways of writing them soon, I hope!

    Thanks all - I will give the brain some rest today ;)
     
  12. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Thanks ever so much Kris for breaking that down for me!! I didn't realize that the language was set up to compare the alphabetical characters mathematically! Wow..
    I like how elegant this was written, I hope I can write code like this someday - its very clean, easy to follow and now it makes sense. Thanks again.
     
  13. KrisBlueNZ

    KrisBlueNZ Sadly passed away in 2015

    8,393
    1,270
    Nov 28, 2011
    No problem. Yes I agree that it's a pretty tidy way of doing it.

    The reason you can compare characters numerically and this equates to an alphabetic comparison is the character set.

    Computers represent everything internally as numbers, and that includes characters. The mapping of internal numeric values to displayed characters is called a "character set" and there are several types of mapping, but most (all, I think) of the modern character sets contain the 95 printable characters from one of the earliest character sets, ASCII (American Standard Code for Information Interchange).

    The ASCII character set defines numeric codes from 32 to 126 to represent the following characters:

    32: space character
    33~39: !"#$%&'
    40~49: ()*+,-./01
    50~59: 23456789:;
    60~69: <=>[email protected]
    70~79: FGHIJKLMNO
    80~89: PQRSTUVWXY
    90~99: Z[\]^_`abc
    100~109: defghijklm
    110~119: nopqrstuvw
    120~126: xyz{|}~

    When you compare two characters with a simple "<" or ">", etc, you are actually comparing the codes that represent the characters. Since the alphabet appears in the ASCII character coding, in ascending numerical order, comparing two alphabetic characters numerically will also compare them alphabetically, but only if they are the same case. "Z" is alphabetically higher than "a", but from the comparison's point of view it is numerically lower.

    You can test this by trying some mixed case strings with your program.

    That solution is easy to follow, but it is a bit inefficient, with all of that string manipulation. Here is how I would implement it. This code uses no other strings, just some integers. Feel free to figure it out and add comments explaining how it works, if you want :)

    Code:
    while True:
        s = input ("Enter string (empty string to quit): ")
        slen = len(s)
        if slen == 0:
            break
        wlen = 1
        lpos = 0
        llen = 1
        for wpos in range(slen - 2, -1, -1):
            if s[wpos] <= s[wpos + 1]:
                wlen += 1
                if wlen >= llen:
                    lpos = wpos
                    llen = wlen
            else:
                wlen = 1
        print ("Longest alphabetical substring (" + str(llen) + " characters) is '" + s[lpos : lpos + llen] + "'")
     
    Last edited: Jan 28, 2015
    chopnhack likes this.
  14. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    I will come back to this! But for now, the course is moving faster than I can keep up with it!
     
  15. KrisBlueNZ

    KrisBlueNZ Sadly passed away in 2015

    8,393
    1,270
    Nov 28, 2011
    Sure :)
     
    chopnhack likes this.
  16. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    Scouts honor mate! LOL I am just really bogged down, you know that I am a slow learner :D
     
  17. KrisBlueNZ

    KrisBlueNZ Sadly passed away in 2015

    8,393
    1,270
    Nov 28, 2011
    I wasn't being sarcastic, though it might have looked like it. And you're not a slow learner! There's a lot to learn and you're doing well.
     
    chopnhack likes this.
  18. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    I know you weren't, no worries. I guess you haven't learned my sour humor yet :D;) Trust me, I am... Recursion - to occur repeatedly, duh... Now, why can't I convert that simple premise, hahaha. ahhh... it's a math thing I guess :rolleyes:
     
  19. KrisBlueNZ

    KrisBlueNZ Sadly passed away in 2015

    8,393
    1,270
    Nov 28, 2011
    In computer science, recursion has a specific meaning. It doesn't just mean to happen repeatedly, or to drill down recursively into subdirectories. It refers to a function that calls itself, either indirectly, or more commonly, directly.

    Look at a typical program.
    Code:
    def print_string(s):
        for character in s:
            print(character)
        return
    
    def print_my_name():
        print_string("John")
        return
    This program doesn't use recursion. print_my_name() calls print_string(). print_string() calls print() several times, then returns to print_my_name(), which then returns to its caller.

    If you were to draw an execution diagram showing what function called what, with the highest level function (print_my_name()) at the top and the lowest level function (print()) at the bottom, arrows would only go directly between the different levels.

    This program uses recursion:

    Code:
    1  def prend(s):
    2      if len(s) > 0:
    3          print(s)
    4          prend(s[1:])
    5      return
    6
    7  prend("John")
    When I ran that program, the output was:
    Code:
    John
    ohn
    hn
    n
    The important characteristics of the prend() function are (a) it is recursive - it calls itself on line 4, and (b) it doesn't always call itself - there is a case (if s is an empty string) where it will return without calling itself.

    When prend() calls itself at line 4, the "itself" that it calls does not receive the whole input string - it receives the string with its first character removed. This is what the notation s[1:] means - it means a part of string s, starting at character 1 (characters are numbered from 0, so character 1 is the second character), continuing until the end of the string. If s contains only one character to start with, there is no second character, so s[1:] is actually an empty string - a string with zero length.

    When you run this program, the prend() function is defined by lines 1~5, then it is invoked at line 7. This is what happens.

    prend() is called with s="John". Line 2 checks the length of string s. Since the length is greater than zero (it is 4), lines 3 and 4 are executed. Line 3 prints the whole string ("John"), and line 4 invokes the prend() function again, but this time, the string that's passed to it is "ohn".

    Just like with any other function call, the code that called the function is suspended while the function call occurs. The CPU that executes code can only do one thing at a time (unless it's a multicore CPU, but let's forget about those), and although there are tricks to make CPUs do (or appear to do) more than one thing at the same time, the basic programming paradigm is a single execution point that travels forwards through the program statements, and when a function is called, execution is transferred to the start of that function.

    It's like when you're reading a book and you skip down to a footnote then return to the text. You don't continue reading the page while you're reading the footnote, because you only have one focus of attention. That's equivalent to the execution point.

    I will call the first invocation of prend() "prend[1]". At line 4 in prend[1], this invocation of prend() is suspended, and execution starts again at the start of the prend() function, but this time, the string s is "ohn". I will call this invocation of prend() "prend[2]".

    prend[2], the first nested invocation of prend(), has its own private variables, so its version of s can be "ohn" although s = "John" for prend[1]. These two different versions of s actually exist at the same time, although only one is accessible at any time because there is only one execution point. It's as if prend[1] has been put into suspended animation, along with its copy of s (which is "John"). The only copy of s that can be used is prend[2]'s copy, which is "ohn".

    So prend[2] checks for an empty string, prints s (which prints "ohn"), then invokes prend() again. This invocation will be prend[3] and its copy of s will be "hn".

    So prend[3] checks for an empty string, prints s (which prints "hn"), then invokes prend() again. This invocation will b prend[4] and its copy of s will be "n".

    So prend[4] checks for an empty string, prints s (which prints "n"), then invokes prend() again. This invocation will be prend[5] and its copy of s will be "" (empty string). So it will skip lines 3 and 4, and will just return at line 5.

    Execution now continues at line 5 of prend[4], which returns, so execution continues at line 5 of prend[3], which returns, so execution continues at line 5 of prend[2], which returns, so execution continues at line 5 of prend[1], which returns, and the program is finished.

    I hope that helps you understand recursion a bit better!
     
    Last edited: Jan 28, 2015
    chopnhack likes this.
  20. chopnhack

    chopnhack

    1,573
    352
    Apr 28, 2014
    I really marvel at how fast you are able to type and explain complex matters - thank you!! I did notice some odd behavior when I ran the program through pythontutor.com which has become my favorite method of debugging - I am able to step through each line and see the variables value's at the time of each step. So handy! What I noticed is that at line 5 after string ended with "n", it prints out "" as the variable's value and then continues to check it - returns value none and then removes it from the frame space. It does this for each part, until its blank and then it breaks. Very strange, may have something to do with the authors coding for the website, but I thought it was interesting to see. Click the link below if you want to see what I mean.

    http://pythontutor.com/visualize.html#togetherjs=ChzRuvsrti
     
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day

-