Assignment 2: Problem Solving Example

With a challenging problem, what is often hardest is getting started. Where to begin?

Let's start by examining the output more closely:

zyxwvutsrq
zyxwvutsr
zyxwvuts
zyxwvut
zyxwvu
zyxwv
zyxw
zyx
zy
z

Here's what we notice:

The first line has letters from 'z' to the 10th letter back from 'z' (that is, 'q').
Successive lines go back one letter less.
So, the next line goes from 'z' to 'r'.
There are 10 lines.

At this point, it's important NOT to think about coding details. This is a critically useful strategy that deserves some explanation:

The type of thinking you do when solving a problem at the higher level is different from the kind of nitpicky-language-level detail during coding.
Experience shows that it's best to avoid doing both simultaneously.
If you like analogies:
- It's best to develop an outline of an essay before focusing on sentences.
- Do the prep (chopping, organizing) before the actual cooking.

So now, let's just think high level but a little code-like.

We call this algorithmic thinking.

Since there are 10 lines, we could say "we're doing something 10 times" (each time slightly differently).

In code-like structure, called pseudcode:

       for i=1 to 10 {
          figure out and print the i-th line
       }

It's worth staring at the above for a few minutes. We'll point out that:

This is NOT actual code but puts structure to the thought "we're doing something 10 times"
The high level structure will later become a real for-loop.
Pseudocode doesn't get hung up on language minutiae like semi-colons. All it needs to do is outline the main idea, like a sketch.

Next, if we could somehow figure out the last letter in each line, we'd be in good shape:

       for i=1 to 10 {
           figure out lastLetter in line i
           // Print the line
           for c='z' to lastletter {
               print c
           }
       }

We need to figure out the last letter in the i-th line:

One problem: i is an integer.
But ... recall the connection between integers and characters?
- We can get the integer representation of a char:
```
       char ch = 'z';
       int k = (char) ch;
    
```
- And, we can go the other way too:
```
       int k = 100;
       char ch = (char) k;
    
```

So, now let's ask: how do we get the letter that's i spots behind 'z'?

Let's first get the number (integer) corresponding to the letter.

That is, if integer for z is:

       char ch = 'z';
       int k = (char) ch;

then consider:

       char ch = 'z';
       int k = (char) ch;
       int j = k - (10 - i);

Let's convert that to a letter:

       char ch = 'z';
       int k = (char) ch;
       int j = k - (10 - i);
       char lastLetter = (char) j;

The "k - (10 - i)" part deserves explanation:
- First, we know that the numbers corresponding to 'q' through 'z' are increasing. In fact, let's print them out (which you could do as part of problem-solving):
```
  q   r   s   t   u   v   w   x   y   z
 113 114 115 116 117 118 119 120 121 122
    
```
- So, here k=122.
- Recall that i goes from 1 to 10.
- And that k-10 is the spot for 'p' (which is too far)
- k-(10-1) is the spot for 'q'
- k-(10-2) is the spot for 'r' (and so on)
- So, on the i-th line, we want k-(10-i).
Was that tricky? Yes!
- We did have to reason it out and play with a few ideas.
- But that's all part of problem-solving.
- You shouldn't think: "Oh, if I don't get it right away, this is not for me".
- Remember: you get better at problem solving after cranking through lots of tricky problems.

At this point, let's write some code to test out our idea:

public class TestCharIdea {

    public static void main (String[] argv)
    {
	int i = 1;
	int k = (int) 'z';
	int j = k - (10 - i);
	char lastLetter = (char) j;
	System.out.println (lastLetter);
    }

}

One can then try different values of i to see if this works.

Now that we have the first letter ('z') and the last letter of a line, we can easily print all the ones in between, using the for-loop we've seen in Module 6.
```
	    for (char c='z'; c>=lastLetter; c--) {
		System.out.print (c);
	    }
    
```

Now let's go back to the pseudocode outline we sketched earlier:

       for i=1 to 10 {
           figure out lastLetter
           // Print the line
           for c='z' to lastletter {
               print c
           }
       }

We can now fill in all the pieces.

First, let's fill in "figure out the last letter in line i", while simultaneously turning the sentence into a comment:

       for i=1 to 10 {
           // Figure out lastLetter in line i
           char ch = 'z';
           int k = (char) ch;
           int j = k - (10 - i);
           char lastLetter = (char) j;

           // Print the line
           for c='z' to lastletter {
               print c
           }
       }

Next, let's substitute the actual code for printing the line:

       for i=1 to 10 {
           // Figure out lastLetter in line i
           char ch = 'z';
           int k = (char) ch;
           int j = k - (10 - i);
           char lastLetter = (char) j;

           // Print the line
           for (char c='z'; c>=lastLetter; c--) {
               System.out.print (c);
	   }
       }

Next, let's flesh out the outer loop:

       for (int i=1; i<=10; i++) {
           // Figure out lastLetter in line i
           char ch = 'z';
           int k = (char) ch;
           int j = k - (10 - i);
           char lastLetter = (char) j;

           // Print the line
           for (char c='z'; c>=lastLetter; c--) {
               System.out.print (c);
	   }
       }

Thus what we have so far is:

public class CharProblem {

    public static void main (String[] argv)
    {
       for (int i=1; i<=10; i++) {
           // Figure out lastLetter in line i
           char ch = 'z';
           int k = (char) ch;
           int j = k - (10 - i);
           char lastLetter = (char) j;

           // Print the line
           for (char c='z'; c>=lastLetter; c--) {
               System.out.print (c);
	   }
        }
    }

}

Is that everything? Try it and see. There's another (small) fix needed.
Once fixed, can you generalize this for any N (we've done N=10)?

At this point, let's step back and reflect on problem-solving:

It is perfectly OK to feel any of these adjectives (and more): lost, confused, befuddled, anxious, overwhelmed.
After all, this (programming) is at the moment an alien landscape in which you have to do all kinds of things to make a program work, and ALL of them have to be correct.
There is also surprising minutiae like the (10-k-i) above that needs reasoning.
One thing to keep in mind: most programming is NOT like this.
- Most programming in the outside world is relatively straightforward after you've reached a basic skill level.
- There indeed are tricky problems to solve but those are less than 10% of regular commercial code.
So why are we incorporating challenging code so early? Because that's the best way to train. Once you've developed grit and perseverance, these habits will make a big difference later.
Other things to keep in mind:
- You are going to get better at this (you'll see).
- It's not worth comparing yourself to others ("How come I'm not getting this, and others are?") because people acquire skills differently.
- You should NOT try and solve a problem all at once. Work on a skeleton and test out parts of it.

Back to the assignment