1. CS-A1110
  2. Week 5
  3. Chapter 5.6: Loops, Strings, and Elections

Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.

Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit.

Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.


Chapter 5.6: Loops, Strings, and Elections

../_images/person03.png

Introduction

So far, we’ve used for loops for processing only buffers and vectors. However, as briefly mentioned in Chapter 5.5, you can loop over many sorts of things. Like strings:

A String in a Loop

For example’s sake, let’s say we want to print out a report that enumerates each character within a string. For example, if the string is "llama", we want to print this:

Letter: l
Letter: l
Letter: a
Letter: m
Letter: a

Here is some Scala code that does just that:

for character <- "llama" do
  println("Letter: " + character)

A string is a collection of characters — values of type Char (Chapter 5.2) — and you can use it in a for loop as shown.

The variable character therefore has the type Char.

The loop body executes as many times as there are characters in the string. The loop iterates over the characters in order, starting with the first one.

What if we want to number the outputs? And to report the Unicode values of each character? Like this:

Index 0 stores l, which is character #108 in Unicode.
Index 1 stores l, which is character #108 in Unicode.
Index 2 stores a, which is character #97 in Unicode.
Index 3 stores m, which is character #109 in Unicode.
Index 4 stores a, which is character #97 in Unicode.

Here’s an implementation:

var index = 0
for character <- "llama" do
  println("Index " + index + " stores " + character + ", which is character #" + character.toInt + " in Unicode.")
  index += 1

A stepper variable tracks the current index. We increment the stepper after each execution of the print command.

The Char class gives us toInt, a method that returns the character’s Unicode number.

The above program, like many others in this chapter, is available in package o1.looptest within the ForLoops module.

Use the debugger to explore

A debugger is an auxiliary program that helps the programmer examine what goes on as a program executes. IntelliJ, for instance, comes with a built-in debugger.

This ebook has a separate page that introduces the basics of debugger use. We recommend that you take a look at it before you continue. You can then use the debugger to step through the programs in this chapter line by line. This can help you understand the examples and provides practice with the debugger.

You may also find the debugger useful as you try to find defects in your own code.

Tiny programming task: upper case only

Find task2.scala in the ForLoops module. Read the comments to find out what the program is supposed to do. Write the program as requested.

A+ presents the exercise submission form here.

A wordier but short task: DNA properties

The DNA of our bodies contains four important (nucleo)bases: guanine (G), adenine (A), cytosine (C), and thymine (T). We can describe a strand of DNA by listing its bases in order, as in GATCACAGGT. Each organism has its specific DNA, but the differences between individual organisms are minor, and even the DNA from organisms of different species can be highly similar.

Certain properties of DNA can be captured by computing its GC content: the percentage of guanine and cytosine within it. For instance, the DNA slice ATGGACAT has a GC content of 37.5%, since three of the eight bases is either guanine or cytosine. GC content is a meaningful concept in molecular biology.

Open task3.scala. You can try running the program. Here is what it looks like in the text console:

Enter a species file name (without .mtdna extension): human
The GC content is 80.13914555929992%.

Given a species name by the user, the program appears to compute the GC content of that species’s DNA. The program accepts the inputs human, chicken, chimpanzee, mouse, opossum, pufferfish, yeast, and test; the names correspond to files that come with the program and store DNA sequences from assorted species. (More specifically, they are mitochondrial DNA or mtDNA sequences.)

The program doesn’t actually work, however. For a human, the output should be roughly 44%, not 80%.

The function gcContent in task3.scala is incorrect. Your task is to study the function (replicated below) and make a small change so that the program works as intended.

The function should return the GC content of the given string as a Double; for example, given the string "ATGGACAT", it should return 37.5. In this toy program, we’ll simply ignore any characters other than the four that stand for the nucleobases, so the input "ATG G ACATXXYZYZ" should also produce 37.5.

def gcContent(dna: String) =
  var gcCount = 0
  var totalCount = 0
  for base <- dna do
    if base == 'G' || base == 'C' then
      gcCount += 1
    else if base == 'A' || base == 'T' then
      totalCount += 1
  end for
  100.0 * gcCount / totalCount

Char objects have their own literal notation, just like numbers, Booleans, and Strings do. Unlike a String literal, a Char literal goes in single quotation marks.

If you want to try the program on a DNA sequence of your own choosing, you can edit test.mtdna in the folder mkDNA_examples and enter test when the program prompts you for a species file.

A+ presents the exercise submission form here.

Looping over a Range of Numbers: to, until, and indices

Chapter 5.2 mentioned that Int objects have a method named to, which we usually call using operator notation. The method returns a reference to a Range:

5 to 15res0: Range.Inclusive = Range 5 to 15

A Range object represents a sequence of numbers. We can use a for loop to iterate over that sequence:

val upToAThousand = 1 to 1000
for number <- upToAThousand do
  println(number)

The loop variable number serves as a stepper that receives each positive integer in turn: 1, 2, 3, ..., 1000. The program prints out these numbers in order.

Here is a shorter way to express the same thing:

for number <- 1 to 1000 do
  println(number)

A similar command works for covering the indices of a collection such as a String. This program produces a familiar output:

val myString = "llama"
for index <- 0 to myString.length - 1 do
  val character = myString(index)
  println("Index " + index + " stores " + character + ", which is character #" + character.toInt + " in Unicode.")

Indices run from zero upwards, so if you use to, you need to subtract one from the myString.length so that you don’t go past the last element.

Practice tasks: to, until, etc.

The ForLoops module contains some more mini-programs for you to edit: task4.scala, task5.scala, task6.scala. (You can save task7 for later.)

Edit each file so that it meets the requirements set out in the comments. You can work on each file separately; the programs don’t depend on each other.

Test your programs before you submit them for grading.

Remember that you can use the debugger to help you spot errors.

A+ presents the exercise submission form here.

A+ presents the exercise submission form here.

A+ presents the exercise submission form here.

Convenient indices

The indices method is a handy alternative to until and to when you want to loop over the indices of a string or some other collection.

val myString = "llama"myString: String = llama
for index <- myString.indices do
  println("Index " + index + " stores " + myString(index))Index 0 stores l
Index 1 stores l
Index 2 stores a
Index 3 stores m
Index 4 stores a

That works because indices returns exactly the sort of Range object that we could have created with until.

myString.indicesres1: Range = Range 0 until 5

Modifying each element of a mutable collection

In Chapter 5.5, we had a flawed function that was supposed to increment each element of a buffer by one, but didn’t. Here’s an implement that works, courtesy of indices:

def incrementEach(numbers: Buffer[Int]) =
  for index <- numbers.indices do
    numbers(index) = numbers(index) + 1

We loop over the indices of our mutable collection.

For each index, we assign a new number.

The shorter numbers(index) += 1 also works.

And you may certainly construct the collection of indices differently if you prefer. For example, until works.

Assignment: Election

Task description

../_images/module_election.png

The Election program has a pretty simple structure.

  • Fetch the Election module,

  • Read its Scaladocs. Also read the given code of class Candidate, which represents electoral candidates.

  • Implement class District, which represents electoral districts.

  • Test your implementation (obviously).

General instructions and hints

  • District resembles AuctionHouse from Chapter 5.5. Use what you learned in that chapter.

    • You can use a for loop in many of the methods.

    • Look at AuctionHouse for inspiration.

  • Use the main function testElection. It calls several methods in class District. Feel free to edit the function as you see fit so that it covers more test cases.

    • You can’t run testElection as given before you have some sort of implementation for each of the requested methods in District.

    • What you can do is “comment out” parts of testElection and test the parts of District that you already wrote. Another option is to write a quick “dummy implementation” for the missing methods (e.g., by using ??? as in Chapter 4.1.)

  • We recommend that you tackle the assignment in the following order:

Mini-Assignment: Constructing an Image in a Loop

Here’s some code for you to study or run in the REPL:

val colors = Vector(White, Blue, Green, Black, Orange)
var combo = rectangle(150, 150, Red)
for color <- colors do
  val stripe = rectangle(50, 150, color)
  combo.leftOf(stripe)
combo.show()

Which of the following options correctly describe this program? (Select all that apply.)

Assignment: FlappyBug (Part 16 of 17: More Obstacles)

So far, FlappyBug has had just a single obstacle. Edit the game so that there are multiple obstacles. The obstacles will be represented by separate instances of class Obstacle and stored in a Vector. Each obstacle behaves the same way as the others, but they have different sizes and locations. Use for loops to implement the changes.

Here’s what you need to do:

  1. Add the obstacles to the game: Remove the variable obstacle of class Game and the single 70-pixel obstacle it refers to. Replace them with a variable named obstacles that refers to a vector with three obstacles. The first obstacle should have a radius of 70 pixels, the second one a radius of 30 pixels, and the last one a radius of 20 pixels.

  2. Make each obstacle move: edit the timePasses method in class Game so that it advances each of the obstacles stored in the vector.

    • A simple for loop will do.

  3. Update the game-over condition: Edit the isLost method in class Game so that it returns true if the bug is out of bounds or if any of the obstacles in the vector touches the bug.

    • This step is a bit more complicated. You may want to take a look at the optional hint below.

    Hint

    One solution is to use a var of type Boolean to track whether your loop has already found an obstacle that touches the bug. Make the variable a local variable; define it within the method but before the loop.

  4. Make the obstacles visible: edit the makePic method in the GUI so that all the obstacles get placed against the background image. The bug image should be added last, as before.

    Hint

    You can use a gatherer of type Pic in combination with for: as you loop through the vector, update the gatherer by placing a picture of the current obstacle against the previous value of the gatherer. (Cf. the previous mini-assignment.)

A+ presents the exercise submission form here.

New role: the (one-way) flag

The hint for isLost suggested that you use a Boolean variable in a particular way. This is an example of a common way to use a variable — a role — that we haven’t discussed before.

In programmers’ parlance, a flag (lippu) is a data item that is used to indicate whether a particular situation has occurred: figuratively, we “raise the flag” to indicate that it has.

In isLost, the flag variable is “raised” (i.e., gets the value true) when or if it turns out that an obstacle is being touched. To be more precise, the variable is a one-way flag (yksisuuntainen lippu): after its value changes once, it never changes back.

A flag has only two different states, which is why flags are often Boolean variables.

Worried about efficiency?

As soon as isLost works out that there is even a single obstacle that touches the bug, it knows that it needs to return true. Once that’s established, the method wouldn’t actually need to look at any of the other obstacles. However, if you implement the method as we suggested, it always checks every obstacle in the vector.

Given that the game has just three obstacles, any computer can check all of them in the barest of instants. But what if we were operating on a vast collection of data and needed to check whether it contains at least one element that matches a specific condition? Ideally, we’d like the computer to stop checking as soon as it knows the result.

There are ways to do that. We’ll return to the matter in Chapters 7.1 and 7.2 at which point we’ll have a heftier toolkit.

Nested Loops

You can put a loop inside another. What happens is that the entire inner loop gets executed each time the outer loop’s body runs.

In the example above, the inner loop (with two cycles) runs multiple times whereas the outer loop (with three) runs only once. The innermost println is executed six times in total.

Loop-reading practice

Consider the toy program below. As the program runs, what values does each variable hold at each step? Which string is eventually stored in result?

val words = Vector("function", "method", "subprogram", "procedure", "routine")
var result = ""
for word <- words do
  if word.length < 9 then
    var counter = 0
    for letter <- word do
      if counter % 2 == 0 then
        result += letter
      end if
      counter += 1
    end for
  end if
end for
println(result)

How many times (in total) is counter initialized to zero?

How many times (in total) does the program check whether counter stores an even number?

What is the largest value that counter reaches?

What string of letters does the last line print out?

A mini-assignment on nested loops

Return to o1.looptest and do task7.scala.

Again: remember to test your solution and use the debugger as needed.

A+ presents the exercise submission form here.

Scopes

By now, you have seen many examples of nested code structures, but we haven’t properly discussed how nesting impacts on variable definitions and the like.

Each program component — variable, method, class, and singleton object — has a scope (käyttöalue; skooppi) within the program: the component can be accessed only from certain parts of the program code. This scope depends on the context where the component is defined; you can further adjust it with access modifiers such as private.

An attempt to use a variable or method outside its scope results in a compile-time error.

Let’s look at the scope of class members first, then consider local variables.

Class members and scope

The code of a ChristmasTree class is given below. You don’t have to understand how the class works (even though it is possible to do that, given what we have covered in O1). This class is here merely as an example of nesting and scopes, and we’ll go through the code only superficially, from that perspective.

class ChristmasTree(treeHeight: Int):
  val height = treeHeight.min(1000)
  private val widestPoint = this.width(this.height - 1)

  override def toString =
    var pic = this.line('*', 1)
    for lineNbr <- 1 until this.height do
      pic += this.line('^', this.width(lineNbr))
    pic += this.line('|', (this.widestPoint - 4).min(3).max(1))
    pic

  private def width(line: Int) = line / 2 * 2 + 1

  private def line(character: Char, howMany: Int) =
    val spaceAtLeft = (this.widestPoint - howMany) / 2
    val wholeLine = " " * spaceAtLeft + character.toString * howMany + "\n"
    wholeLine

end ChristmasTree

The scope of a public instance variable such as height encompasses the entire class. Moreover, the variable is accessible from outside the class, too, as long as we have an instance of the class available: myObject.height. Similarly, we can call a public method such as toString anywhere within the class or outside of it. Instance variables and methods are public unless otherwise specified.

The scope of a private instance variable, such as widestPoint, or a private method, such as width or line, is limited to the enclosing class (and any companion object the class may have; Chapter 5.3).

The class itself is public, so we’re free to use it anywhere in the program. (It’s possible to define private classes, too, but we won’t be doing that in O1.)

Local variables and scope

class ChristmasTree(treeHeight: Int):
  val height = treeHeight.min(1000)
  private val widestPoint = this.width(this.height - 1)

  override def toString =
    var pic = this.line('*', 1)
    for lineNbr <- 1 until this.height do
      pic += this.line('^', this.width(lineNbr))
    pic += this.line('|', (this.widestPoint - 4).min(3).max(1))
    pic

  private def width(line: Int) = line / 2 * 2 + 1

  private def line(character: Char, howMany: Int) =
    val spaceAtLeft = (this.widestPoint - howMany) / 2
    val wholeLine = " " * spaceAtLeft + character.toString * howMany + "\n"
    wholeLine

end ChristmasTree

Method implementations are always inaccessible from outside the method.

Mouse over the boxes below to highlight the corresponding scope within the program.

A parameter variable such as character or howMany is defined within the entire method. You can use it anywhere within the method.

A variable defined at the outermost “level” within the method, such as spaceAtLeft, can be used anywhere between its definition and the end of the method.

The same goes for wholeLine.

If a command contains a variable definition, the variable is available only within that command. The variable lineNbr, for example, is defined only within the for loop.

Another example

This method further highlights the scopes of local variables (but is otherwise meaningless):

def myMethod(myParam: Int) =
  println("Hello")
  var outer = myParam * 2
  val myVal = 1
  for middle <- 1 to 3 do
    println("Hi")
    val myVal = 10
    outer += middle * 2 + myVal
    if middle < outer + myParam then
       val inner = readLine("Enter a number: ").toInt
       outer += inner + myVal
    end if
  end for
  outer + myVal

The scope of myParam is the entire method.

The scope of outer is the rest of the method from the variable definition onwards.

middle is available only within the loop.

inner is available only within the if.

What about myVal? There are two of them, which is legal in nested structures:

The scope of the inner myVal runs from the variable definition to the end of the loop.

The outer myVal would be available to the rest of the method. However: the inner myVal shadows the outer variable of the same name and effectively prevents it from being used within the loop. Therefore...

... some of the myVals refer to the inner variable...

... while one refers to the outer definition.

The example illustrates a general principle: a local variable’s scope is limited to the innermost block (lohko) within which the variable definition appears. Informally, we can define a block as a section of program code that contains a sequence of commands, such as the body of a for loop or a branch of an if. Blocks can be nested in other blocks; indentation highlights the blocks of a program.

Choosing a scope for a variable

A rule of thumb: Choose the narrowest scope that works.

Unless you have a good reason to make your variable an instance variable, make it a local variable instead. Define that local variable in the innermost block that works.

By keeping scopes narrow, you make your code easier to read and modify. If a variable has a narrow scope, it’s easier to tell which parts of code depend on it, and you’re less likely to introduce unnecessary dependencies between parts of your program. In some cases, narrow scoping can reduce memory usage or even speed up the program somewhat.

Beginner programmers commonly overuse instance variables where local variables would do. For that reason, here’s one more example of scopes: the VendingMachine class from Chapter 3.5.

class VendingMachine(var bottlePrice: Int, private var bottleCount: Int):
  private var earnedCash = 0
  private var insertedCash = 0

  def sellBottle() =
    if this.isSoldOut || !this.enoughMoneyInserted then
      None
    else
      this.earnedCash = this.earnedCash + this.bottlePrice
      this.bottleCount = this.bottleCount - 1
      val changeGiven = this.insertedCash - this.bottlePrice
      this.insertedCash = 0
      Some(changeGiven)

  def addBottles(newBottles: Int) =
    this.bottleCount = this.bottleCount + newBottles

The amount of money stored is part of the machine’s state, a property of the VendingMachine object. This value should be stored even while none of the machine’s methods is running. Therefore, it makes sense to define earnedCash as an instance variable. The same goes for this class’s other instance variables.

sellBottle temporarily needs a variable for storing the amount of change. This is an intermediate result associated with a single invocation of the method; it’s not a persistent part the machine’s state nor is it needed by any of the other methods. It therefore makes sense to use a local variable.

Each method parameter is meaningful only to that particular method.

To summarize: prefer local variables to instance variables unless one of the following applies.

  • The variable obviously represents information that defines an object (e.g., the name of a person; the courses a student is enrolled in).

  • The variable stores data that needs to be stored even while none of the object’s methods is running. Or:

  • There is some other justification for the instance variable, such as a specific trick to optimize efficiency. (We won’t go into that in O1.)

Summary of Key Points

  • Vectors and buffers aren’t the only thing you can loop through. You can use for on strings and ranges of numbers, for instance.

  • You can nest a loop within another. If you do, the entire inner loop can be executed multiple times as part of the outer loop’s body.

  • Each variable and method has a scope: it’s accessible from some parts of the program only.

    • It’s usually unwise to make the scope of a variable or method wider than necessary.

    • The block structure of a method impacts on the scope of local variables.

  • Links to the glossary: loop, for loop, iteration; collection, string; scope, block; one-way flag; debugger.

Feedback

Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.

Credits

Thousands of students have given feedback and so contributed to this ebook’s design. Thank you!

The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.

The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.

The automatic assessment of the assignments has been developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Onni Komulainen, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Joel Toppinen, Anna Valldeoriola Cardó, and Aleksi Vartiainen.

The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.

The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio did the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.

The other diagrams and interactive presentations in the ebook are by Juha Sorva.

The O1Library software has been developed by Aleksi Lukkarinen, Juha Sorva, and Jaakko Nakaza. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using O1Library for simple graphical programming (such as Pic) is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and Krishnamurthi and Picturing Programs by Stephen Bloch.

The course platform A+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services; dozens of Aalto students and others have also contributed.

The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.

For O1’s current teaching staff, please see Chapter 1.1.

Additional credits appear at the ends of some chapters.

a drop of ink
Posting submission...