Unit 6 — What Does This Program Do? (Looping)

The problem: How far does the ball travel?

A ball is dropped from a height of h centimetres. Each time it hits the floor it bounces back up to three fifths of the height it fell from, rounded down to a whole centimetre. This ACSL program follows the ball while it is still bouncing at least 10 cm high:

INPUT h
bounces = 0
distance = h
WHILE h >= 10
   h = int(h * 3 / 5)
   bounces = bounces + 1
   distance = distance + 2 * h
END WHILE
OUTPUT bounces, distance

What is output when the input is h = 100?

This is the Junior What Does This Program Do? question for Contest 2: a short program with a loop, traced by hand with no computer. A loop runs the same few lines again and again, and every pass changes the variables a little. One slip on pass 3 and every pass after it is wrong, so the skill is keeping careful track.

This unit teaches it in three steps: how ACSL writes its two loops and how to turn them into Python (Lesson 1), how to trace a loop by hand with a table, including counters, totals and a running maximum (Lesson 2), and how to trace one loop inside another (Lesson 3). Write down your first guess now. You will check it in Lesson 1 and work it out by hand in Lesson 2.

You will learn

Translate ACSL FOR … TO … STEP loops into Python range, including loops that count down.
Count a loop's passes before tracing it, and spot loops that never start.
Trace WHILE loops, counters, accumulators and a running maximum by hand.
Trace loops inside loops whose inner bounds depend on the outer counter.

Lesson 1 — Loops in ACSL pseudocode

Division: Junior and above.

ACSL pseudocode has two loops.

FOR k = start TO end STEP s … NEXT k counts k from start to end, adding s each time.
WHILE condition … END WHILE repeats while the condition is true.

Everything else is the dialect you learned in Unit 3: % is the remainder, abs(x) drops the sign, and int(x) rounds down. In this unit every value is a whole number, and a division always appears inside int( … ).

FOR includes the end value

FOR k = 4 TO 16 STEP 4
   OUTPUT k
NEXT k

This outputs 4, 8, 12 and 16: ACSL's FOR includes its end value. Python's range stops before its end, so the translation needs an end one step further on: range(4, 17, 4).

for k in range(4, 17, 4):
    print(k)

Output

Notice

16 is printed. With range(4, 16, 4) it would not be, and the loop would run one pass short. When there is no STEP, the step is 1: FOR k = 1 TO 5 is range(1, 6).

Counting down with a negative STEP

A negative STEP counts down. FOR k = 10 TO 1 STEP -3 visits 10, 7, 4 and 1. Counting down, Python's end must be one below ACSL's end, so the translation is range(10, 0, -3).

total = 0
for k in range(10, 0, -3):
    total = total + k
print(total)

Output

Notice

10 + 7 + 4 + 1 is 22. The rule for translating: go one past the ACSL end in the direction of travel. Add 1 when counting up; subtract 1 when counting down.

When the end is not hit exactly

The counter does not have to land on the end value. FOR k = 3 TO 14 STEP 4 visits 3, 7 and 11. The next value, 15, is past 14, so the loop stops there.

for k in range(3, 15, 4):
    print(k)

Output

3
7
11

Notice

The last pass is the last value that is not past the end. Before tracing a stepped loop, write out the whole list of counter values.

A loop that never starts

If the start is already past the end, the body runs zero times. FOR k = 5 TO 2 counts up from 5, but 5 is already past 2.

count = 0
for k in range(5, 3):
    count = count + 1
print(count)

Output

Notice

count is still 0. The same happens with a negative STEP when the start is below the end: FOR k = 1 TO 8 STEP -2 never runs.

How many passes?

When a FOR loop does run, the number of passes is

int((end - start) / step) + 1

For FOR k = 3 TO 14 STEP 4 that is int(11 / 4) + 1, which is 2 + 1 = 3. Python's len gives the number of values in a range, so you can check the formula.

print(len(range(3, 15, 4)), (14 - 3) // 4 + 1)
print(len(range(10, 0, -3)), (1 - 10) // -3 + 1)

Output

3 3
4 4

Notice

Both lines agree: 3 passes, then 4 passes. Counting the passes first tells you how many rows your trace table will need.

WHILE tests at the top

WHILE condition
   …
END WHILE

The condition is tested before each pass. If it is false the very first time, the body runs zero times. It is not tested in the middle of the body, so a variable can go past the limit during the last pass.

x = 1
while x < 50:
    x = x * 3
print(x)

Output

Notice

x goes 1, 3, 9, 27, 81. When x is 27 the test 27 < 50 is true, so the body runs once more and x becomes 81. Then 81 < 50 is false and the loop ends. The output is 81, not a number below 50.

ACSL `int(a / b)` is Python's `//`

When a and b are whole numbers, ACSL's int(a / b) is exactly Python's a // b. Both round down, even below zero. math.floor(a / b), from Unit 3, gives the same answer; Python's own int(a / b) does not.

import math

print(17 // 5, math.floor(17 / 5))
print(-17 // 5, math.floor(-17 / 5), int(-17 / 5))

Output

3 3
-4 -4 -3

Notice

-17 / 5 is -3.4, and rounding down gives -4. // and math.floor both give -4; Python's int chops toward zero and gives -3. So translate ACSL int(a / b) as a // b. In this unit's questions, % is only used on numbers that are not negative.

Translating the opening problem

Here is the bouncing-ball program, translated line by line. The input value is typed in, since nobody is here to type it.

h = 100
bounces = 0
distance = h
while h >= 10:
    h = h * 3 // 5
    bounces = bounces + 1
    distance = distance + 2 * h
print(bounces, distance)

Output

5 372

Notice

WHILE … END WHILE became while with an indented body, and int(h * 3 / 5) became h * 3 // 5. Each bounce adds 2 * h: the ball goes up h and comes back down h. Did it match your guess? Running the translation is how you check an answer while you practise; in the contest, Lesson 2's trace table is how you get it.

The full program, reading h from the input, is saved as assets/l1.py.

Try it yourself

h = int(input())
bounces = 0
distance = h
while h >= 10:
    h = h * 3 // 5
    bounces = bounces + 1
    distance = distance + 2 * h
print(bounces, distance)

Run it from this unit's folder, feeding it an input file:

python assets/l1.py < assets/l1/1.in

assets/l1/2.in drops the ball from 9 cm. Predict what happens before you run it: how many times does the WHILE body run?

Lesson 2 — Tracing loops by hand

Division: Junior and above.

To trace a loop, keep a table with one column per variable and one row per pass. Before a FOR loop, write down the list of counter values. Before each pass of a WHILE loop, work out the test and write true or false. Fill each row from left to right, using the values in the row above.

Tracing the opening problem

Input: h = 100, so bounces = 0 and distance = 100 before the loop.

pass	test `h >= 10`	`h`	`bounces`	`distance`	note
1	`100 >= 10` true	60	1	220	300 / 5 = 60
2	`60 >= 10` true	36	2	292	180 / 5 = 36
3	`36 >= 10` true	21	3	334	108 / 5 = 21.6, down to 21
4	`21 >= 10` true	12	4	358	63 / 5 = 12.6, down to 12
5	`12 >= 10` true	7	5	372	36 / 5 = 7.2, down to 7
–	`7 >= 10` false				the loop ends

The output is 5 372. Check it against assets/l1/1.out.

Counters and accumulators

A counter goes up by 1 each time something happens. An accumulator (a running total) adds a value each time. Both start before the loop, usually at 0.

total = 0
count = 0
FOR k = 3 TO 30 STEP 5
   IF k % 2 == 0 THEN
      total = total + k
   ELSE
      count = count + 1
   END IF
NEXT k
OUTPUT total, count

total = 0
count = 0
for k in range(3, 31, 5):
    if k % 2 == 0:
        total = total + k
    else:
        count = count + 1
print(total, count)

Output

54 3

Notice

The counter values are 3, 8, 13, 18, 23, 28. The even ones, 8 + 18 + 28, make total 54, and the three odd ones make count 3. In a trace table, only one of the two columns changes on each row.

A running maximum

A running maximum remembers the largest value seen so far, and often where it was seen. Each pass compares the new value with the best so far and replaces it only when the new one is larger.

best = 0
where = 0
for k in range(1, 7):
    v = k * 5 % 13
    if v > best:
        best = v
        where = k
print(best, where)

Output

12 5

Notice

v goes 5, 10, 2, 7, 12, 4, so best goes 5, 10, 10, 10, 12, 12, and the answer is 12 5. Starting best at 0 is safe here only because v is never negative.

Watch the comparison when two values tie. With >, a tie does not replace the best, so the first one is kept. With >=, a tie does replace it, so the last one is kept.

first = 0
last = 0
best1 = -1
best2 = -1
for k in range(1, 6):
    v = k * 4 % 6
    if v > best1:
        best1 = v
        first = k
    if v >= best2:
        best2 = v
        last = k
print(first, last)

Output

1 4

Notice

v goes 4, 2, 0, 4, 2. The largest value, 4, appears at k = 1 and again at k = 4. > keeps 1; >= moves on to 4. Contest questions often hang on exactly this one character.

Taking a number apart, digit by digit

n % 10 is the last digit of n, and int(n / 10) removes it. A WHILE loop that repeats both, until n is 0, visits every digit from right to left.

n = 5083
s = 0
big = 0
WHILE n > 0
   d = n % 10
   s = s + d
   IF d > big THEN
      big = d
   END IF
   n = int(n / 10)
END WHILE
OUTPUT s, big

n = 5083
s = 0
big = 0
while n > 0:
    d = n % 10
    s = s + d
    if d > big:
        big = d
    n = n // 10
print(s, big)

Output

16 8

Notice

n goes 5083, 508, 50, 5, 0, and d takes the digits 3, 8, 0, 5. The output is 16 8. The loop runs once per digit, which is why WHILE fits here: the program does not know in advance how many digits there are.

`abs` inside a loop

abs turns a difference into a distance, which can never be negative. Here a marker jumps along a number line, and the program adds up how far it travels.

pos = 0
dist = 0
for k in range(1, 7):
    new = k * k % 7 - 3
    dist = dist + abs(new - pos)
    pos = new
print(dist)

Output

Notice

The marker visits -2, 1, -1, -1, 1, -2, starting from 0. The jumps are 2, 3, 2, 0, 2, 3, all counted as positive, so the output is 12. Without abs, the jumps to the left would cancel the jumps to the right.

Rounding down below zero, again and again

Inside a loop, a mistake with int is repeated on every pass. Compare ACSL's int (//) with Python's int, which chops toward zero.

x = 9
y = 9
for k in range(4):
    x = x // 2 - 3
    y = int(y / 2) - 3
    print(x, y)

Output

1 1
-3 -3
-5 -4
-6 -5

Notice

The two agree while the numbers are positive. At -3, ACSL's int(-3 / 2) is int(-1.5), which is -2, but Python's int gives -1. From then on every pass starts from a different value, and the last line is -6 -5. The ACSL answer is -6.

Put it together: this program reads one whole number, which may be negative but is not 0, and prints how many digits it has, their sum, and the largest digit. It uses abs, a counter, an accumulator and a running maximum in one WHILE loop. It is saved as assets/l2.py.

Try it yourself

n = abs(int(input()))
digits = 0
total = 0
largest = 0
while n > 0:
    d = n % 10
    digits = digits + 1
    total = total + d
    if d > largest:
        largest = d
    n = n // 10
print(digits, total, largest)

Trace it by hand on each input before you run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

Notice

abs comes first, so -4096 is treated as 4096 (assets/l2/2.in). The input 0 is not allowed: WHILE 0 > 0 is false at once, so the program would say that 0 has no digits at all.

Lesson 3 — Loops inside loops

Division: Junior and above.

A loop can sit inside another loop. The inner loop runs all the way through on every pass of the outer loop. In ACSL questions the inner loop's start or end often uses the outer counter, so the inner loop runs a different number of times on each outer pass.

An inner loop that grows

c = 0
FOR i = 1 TO 4
   FOR j = 1 TO i
      c = c + 1
   NEXT j
NEXT i
OUTPUT c

Make one row per outer pass and write out the inner values:

`i`	`j` takes	inner passes
1	1	1
2	1, 2	2
3	1, 2, 3	3
4	1, 2, 3, 4	4

So c is 1 + 2 + 3 + 4, which is 10.

c = 0
for i in range(1, 5):
    for j in range(1, i + 1):
        c = c + 1
print(c)

Output

Notice

The inner end i becomes i + 1 in Python, by the same "one past the end" rule.

An inner loop that shrinks

If the inner loop starts at the outer counter, FOR j = i TO 4, it gets shorter each time: 4 passes, then 3, 2 and 1. Each (i, j) pair has i <= j, so every pair of numbers from 1 to 4 is visited once, with doubles such as (2, 2) included.

c = 0
for i in range(1, 5):
    for j in range(i, 5):
        c = c + 1
        print(i, j)
print(c)

Output

Notice

(1, 1) to (1, 4) come first, then (2, 2) to (2, 4), and so on down to (4, 4). c is 4 + 3 + 2 + 1, which is 10 again.

An inner loop that sometimes never starts

c = 0
FOR i = 1 TO 5
   FOR j = 3 TO i
      c = c + 1
   NEXT j
NEXT i
OUTPUT c

When i is 1 or 2, the inner start 3 is already past the end, so the inner loop runs zero times.

c = 0
for i in range(1, 6):
    for j in range(3, i + 1):
        c = c + 1
print(c)

Output

Notice

The inner passes are 0, 0, 1, 2, 3, so c is 6. When you make the table, write none in the rows where the inner loop does not run, so you do not invent passes.

A negative STEP outside, `int` inside

t = 0
FOR i = 6 TO 1 STEP -2
   FOR j = 1 TO int(i / 2)
      t = t + j
   NEXT j
NEXT i
OUTPUT t

The outer counter takes 6, 4, 2. The inner end is int(i / 2): 3, then 2, then 1.

t = 0
for i in range(6, 0, -2):
    for j in range(1, i // 2 + 1):
        t = t + j
print(t)

Output

Notice

The three outer passes add 1 + 2 + 3, then 1 + 2, then 1, which makes 10. Work out the inner end once per outer pass and write it at the start of the row.

A WHILE loop inside a FOR loop

The inner loop can be a WHILE. Here it takes each k apart into its digits, as in Lesson 2. The variables the inner loop uses must be reset at the top of every outer pass.

count = 0
for k in range(19, 26, 3):
    m = k
    s = 0
    while m > 0:
        s = s + m % 10
        m = m // 10
    print(k, s)
    if s > 5:
        count = count + 1
print(count)

Output

Notice

k takes 19, 22, 25, with digit sums 10, 4, 7, so count is 2. If s = 0 were written before the FOR loop instead, the digit sums would pile up: 10, then 14, then 21.

Put it together: a number's proper divisors are the numbers smaller than it that divide it exactly: for 12 they are 1, 2, 3, 4, 6, which add up to 16. This program reads n and finds which number from 1 to n has the largest sum of proper divisors, printing that number and the sum. If two numbers tie, the smaller one wins.

INPUT n
best_k = 1
best_sum = 0
FOR k = 1 TO n
   s = 0
   FOR j = 1 TO int(k / 2)
      IF k % j == 0 THEN
         s = s + j
      END IF
   NEXT j
   IF s > best_sum THEN
      best_k = k
      best_sum = s
   END IF
NEXT k
OUTPUT best_k, best_sum

The inner loop stops at int(k / 2), because no proper divisor of k is bigger than half of k. It is saved as assets/l3.py.

Try it yourself

n = int(input())
best_k = 1
best_sum = 0
for k in range(1, n + 1):
    s = 0
    for j in range(1, k // 2 + 1):
        if k % j == 0:
            s = s + j
    if s > best_sum:
        best_k = k
        best_sum = s
print(best_k, best_sum)

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

Notice

For k = 1 the inner loop is FOR j = 1 TO 0, which runs zero times, so the sum for 1 is 0. That is why best_k = 1 and best_sum = 0 are a correct start: they are the real first value, not a made-up one. With n = 1 (assets/l3/2.in) the outer loop runs once and the output is 1 0.

Recap

An ACSL FOR includes its end value, so go one past the end, in the direction of travel, for Python's range.
WHILE tests only at the top, so a variable can overshoot the limit before the loop stops.
In a running maximum, > and >= treat ties differently.
ACSL's int(a / b) rounds down, which is Python's //, even below zero.
In nested loops, run the whole inner loop for each pass of the outer one. The opening program prints 5 372.

You can now trace a looping ACSL program by hand and write its exact output.

Unit 6 — What Does This Program Do? (Looping)

The problem: How far does the ball travel?

Lesson 1 — Loops in ACSL pseudocode

FOR includes the end value

Counting down with a negative STEP

When the end is not hit exactly

A loop that never starts

How many passes?

WHILE tests at the top

ACSL int(a / b) is Python's //

Translating the opening problem

Lesson 2 — Tracing loops by hand

Tracing the opening problem

Counters and accumulators

A running maximum

Taking a number apart, digit by digit

abs inside a loop

Rounding down below zero, again and again

Lesson 3 — Loops inside loops

An inner loop that grows

An inner loop that shrinks

An inner loop that sometimes never starts

A negative STEP outside, int inside

A WHILE loop inside a FOR loop

ACSL `int(a / b)` is Python's `//`

`abs` inside a loop

A negative STEP outside, `int` inside