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. Myös suomenkielisessä materiaalissa käytetään ohjelmaprojektien koodissa englanninkielisiä nimiä kurssin alkupään johdantoesimerkkejä lukuunottamatta.

Voit vaihtaa kieltä A+:n valikon yläreunassa olevasta painikkeesta. Tai tästä: Vaihda suomeksi.

Chapter 5.4: Loops, Strings, and Elections

About This Page

Questions Answered: Could I have some more examples of for loops? What if I put a loop within a loop? How about having multiple obstacles in FlappyBug?

Topics: Practice on the previous chapter’s topics. Additional topics: looping over strings and Ranges; nested for loops.

What Will I Do? Write programs, for the most part.

Rough Estimate of Workload:? Four hours.

Points Available: A225.

Related Projects: ForLoops, Election (new), FlappyBug.

Introduction

So far, we’ve used for loops for processing only buffers and vectors. However, as briefly mentioned in Chapter 5.3, 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") {
  println("Letter: " + character)
}

A string is a collection of characters — values of type Char (Chapter 4.5) — 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") {
  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 project.

Tiny programming task: upper case only

Find the app object o1.looptest.Task2 in the ForLoops project. 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 by 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 on 37.5%, since three of the eight bases is either guanine or cytosine. GC content is a meaningful concept in molecular biology.

Fetch Task3. 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 project 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) {
    if (base == 'G' || base == 'C') {
      gcCount += 1
    } else if (base == 'A' || base == 'T') {
      totalCount += 1
    }
  }
  100.0 * gcCount / totalCount
}

Char objects have their own literal notation, just like numbers, Booleans, and Strings do. Notice that 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 4.5 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) {
  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) {
  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) {
  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 project contains some more app objects for you to edit: Task4.scala, Task5.scala, Task6.scala, Task7.scala. (You can save Task8 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.

A+ presents the exercise submission form here.

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 convenient 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) {
  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

Assignment: Election

Task description

• Fetch the project Election,
• 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.3. 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 app object ElectionTest. It calls several methods in class District. Feel free to edit the app object as you see fit so that it covers more test cases.
  • You can’t run ElectionTest 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 ElectionTest 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 3.6.)
• We recommend that you tackle the assignment in the following order:

Recommended steps

1. Read the documentation. Notice that some of the methods in class District will be implemented in a much later assignment (in Chapter 9.2). Focus on the rest of the methods, which are relevant now.
2. Study the given Scala code.
3. Start working on District as follows. Use ElectionTest repeatedly to test your solution as you go.
4. Implement toString.
5. Implement printCandidates.
   • For inspiration, look at nextDay in AuctionHouse.
6. Implement candidatesFrom.
   • For inspiration, look at purchasesOf in AuctionHouse.
   • Note that the return type is Vector[Candidate]. You can use a buffer to collect the right candidates, but you need to then use toVector to produce a vector.
7. Implement topCandidate.
   • For inspiration, look at priciest in AuctionHouse.
   • Can you use the vector’s head and tail methods so that the topCandidate doesn’t needlessly compare the first element with itself? (This is not required.)
8. Implement the totalVotes methods.
   • For inspiration, look at totalPrice and numberOfOpenItems in AuctionHouse.

This is voluntary but highly recommended:

Did you get the two totalVotes methods working? Excellent! But are they very similar to each other? Do they have multiple identical lines of code?

Duplicate code isn’t pretty. It can also make it harder to modify a program and invites bugs.

A good way to reduce duplication is to create an auxiliary method that takes care of what the other methods have in common. Here, the common part is taking a vector of candidates and summing up those candidates’ votes; the totalVotes methods both need to do that, and differ from each other only in which candidates are included.

Here’s an outline for the auxiliary method:

private def countVotes(candidates: Vector[Candidate]) = {
  // Sum the votes in the given vector and return the result.
}

Since the method is meant for District’s internal use, it makes sense that it’s private.

Can you define countVotes and implement the two totalVotes methods so that they call countVotes and pass in the appropriate vector as a parameter?

A repeating pattern

A pattern repeats across the methods of class AuctionHouse and presumably also many of the methods you wrote in class District:

1. We initialize a variable that we’ll use to accumulate the method’s return value.
2. We then loop over a collection and perform an operation on each element: for (element <- collection) { ... }
3. Finally, we return the value of the result variable, which our loop has updated.

Since many of our methods follow this pattern, their code looks rather similar. Some of the methods contain identical lines of code.

This is a kind of duplication, too, isn’t it? Could we avoid it?

Yes. By the time we get to Chapter 6.3, you’ll have learned how to do that very elegantly.

Submission form

A+ presents the exercise submission form here.

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

Task description

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.

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.
   • Hint: Use a for loop. A simple one 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.
   • Hint: This step is a bit more complicated. 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.

Submission form

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 6.3 and 7.1 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) {
  if (word.length < 9) {
    var counter = 0
    for (letter <- word) {
      if (counter % 2 == 0) {
        result += letter
      }
      counter += 1
    }
  }
}
println(result)

Question 1

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

Question 2

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

Question 3

What is the largest value that counter reaches?

Question 4

What string of letters does the last line print out?

A mini-assignment on nested loops

Return to o1.looptest and do Task8.scala.

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 work that out 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) {
      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
  }
}

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.1).

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) {
      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
  }
}

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) {
    println("Hi")
    val myVal = 10
    outer += middle * 2 + myVal
    if (middle < outer + myParam) {
       val inner = readLine("Enter a number: ").toInt
       outer += inner + myVal
    }
  }
  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 a for loop or a branch of an if. Blocks can be nested in other blocks; in well-written code, indentation highlights the program’s blocks.

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.4.

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

  def sellBottle() = {
    if (this.isSoldOut || !this.enoughMoneyInserted) {
      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 variable 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.

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.

Time spent: (*) Required

Please estimate the total number of minutes you spent on this chapter (reading, assignments, etc.). You don’t have to be exact, but if you can produce an estimate to within 15 minutes or half an hour, that would be great.

Which one is the best match?

I feel like I know how to format my Scala code properly (indentations etc.).

I don’t feel like I know how to format my Scala code properly.

I’m not sure. / No comment.

Which one is the best match?

I’m usually quite lost when I have to read and understand given example code.

I’m often unsure about the runtime behavior of given example code.

I feel that I mostly know how to predict the runtime behavior of given example code.

I’m very confident in my understanding of given example code.

I’m not sure. / No comment.

Written comment or question:

You aren’t required to give written feedback. Nevertheless, please do ask something, give feedback, or reflect on your learning! (However, the right place to ask urgent questions about programs that you’re currently working on isn’t this form but Piazza or the lab sessions. We can’t guarantee that anyone will even see anything you type here before the weekly deadline.)

Credits

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

Weeks 1 to 13 of the ebook, including the assignments and weekly bulletins, have been written in Finnish and translated into English by Juha Sorva.

Weeks 14 to 20 are by Otto Seppälä. That part of the ebook isn’t available during the fall term, but we’ll publish it when it’s time.

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 programmed by Riku Autio, Jaakko Kantojärvi, Teemu Lehtinen, Timi Seppälä, Teemu Sirkiä, 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 have done 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 and Juha Sorva. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using tools from O1Library (such as Pic) for simple graphical programming 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+ has been created by Aalto’s LeTech research group and is largely developed by students. The current lead developer is Jaakko Kantojärvi; many other students of computer science and information networks are also active on the project.

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

Additional credits appear at the ends of some chapters.

Posting submission...

×

Identical submission

This submission is identical to the previous submission . Are you sure you want to submit it?

Cancel Submit