7

Scaffolded Code Exercises

Once you select a development environment, you can start setting up more involved code exercises for your students. In this chapter, we’ll learn three coding activities of increasing complexity that address multiple computer science standards, such as evaluating and enhancing algorithms, learning to talk about code, using encryption, and debugging. Each exercise will require you to provide students with prewritten code in your chosen development environment as a scaffolding for student understanding. This way, students will continue to learn from existing code but be given specific direction for engaging with that code to better understand it.

Evaluating Algorithms

The computer science standards have students practice evaluating and comparing algorithms. In this evaluation exercise, which is from the organization freeCodeCamp, you’ll present your students with many different algorithms to test for palindromes, text strings that read the same forward as backward. One technique for finding palindromes would be to choose a string input, reverse it, and see whether the reversed string equals the original string. When this possible solution is abstracted, one component of this function would likely take a string of characters and return that string with the character order reversed. Edd Mann, a blogger and developer, documented 10 ways to do this in JavaScript (https://eddmann.com/posts/ten-ways-to-reverse-a-string-in-javascript/). We’ll review three of the solutions he developed, but the full exercise should include many more examples.

for Loop

The first example in Listing 7-1 is a simple for loop. It takes the string input, loops backward through each character in the string via the i = stringToReverse.length - 1; i >= 0; i-- arguments, and appends the last character in the string to the new string.

function reverseString(stringToReverse) {
  var reversedString = "";
  for (var i = stringToReverse.length - 1; i >= 0; i--) {
    reversedString += stringToReverse[i];
  }
  return reversedString;
}

Listing 7-1: Using a for loop to reverse a string

Students can see the output of the reverseString function in Listing 7-2 where the word “aibohphobia,” the fear of palindromes, is the input.

document.write(reverseString("aibohphobia"));

Listing 7-2: Code to execute the reverseString function

When evaluating this algorithm, you have an excellent opportunity to introduce your students to the debugging tools built into the web browser. Have your students open this code in the browser, launch the web development tools, and then click Sources or Debugger from the top menu depending on the browser they’re using. Figure 7-1 shows a screen similar to what they’ll see.

Three main panels are in this screenshot. The File Navigator ❶ is where every file used in the web page is listed. Clicking these files displays their contents in the Code Editor ❷. Clicking the line numbers in this panel will set breakpoints, places where we want the browser to pause code execution so we can review variable values or begin stepping through the code. The JavaScript Debugging panel ❸ is where the current program state and other tools for troubleshooting code reside.

When evaluating an algorithm, students click the line number at the function’s start and trigger the code execution by manually refreshing the page in the browser. The browser pauses processing the code at the breakpoint. Students should then begin stepping through the code using the navigation controls at the top of the Debugging panel. As they step through the code, they’ll see how the browser highlights each executed step in the algorithm and how the variables change values.

Figure 7-1 shows a set breakpoint at line five of the code. From there, the figure shows that the developer has stepped to line six. The mouse is hovering over the i variable, so we can see its value of 5 hovering above it. Alongside the reversedString variable is the value aibhop: six letters are now appended in reverse to the string at this iteration. The Debugging panel shows the variable values listed under Scope, a list of the breakpoints, and the call stack, which is the list of functions currently being called. In this case, the code is only calling one function. But as we dive into more complex code, following the stack and seeing what functions are calling other functions becomes more important.

Recursion

Once your students have had the chance to play with the Debugger and understand the loop strategy for reversing the string, you can introduce a more complex algorithm. The example in Listing 7-3 uses recursion, a technique where a function calls itself, which creates a loop similar to a while loop. Here the function first checks whether the ­stringToReverse input variable is empty; if not, the function returns every character after the first using the .substr(1) command and appends the first character in the string to the end via the .charAt(0) command.

function reverseString(stringToReverse) {
  if (stringToReverse === "") {
    return "";
  } else {
    return reverseString(stringToReverse.substr(1)) 
      + stringToReverse.charAt(0);
  }
}

Listing 7-3: Reversing a string using recursion

Although the concept of recursion is easy to define, your students might find it difficult to follow and understand this example, and they’re not alone. Many developers express difficulty following along with some recursive algorithms. To help them, direct your students to the call stack as they step through the function’s execution. Have them watch the list of function calls grow and eventually shrink with each iteration. Additionally, have them compare this function to a while loop because both controls iterate until a condition is met. It’s worth noting that a recursive function is not the same as a while loop, although there are some similarities.

Despite being a bit difficult to follow, recursion can be an ideal solution for certain tasks. For example, the minimax algorithm is a popular function used in making AI opponents for games like chess and tic-tac-toe. Minimax iterates and evaluates all possible moves to determine the best reply to each possible player move. Figure 7-2 shows how each point in a tic-tac-toe game can branch out into several possibilities.

Each branch potentially has more branches. Although navigating a one-dimensional array of characters only needs a single loop, navigating this data tree would require loops within loops. With 255,168 different possible games in tic-tac-toe alone, writing enough loops to explore them all would be unfeasible, which is why Figure 7-2 only illustrates a few branches. Recursion allows us to more easily explore complex data structures without needing to know all their dimensions.

Array Manipulation

A third way to reverse the string, as shown in Listing 7-4, uses array manipulation and array functions built into JavaScript. The .split("") function splits all the characters in the string into an array, which is then flipped using the .reverse() command, and then appended back together into a string again via .join(""). Although it’s one line of code, the array manipulation approach executes three steps we can see and many steps we can’t see because they’re abstracted behind the function calls.

function reverseString(stringToReverse) {
  return stringToReverse.split("").reverse().join("");
}

Listing 7-4: Reversing a string using array manipulation

After reviewing many ways to accomplish the same task, ask your students for their opinions on the different methods. What do they like and dislike about them? Ask them to justify their answers in terms of implementation, code readability, and performance to practice appraising code.

An important point to make is that there aren’t explicitly right and wrong answers. But in some cases, for instance when iterating over data in a tree structure, recursion will feel more natural, and a loop will feel bulkier. At times, the coder might break a chain of functions out of one line of code and into multiple lines to improve readability or will add extensive comments to a single code line to explain what’s going on to their peers and future selves. The point of this exercise isn’t to tell students what the best practices are, but to practice thinking about the different solutions and articulating why they might prefer one technique over another.

There are many other ways to extend the exercise to cover computer science standards beyond evaluating and comparing algorithms. For example, when covering the recursion example, you could challenge your students to rewrite it as a while loop as an exercise in modifying an existing algorithm. We’ve also covered computer science standards such as recursion as a control structure, tree structures for data and the minimax algorithm, and debugging tools as a means of reading algorithms step-by-step for deeper understanding.

In the function execution example provided, we used a palindrome for the input. Ask your students, using this input, whether we’re verifying that the functions are working correctly. How do we know the output string is really reversed? What argument should we use to properly test these functions? By doing so, we’re also introducing quality assurance and testing aspects to the exercise.

Once students are familiar with systematically stepping through and evaluating code, comparing algorithms, and learning about the different ways to accomplish the same task, we can introduce them to extending those algorithms. Next, we’ll introduce them to an engaging exercise that involves extending existing code iteratively and making it increasingly complex by design.

Enhancing Algorithms

In addition to evaluating and comparing algorithms, computer science standards also require students to refine or enhance them. We’ll use this exercise as an opportunity to bring some basic cybersecurity concepts into the mix. Here students will learn about a simple algorithm for encrypting messages, explore a code sample to execute this process, figure out how to crack the encryption, and determine how to make their original encryption harder to crack.

Huge advances in computing originated from wartime necessities. One computational arms race centered on cryptography, keeping communications secure against third parties reading them. The Caesar cipher, named for the fact that Julius Caesar used it in correspondence, is a very basic encryption algorithm. In it, each letter in a string is shifted a specific number of characters along the alphabet. For example, input “A” with a shift of one to output “B,” or input “A” with a shift of two to output “C.” Figure 7-3 shows a Federal Bureau of Investigations, Cryptanalysis and Racketeering Records Unit challenge coin featuring a cipher wheel in its design. In this example, the computational device is shifted three places so the input “TOP SECRET” would output “WRS VHFUHW.” The Confederate Army used ciphers like this during the Civil War.

The function in Listing 7-5 contains an algorithm that takes a string input, makes a shift, and outputs the string with each character transposed according to the defined shift. Provide this function to your students in your chosen development environment.

var caesarCipher = function(str, shift) {
  if (shift < 0) return caesarCipher(str, shift+26);
  var output = '';
  str = str.toUpperCase();
  for (var i = 0; i < str.length; i++) {
    var c = str[i];
    if (c.match(/[a-z]/i)) {
      var code = str.charCodeAt(i);
      var asciiA = 'A'.charCodeAt();
      c = String.fromCharCode(((code- asciiA+shift)%26)+asciiA);
    }
    output += c;
  }
  return output;
}

Listing 7-5: Caesar cipher function by Evan Hahn, released to the public domain

Students can test this function using the line of code in Listing 7-6 to see the output.

document.write(caesarCipher('Hello, Classmate', 11));

Listing 7-6: Executing the Caesar cipher

Have your students take some time to decompose this code. They should try out some of the bits and pieces in the browser console to understand the parts and search the web for some of the functions. Have them add comments to the code for practice in communicating with other developers and documenting code.

To keep the code compact and concise, the author has used a few somewhat advanced techniques. For example, the /[a-z]/i portion in the str.match() function is a regular expression, a powerful search pattern syntax. In this case, it checks for letters a through z. The .charCodeAt() function returns the Unicode value for the first letter in a string, so executing 'A'.charCodeAt() in the console will return “65.” Conversely, the String .fromCharCode() function converts a Unicode number identifier for a character into the character, so String.fromCharCode(65) will output “A.” Using these two functions, the author cleverly uses Unicode to shift the inputs.

With comments, this procedure might look something like Listing 7-7.

var caesarCipher = function(str, shift) {
  //Check for negative number shifts
  if (shift < 0) return caesarCipher(str, shift+26);
  var output = '';
  //Convert to uppercase to avoid checking lowercase unicodes
  str = str.toUpperCase();
  for (var i = 0; i < str.length; i++) {
    var c = str[i];
    //Check if its alphabetic
    if (c.match(/[a-z]/i)) {
      //Get the unicode value for it
      var code = str.charCodeAt(i);
      //Get the unicode value for A
      var asciiA = 'A'.charCodeAt();
      //Shift the unicode value and return the character
      c = String.fromCharCode(((code-asciiA+shift)%26)+asciiA);
    }
    output += c;
  }
  return output;
}

Listing 7-7: Caesar cipher function with explanatory comments

Now that students hopefully have a firm understanding of this procedure, ask them how they would, assuming the sender and receiver share the shift value, use this function to decode a message. How do we shift the encrypted message backward?

The answer is to make the shift negative, so 11 becomes −11, but your students shouldn’t expect their user decoders to know this. So let’s abstract away this finding into a function like the one in Listing 7-8. Then users can invoke the more intuitive caesarCipherDecode('SPWWZ NWLDDXLEP',11) to decode the message.

var caesarCipherDecode = function(str, shift) {
  return caesarCipher(str, (shift * -1));
}

Listing 7-8: Caesar cipher decode function

Cryptography in wartime and peacetime is a computational arms race. So next, have your students take the perspective of someone who wants to crack the cipher. Let’s say the code cracker has the encoded string but doesn’t know the shift to unlock it. What steps could they execute to find the shift value?

Because the alphabet has 26 letters, there are only 26 possible shifts if we include the zero shift. Cracking the code means taking an encoded string and methodically testing each of the possibilities. Once students have explained the algorithm for cracking the cipher, you can provide them with the code in Listing 7-9, which will execute it.

var caesarCipherCracker = function(str) {
  var output = "";
  for (var i = -25; i < 1; i++) {
    output += i + " " + caesarCipher(str, i) + "<br/>";
  }
  return output;
}

Listing 7-9: The caesarCipherCracker function

This code snippet is a brute force search, an algorithm that systematically tests every possibility. When your students execute the command in Listing 7-10, the function will output 26 rows of text showing the result of each shift value on the string input. When students find a row with a legible message, they’ve found the shift value.

document.write(caesarCipherCracker('MJQQT HQFXXRFYJ'));

Listing 7-10: Executing the caesarCipherCracker function

The cryptographic arms race continues. With our Caesar cipher cracked, we need to make our algorithm more complex. There are lots of ways to do this, and you’ll have fun seeing what algorithms your students come up with. Listing 7-11 shows an example that adds a rotate variable to the mix, so the shift variable changes for each character in the string.

var rotatingCaesarCipher = function(str, shift, rotate) {
  var output = "";
  for (var i = 0; i < str.length; i++) {
    shift += rotate;
    output += caesarCipher(str[i], shift);
  }
  return output;
}

Listing 7-11: Adding a rotating shift to the Caesar cipher

With a shift of 11 and a rotate of 3, the first character will shift 14, the second 17, the third 20, and so forth. With 26 possible shift values and 26 possible rotate values, a brute force cracker function would need to iterate over 625 possible combinations to find the two keys. In just one iteration, we’ve squared the number of steps in our algorithm as well as the processing power to execute our code. Thinking about code breaking efforts in World War II, we can see how so many innovations in computational techniques and advances in computing power emerged from this conflict. If we can exponentially increase the complexity of our encryption over a few coding lessons, think of how complex the art of cryptography has become over decades of iterations between those keeping data secure and those trying to access it.

Computer science standards involving documentation, algorithm analysis and enhancement, iterative development, and cryptography were all covered in this one extensive exercise. The small code snippets used in this section are just a launching point. Students can continue to extend this code, adding layers of complexity to make their messages more secure. We can also use game-based incentives as students figure out how to crack those messages. Now that your students have iteratively developed a relatively simple code example into a more complex version, we can introduce them to an even more complicated and engaging example.

Adding an Interface

The exercise in this section builds on the concepts covered in the previous two exercises and adds a user interface to the mix. The interface offers ideal opportunities to visualize code outputs. The interface also adds event-driven triggers behind graphical elements, such as buttons, where users click these abstractions to execute functions.

In this exercise, students work with a function that generates random mazes. There are many kinds of maze-generation algorithms to explore. Each produces distinct maze styles. In this example, we’ll use a randomized depth-first search algorithm. Listing 7-12 shows the steps for this algorithm.

1. Create a grid.
2. Start with the top-left cell.
3. Mark the current cell as visited.
4. Get a list of its orthogonal neighbors. 
5. Start with a random neighbor, for each neighbor:
  a. If that neighbor hasn't been visited:
    I. Remove the wall between this cell and the unvisited neighbor.
    II. Return to step 3.

Listing 7-12: Steps in a randomized depth-first search algorithm

The steps for this algorithm are simple to follow, but translating them into code can get very elaborate. The JavaScript code in Listing 7-13 is from the Rosetta Code website (https://rosettacode.org/wiki/Maze_generation), which offers GNU Free Documentation Licensed examples of various algorithms in as many different programming languages as possible. This is just one of many code snippets you can use in your lesson.

function maze(width,height) {
  var cells=height*width-1;
  if (cells<0) {alert("illegal maze dimensions");return;}
  //Horizontal walls.
  var horiz =[]; for (var j= 0; j<height+1; j++) horiz[j]= [],
  //Vertical walls.
    verti =[]; for (var j= 0; j<height+1; j++) verti[j]= [],
  //Start at the top-left cell.
    here = [0, 0],
    path = [here],
    unvisited = [];
  //Build an array of unvisited cells.
  for (var j = 0; j<height+2; j++) {
    unvisited[j] = [];
    for (var k= 0; k<width+1; k++)
      unvisited[j].push(
        j>0 && j<height+1 && k>0 && (j != here[0]+1 || k != here[1]+1)
      );
  }
  while (0<cells) {
    //Build an array of potential neighbors.
    var potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
        [here[0]-1, here[1]], [here[0],here[1]-1]];
    //Build an array of unvisited neighbors.
    var neighbors = [];
    for (var j = 0; j < 4; j++) {
      if (unvisited[potential[j][0]+1][potential[j][1]+1])
        neighbors.push(potential[j]);
    }
    if (neighbors.length) {
      cells = cells-1;
      //Get the next random neighbors.
      next= neighbors[Math.floor(Math.random()*neighbors.length)];
      unvisited[next[0]+1][next[1]+1] = false;
      //If neighboring horizontally
      if (next[0] == here[0])
        horiz[next[0]][(next[1]+here[1]-1)/2] = true;
      else //Vertically
        verti[(next[0]+here[0]-1)/2][next[1]] = true;
      path.push(here = next);
    } else {
      //Pull the last element in the path.
      here = path.pop();
    }
  }
  return {height: height, width: width, horiz: horiz, verti: verti};
}

Listing 7-13: The depth-first search algorithm JavaScript example from Rosetta Code

Depending on your students’ knowledge, you could have them read and document this code snippet to explain how it executes the depth-first search algorithm. Your students should take a moment to realize that this algorithm doesn’t draw the maze. It only returns the x, y dimensions of the maze and two arrays of horizontal and vertical Boolean values, so every true value in the array is where a wall is removed. The maze(x,y) function is UI independent. It will take another function to loop through the horizontal and vertical arrays, and to draw the lines as needed. As a result, you can reuse the code from the maze(x,y) function if you decide to switch out your UI. By separating the functions’ responsibilities so changes to one don’t impact the other, the code is modular and decoupled. Listing 7-14 provides an example of taking the output of the maze(x,y) function and drawing it using characters.

function display(m) {
  var text= [];
  for (var j= 0; j<m.height*2+1; j++) {
    var line= [];
    if (0 == j%2)
      for (var k=0; k<m.width*4+1; k++)
        if (0 == k%4) 
          line[k]= '+';
        else
          if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
            line[k]= ' ';
          else
            line[k]= '-';
    else
      for (var k=0; k<m.width*4+1; k++)
        if (0 == k%4)
          if (k>0 && m.horiz[(j-1)/2][k/4-1])
            line[k]= ' ';
          else
            line[k]= '|';
        else
          line[k]= ' ';
    if (0 == j) line[1]= line[2]= line[3]= ' ';
    if (m.height*2-1 == j) line[4*m.width]= ' ';
    text.push(line.join('')+'
');
  }
  return text.join('');	
}

Listing 7-14: Function that converts the output of the maze() function into text

Students can then execute this code using the HTML <pre> tag in Listing 7-15 and the JavaScript following it. The <pre> tag is for “preformatted text” and tells the browser to render everything between the opening and closing tags exactly as it’s typed with all spaces included.

<pre id="out"></pre>
<script>
document.getElementById('out').innerHTML= display(maze(10,10)); 
</script>

Listing 7-15: Executing the display() function to output in the web page body

Figure 7-4 shows sample output for this code. For the first line, the horizontal array values are [true, true, true, true, true, true, true, empty, true] and the vertical array values are [empty, empty, empty, empty, true, empty, true, true, true, true,].

This example uses pipes, plus signs, and minus signs to draw the maze in text. But it could just as well be drawn in the HTML <canvas> element, which allows for drawing images into an area of the browser window. Figure 7-5 shows a maze generated on an HTML canvas. The modularity of the maze-generating and maze-rendering functions allows for easily swapping out how we render the maze visually.

The example maze generator in Listing 7-13 has the entire algorithm wrapped in one function, but other examples you find might break it up further. Perhaps using functions named getNeighbors(), removeWall(), and getRandomCell() to further decompose rendering the maze into many smaller problems. A powerful advantage to breaking up the algorithm this way is that it provides students with the ability to call each step in the maze-generating process individually and render the creation of the maze at each step in the process. Doing so animates the creation of the maze, and they can see the algorithm in action.

As the educator, you should provide the code for students to play with and learn from. That includes the maze-generation algorithm, the maze-rendering algorithm in text, an algorithm rendering the maze on an HTML canvas, and the many functions to animate rendering the maze. Your students won’t need to write any code from scratch, just as you won’t; you’ll build code from the endless code samples other developers around the world provide online for everyone to learn from.

You will provide this scaffolding code for the next iteration in the exercise, adding an avatar to the maze so students can navigate it in real time. Providing students with a set of functions like right(), left(), up(), and down() will challenge them to find the right combination of function calls to reach the exit. Once students write the functions to navigate the maze, they could add buttons to the interface, like those in Figure 7-6. Then they would attach the navigation functions to these buttons using the JavaScript onclick() event handler, which triggers an assigned function when the user clicks the object with their mouse or touchpad.

Just as the maze(x,y) function abstracts away the algorithm for generating a random maze, these buttons abstract away having to know the names of the left(), right(), up(), and down() functions to simple mouse clicks.

As students iteratively add functionality and interactivity to their mazes, they begin to make this microworld their own. They could add animation and sound effects to the interface for when the user bumps into a wall or reaches the goal. They could add an animated GIF image representing the player’s avatar. On a more advanced level, students could write the process mentioned in “Algorithms” on page 64 to solve the maze automatically. Once they know how to automate solving the maze, they can use that knowledge to add an AI enemy to chase the player through the maze.

The options for extending this example are endless for you as the educator as well. Having students show off and share the code they use to enhance their projects allows them to document, communicate, and collaborate on extending the base application. Asking students for features to make their mazes more accessible to the visually impaired can further challenge them.

Summary

The three exercises we covered in this chapter involve you, the educator, providing code for students to understand, experiment with, and extend. In the first exercise, you provide students with as many examples as possible to show different ways to solve the same problem. Students compare, contrast, and form opinions on each of these methods and learn to articulate which they prefer and justify their preferences.

In our second exercise, you give students a simple encryption function. From this starting point, they alternate between figuring out how to crack the encryption and iteratively enhance the function to make it harder to crack. Cryptography and computational complexity are additional concepts tangential to this lesson.

Our third exercise includes understanding an existing function and adds a user interface where students can see the output of this function. From this starter code, students experiment with animating their algorithm’s maze output, adding a player to navigate the maze, and abstracting away the navigation function names behind clickable arrows. From here, students can follow their passions, adding functionality, collaborating with peers on their innovations, and making the code their own.

Much of software development involves asking the right questions and finding the right existing solutions rather than writing new code from scratch. When students feel comfortable working with other people’s code, they have the power to assemble applications from prewritten functions. Having students practice working with existing code gives them a foundation for launching their own projects.

In the next chapter, we’ll learn about projects that can benefit your school while students learn to work independently.