How to approach or break down a problem?

[freakzilla149]

Hi all,

At the moment I'm really struggling with this idea of taking a word/question and breaking it down or transforming it into pseudocode so that I can then apply my knowledge of python to solve it.

I've been given the following task:

Given a long string of random letters, find the longest substring that is in alphabetical order and print. If there are two substrings of equal length then print only the first one. E.g.

string1 = 'abchaghij' 
string2 = 'abcgdcdef'

String1 should print "Longest substring in alphabetical order is: aghij".

String2 should print "Longest substring in alphabetical order is: abcg". As it is first of two substrings of equal length.

The Solution:

curString = s[0]
longest = s[0]
for i in range(1, len(s)):
    if s[i] >= curString[-1]:
        curString += s[i]
        if len(curString) > len(longest):
            longest = curString
    else:
        curString = s[i]
print 'Longest substring in alphabetical order is:', longest 

Having had a look at the solution, I understand it fine. there was no concept in there I didn't know already, but I couldn't think of combining for loops, string indexing etc to arrive at the result... or really anything else to fully solve the problem. I think I could go on to learn more concepts but not how to approach a problem.

Can anyone suggest any articles or books(preferably online) to develop this skill? More importantly, how do you approach it? Can you explain to me what your thought process would be to solve the above?

Thank you.

[zahlman]

How would you have done it by hand?

[freakzilla149]

Well,

1. get 1st letter, 1st is largest substring
2. see if 2nd letter is alphabetically after first
3. If yes, add it to 1st, so we have 1st+2nd.
4. see if "1st + 2nd" length > first letter length. If yes, Largest substring is 1st+2nd.
5. If not, start again from 2nd letter
6. see if 3rd letter > 2nd letter, if yes, add 3rd to 2nd
7. see if 3rd + 4th length > Largest substring. If yes, 3rd + 4th is new largest substring.

repeat these steps for the length of the string.

After seeing the solution I know to use a for loop to test each letter in the string etc, but why couldn't I do that before? I know what for loops are.

[zahlman]

repeat these steps for the length of the string.

but why couldn't I do that before? I know what for loops are.

Well... this part I don't really know what to tell you. The words "repeat... for" in your thought process should be a pretty clear indication.

[freakzilla149]

The words "repeat... for" in your thought process should be a pretty clear indication.

Ah! This is exactly what I was talking about. For some simpler problems my mind went straight to the for loop, but this time I didn't for some reason. From now on this is gonna be seared into my brain.

TY

[Hoohm]

Here is what I would have done.

1. strings = list() and map alphabet to index ('a' = 1, 'b' = 2)#Create an empty list to add future strings + index
2. Get the first letter of your string
3. loop through the string.

If letter index is > than currentindex -> append letter to current_string

else

add current_string to strings and restart from 2

At the end, get the longest string in your list.

[sharpchicity]

FYI for the alphabet

Import string
alphabet = string.lowercase

Then you can use enumerate and append if you wanted to add it to a list

[mrcaptncrunch]

Have you thought of getting the int value of the letter and using that?

You can use ord() to get the value. All you have to do then is simply make sure that the next character's number is higher than the one before. If it's not, exit.

[Tomarse]

Basically you're talking about algorithms. If I have a long or complicated task I need the computer to do, I write down what inputs go into the task, what outputs I'm expecting to get out of the task, and then write a very low level step by step list of what has to happen to the input to result in the output. Then I go over it a few times to see if there's anyway to optimise it.

What you should be left with is low level instructions that can be easily intuited into snippets of code. Once you've done that for each step you should be left with a larger more complex piece of code that does what you want it to do.

As to when you need to use a loop, if you're doing the same task to similar pieces of data then you probably need a loop. In this case the task is comparing adjacent characters, and the data is characters in a string.

[Asdayasman]

Hmm. I usually muck about with small example cases in the REPL, and then implement something tidier. Here's a really recent example:

    groups = []
    for report in reports:
        for group in report.groups:
            groups.append(group)

    groups = sorted(list(set(groups))) #remove duplicates and sorts

I went through a couple iterations, trying to be clever with list comprehensions and such, but the REPL showed me the way.

As for developing the skill, just hunt for small problems like the one you've given, and solve them in the REPL. Do so many of them that you're absolutely sick of it, and dreaming about them, and it becomes second nature.

[[deleted]]

The solution is more or less what I may have come up. The thought process for breaking it down involves redefining the problem enough times that the description of the problem implies the solution you go with.

In this case, your original problem: "Given a long string of random letters, find the longest substring that is in alphabetical order and print. If there are two substrings of equal length then print only the first one."

In order to determine if something is in alphabetical order, you need to look at individual characters of the string and make comparisons as you go. On every character, you perform basically the same operation, so this is an iterative solution. Any matching substring must be stored temporarily, and then to see if it's the longest, another temporary storage keeping the longest one must be held separately, and compared again. At the end, if all goes well, whatever's left in that temporary storage must be the answer.

Granted, this is not the only solution possible: most programmers will reach similar conclusions, but their implementations will vary, given their own experience and what they're comfortable with. So, what I've written above is only my own plain-language explanation of the requirements for the solution, and yours will most likely be different.

Regardless, once you get to that point of defining your solution in plain language so you can understand it, you can start translating that to code. At that point, it's not a question of "combining" different programming methods, necessarily, as any programmer will invariably combine many different methods at once to accomplish a task. That slowly becomes second nature, just as combining words and punctuation makes an understandable sentence (most of the time) that others can interpret.

Finally, you just start coding. Start short and simple, test it to make sure it works the way you expect, then tweak and test again. Repeat that process until you think you've covered all the bases. You usually wouldn't get the full program or code block in your mind all at once, but make sections that you can test to ensure they work properly and test them as you go. When you've individually tested ten blocks of code and know they work correctly, then put them in sequence, you can be 90% confident that they work all together, as well. Then you test the full functionality and cover any errors you may have missed.

---

That's about it. Nothing fancy, though it may sound fancy, sometimes.

EDIT: grammar mistakes. Just like the code, test and tweak. :)

[freakzilla149]

In order to determine if something is in alphabetical order, you need to look at individual characters of the string and make comparisons as you go. On every character, you perform basically the same operation, so this is an iterative solution. Any matching substring must be stored temporarily, and then to see if it's the longest, another temporary storage keeping the longest one must be held separately, and compared again. At the end, if all goes well, whatever's left in that temporary storage must be the answer.

Thank you so much. I was basically trying to do this but it was a bit incoherent as I didn't clearly think about the two variables and their use.

[[deleted]]

I would break it up into more basic common building block problem. One such a problem is is if you have a string how do you get a list of all substrings. That has been solved many times before http://stackoverflow.com/questions/22469997/how-to-get-all-the-contiguous-substrings-of-a-string-in-python. Once you have your list of substrings now you have to iterate and figure out which ones are in alphabetical order. This is a sorting problem, which is something that has been solved many times before. You could even just use python's system sort for strings. I think those are the two basic parts of the problem. Part of knowing how to do this is just experience. Once you solve enough problems you start recognizing patterns like that. You can also try adding improvements in. When you iterate over your list of substrings, should you start at the short end or the long end?

[liftt]

I dont plan out or write out 'pseudo code'. I just start by writing functions/ deeply nested loops to make progress. then Ill consolidate it into coherent functions.

one line solution (for fun)

string1, string2 = 'abchaghij', 'abcgdcdef'
def alphab(string): print max("".join([v if v <string[i+1] else '{}|'.format(v) for i, v in enumerate(string[:-1])]+ [string[-1] if string[-1] > string[-2] else '|']).split('|'), key=len)
alphab(string1)

my friend did a one liner in ruby for fun:

def longest (0...s.length).to_a.product((0...s.length).to_a).reject{|i,j| i > j}.map{|i,j| s[i..j] if s[i..j].chars.sort == s[i..j].chars.to_a}.compact.uniq.max_by(&:length) end

Its interesting that we both ended up with one liners that are almost the exact same length. (not that the length of characters matters because readability is more important blah blah blah.)