Class 21 — Monday, November 9
Quiz 7 first. Then loops that stop before the list ends, in Wednesday’s Walks.java, in your cmsc-120-lst project.
[CU] 6.1 — while Loops was due today. A10 is due Tuesday, November 10.
Outline
- A loop that stops early — keyboards down
- Stopping early — pairs, at the keyboard
- Before the break: save to GitHub
- Two lists at once — predict, then run
- Walking two lists — pairs again
- The body first — keyboards down
- Loops, three more — pairs
while (true), andbreak— keyboards down, then pairs- Before you leave: save again
- Before Wednesday
1. A loop that stops early
Keyboards stop. Predict first.
Wednesday’s loops walked to the end of the list. This one asks two things each time round, joined by &&:
void main() {
IO.println(unitsBefore(Lst.of(4, 7, 10, 3)));
}
// the units before the first outlined one, added up
int unitsBefore(Lst<Integer> units) {
int sum = 0;
Lst<Integer> todo = units;
while (todo instanceof Lst.Link(var u, var rest) && u < 10) {
sum = sum + u;
todo = rest;
}
return sum;
}What does it print: 11, or 14?
11. The condition is asked before every round, and the first time it says no the loop is over for good: at 10, u < 10 fails, and the 3 is never looked at. unitsBefore(Lst.of(10, 4)) is 0, and so is the empty list’s: the first part of the condition fails, and && never asks the second, which is why the second may use u at all.
The other way to stop early: return inside the loop. position gives back where x is in the list, counting from 0, and -1 when it is not there:
// where x is in the list, counting from 0; -1 when it is not there
int position(Lst<Integer> units, int x) {
int i = 0;
Lst<Integer> todo = units;
while (todo instanceof Lst.Link(var u, var rest)) {
if (u == x) {
return i;
}
i = i + 1;
todo = rest;
}
return -1;
}What are position(Lst.of(4, 10, 20), 10) and position(Lst.of(4, 10, 20), 7)? Why -1 and not 0 for the second?
1 and -1. A return inside the loop ends the whole function the moment it has the answer, so the loop never reaches the 20. When the loop does run out, the only line left is the one after it, and that is where the answer for not there goes. It cannot be 0, because 0 is a real position, the first one. Two ways to stop early, then: the condition, when you need to know where the walk stopped, as in unitsBefore; a return inside, when you have the answer.
The reading’s shorthand. sum += u is sum = sum + u, and i++ is i = i + 1. Both spellings are fine here. The reading’s int y = x++; is legal Java too, and its question, which happens first, is one you can skip by writing the increment as a line of its own, which is what this course does.
2. Stopping early
- The navigator (not typing) says the examples first. Then they say the steps the function takes.
- The driver types the above, and decides how each step becomes Java.
- If either of you is stuck, drop the roles for a minute and talk it over.
- Swap at every function.
In Wednesday’s Walks.java. Each function is a while loop, no call to itself and no Lst function but Lst.of. A // line above it, and at least two Check.is lines in main, one on the empty list.
countBefore
int countBefore(Lst<Integer> units) — how many units come before the first outlined one: countBefore(Lst.of(4, 7, 10, 3)) is 2, and countBefore(Lst.of(10, 4)) is 0.
Done when checks pass on those two and on the empty list.
firstOutlined
int firstOutlined(Lst<Integer> units) — the first outlined unit, and 0 when there is none: firstOutlined(Lst.of(4, 7, 10, 3)) is 10. A return inside the loop, as position did: the moment the loop meets an outlined unit, the function is done. After the loop, the list has run out, and return 0 is the only line left.
Done when checks pass on [4, 7, 10, 3], on [4, 7] and on the empty list.
allOutlined, two ways
If you are done, here is one function to write twice.
boolean allOutlined(Lst<Integer> units) — whether every unit is outlined; true for no units. Write it two ways. First with a boolean so far, true until a unit says otherwise, which the condition asks too: && all. Then again as allOutlinedReturn, with return false inside the loop at the first unit that is not outlined, and return true after the loop.
Done when both pass the same three checks, on [10, 20], on [10, 4, 20] and on the empty list, and you can say which of the two you would rather be handed.
3. Before the break: save to GitHub
Everyone, before the break.
In IDEA: Git → Commit… (Ctrl+K). Tick your files, write a line saying what you did, then Commit and Push… and Push. Then open your repository on GitHub and check that the commit is there.
If the push is refused, leave it for the end of class: your work is on this machine either way. The same project at home, and what to do when a push is refused: Git and GitHub at home.
4. Two lists at once
Write your prediction in the Journal before anyone runs anything.
Two names walk, one per list, and the condition asks about both:
void main() {
IO.println(sums(Lst.of(1, 2, 3), Lst.of(10, 20)));
}
// the two lists added up unit by unit, as far as the shorter one goes
Lst<Integer> sums(Lst<Integer> as, Lst<Integer> bs) {
Lst<Integer> made = new Lst.Empty<>();
Lst<Integer> ta = as;
Lst<Integer> tb = bs;
while (ta instanceof Lst.Link(var a, var ra) && tb instanceof Lst.Link(var b, var rb)) {
made = new Lst.Link<>(a + b, made);
ta = ra;
tb = rb;
}
return backwards(made);
}backwards is Wednesday’s. What does it print?
[list: 11, 22]. The loop stops when either list runs out, so the 3 has no partner and is never looked at: no error, and no fourth case for the lists ending at different times. The list is built at the front and turned round at the end, as Wednesday’s outlined was.
5. Walking two lists
Pairs, the same way, in Walks.java.
sums
Section 4’s, with its checks: [1, 2, 3] and [10, 20] give [11, 22]; the empty list and [10, 20] give the empty list.
Done when both pass.
dot
int dot(Lst<Integer> as, Lst<Integer> bs) — the products of the pairs, added up: dot(Lst.of(1, 2, 3), Lst.of(10, 20)) is 50.
Done when checks pass on those two lists and with an empty list.
sameLength
If you are done, here are two more.
boolean sameLength(Lst<Integer> as, Lst<Integer> bs) — whether the two lists are the same length: walk both, and it is true when both ran out together. After the loop, ta instanceof Lst.Empty() asks whether ta is empty.
Done when checks pass on [1, 2] with [10, 20], on [1, 2, 3] with [10, 20], and on two empty lists.
largerOf
Lst<Integer> largerOf(Lst<Integer> as, Lst<Integer> bs) — the larger of each pair: largerOf(Lst.of(1, 20, 3), Lst.of(10, 2)) is [list: 10, 20].
Done when two checks pass, one with an empty list.
6. The body first
Keyboards stop.
Wednesday’s countDigits started count at 1 and left at n / 10, so that 0 would count as one digit. The reading’s other loop asks its question after the body:
// how many digits n has, for n from 0 up
int countDigits(int n) {
int count = 0;
int left = n;
do {
count = count + 1;
left = left / 10;
} while (left > 0);
return count;
}What is countDigits(0) here, 0 or 1? And why can count start at 0 now?
1. A do loop runs its body once before the first question, so 0 is counted before left > 0 is asked and says no. That is the whole difference: while may run its body no times, do runs it at least once, and Wednesday’s special start was standing in for that one run. do is right when the body has to happen at least once, and wrong otherwise, which section 7 has a case of.
7. Loops, three more
Pairs, the same way, in Walks.java.
countDigits
Section 6’s, with checks on 2026, 7 and 0.
Done when all three pass.
route
String route(Lst<String> places) — the places joined by a comma and a space, as a loop: the text so far starts as "", and a ? : decides whether a comma goes in front. route(Lst.of("Danville", "Berwick")) is "Danville, Berwick", one place is that place alone, and no places is "".
Done when all three pass.
sumToBodyFirst
If you are done, here are two more.
int sumToBodyFirst(int n) — Wednesday’s sumTo as a do loop, checked at 100 and at 0.
Done when one of the two checks fails and you can say which, and why do is the wrong loop here.
digits
Lst<Integer> digits(int n) — the digits of n as a list, in order, for n from 0 up: digits(2026) is [list: 2, 0, 2, 6], and digits(0) is [list: 0]. n % 10 is the last digit. It comes off first, so a list built at the front comes out in order.
Done when both pass, and Check.is(fromDigits(digits(2026)), 2026) with them.
8. while (true), and break
Keyboards stop.
A third way to stop a loop. while (true) never stops on its own; break leaves the loop from wherever it stands in the body, and the program goes on with the line after the loop:
// the first square number above n: 16 for 10
int firstSquareAbove(int n) {
int k = 1;
int square = 1;
while (true) {
square = k * k;
if (square > n) {
break;
}
k = k + 1;
}
return square;
}What is firstSquareAbove(16)? Which line does break go to?
25: 16 is not above 16, so the loop goes round once more. break goes to return square;, the line after the loop; return would have left the function, and the loop’s own condition, true, never stops it. So the stop sits wherever the body has the value to test, here after square is worked out and before k moves on, which is why square is declared before the loop: a name made inside the loop is gone after it.
Pairs, in Walks.java.
firstSquareAbove
The one above, with the checks 10 is 16, 16 is 25, 0 is 1.
Done when all three pass.
doublingsBreak
int doublingsBreak(int start, int limit) — Wednesday’s doublings, how many times start doubles before it passes limit, written with while (true) and a break: doublingsBreak(1, 100) is 7, doublingsBreak(100, 50) is 0. Does doublingsBreak(0, 100) stop?
Done when both checks pass and you can say what the third call does.
termsToPass
If you are done, one more.
int termsToPass(int limit) — how many of 1, 2, 3, ... are added up before the sum passes limit: termsToPass(10) is 5, since 1 + 2 + 3 + 4 is only 10 and the fifth term passes it; termsToPass(0) is 1. Here the test comes after the sum has changed, at the bottom of the body.
Done when both pass.
9. Before you leave: save again
As before the break, in section 3: commit, push, and check that the commit is on GitHub.
10. Before Wednesday
A10 is due Tuesday, November 10. Wednesday’s class needs nothing read in advance.