Chapter 8

Loops

We saw in chapter 6 how we could use recursion to produce an iterative behavior where something was done multiple times. We also saw in chapter 7 that we can use collections to make certain operations happen multiple times. These approaches are the primary methods used in functional languages and they often work well to provide the functionality we need in Scala. Most languages, including Scala, provide other constructs called loops that are designed specifically for creating this iterative behavior. In this chapter we will explore the loop structures present in Scala and see how we can use these in our programs. We will start by repeating some of the things that we did previously using recursion.

8.1 while Loop

The most basic looping construct in Scala and many other languages is the while loop. The name tells you roughly what it does. You should keep repeating something while some condition is true. The syntax of the while loop is as follows.

while(condition) statement

The condition can be any expression that evaluates to a Boolean type. The statement is very commonly a block of code, so you will typically see the while followed by curly braces.

To see an example of this, let us use a while loop in a function that builds a List of numbers input by the user. The List will end when the user enters “quit”. This is exactly like the example that we did with recursion. We could not do it with the collections because we did not know in advance how many numbers there would be.

def readInts:List[Int] = {

 var input=readLine()

 while(input!="quit") {

 lst=input.toInt :: lst

 input=readLine()

 }

 lst

}

This code is distinctly imperative. We have to declare two variables with var to make it work. In fact, the while loop and it’s partner, the do-while loop that we will discuss in the next section, are only usable as statements. They are not expressions and can not be used in places that need to have a value. The fact that the while loop has to be used in an imperative way is somewhat implicit in the way it works. For the code inside of the while loop to execute, the condition must be true originally. In order for the loop to finish, the value of the condition has to change to false. This change requires the mutation of data at some point so it is impossible to use the while loop in a completely functional way.

Another thing to note about the while loop is that it is a pre-check loop. This means that the condition is checked before the body of the loop is executed. As a result, it is possible that the contents of the loop will never execute. If the condition is false when the loop is first reached, the body of the loop will never execute.

Let us look at another example of the while loop. One of our first examples of using recursion to get iteration was the factorial. We can re-write factorial using a while loop in the following way.

def factorial(n:Int):Int = {

 var product=1

 var i=1

 while(i<=n) {

 product*=i

 i+=1

 }

 product

}

We declare two variables named product and i at the beginning and initialize both to the value of 1. The condition on the while loop causes it to iterate as long as i is less than or equal to n. Inside the loop, the value product is multiplied by i and i is incremented by one.

The *= and += operators are examples of assignment operators. They provide a handy shorthand for when you want to apply a mathematical operation to a value and store the result back in the original variable. You can follow any operator by an equal sign and Scala will see it as a compound operation that performs the specified operator and stores the value back. The storing of the value is a mutation operation. As such, these operators have to be used with mutable data. That either requires var declarations, or mutable constructs such as Arrays.

This function also shows another element that is common to most while loops and which can lead to a common form of bugs. The line i+=1 is what we often call the iterator of the loop. It is what moves us from one case to the next in the loop. The common bug is to accidentally leave out the iterator. Consider what happens in this code if you do that. Without the line i+=1, the value of i will never change. As a result, the condition will never change either and if it is true to begin with, it will be true forever. This leads to what we call an infinite loop, a loop that never exits. This type of error is easy to put into the code with a while loop, because the loop does not include anything in its structure to remind you to include the iterator.

8.2 do-while Loop

Scala provides a second construct that is very closely related to the while loop. It is the do-while loop. The syntax for the do-while loop is as follows.

do {

 statements

} while(condition)

The curly braces are not technically required here either, but it is rare to see a do-while loop without them. Again, the statement does very much what it says that it does. It will do the statements while the condition is true.

Given how very similar this sounds to the normal while loop, you might wonder what the difference is. The difference is implied by the layout. The normal while loop checks the condition before it executes the statements in the body of the loop. The do-while loop checks the condition after it executes the body of the loop. As a result, the body of a do-while loop will always execute at least once.

The do-while loop is not used that often in programming. The only times it is used are in situations where the post-check nature of the loop is helpful and you want the contents of the loop to always happen once. A common example of this is in menu based applications where you need to read what the user wants to do and then act on it. The decision of whether or not the loop should be executed again is based on what option the user picks.

The mainGrades function from the end of the last chapter was an example of this. In that chapter we wrote the program using recursion because that was the only method we knew for making the program execute the same code repeatedly. This function can be converted over to use a do-while loop and the result might look like the following.

def mainGrades {

 var tests=List[Double]()

 var assignments=List[Double]()

 var quizzes=List[Double]()

 var option=0

 do {

 printMenu

 option=readInt()

 option match {

 case 1 =>

  println ("Enter a test grade.")

  tests ::= readDouble()

 case 2 =>

  println("Enter a quiz grade.") 

  quizzes ::= readDouble()

 case 3 =>

  println("Enter an assignment grade.")

  assignments ::= readDouble()

 case 4 =>

  println("The average is "+

   courseAverage(tests,assignments,quizzes))

 case 5 =>

 case _ =>

  println("Unknown option. Try again.")

 }

 } while(option!=5)

}

Whether you use this or the code in section 7.11 is primarily a question of style. Most developers would probably write this version by default, but that is mainly because most developers have a background in imperative programming and will tend to favor this approach for reasons of familiarity.

8.3 for Loop

The while loop is the simplest loop, but it is not the most commonly used loop in most languages. In languages that provide a for loop, it is typically the most commonly used loop. The for loop in Scala is a bit different from that provided in many other languages, but you will probably find that it is the one that you turn to the most when you are putting iteration into your code.

In most languages, the natural usage of the for loop is to count so we will start with that. A for loop that counts from 1 to 10 and prints out the values would be written as follows in Scala.

for(i <- 1 to 10) {

 println(i)

}

The name i is a variable name just like you would get with a val declaration for Scala. As such, you can call it whatever you want. For counting loops it is very common to use names such as i, j, and k. However, anything will work and as with other variable names, it is better if your choice communicates something to those reading the code to make it easier for them to understand. After the variable name is an arrow pointing to the left made from a less than and a hyphen or minus sign. You will see this in all of your for loops in Scala. You can read the <- as “in”. After that is a nice expression that you should be able to read. We will talk more about exactly what that means shortly. You can read this for loop as something like “for i in 1 to 10”.

As we saw in chapter 7, the indexes in collections in Scala do not start counting at one. Instead, they start counting at zero. As such, you often would not count from 1 to Instead, we would normally count from 0 up to 9. This could be expressed in Scala by replacing 1 to 10 with 0 to 9. However, it is very common that you want to start at zero and express the number of elements you want to go through. For this reason, the following also works in Scala.

for(i <- 0 until 10) {

 println(i)

}

Using until causes the counting to finish one before the last value listed.

The for loop in Scala is not just about counting though. Indeed, this usage is something of a special case in Scala. In general, the expression to the right of the <- in a for loop in Scala can evaluate to any type of collection. In other languages, this type of loop that runs through the elements of a collection is often called a for-each loop because it does something for each element of the collection. That might remind you of the foreach method from section 7.4. This is more than a passing resemblance, but that is something you do not need to understand at this point.

To illustrate this usage of the for loop, consider the following code in the REPL.

scala> List.tabulate(10)(i =< i*i)

res0: List[Int] = List(0, 1, 4, 9, 16, 25, 36, 49, 64, 81)

scala> for(elem <- res0) {

 | println(elem)

 |}

0

1

4

9

16

25

36

49

64

81

In this case, the for loop actually does exactly the same thing that foreach does and runs the code inside the loop on each of the different elements in the list. What code you put in the for loop can be arbitrarily complex. The println statements shown here just make simple examples.

A more general description of the syntax of the for loop would be the following.

for(name <- collection) statement

The name can be any valid Scala name. The collection can be any expression that results in a collection. The statement can be anything that you want to have happen. Frequently a code block is used and you will see multiple statements in curly braces.

Let us use a for loop to evaluate a polynomial. We will treat an Array[Double] as the polynomial where each element in the array is a coefficient of a term in the polynomial. For example, the polynomial 3x3 + 6x2 − 4x + 7 is represented as Array(3.0,6.0,-4.0,7.0). We want the function to evaluate the polynomial for a particular value of x that will also be passed into the function. We will write this in several ways. The first one will use a counting loop.

def evalPolyCount(coefs:Array[Double],x:Double):Double = {

 var ret=0.0

 for(i <- 0 until coefs.length) {

 ret+=coefs(i)*math.pow(x,coefs.length-1-i)

 }

 ret

}

This will work, but it is particularly inefficient. The use of math.pow for small integer exponents is very inefficient. Walking through the Array with the index is not bad, but if we decided to use a List for the coefficients that would change.

Recall that the for loop is intended to go through the elements of a collection. As such, we could just run through the elements of coefs and perform the math. The only challenge in this is that we were using the index, i, to calculate the power of x as well. We could get rid of that and remove the use of pow if we simply went through the Array in the reverse order. Putting that logic into code produces this.

def evalPolyReverse(coefs:Array[Double],x:Double):Double = {

 var ret=0.0

 var power=1.0

 for(c <- coefs.reverse) {

 ret+=c*power

 power*=x

 }

 ret

}

This version does not count with an index. Instead it runs through the array elements. Each value in the Array is put into c and then the return value is incremented. A separate variable called power is created with a value of 1.0 and each time through it is multiplied by x. This provides us with a running power of x and removes the need to call math.pow.

This function is also perfectly correct. It’s main drawback is that in order to do the powers of x properly, the Array had to be reversed. Given this usage, that will create a completely new Array and copy the elements across in the reverse order. While that is also inefficient, this does allow us to nicely illustrate the usage of the for loop to run through any collection, even one that is created through operations on other collections.

8.3.1 Range Type

Now that you have seen that the for loop really just runs through a collection, you might wonder about the counting usage with something like this.

for(i <- 0 until 10) {...

To understand this it might help to type some expressions into the REPL and see what is really going on. Here we have done that.

scala> 1 to 10

res8: scala.collection.immutable.Range.Inclusive with

scala.collection.immutable.Range.ByOne = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> 0 until 10

res9: scala.collection.immutable.Range with

scala.collection.immutable.Range.ByOne = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

We will not try to understand what this gives us in any great detail, but there is one significant thing to realize from this. The expressions 1 to 10 and 0 until 10 give us back values that actually are collections. These are instances of the Range type.

The Range type in Scala gives us a simple way to use the for-each style loop that Scala provides to do the counting operations that most programmers are used to using the for loop to accomplish. You can use to and until with other integer types including the Char type. So the expression ’a’ to ’z’ will give you a collection of all of the lowercase letter.

What if you want to count down? The Range type has an operation by defined on it that will allow you to specify the step between elements in the Range. So if you want to go from 10 down to 1 you can use 10 to 1 by -1. We can use this to get a version of the polynomial evaluation function the uses the index counting, but does not require math.pow and instead keeps track of the exponent of x.

def evalPolyCountDown(coefs:Array[Double],x:Double):Double = {

 var ret=0.0

 var power=1.0

 for(i <- coefs.length-1 to 0 by -1) {

 ret+=coefs(i)*power

 power*=x

 }

 ret

}

This version has most of the advantages of both of the previous versions. It does not have to reverse the Array, nor does it require the use of math.pow. The one downside is that it still would not translate well to a List.

If you use by, you can also use Ranges of the Double type. Other, less standard, numeric types like BigInt will also work nicely with the Range type. The fact that the Range type is really a collection means that all of the methods that were discussed in the last chapter are available for them. This leads to a concise way of expressing factorial.

scala> (1 to 5).product

res21: Int = 120

In addition to product and sum, you can also apply map, filter, or other operations to instances of the Range type.

There are sometimes when you want to count through the indices of a collection like an Array. You could do this with code like the following assuming that you have an Array called a.

for(i <- 0 until a.length) ...

You can also use the indices method on the collection. Calling a.indices will give you a Range that goes from the first index to the last one. So this loop could also be expressed in this way.

for(i <- a.indices) ...

Not only is this shorter, it is slightly less error prone in that you can not accidentally start at 1 instead of 0, nor can you accidentally use to instead of until.

8.3.2 yield

The while loop is a statement only and can not be used as an expression. This is not true of the for loop. You can cause the for loop to produce a value so that is can be used as an expression. This is done by putting the yield keyword right after the close parentheses of the for loop. When you use yield, instead of a statement you need to have an expression. The result of the for expression is a new collection with all of the yielded values in it. The following shows a simple example of this.

scala> for(i <- 1 to 10) yield i*i

res22: scala.collection.immutable.IndexedSeq[Int] =

Vector(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

Another slightly different example shows how you could use a for loop to make a collection that is filled with values read in from input.

val nums=for(i <- 1 to 10) yield readInt()

This could work as an alternative to fill if you find it more readable.

You should note that the example gives a result with a type we have not seen before. The general type is listed as an IndexedSeq[Int] and the specific object is a Vector[Int]. Do not let these different types throw you off. For our purposes, we will use them just like we would the Array type. The difference between the Array and the Vector is that the Vector is immutable. You can index into it efficiently like an Array, but like a List, you are not allowed to change the values of the elements. All the standard functions that we saw earlier for Array and List will work on these types as well.

8.3.3 if Guards

The for loop in Scala also allows conditionals. After the first generator, you can put an if that has a condition on it. The for loop will only happen for those instances where the condition is true. This can lead to a more compact syntax than putting a if inside of the for loop. It can also be more efficient. Most importantly, it can be useful when you have a yield so that you do not add unwanted elements to the value of the expression.

As an example of this, and other aspects of the for loop, let us consider having a sequence of points in 2-D that are stored as (Double,Double). I want an expression that will give me back a sequence that has the distances to those points. The catch is that I only want the distances that are less than one. Without the if guard, this would require two steps. One would calculate the distances and a second would filter out the large values. The if guard lets us do this in a single loop.

for((x,y) <- points; if magnitude(x,y)<1.0) yield magnitude(x,y)

This example was written assuming a function called magnitude that might look like the following.

def magnitude(x:Double,y:Double):Double = math.sqrt(x*x+y*y)

The beginning of this loop illustrates how you can use a pattern on a tuple to pull out the two elements in the point. This is actually one of the great strengths of the for loop in Scala that helps simplify your programming.

The one significant drawback of this approach is that the magnitude function is called twice. The sqrt function can be expensive so this is less than ideal. We will see how to get around that shortly.

8.3.4 Multiple Generators

The for loop in Scala also supports the ability to iterate across multiple collections in a single for loop. This can be done by putting more than one variableName <- collection in the parentheses. Each of these that you put into the for loop will generate values from the collection to run through the logic. The first generator will pull the first value from its collection. A second generator will then run through all of its values before the first one goes on to the second option. So the number of times the body of the loop happens goes as the product of the number of elements in the collections for the generators, not the sum. To help you understand this, consider the following example.

scala> for(i <- 1 to 5; c <- ’a’ to ’c’) println(i+" "+c)

1 a

1 b

1 c

2 a

2 b

2 c

3 a

3 b

3 c

4 a

4 b

4 c

5 a

5 b

5 c

You can see that the character variable, c, goes through all of its values for each value that i takes on. As a result, there are 15 lines printed.

You might wonder why you would want to do this. Consider again the example of using a 2-tuple to represent points. You might want to make a collection of all the points on a grid in some range of x and y values with a particular spacing in the grid. You could do that with the following code.

val xmin = -1.5

val xmax = 0.5

val xstep = 0.01

val ymin = -1.0

val ymax = 1.0

val ystep = 0.01

val pnts=for(x <- xmin to xmax by xstep;

 y <- ymin to ymax by ystep) yield (x,y)

The output from the last line will appear in the REPL as something like the following.

pnts: scala.collection.immutable.IndexedSeq[(Double, Double)] =

Vector((-1.5,-1.0), (-1.5,-0.99), (-1.5,-0.98), (-1.5,-0.97),

(-1.5,-0.96), (-1.5,-0.95), (-1.5,-0.94), (-1.5,-0.93), (-1.5,-0.92),

(-1.5,-0.91), (-1.5,-0.9), (-1.5,-0.89), (-1.5,-0.88), (-1.5,-0.87),

(-1.5,-0.86), (-1.5,-0.85), (-1.5,-0.84), (-1.5,-0.83), (-1.5,-0.82),

(-1.5,-0.81), (-1.5,-0.8), (-1.5,-0.79), (-1.5,-0.78), (-1.5,-0.77),

(-1.5,-0.76), (-1.5,-0.75), (-1.5,-0.74), (-1.5,-0.73), (-1.5,-0.72),

(-1.5,-0.71), (-1.5,-0.7), (-1.5,-0.69), (-1.5,-0.68), (-1.5,-0.67),

(-1.5,-0.66), (-1.5,-0.65), (-1.5,-0.64), (-1.5,-0.63), (-1.5,-0.62),

(-1.5,-0.61), (-1.5,-0.6), (-1.5,-0.59), (-1.5,-0.58), (-1.5,-0.57),

(-1.5,-0.56), (-1.5,-0.55), (-1.5,-0.54), (-1.5,-0.53), (-1.5,-0.52),

(-1.5,-0.51), (-1.5,-0.5), (-1.5,-0.49), (-1....

In this case, the output is truncated before it even gets to the second value of x.

8.3.5 Patterns in for Loops

One example above used the pattern (x,y) to the left of the <- in a for loop. You can use any pattern that you want in that position of a for loop. Over time we will learn about more patterns to demonstrate just how powerful this is. What makes it truly useful in for loops is that any value that does not match the pattern is skipped.

The true usefulness of this will be exposed in the second half of the book. In the first half, the main usage will be to quickly and easily pull values out of tuples. However, we can present one other interesting usage here that uses the fact that collections can be used as patterns. Consider the following code that makes an Array[Array[Double]] where each of the contained Arrays has a variable length between 3 and 9.

scala> val twoD = Array.fill(100){

 | Array.fill(util.Random.nextInt(7)+3)(math.random)

 |}

twoD: Array[Array[Double]] = Array(Array(0.9714402463829903, 0.14015197447391436,

 0.8524582916143384, 0.6162004743306447, 0.620366190244299, 0.36698269639501,

 0.8524582916143384, 0.6162004743306447, 0.620366190244299, 0.36698269639501

 0.46318519546397396), Array(0.6436214632596926, 0.48145976017298175,

 0.5205354884596076, 0.20188086494076174, 0.9186534118857578,

 0.206412655336915), Array(0.41326520865491023, 0.5388572013936772,

 0.3835287127371739, 0.840667735649998, 0.5776048750341035, 0.8564378792435797,

 0.33358311231736193), Array(0.8386133676386185, 0.19634635871412187,

 0.85047321636848, 0.8920110191832437, 0.22432093122102714, 0.9053781210756321,

 0.7642421256500077), Array(0.7958975255688977, 0.30398364976466374,

 0.8810424486159291, 0.1328719423800543, 0.7129174104031204),

 Array(0.6067234631262645, 0.5276942206810142, 0.06504059155788122,

 0.4145379572950526...

You can imagine a situation where this is data that you got from some data set and you only care about the entries with only three values in them and for those you only want the average value. The following for loop would provide exactly that data.

scala> for(Array(d1,d2,d3) <- twoD) yield (d1+d2+d3)/3

res1: Array[Double] = Array(0.7844266684446944, 0.4057923197637461,

 0.44310232980470454, 0.5634809009372609, 0.576642991638965,

 0.3789396949661376, 0.5706536514773105, 0.5844720273258665,

 0.3445436835569556, 0.3547819380526076, 0.5996534540605474,

 0.38416980809208406, 0.8018516553113365, 0.2244482193993954,

 0.5098449834833878, 0.6578966352311121)

Note that the array twoD has a length of 100, but res1 has only 16 elements. That is because the other 84 had more than three elements in them. The pattern Array(d1,d2,d3) matches only Arrays that have exactly three elements in them. Those three elements are bound to the names d1, d2, and d2.

8.3.6 Variable Declarations

if guards, multiple generators, matching patterns, the for loop seems like a dream, but wait! There’s more! You can define variables inside of the for loop. This is helpful for situations like we had earlier where we do not want to have to calculate the magnitude twice for each iteration.

for((x,y) <- points; val dist=magnitude(x,y); if dist<1.0) yield dist

In this sample, the magnitude is calculated and stored in dist. That value is then used in the two different locations where it had been calculated before.

The generators, if guards, and value declarations can be combined in any way given that a generator comes first. This provides a significant amount of power in a single construct. Just do not abuse it to make code that no one can understand.

8.4 Multidimensional Arrays

When we first introduced Arrays and Lists back in chapter 7, we saw that these types are parametric. That means that the type requires a type argument to be fully defined. So you can not have just an Array or just a List. Instead you have Array[Int] or List[String]. Each of these is a type in Scala. The parameter for these parametric types can be any type.1 If you put these together you can build things like Array[Array[Double]], List[List[String]], or List[Array[Int]]. You do not have to stop there though. Scala will be perfectly happy with a List[Array[List[List[Array[Int]]]]]. It is not clear what you would want such a type for, but if you find a use, Scala will support it.

In the case of Arrays of Array types, we have a special term for them. They are called multidimensional arrays. This is because of how you might picture them in your head. You can picture a normal Array as a row with multiple bins that each store a value. An Array[Array[Int]] could be pictured as a table of integers that has rows and columns. Such a table could be said to be two-dimensional. If you had an Array[Array[Array[Int]]] you could picture it as a cube of values in three dimensions. In general all these things can be applied to Lists just as well as Arrays, but the term multidimensional list is not nearly as common.

So how can you create and use multidimensional arrays? The most basic syntax mirrors what we used to originally create normal Arrays.

scala> val tda1=Array(Array(1,2,3),Array(4,5,6))

tda1: Array[Array[Int]] = Array(Array(1, 2, 3), Array(4, 5, 6))

In this usage the number of elements in each subarray does not have to be the same. When the lengths are different, they are called ragged arrays. When they are all the same, they are called rectangular arrays.

If you are interested in making large rectangular arrays, you should use either the fill method or the tabulate method. This usage is shown below.

scala> val tda2=Array.fill(10,10)(0)

tda2: Array[Array[Int]] = Array(Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0))

scala> val tda2=Array.tabulate(10,10)((i,j) =< i*j)

tda2: Array[Array[Int]] = Array(Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Array(0, 2, 4, 6, 8, 10, 12, 14, 16, 18),

Array(0, 3, 6, 9, 12, 15, 18, 21, 24, 27), Array(0, 4, 8, 12, 16, 20, 24, 28,

32, 36), Array(0, 5, 10, 15, 20, 25, 30, 35, 40, 45), Array(0, 6, 12, 18, 24,

30, 36, 42, 48, 54), Array(0, 7, 14, 21, 28, 35, 42, 49, 56, 63), Array(0, 8,

16, 24, 32, 40, 48, 56, 64, 72), Array(0, 9, 18, 27, 36, 45, 54, 63, 72, 81))

Note that the number of arguments you pass into the first argument list of tabulate or fill determines the dimensionality of the resulting structure. In the case of tabulate, the function that is passed in second needs to take as many arguments as there are dimensions.

You can also use tabulate to make non-rectangular arrays by building a 1-D array whose contents are arrays and using the index to determine the length. That technique is used here to create a triangular 2-D array.

scala> val tda3=Array.tabulate(10)(i =< Array.fill(i+1)(0))

tda3: Array[Array[Int]] = Array(Array(0), Array(0, 0), Array(0, 0, 0),

Array(0, 0, 0, 0), Array(0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0),

Array(0, 0, 0, 0, 0, 0, 0, 0, 0), Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0))

Note that the output here has a different number of elements in each of the subarrays.

To access the elements of a 2-D Array, simply put two sets of parentheses after the Array name with two different indices in them. For example, we can pull values out of tda2 in this way.

scala> tda2(3)(4)

res0: Int = 12

The 2-D Array tda2 was created to be something like a multiplication table. This particular expression pulled off the element at position 3,4 which is 12.

The advantages and restrictions of the List and Array types that were discussed previously apply to higher-dimensional cases as well. Once you have made an Array, the values can be changed, but the length can not. Similarly, you can make new Lists by efficiently adding to the head of old ones, but you can not mutate values in a List even if it has a higher dimension.

To bring these things back to the original topic of the chapter, how can you use for loops to produce higher-dimensional data structures? One might think that multiple generators would do this. However, that is not the case as you can see if you go back to our examples in that section. If you want to have a construct with higher dimensions, you need to have multiple nested for loops. As an example of this, we will use for loops to build the multiplication table that we built earlier with tabulate.

val multTable = for(i <- 0 until 10) yield {

for(j <- 0 until 10) yield i*j

}

If you execute this code in the REPL you get the following result.

multTable: scala.collection.immutable.IndexedSeq[scala.collection.immutable.

IndexedSeq[Int]] = Vector(Vector(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),

Vector(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), Vector(0, 2, 4, 6, 8, 10, 12,

14, 16, 18), Vector(0, 3, 6, 9, 12, 15, 18, 21, 24, 27),

Vector(0, 4, 8, 12, 16, 20, 24, 28, 32, 36), Vector(0, 5, 10, 15,

20, 25, 30, 35, 40, 45), Vector(0, 6, 12, 18, 24, 30, 36, 42, 48, 54),

Vector(0, 7, 14, 21, 28, 35, 42, 49, 56, 63), Vector(0, 8, 16, 24,

32, 40, 48, 56, 64, 72), Vector(0, 9, 18, 27, 36, 45, 54, 63, 72, 81))

This has the same values as the Array[Array[Int]] that we made earlier and we can use it the same way despite the fact that it is technically a Vector[Vector[Int]].

scala> def fact(n:BigInt):BigInt = if(n<2) 1 else n*fact(n-1)

fact: (n: BigInt)BigInt

scala> for(i <- 30 to 15 by -1) println(fact(i))

265252859812191058636308480000000

8841761993739701954543616000000

304888344611713860501504000000

10888869450418352160768000000

403291461126605635584000000

15511210043330985984000000

620448401733239439360000

25852016738884976640000

1124000727777607680000

51090942171709440000

2432902008176640000

121645100408832000

6402373705728000

355687428096000

20922789888000

1307674368000

scala> for(i <- 30 to 15 by -1 par) println(fact(i))

1124000727777607680000

51090942171709440000

2432902008176640000

265252859812191058636308480000000

121645100408832000

6402373705728000

403291461126605635584000000

355687428096000

15511210043330985984000000

20922789888000

620448401733239439360000

304888344611713860501504000000

25852016738884976640000

10888869450418352160768000000

1307674368000

8841761993739701954543616000000

scala> var count = 0

count: Int = 0

scala> for(i <- 1 to 1000000 par) count +=1

scala> count

res0: Int = 930420

8.5 Testing

We have now gotten to the point where you can write programs of reasonable complexity. You know most of the constructs that exist in the Scala programming language. As soon as you start writing larger programs, there are some new elements of the programming process that becomes more significant such as testing and debugging.

Just because you have written the code and it compiles and runs does not mean that it is correct. To determine if it actually does what you want it to you need to test it. This means that you need to run the code with a variety of different inputs to make sure that they all work and then fix the problems when they do not.

The first part of this, running the program with different inputs is called testing. The challenge in testing is trying to figure out what inputs make good tests. When you are testing code you are actually looking for inputs that will break what you have written. You want to give it some things that you know it will work on, but you also want to give it some things that you think might break it. In addition, a good set of tests will go through all of the functionality of the code.

Thinking of things that will break the code often involves looking for boundary conditions. Things that are right at the edge of valid input. For example, if you have a function that takes an Array or a List, what happens if the List or Array you pass in is empty? You want to check different small number input sets as well as large ones. If the code takes numeric values, does it work for both positive and negative? What about zero? Giving you back answers that are wrong or do not make sense can be worse than crashing. If the input is a String, what happens when the String is empty?

There are some situations where you will be certain that the input has a particular structure. In other situations the input will be coming from a user who might give you something that is not quite what you expected. Even when the input is coming from another part of the program and something that you think will have the right format, there can be cases that you have not considered. Good testing will help you find these situations.

If parts of your code require that certain things be true, you can use the require function in Scala to force the program to terminate if a condition is violated. You can call require with just a Boolean argument. If the Boolean is false, the program will terminate. The termination can be made more informative by providing a second argument that is a message to give the user if the requirement fails. The following shows how this might be used.

def weightedAverage(values:Array[Double],weights:Array[Double]):Double = {

 require(values.length==weights.length,

 "Must have same number of values and weights.")

 require(weights.length>0,"Average of zero elements not defined.")

 require(weights.sum!=0.0,"Sum of weights can’t be zero.")

 (for((v,w) <- values.zip(weights)) yield v*w).sum/weights.sum

}

This function is intended to take the weighted sum of a set of values. There are a number of requirements on the values passed into it. There are three require calls that make sure that each of these is true before it calculates the value. This might seem like a lot of extra typing, but if you put calls to require in your code whenever there really is a requirement, you will find that it makes the debugging process a lot easier.

The other part of testing is coverage. Showing that the code works for one test input is not sufficient to show that it is really correct. How many tests do you have to write to feel confident that your code works? One of the challenges of Computer Science is that you can not, in general, prove that programs are correct. This was one of the earliest results of Computer Science and is still a fundamental aspect of the theory of the field.3 Certainly, some programs can be proved to be correct, but generally the best we achieve is to show that our programs work across a broad range of inputs.

There are some criteria, beyond looking for boundary cases, you can use to determine if you have enough tests. The metric to determine this is called code coverage. You want to know what fraction of your code has been executed by the tests. There are a number of different code coverage metrics that can be used.

• Function coverage - Has every function been called?
• Statement coverage - Has every statement been executed?
• Decision coverage - Has every option in branching structures (if and match) been executed?
• Condition coverage - Has every Boolean subexpression evaluated as both true and false?
• Condition/decision coverage - Combination of the two above.
• Loop coverage - Has every loop been executed zero, one, and more than one times?
• Path coverage - Has every path through part of the code been executed?

The more complete the coverage your test set has, the more confident that you are that your code is correct. The levels of coverage higher in this list are basically minimal standards. If your tests have not gone to every function or every statement, then there are parts of the program that you simply have not tested. Going beyond those you start looking at different ways for things to happen. There are often several different places from which a function can be called. Covering decisions will make sure that you have called them from different locations. Covering conditions makes sure that all the possibilities for why different parts of the code might be reached have been exercised.

If you stop and think about it, you will probably realize that getting condition/decision coverage requires quite a few test cases. Even these options potentially leave a lot of possibilities unchecked as they do not force loops to happen different numbers of times.

The ultimate form of coverage, path coverage, is generally unattainable for any program of even modest size. Having path coverage implies that you have tested every possible path that the execution could take through the code. Consider a simple function with three if statements one after the other. One path through the code would have all three evaluate to true. Another path might have the first two true and the last false. There are actually eight different paths through such a function. If you add another if, the number of paths doubles to 16. Path coverage requires exponentially many different cases be tested as conditional statements are added. If that was not bad enough, a single while loop creates an infinite number of different paths as the loop could execute zero, one, two, or more times. Each one is a different path through the code. As such, path coverage is generally viewed as an unattainable ideal for anything beyond fairly simple functions.

Due to the challenges of getting good coverage on large collections of code, it is common to do testing on small blocks at a time. This process is called Unit testing. Each different unit of the code has a test suite written for it that checks its functionality independent of other parts of the code. These test suites are run over and over again during development to make sure that no new changes break code that was written earlier.

The real advantage of Unit testing is that in a small unit, one can hope to get fairly complete path coverage. However, it is not sufficient to only do Unit tests. As the different units are assembled, they have to be put through integration tests that test how the pieces work together. It is very possible for two units of code to work perfectly in isolation and fail miserably when they are put together.

numList.filter(_>70).map(_/10-6).sum

numList.view.filter(_>70).map(_/10-6).sum

8.6 Putting it Together

Going back to the theme park, imagine that you have the job of scheduling workers to operate rides. Your scheduling needs to take into account a number of different factors. Each ride needs a minimum number of operators and, on days when there are lots of people riding, that number needs to be increased. Also, the people who are working have to be trained to operate rides. Not everyone has been trained for every ride, so you have to make sure you have enough people scheduled who can operate each ride.

You have data from multiple weeks telling you how many people ride each ride on different days of the week. That is fairly consistent so you will use averages of those values to plan for each day. It is possible to write a program that will generate optimal schedules for an entire week. We are not yet at the point where we are ready to write such a program. Instead, we will write a program that outputs potential schedules for each day of the week. This will help you to build schedules, but will not complete the entire task for you.

The script needs to start by reading in all the data on rides and employees. There will need to be a fair bit of this so this is a script that should probably be run using input redirection and having the contents of a file put in as the standard input. The input will start by telling you how many rides there are followed by information for each ride. That information will include a name, the number of operators needed on a slow day, and the number of riders that qualifies as a heavy day. We will assume that on heavy days, one extra operator is needed. That will be followed by the number of employees. For each employee there will be a name, a number of rides they are trained on, and the names of those rides. The last type of data in the input will be information on sample days. This will start by telling you how many samples there are. Each sample will have the name of a day, the name of the ride, and the total number of people who rode it that day. No assumptions will be made about the days or how many times each day appears.

Once the data has all been read in, the script should run through every day that there is data for, average the number of riders for each ride on that day, and list possible combinations of workers who can cover the rides that day. Any ride that does not have data for a given day can be assumed to be closed and does not need an operator.

The approach to finding possible groups of ride operators requires looping through the rides that are active on a given day and determining how many operators each one needs based on the average number of riders in the data. Our code will store this by having a single sequence with one entry for each operator needed on each ride. The length of that sequence tells us how many total operators are needed.

The combinations method is then used to pick all groupings of that many workers as our goal is to not bring in more people than we have to. For each combination, the code will run through permutations of the ride-operator list using permutations. It will check whether that permutation has operators who match up with rides they know how to run. If any permutation matches, that combination of operators is a possibility and it is printed. Code for doing this is shown here.

def readRide():(String,Int,Int) = {

 val name = readLine()

 val numOps = readInt()

 val heavyRiders = readInt()

 (name,numOps,heavyRiders)

}

def readEmploy():(String,List[String]) = {

 val name = readLine()

 val num = readInt()

 val rides = List.fill(num)(readLine())

 (name,rides)

}

def readDay():(String,String,Int) = {

 val day = readLine()

 val ride = readLine()

 val numRiders = readInt()

 (day,ride,numRiders)

}

val numRides = readInt()

val rideInfo = Array.fill(numRides)(readRide())

val numEmploys = readInt()

val employInfo = Array.fill(numEmploys)(readEmploy())

val numDays = readInt()

val daysInfo = Array.fill(numDays)(readDay())

val days = daysInfo.map(_._1).distinct

for(day <- days) {

 val thisDay = daysInfo.filter(_._1==day)

 val rides = thisDay.map(_._2).distinct

 val operatorRides = rides.flatMap(ride =< {

 val nums = thisDay.filter(_._2==ride).map(_._3)

 val avg = nums.sum/nums.length

 val rideData = rideInfo.find(_._1==ride).get

 Array.fill(rideData._2+(if(avg>=rideData._3) 1 else 0))(ride)

 })

 val totalOps = operatorRides.length

 for(choice <- employInfo.combinations(totalOps)) {

 val perms = operatorRides.permutations

 var works = false

 while(!works && perms.hasNext) {

  val perm = perms.next

  if((perm,choice).zipped.forall((r,op) =< op._2.contains(r)))

   works = true

  }

  if(works) {

   println(day+" : "+choice.map(_._1).mkString(", "))

 }

 }

}

The top of the code defines some functions for reading information, then reads in all the data. Once the data has been read in, the days we have data for is put into days using the distinct call to remove duplicates.

Inside of the loop running through the days the variable thisDay gets all the ride data for the day being considered. That is used to build rides, which contains the unique rides that we have data for on that day. The next step is to expand that so we have a sequence, called operatorRides with each ride duplicated a number of times equal to how many operators are needed for it. This is done using flatMap with a function that returns an Array of the proper size that is built using fill.

Another loop then goes through all combinations of employees with a length matching the number of operators needed. The selection of operators goes into choice. Permutations of operatorRides are then taken and a check is done to see if operators match with rides in that permutation. This is done with a while loop so that it can exist early if any match is found. If there is a match, the choice sequence with operator names is printed along with the day in question.

A sample input can be found at the website. The output from running that program on the sample input is shown here. This sample input had only four rides and ten employees, but it does show the basic functionality.

Fri : Mark, Amy, Madison, Kelsey, John, Jason

Fri : Mark, Amy, Madison, Kelsey, John, Kevin

Fri : Mark, Amy, Kelsey, John, Jason, Kevin

Fri : Mark, Madison, Kelsey, John, Jason, Jane

Fri : Mark, Madison, Kelsey, John, Kevin, Jane

Fri : Mark, Kelsey, John, Jason, Kevin, Jane

Sat : Mark, Amy, Madison, Amber, Kelsey, John, Jason, Kevin, Jane

Sat : Mark, Amy, Madison, Amber, Kelsey, John, Jason, Jim, Jane

Sat : Mark, Amy, Madison, Amber, Kelsey, John, Kevin, Jim, Jane

Sat : Mark, Amy, Madison, Kelsey, John, Jason, Kevin, Jim, Jane

Sat : Mark, Amy, Amber, Kelsey, John, Jason, Kevin, Jim, Jane

Sun : Mark, Madison, Amber, Kelsey, John, Jason, Kevin

Sun : Mark, Madison, Amber, Kelsey, John, Jason, Jim

Sun : Mark, Madison, Amber, Kelsey, John, Kevin, Jim

Sun : Mark, Madison, Kelsey, John, Jason, Kevin, Jim

Sun : Mark, Amber, Kelsey, John, Jason, Kevin, Jim

One of the significant aspects of this example is the use of combinations and permutations to run through various possibilities. We will explore alternate ways of solving problems like this that can be more efficient in chapter 15. For now, these methods give us the ability to solve complex problems that would otherwise be out of our reach.

8.7 End of Chapter Material

8.7.1 Problem-Solving Approach

This chapter added quite a few new constructs for you to pick from for any given line of code in the form of three different types of loops. These have been added below to what was given in chapter 6.

1. Call a function just for the side effects.
2. Declare something:
   • A variable with val or var.
   • A function with def. Inside of the function will be statements that can pull from any of these rules.
3. Assign a value to a variable.
4. Write a conditional statement:
   • An if statement.
   • A match statement.
5. Write a loop statement:
   • Use a while loop when you do not have a collection or know how many times something will happen, nor do you need to use it as an expression.
   • Use a do-while loop in a situation where you could consider a while loop, but you know that it should always happen at least once.
   • Use a for loop to run through the elements of a collection or to do simple counting.

8.7.2 Summary of Concepts

• The while loop is a pre-test conditional loop. It will repeat the body of the loop until a condition check returns false. The condition is checked before the first execution of the body and then before any subsequent executions. The while loop is used as a statement only. It has no value so it can not be used as an expression.
• The do-while loop is just like the while loop except that the condition is checked after each execution of the body. This means that the body of a do-while loop will always execute at least once.
• The most commonly used loop is the for loop. Scala’s for loop is a for-each loop that iterates through each member of a collection. It has many options that give it a lot of flexibility and power.
  • A generator in a for loop has a pattern followed by a <- followed by a collection that is iterated through. The <- symbol should be read as “in”.
  • To make counting easy, there is a Range type that can specify ranges of numeric values. The methods to and until can produce Ranges on numeric types. The method by can adjust stepping. Floating point Ranges require a stepping.
  • The yield keyword can be put before the body of a for loop to cause it to produce a value so that it is an expression. When you have a for loop yield a value, it produces a collection similar to the one the generator is iterating over with the values that are produced by the expression in the body of the loop.
  • The left side of a generator in a for loop is a pattern. This can allow you to pull values out of the elements of the collection, such as parts of a tuple. In addition, any elements of the collection that do not match the pattern are skipped over.
  • if guards can be placed in for loops. This is particularly helpful when using yield and the values that fail the conditional check will not produce an output in the result.
  • You can also place variable declarations in the specification of a for loop. This can help make the code shorter, easier to read, and faster.
• The type parameters on collections can themselves be other collections. This allows for the creation of multidimensional Arrays and Lists in Scala. The fill and tabulate methods can produce these by passing the proper number of arguments into the first argument list.
• Testing is an essential part of software development. This is where you run the program using various inputs to make certain that does not fail and produces the correct output. Proper testing should exercise all parts of the code. It is generally impossible to test all paths through the code, though good coverage for that is also ideal. Challenging test cases often include boundary values.

8.7.3 Self-Directed Study

Enter the following statements into the REPL and see what they do. Some will produce errors. You should try to figure out why. Try some variations to make sure you understand what is going on.

scala> var i = 0

scala> while(i<20) {

 println(i)

 i += 2

}

scala> while(i<30) {

 println(i)

}

scala> do {

 println(i)

 i -= 1

} while(i>0)

scala> var resp = ""

scala> do {

 println("Go again? (Y/N)")

 resp = readLine()

} while(resp=="Y")

scala> 1 to 10

scala> 1 to 10 by 2

scala> 0.0 to 1.0 by 0.1

scala> for(i <- 1 to 10) println(i)

scala> for(i <- 1 to 10) yield i

scala> for(i <- 1 to 5; j <- 2 to 4) println(i+" "+j)

scala> val tups = for(i <- 1 to 5; j <- 2 to 4) yield (i,j)

scala> for((n1,n2) <- tups) yield n1*n2

scala> val twoD = List.fill(6,4)(99)

scala> val mult = Array.tabulate(10,10)((i,j) =< i*j)

scala> mult(3)(4)

scala> twoD(1)

8.7.4 Exercises

Many of these exercises are identical to ones that were given in chapter 6. The only difference is that those problems were to be solved with recursion and these are to be solved with loops.

1. Write the isPrime that returns a Boolean telling if a number is prime using a loop.
2. Write a function using a loop that will print powers of two up to some value.
3. Write a function using a loop that will print powers of two up to some power.
4. Write a function using loops that will print a multiplication table up to 10s. Try to get it running first, then consider how you could make everything line up.
5. Write a function that returns a List[Int] of the prime factors of a number using a loop.
6. Repeat exercise 6 (p.130) using a loop instead of recursion.
7. Write code that can take a List[Int] and give you back a new one where all the values have been doubled. Do this with a while loop, a for loop without a yield, and a for loop with a yield.
8. This problem is like exercise 8 (p.170) in that you are supposed to count the number of even values in an Array[Int]. The difference is that now you will do it once with a while loop and once with a for loop.
9. Another problem that is significant when doing real cryptography is solving linear equations under modulo arithmetic. That sounds complex, but it is really just solutions to the following:

   $ax\equiv b\mathrm{mod}n,$

   where we know a, b, and n and want to find x. To find the solutions to this, there can be more than one, you need to use the extended Euclid’s algorithm for exercise 12 (p.130).

   You start off by calling the extended Euclid’s algorithm on a and n, putting the returned values into d, x, and y. If b is not divisible by d then there is no solution. Otherwise make x0 = x(b/d) mod n. The solutions are given by (x0 + i(n/d)) mod n for i ∈ [0, d − 1].

10. Try to write functions to do these different things with Strings in the following ways: with a while loop and an index, with a for loop and an index, with a for loop and no index, with a Range and higher-order methods but no loops, and with only higher-order methods.
    • Determine if a String is a palindrome.
    • Count the number of times a letter occurs.
    • Remove all occurrences of a letter.
    • Replace all occurrences of a letter (without using any replace methods).
    • Count the number of occurrences of a substring.
    • Remove all occurrence of a substring.
    • Replace all occurrences of a substring (without using any replace methods).
    • Count the number of vowels.
    • Remove all vowels.
    • Convert all characters to uppercase (without using toUpper).
    • Convert all characters to lowercase (without using toLower).

8.7.5 Projects

1. This project builds on top of project 4 (p.178). For this you will fill in an entire grid of values with intersection parameters for a set of geometry. Most images on computers are made as grids of values where the values give the colors. We do not quite have the ability to introduce colors and images yet, but we are getting close.

   For now you will fill an Array[Array[Double]] with the t parameters for a collection of geometry. You should write a function that takes the following arguments: location of the viewer as a 3-D point, forward direction for the viewer as a 3-D vector, up direction for the viewer as a 3-D vector,4 a sequence of geometry (spheres and planes), and the number of cells across the square grid should be. You will cast one ray for each cell in the grid and see if it hits anything and if so, how far out it hits. Fill the grid with the values for a minimum intersection parameter.

   The grid represents a plane in space that is one unit in front of the viewer position with a top-left corner that is one unit up and one unit to the left. (You can find a left vector by doing the cross product of the up and forward vectors.) The grid extends to one unit to the right and one unit down. This is the basic approach for building images using ray tracing.

2. One of the useful things that you learn in calculus is that functions can be approximated. Your calculus text will mention both the MacLaurin series approximation and the Taylor series approximation. They are basically the same other than MacLaurin series are always taken about x = 0 and this is what we will be working with here. The definition of the MacLaurin series is

   $f(x)\sim {\displaystyle \sum _i\frac{f^{(i)}(0)}{i!}{x}^i}$

   So this is the sum from i = 0 up to some n (or infinity if you want to be really accurate). In the sum we have x raised to the i power times the ith derivative of f (x) evaluated at 0 divided by i factorial. Obviously, this is a real pain to use on functions where taking the derivative is not easy. However, for some functions where the derivatives are straightforward, performing this approximation is very easy. Examples of that would be ex, sin(x), and cos(x).

   Write a program that does a Maclaurin approximation of cos(x). That is not that hard because the derivative is – sin(x), which has a derivative of – cos(x) which goes to sin(x) then back to cos(x). Also note that you are always evaluating at x = 0 so all the terms for sin go to zero.

   The first few terms in this series are:

   $1-0-\frac{x^2}{2!}+0\text{}+\frac{x^4}{4!}-0-\frac{x^6}{6!}+0+\frac{x^8}{8!}+\mathrm{...}$

   For this project, you should ask the user for the x to use, as well as an accuracy. Use the math.cos function to get the “real” value of cosine at that value of x. Iterate until the difference between the series value and what that function gives you is less than the input accuracy. After the loop, print out the real value, the value you got from the series, and how many terms you had to sum to get that. (For an extra challenge, make your program use a Taylor series instead. This means inputing another value x0 which the series is expanded around.)

3. Computers are used extensively for simulating physical systems, especially when the system is hard or impossible to build in a lab. For this project you will write a simple simulation of the gravitational Kepler problem. You will also explore the accuracy of what you are doing a little bit. Imagine you have a body in orbit around a star. We will assume that the star is much larger than the other body so it stays at the origin, (0, 0), of our coordinate system. The other body starts at some position (x, y) with a velocity (vx, vy). A simple “integrator” for a system like this can be constructed by a discretization of Newton’s laws (a fancy way of saying that we avoid calculus and do things in a way that is more computer friendly). Newton’s second law tells us F1 = m1 * a1 and for gravity $F=-G\frac{m_1*m_2}{d^2}$. We are going to simplify this for our toy system and just say that $a=-\frac{1}{d^2}$. We can break this into components and get $a_x=-\frac{x}{d^3}$ and $a_y=-\frac{y}{d^3}$. Now, the trick on the computer is to say that instead of moving smoothly, the particle jumps over certain time steps, Δt. So after one time step the new position is x = x + Δt*vx and y = y + Δt*vy. Similarly, vx = vx + Δt*ax and vy = vy + Δt * ay. Doing this in a loop “integrates” the motion of the body. (Use the math.sqrt function to calculate d.)

   This integrator is very simple, but far from perfect. If you start with your body at (1, 0) with a velocity of (0, 1) it should be in a nice circular orbit staying that distance forever. By measuring how that distance changes, you can get a measure of how accurate, or inaccurate, the integrator is. You can play with other positions and velocities to see what happens.

   You will write a program that takes the initial x, y, vx, and vy as well as a time step, Δt, as inputs. It should advance the system for a total time of 10.0 (so if Δt = 0.1 that requires 100 iterations). At the end of it you should measure the distance from the origin and print a message giving that and the original distance. Then check to see if the change is less than 1%. If it is, say that the integration was accurate enough, otherwise say it is not. In a comment in your code you should tell how small you had to make your time step for this to be reached given the coordinate 1 0 0 1. (Note that this measure of accuracy is only good for circular orbits. We are not going to do enough physics to go beyond that, but if you happen to want to, the real objective is to conserve total energy. For an extra challenge, compare initial and final total energies of the system.)

   For fun, you can change it so it prints the x and y values during the simulation and see what is happening with a spreadsheet of using gnuplot in a manner similar to what is described in project 4 (p.131). This can also be helpful for debugging. Such plots are shown on the website.

4. An alternate physics problem that can be solved in the same way as that for the previous project is calculating the trajectory of a projectile. If you consider air resistance, the path of a body is not a simple parabola. Using a numerical integrator that was described in the previous project, you can figure out how far a projectile will go assuming there is air resistance.

   The force of gravity near the ground can be approximated a $\overrightarrow{F_g}=-gm\widehat{j}.$5 The friction force from the air can be approximated by $F_d=\frac{1}{2}\rho v^2{C}_{d}A$ where ρ is the density of the fluid, Cd is the drag coefficient of the shape, and A is the cross-sectional surface area of the particle. The value of Cd for a smooth sphere is 0.1. The density of air is about 1.2kg/m3. This force is directed in the opposite direction of the motion.

   Using a while loop write a script that will tell you how far a ball will go before it hits the ground with the user specifying the height from which it is thrown/launched, its initial speed, its initial angle, its radius, and its density. If you want a bit of extra challenge, allow the user to input a wind speed.

5. For this problem you will do some string parsing that has relationships to chemical formulas in chemistry. We are going to keep things fairly simple for this. The basic idea is that the user types in a string that is a chemical formula, and your program should parse that string and tell how many of each type of element are on each side of the equation. This is the first step in balancing a chemical equation. A later project will have you go through the process of doing the actual balancing.

   The format of the chemical equation will look something like this: CH4+O2=H2O+CO2. This is a reaction for burning/oxidizing methane. Note that it is not well balanced as there need to be coefficients in front of each term. Your program will assume a coefficient on each term in the equation as a lowercase letter starting with ’a’ in alphabetical order from left to right and output how many of each element there are. So for this input the output would be:

   C: a*1=d*1

   H: a*4=c*2

   O: b*2=c*1+d*2

   or if you want to clean it up a bit,

   C: a=d

   H: a*4=c*2 O:

   b*2=c+d*2

   This gives us three linear equations that we could try to solve (actually we have 3 equations for 4 unknowns so the system is under-determined, but that is often the case, so we will find the solution where a, b, c, and d have the smallest values possible and are all integers but you don’t have to worry about that now). We will not be solving it in this project.

   To be more specific about the input, it has a sequence of terms that are separated by + or =. The reagents are in terms on the left-hand side of the = and the products are on the right-hand side of the =. Each term can have one or more element names, each followed by the number of that element in the given molecule. The element names will all be one character long and capitalized. Also, the number of elements will be just one digit. If no number is present you assume there is only one. Allowing elements with more than one letter (uppercase followed by lowercase) or numbers with more than one digit makes a nice project for anyone looking for an extra challenge.

   The output should have a separate line for each element that was present in the equation. It should list the symbol for the element followed by a colon and then the equation that tells what the coefficients have to satisfy for that element to be balanced on both sides of the equation. You can choose either format above.

6. For this project you can keep working with recipes. You can think of this as an extension of project 6 (p.178), but you do not have to have completed that project to do this one. For this project you will write a text menu with the following options.
   1. (a) Add a pantry item.
   2. (b) Print pantry contents.
   3. (c) Check a recipe.
   4. (d) Cook recipe.
   5. (e) Quit

   If the user selects to add a pantry item you ask for the name of the item and how much they are adding then return to the menus. The option to check a recipe has them enter names and amounts until they give a name of “quit”. It then tells them whether or not they can make the recipe based on what they currently have. The last option will subtract the appropriate amounts for the items in the last recipe that was successfully checked. If no recipe has been successfully checked, it should print an appropriate message.

7. For this project you can upgrade what you did for project 7 (p.178) so that there is a text menu with options.
   1. (a) Add course of interest.
   2. (b) Print current courses.
   3. (c) Remove course of interest.
   4. (d) Build a schedule.
   5. (e) Quit

   Adding a course should have them type in a unique String for the course number or description along with a numeric value for how much they want that course and an integer for the time slot.6 When they select remove they should type in the unique ID and that course will be removed from consideration. The schedule building option should ask for how many hours they want to take that semester. It will then print out the three “best” schedules that match that number of hours and do not contain courses at conflicting times

Additional exercises and projects, along with data files, are available on the book’s website.

1There can be restrictions on parametric types, but the collections generally allow any type to be used.

2You can call the par method on a List, but it is not efficient.

3The proof itself was due to Alan Turing showing that you can not write a program that will take any program and an input and determine if the program terminates when run on that input. This is called the “Halting Problem”. The implication is that you can not, in a completely general way, even show that your program will terminate, much less give the right answer assuming it does stop. There are ways of writing things that avoid errors, but no systematic way of demonstrating correctness. It is worth noting that one nice thing about for loops is that they do always terminate as long as they are run on finite collections.
It should also be mentioned that while there is no completely systematic way to prove programs correct, there is a significant amount of work that has gone into proofs of correctness. Unfortunately, proving a program or algorithm correct is often challenging so it is only done for small algorithms or when it is absolutely required. Making this more applicable to general programming could be a significant boost to a world that is increasingly dependent on the proper functioning of programs.

4For a standard projection the up and forward directions should be perpendicular. However, the math works as long as they are not parallel. You simply get a distorted view in that case.

5If you are not familiar with the notation, $\widehat{i}$ and $\widehat{j}$ represent unit vectors in the x and y directions respectively.

6Real time slots involve days and times. That would make this problem a lot harder. You can do that if you want the challenge, but to keep things simple you could use a number for each standard time slot in the schedule. So use 1 for the first MWF (Monday, Wednesday, Friday) slot, 2 for the next one and so on.