CEMC Banner

Problem of the Week
Problem B and Solution
Code to Guide Cupid

Problem

In the grid, the black squares represent obstacles to Cupid, who cannot go through them; nor can Cupid step outside the grid boundaries.

A description of the grid follows.

Let’s play with some pseudocode to guide Cupid’s path to the heart. The code will use the following instructions:

  1. For each set of pseudocode instructions, determine where Cupid ends up, or if an obstacle ends his quest (i.e., the code crashes). 
    1. fly1
rotc
fly1
fly1
rotc
fly1
    1. fly1
rotc
fly1
rotcc
fly1

  2. Write pseudocode which guides Cupid to the heart.

Solution

    1. We go through the pseudocode, moving Cupid as directed.

      • fly1: Cupid moves one square east
      • rotc: Cupid turns south
      • fly1: Cupid moves south one square
      • fly1: Cupid moves south one square
      • rotc: Cupid turns west
      • fly1: Cupid moves one square west

      Following this sequence of moves, Cupid ends up in the lower left square on the grid.

      Starting at the first square in the second row, Cupid moves one square east, then one square south, then another square south, then one square west, ending at the first square in the fourth row.

    2. We go through the pseudocode, moving Cupid as directed.

      • fly1: Cupid moves one square east
      • rotc: Cupid turns south
      • fly1: Cupid moves south one square
      • rotcc: Cupid turns east
      • fly1: Cupid moves east one square

      Following this sequence of moves crashes the code, since Cupid is attempting to move through an obstacle.

      Starting at the first square in the second row, Cupid moves one square east, then one square south, then one square east, ending at the third square in the third row which is a black square.

  2. There are several possible sets of pseudocode. The two with the least number of instructions are given. 
    1. fly1
rotc
fly1
fly1
rotcc
fly1
fly1
rotcc
fly1
    1. rotc
fly1
fly1
rotcc
fly1
fly1
fly1
rotcc
fly1