Monday, October 12, 2009

Program to Find the Digital Root of an Integer


Problem: "The digital root of an integer n is defined as the result of summing the digits repeatedly until only a single digit remains. For example, the digital root of 1729 can be calculated using the following steps:

Step 1: 1+7+2+9 = 19
Step 2: 1+9 = 10
Step 3: 1+0 = 1

Because the total at the end of step 3 is the single digit 1, that value is the digital root.

Rewrite the DigitSum program shown in Figure 4-6 so that it calculates the digital root of the imput value." (Roberts ch 4, exercise 7).

Here's the code:

/*
* File: DigitalRoot.java
* Name: Chu
* Section Leader: Ambiguous. Probably Usman Akeju.
* -----------------------------

This program uses a while loop inside while loop to run integer n thru the DigitSum
program multiple times until you get to the digital root. The DigitSum program took advantage
of the fact that the remainder of n after getting divided by 10 equals the last digit
in the integer. This program uses that as the inner loop. Then after running through the inner
loop, the output of the inner loop is made to be equal to the integer temp, which is
evaluated as a condition of the outer while loop. This is what lets us feed the integer through
the DigitSum program over and over.
**/

import acm.program.*;

public class DigitalRoot extends ConsoleProgram {

public void run () {
println("This program finds the digital root of an integer.");
int n = readInt("Enter a positive integer: ");

//If the imput is one digit to begin with, print it; we're done.

if (n <=9) {
println("The digital root is " + n);
}

else {

int dsum = 0;
int temp = n;

//Outer loop; keeps running until we get a single-digit output.

while (temp > 9) {

n = temp;
dsum = 0;

/*Inner loop: Keeps finding the remainder after you divide n by 10 to
* find the sum of digits
*/

while (n > 0) {
dsum += n % 10;
n /= 10;
}

//Set temp to dsum so that dsum can get fed through the outer loop again.
temp = dsum;

}
println("The digital root is " + temp);

}
}
}

What the output looks like:

What made it tough:

1) A loop of loops:
As was mentioned in the question, this problem builds off an example program given in the text to sum the digits of any given integer, which is any one of the steps 1 through 3 in the explanation. The sample problem gave us what would be the inner while loop of this program. The trick was to create a loop of loops that would take the solution from step 1 and feed it back through the inner loop to find the output for step 2, and so on.

I had a go at it at first by writing it as three individual loops:


public class DigitalRoot extends ConsoleProgram {

public void run () {
println("This program finds the digital root of an integer.");
int n = readInt("Enter a positive integer: ");
int dsum = 0;
while (n > 0) {
dsum += n % 10;
n /= 10;
}

/*NEED: If dsum is > 10, send it back thru the while loop. (How?...)
If dsum < 10, print "The digital root is" + dsum.*/

int o = dsum;
dsum = 0;
while (o > 0) {
dsum += o % 10;
o /= 10;
}

int p = dsum;
dsum = 0;
while (p > 0) {
dsum += p % 10;
p /= 10;
}

println("The digital root is " + dsum);

}
}

The program worked only for inputs of 4 digits, since there are three loops. For a long time, I couldn't figure out how to get the output of one of the loops to cycle back up and go through the loop again.

2) Debugging:
Once I made up a loop of loops and used the temp variable (thanks to inspiration from the comments to Fib Seq), this problem gave me the damndest time when it came to debugging. For a long time after I sketched out the strategy and wrote my code, I'd run the program, enter the output, and got nothing; my program would just blink stupidly at me.

Usman showed me the clever tip to debug by printing lines of text at different stages of the program:

//DEBUG:
println("Entering OUTER loop: n= "+ n +" dsum= "+dsum +" temp= "+temp);
while (temp > 9) {
n = temp;
dsum = 0;

//DEBUG:
println("Entering INNER loop: n= "+ n +" dsum= "+dsum+" temp= "+temp);
while (n >= 0) {
dsum += n % 10;
n /= 10;
//DEBUG:
println(" End INNER loop: n= "+ n +" dsum= "+dsum+" temp= "+temp);
}

temp = dsum;
}

Inserting the debut text gave this output:

We had told the program to print text when a) it got to entering the outer loop, b) it entered the inner loop, and c) it exited the inner loop. Since the third line of text never got printed, that told me that the program was getting stuck somewhere in the inner loop. Specifically, it was getting stuck when it got to n = 0, since of the condition to keep the loop running was n>=0.


Here's what the debug code looks like when fixed:


Time to completion: I read the problem and worked on it for an hour every night last week.

Lingering questions: How come this took so damn long!

Tuesday, October 6, 2009

Fib Sequence, the Usman Version


OK. So in response to the Fib Sequence problem from 10/5, Usman ("manus") said that I could make my code more elegant by using two variables instead of three. Never one to back down from a challenge (ok, that's not true, but this time I don't), I'll giving it a whirl. I think I'm on the right track, but so far my answers aren't right. Any ideas, folks?

/*
* File: FibSequence2.java
* Name: Renee
* Section Leader: Me!
* -----------------
* THE USMAN VERSION
*/


import acm.program.*;


public class FibSequence2 extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
println(n1);

//Now kicking off the fun part.
for (int i = 2; i < END; i++) {
n1=n1+n0;
println(n1);
n0=n1;

}
}

//Private constant; "End" is the the nth number in the Fib sequence displayed.

private static final double END = 15;




Monday, October 5, 2009

Program to Display the First N Values of the Fibonacci Sequence


Problem: "In mathematics, there is a famous sequence of numbers called the Fibonacci sequence, after the thirteenth-century Italian mathematician Leonardo Fibonacci. The first two terms in this sequence are 0 and 1, and every subsequent term is the sum of the preceding two. Thus the first several terms in the Fibonacci sequence are as follows:

fib0 = 0
fib1 = 1
fib2 = 1 (0+1)
fib3 = 2 (1+1)
fib4 = 3 (1+2)
fib5 = 5 (2+3)
fib6 = 8 (3+5)

Write a program to display the values in this sequence from fib0 through fib15" (Roberts Ch 4, Exercise 9).

Program from PrettyPrinter.de: (thanks for the tip, Arnab! no more screenshots of Eclipse)


/*
* File: FibSequence.java
* Name: Renee
* Section Leader: Me!
* -----------------
* This program displays the first N numbers in the Fib sequence (the user can pick how
* far N is by changing the private constant "END.") It first sets the sequence in motion
* by explicitly defining and printing out fib0 and fib1, but henceforth builds off
* the prior numbers of the sequence by re-setting the values of n2, n1, and n0 for every
* loop in the program.
*/


import acm.program.*;


public class FibSequence extends ConsoleProgram {
public void run() {
//Getting the first two in the sequence started...this is a bit inelegant.
int n0 = 0;
int n1 = 1;
println(n0);
println(n1);

//Now kicking off the fun part.
for (int i = 2; i < END; i++) {
int n2 = n1 + n0;
println(n2);
n0=n1;
n1=n2;

}
}

//Private constant; "End" is the the nth number in the Fib sequence displayed.

private static final double END = 15;
}



What the output looks like:




What made it tough: There are some things you learn in Java that completely fly in the face of what you learned in math class. For example, if you have the decimal number (or, "double") 2.9, but you want it to be converted into an integer, it would be converted to 2. Not 3! Everything after the integer gets truncated, even if it's not the closest integer! Similarly, if your program is working in integers, and you divide 15 by 4, the number is displayed as 3! No decimal points allowed.

The other practice that I'm struggling with is that of re-declaring variables. In one program, n can equal 1, and later on in the program, n equals 2. N just changes as your program moves along if you want it to!

If that weren't anti-instinctive enough, this Fib program gets solved declaring a variable to equal another variable, but then changing those assignments around. You find the number in a Fib sequence by summing the two outputs of the sequence that came before it (ie, Fib(n)=Fib(n-1)+Fib(n-2)), but since I can't do functions in Java yet, I store the values of the past functions by reassigning the variables down the chain.

If you look at the "fun part," once we print n2 (the latest number in the sequence to be calculated), we move the value of n2 down to the variable n1, and move the value of n1 down to the variable n0, and then we use the new n1 and n0 to calculate the new n2.

Time to completion: 3 hours.

Lingering questions: I don't like that I started off explicitly writing fib(0) and fib(1) before I could start the elegant part of the code. Is there a way to do this without?

Program to Average an Indefinite List of Integers


Problem: "Write a program called AverageList that reads in a list of integers representing exam scores, and then prints out the average. Because some unprepared student might actually get a score of 0, your program should use -1 as the sentinel to mark the end of the input." (Roberts Ch 4, Exercise 5.)

Program in Eclipse Editor (click to enlarge):


What the output looks like:




What made it tough: One of the earlier problems in this set asked "Write a program that finds the average of a pre-defined list of integers". That was easier, because if the list took in N inputs from the user, you'd know to divide the sum of your integers by N. Another problem asked, "Write a program that finds the sum of an indefinite list of integers." That was also easier, because you could keep adding to your sum until the user entered the sentinel. This one took me a while to figure out how you'd know what to divide your sum by, but it eventually cemented in my head the ways you can use increment operators like i++.

Time to completion: 3 hrs

Lingering Questions: Although my program says that it can average non-negative integers, you really can average any integer except the one used as the sentinel. Ben wants to know why you can't just use a letter as your sentinel, so that you could average any possible integer. I tried setting the sentinel constant as "A." Eclipse didn't like that. Is there a way to design this program so that you could use a letter as your sentinel?