3.9 Developing algorithmsMany ways to solve it, and the robot

Algorithms can be written in different ways and still accomplish the same task. Algorithms that look almost the same can produce different results or side effects. Some conditional statements can be rewritten as equivalent Boolean expressions, and some Boolean expressions can be rewritten as other, equivalent Boolean expressions. The exam often shows two versions of code and asks whether they always do the same thing.
1IF (a > b)2{3 big ← a4}5ELSE6{7 big ← b8}
1big ← a2IF (b > big)3{4 big ← b5}
Are A and B equivalent? Test the cases: a bigger, b bigger, and the tie. If a = b, A goes to the ELSE and sets big to b, while B keeps big as a. Since a and b are equal, both give the same value. So yes, they always produce the same result. Checking the tie is the step people skip, and it's where non-equivalent versions usually differ.
?Wait, how do I decide whether two code segments are equivalent?
You don't have to invent every algorithm from scratch. Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing ones. The course expects you to know a few building blocks: finding the maximum or minimum of two or more numbers, computing a sum or an average, deciding whether one integer is evenly divisible by another (n MOD d = 0), and finding a robot's path through a maze. Using existing correct algorithms as building blocks saves development time, reduces testing, and makes errors easier to find.
The robot
Robot questions show a grid of squares. The robot sits in one square, facing a direction. Dark squares are blocked. The reference sheet gives four commands.
| Command | What the robot does |
|---|---|
| MOVE_FORWARD() | One square in the direction it faces |
| ROTATE_LEFT() | Turns 90° left, staying in its square |
| ROTATE_RIGHT() | Turns 90° right, staying in its square |
| CAN_MOVE(direction) | true if the square to its left, right, forward or backward is open |
| Blocked or off the grid | The robot stays put and the program ends |
?Wait, which way is "left" for the robot?
I thought about it. Show me
- Line 1 checks CAN_MOVE(forward) before each pass. Facing up from the bottom row, the square above is open, so it moves up one.
Why?
REPEAT UNTIL (NOT CAN_MOVE(forward)) means "keep moving while the square ahead is open". - It moves up again: now it's in the middle row. The square above that is blocked, so CAN_MOVE(forward) is false, NOT false is true, and the loop stops.
- ROTATE_RIGHT(): from facing up, the robot now faces right.
- REPEAT 2 TIMES MOVE_FORWARD(): two squares right. It ends in the middle row, third column: the goal square, facing right.
Why?
Write the square and direction after every line. Robot questions are lost by one wrong turn.
Answer: It ends on the goal square, middle row and third column from the left, facing right.
1REPEAT UNTIL (NOT CAN_MOVE(forward))12{3 MOVE_FORWARD()4}5ROTATE_RIGHT()26REPEAT 2 TIMES7{8 MOVE_FORWARD()9}
- line 1 Keep going until the square ahead is blocked
- line 5 A right turn from the robot's point of view
Stuck? Get a hint
- Start by moving up. When is the square ahead blocked?
- After the loop, turn right from the robot's view: up becomes right.
- Then count two squares to the right.
- AisDiv ← (n / 4 = 1)
- BisDiv ← (n MOD 4 = 0)
- CisDiv ← (4 MOD n = 0)
- DisDiv ← (n MOD 4 = 4)
Show the answer
B. n is divisible by 4 when n ÷ 4 leaves no remainder: n MOD 4 = 0. Notice that a Boolean expression can be assigned directly to a variable; no IF is needed.
- Different algorithms can solve the same problem; similar-looking ones can give different results.
- Check equivalence on every case, especially boundaries and ties.
- Know the building blocks: max/min, sum/average, divisibility (MOD), robot paths.
- Robot: directions are from the robot's view. Blocked or off-grid moves end the program.