Maker Pro
Maker Pro

Python programming course help

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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.
 

KrisBlueNZ

Sadly passed away in 2015
Nov 28, 2011
8,393
Joined
Nov 28, 2011
Messages
8,393
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

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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.

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.
 

Gryd3

Jun 25, 2014
4,098
Joined
Jun 25, 2014
Messages
4,098
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

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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?
Compounded monthly after the payment is made - my code is not going through a full 12 months before resetting to 0!!
 

Gryd3

Jun 25, 2014
4,098
Joined
Jun 25, 2014
Messages
4,098
Compounded monthly after the payment is made - my code is not going through a full 12 months before resetting to 0!!
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

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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
 

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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.....
 

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
Is there any reason why you can't apply the amortization annuity formula?
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
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 ;)
 

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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.

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.
 

KrisBlueNZ

Sadly passed away in 2015
Nov 28, 2011
8,393
Joined
Nov 28, 2011
Messages
8,393
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: <=>?@ABCDE
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:

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
I will come back to this! But for now, the course is moving faster than I can keep up with it!
 

KrisBlueNZ

Sadly passed away in 2015
Nov 28, 2011
8,393
Joined
Nov 28, 2011
Messages
8,393
Scouts honor mate! LOL I am just really bogged down, you know that I am a slow learner :D
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

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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.
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:
 

KrisBlueNZ

Sadly passed away in 2015
Nov 28, 2011
8,393
Joined
Nov 28, 2011
Messages
8,393
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:

chopnhack

Apr 28, 2014
1,576
Joined
Apr 28, 2014
Messages
1,576
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!
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
http://pythontutor.com/visualize.html#togetherjs=ChzRuvsrti
 
Top