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 7.4: A Game and a Simulator

About This Page

Questions Answered: How about some more practice? How will I manage with a bigger program with multiple classes?

Topics: The chapter consists of two assignments with a points value and third one that’s optional. The assignments feature inheritance and collection methods, among other things. There’s an example of using inheritance for refectoring.

What Will I Do? Study given code and program.

Rough Estimate of Workload:? Five hours? This will vary greatly from person to person, but in any case, this should be the most time-consuming chapter in Week 7 by some distance.

Points Available: B60 + C60.

Related Projects: Viinaharava (new), Segregation (new). AuctionHouse2 (new) in the optional assignment.

The Game of Viinaharava

A game of Viinaharava in progress. Some of the glasses have been drunk; those squares either contain a number indicating the number of neighboring booze glasses or are empty to indicate that there is no booze in the immediate vicinity. (Yes, it’s a different-looking Minesweeper.)

The local temperance society has commissioned a game that promotes water as a healthy drink. To that end, a game named Viinaharava has been designed; its implementation is more or less ready but needs you to flesh it out.

Viinaharava takes place on a board that consists of small drinking glasses arranged in a grid. Most of them contain water but a few contain a stiff, transparent alcoholic drink: a “booze”. The player’s task is to drink all the water glasses without touching a booze.

The player virtually drinks a glass by clicking on it. Their task is simplified by the fact that there’s a hint at the bottom of each glass: the number of boozes in neighboring glasses. The game is over when either all the water or even a single booze has been drunk.

Task description

You’ll find a partially operational implementation for the game in the Viinaharava project. See below for an introduction.

Study this project and fill in the missing parts.

Recommended steps

1. Launch Viinaharava with the app object o1.viinaharava.gui.Viinaharava. Notice: the board shows up but the game doesn’t work.
2. Study the class o1.Grid, which has been used in Viinaharava’s implementation. See below for further information.
3. Familiarize yourself with the classes in package o1.viinaharava. Start from the overview of the package below, then turn to the Scaladocs and the source code.
4. Once you understand the program as given, add the missing parts. See below for additional instructions and hints.

Tools for representing grids

You’ll remember Snake from Chapter 6.2. In that game, the snake and its food were located on the spaces of a grid-like playing field, which we recorded as GridPos objects. Each GridPos was composed of two integers x and y, the pair of which pinpointed a space on the grid.

Viinaharava resembles Snake: it, too, has a playing field that is essentially a grid. We can again use GridPos as we represent the locations of each glass on the game board.

(In this assignment, you don’t have to concern yourself with pixels or graphics. The given GUI takes care of that. You can focus on modeling the rules of the game itself. It suffices to consider each location in terms of its position on the grid, a GridPos.)

In Snake, we had a “sparse” grid: there were few actual items (snake segments; food) in the grid compared to the total number of spaces. We represented the game’s state by simply tracking those GridPos coordinates that actually did contain something and considered each other space to be empty,

This time we’ll be different and represent game boards as “dense” grids. We’ll record, for every single space on the board, which kind of glass it contains: Is it a water glass or a booze? Have the contents been drunk already? How many dangerous neighbors does it have?

We’ll find it easier to represent dense grids if we adopt a tool designed for just that purpose, class Grid.

Class Grid

The o1 package provides a Grid class. Each Grid instance represents a grid that consists of elements of similar size that have been laid out in rows and columns; the elements could be glasses, for example.

The class has a number of methods for manipulating such grids. For instance, there are methods for picking out a particular element given its position (elementAt and apply), finding all the spaces that are adjacent to a given space (neighbors), and determining the grid’s dimensions (width, height, and size).

Grid is an abstract class. We can’t simply call new Grid; we need to instantiate it via a subclass. The abstract Grid class is designed to work in different applications that feature grids and GridPoses: it doesn’t specify what kind of spaces grids consist of. That’s something we’ll need to specify in a subclass.

Viinaharava is a particular use case for Grid: each game board is a grid that consists of objects that represent glasses. (In later assignments, we’ll use Grid to represent grids with other kinds of content.)

Overview of the project

Project Viinaharava contains two packages. We won’t go into the GUI package o1.viinaharava.gui and you don’t need to understand how it works; it’s enough that you find the app object there and use it to start the program. The parent package o1.viinaharava, on the other hand, is very relevant now.

Its two key classes are:

• Glass: instances of this class represent individual glasses that the game board consists of.
• GameBoard, a subclass of Grid: a GameBoard object represents an entire game board, a grid of Glasses.

The diagram below describes the relationships between the classes:

The lower part of the diagram means that each game board is associated with multiple glasses, each at its particular position: we can use a GridPos to pick out a particular Glass on a GameBoard.

Glass and its missing methods

Each glass can be either full or empty. It can be either a glass of water or a glass of booze. Moreover, each Glass object keeps track of how dangerous it is: how many boozes there are in the adjacent glasses. The danger level is a number between zero and eight; diagonally adjacent counts, too.

Glass objects have instance variables for recording their contents and danger level. Each glass also “knows” which game board it’s on and which GridPos it’s at.

When created, a glass is full of water. The Glass class is supposed to have methods for modifying that initial state. Specifically:

• We should be able to fill a glass with booze (pourBooze). This has the additional effect of increasing the danger levels of neighboring glasses. pourBooze is called several times at the start of each game to place the hidden booze on the board. (For testing purposes, the GUI also lets the player add booze during a game.)
• We should be able to empty a glass. The drink method is invoked whenever the user (left-)clicks a glass in the GUI. If the player hits booze, all the other booze on the board is immediately drunk as well (and the game is over).

However, pourBooze and drink don’t have proper implementations in the given code, which is why the game doesn’t do anything when clicked. The neighbors method, which is supposed to find the adjacent glasses, is also missing.

GameBoard and its missing methods

Here’s a start for the GameBoard class:

class GameBoard(width: Int, height: Int, boozeCount: Int) extends Grid(width, height) {
  // ...

A new GameBoard instance needs three constructor parameters: the number of columns on the grid, the number of rows, and the number of booze glasses initially hidden on the board.

Initializing any Grid object requires a width and a height. We pass these two parameters on to the superclass.

The class header needs one more thing before it works. This is because the superclass Grid demands a type parameter in addition to the constructor parameters. Just like we have used square brackets to mark the element type of a Buffer, we can mark the element type of a Grid:

class GameBoard(width: Int, height: Int, boozeCount: Int) extends Grid[Glass](width, height) {
  // ...

A GameBoard object is a Grid whose elements are Glass objects.

As you saw when you launched the game, the given implementation already fills the board with water glasses. A further inspection of the given code in GameBoard.scala shows us how:

class GameBoard(width: Int, height: Int, boozeCount: Int) extends Grid[Glass](width, height) {

  def initialElements = {
    val allLocations = (0 until this.size).map( n => GridPos(n % this.width, n / this.width) )
    allLocations.map( loc => new Glass(this, loc) )
  }

  this.placeBoozeAtRandom(boozeCount)

As the documentation says: this method, which produces a collection of all the elements that initially occupy the grid, is left as abstract by the superclass Grid. (However, the superclass automatically calls this method when a new Grid is created.)

The subclass GameBoard implements the method by returning a collection of empty Glasses. Feel free to study this implementation, but it’s not strictly necessary for the present assignment. Don’t change this method.

The placeBoozeAtRandom call written directly into the class body is part of the code that initializes new instances of GameBoard (i.e., the class’s constructor). The method is invoked every time a new GameBoard is created.

The aforementioned placeBoozeAtRandom method doesn’t have an implementation yet, so there’s no booze on the board. That will require your attention. The isOutOfWater method is also missing; it’s needed for determining when the game is over.

What follows is a suggestion of how you may tackle with the assignment in three steps.

Recommended step 1 of 3: water

In Glass.scala, write the missing if branch of the drink method that deals with water glasses. Not much to do there.

Then implement isOutOfWater in GameBoard.

• For easy access to all the glasses on the game board, you can use the allElements method that GameBoard inherits from Grid.
• If you pick the right higher-order method (from Chapter 6.2), the implementation will be quite simple.

Try running the game again. You can now empty glasses to your heart’s content. Once all the water is gone, the app lets you know. The game still lacks the booze and the consequent suspense.

Recommended step 2 of 3: placing the booze

Implement neighbors on Glass. Hint: use an existing method for a very simple solution.

Then write the pourBooze method in the same class. Once that’s done, it’s possible pour booze in glasses and thereby adjust the danger levels of neighboring glasses. The actual game still works as before, however, since the newly implemented method doesn’t get called.

Switch your attention to placeBoozeAtRandom in class GameBoard, a private method. Implement this method so that it selects a random set of glasses and pours booze in them. The method should randomize the glasses in such a way that each new game (each new GameBoard) is unpredictable.

Here are two different ways to approach the problem. Feel free to pick either of them, or come up with something else, as long as your method works.

Algorithm #1:

1. Use a random-number generator to pick a pair of coordinates.
2. Find out if those coordinates already contain booze.
   • If so, do nothing.
   • If not, pour booze there.
3. Keep repeating steps 1 and 2 until the target number of booze glasses is reached.

Which one is better?

If you want, you can reflect on which of these two algorithms demands more work (time) from the computer. How does the amount of work depend on how big the game board is and how many booze glasses you intend to place?

Algorithm #2:

1. Form a collection that contains each of the glass objects.
2. Shuffle the collection so that the glasses are in random order. (It’s possible to write, say, a loop that does this, but you can also use the convenient method Random.shuffle; see below for an example.)
3. Take the desired number of glasses from the collection. Pour booze in each of those glasses.

Here’s an example of shuffle:

import scala.util.Randomimport scala.util.Random
val numbers = (1 to 10).toVectornumbers: Vector[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
Random.shuffle(numbers)res0: Vector[Int] = Vector(8, 9, 7, 4, 6, 1, 10, 2, 5, 3)
Random.shuffle(numbers)res1: Vector[Int] = Vector(8, 6, 4, 5, 9, 1, 3, 7, 2, 10)

Recommended step 3 of 3: drinking

Try running the program again. It should be more or less playable now, but let’s make one more change.

When the player hits a booze glass and the game is over, we’d like the game to reveal (i.e., empty) all the booze glasses on the board.

Write the branch of the drink method that deals with booze glasses.

• Make use of boozeGlasses in class GameBoard, which returns all the booze glasses on the board in a vector.
• You can empty each booze glass by adjusting its isFull variable. (There is no need to call the drink method from within itself.)

Try the program.

One drink per click, please

When the player clicks on a water glass and reveals that it had a danger level of zero, one can safely drink all the neighboring glasses as well. Perhaps you’d like the program to do so automatically without the player having to click on each safe neighbor separately. In Chapter 11.2 we’ll do just that with the help of a technique known as recursion.

Submission form

A+ presents the exercise submission form here.

Citizens in a Simulator

Our simulator is based on a grid that represents a city map. Each location on the grid is an address that a citizen (or family) can move into. Blue and red represent different demographics. Addresses marked in white are currently vacant.

One of the most powerful things about programming is that you can create dynamic models of phenomena and processes in the real world. In this assignment, we’ll form a computational model of a social phenomenon. You’ll take control of an application that simulates people’s movements on a city map; in particular, this simulation will explore how demographics may impact on the social layout of a city.

In this context, a demographic is any subset of the city’s population that the citizens may perceive to be relevant as they assess their own neighborhood. For instance, we can split the citizens in demographics on the basis of their financial status, political views, ethnic background, or age. In this chapter, our simulator will have only two demographics, red and blue. In Chapter 9.2, we’ll extend the simulator to support more demographics.

At the start of each simulation run, we place red and blue citizens at random addresses on the city map. The simulation then advances in steps: at each step, the citizens assess how satisfied they are with their current neighborhood and may decide to move to a vacant address instead of remaining where they are. A citizen is satisfied in case a sufficiently large proportion of their neighbors belongs in the same demographic.

This model is based on the work of Thomas Schelling, a winner of the Nobel Prize in Economics. Naturally, it is a simplification of the real world; models are.

Let me remind you of the particular characteristics of all of these behavior systems[.] It is that people are impinging on other people and adapting to other people. What people do affects what other people do.

—Thomas Schelling

Segregation-projekti

Project Segregation contains two packages. The simulation model itself is in package o1.segregation, whose main contents are:

• Simulator (partial implementation given). You can ask a simulator object to launch a new simulation run (startNew) or advance the most recently launched simulation by one step (moveResidents). The simulator delegates some of its work to another object that represents the map of the city and is of the type:
• CityMap (ready as given). A city map is a grid, and CityMap inherits Grid much like GameBoard did in the previous assignment. Each of the elements in this grid is of the type:
• Demographic (missing entirely). This simple sealed trait serves as a supertype for an Occupied class and a singleton Vacant, which represent occupied and vacant addresses, respectively.

The classes in o1.segregation.gui define the user interface, which you can safely ignore apart from the fact that SimulatorApp is an app object: it creates an instance of Simulator and calls its methods when the user presses the buttons in the GUI and slides the sliders.

Here’s a diagram of these components:

Task description

Add the trait Demographic and its subordinate concepts Occupied and Vacant.

Add the methods findDemographic, dissatisfiedResidents, and moveResidents in class Simulator. (The residents method is also missing but we’ll leave that for later.)

Run the program, experiment with different settings in the UI, and consider how they affect the results.

Instructions and hints

On Demographic trait:

• This is an exceedingly simple trait: it doesn’t have any methods at all.
• Occupied and Vacant just need an extends, and that’s about it.
• Seal the trait with sealed (Chapter 7.2). Once you do, any Demographic is guaranteed to be either an Occupied object or Vacant.
• The outcome is a set of types that resemble the Option class and its derivatives Some and None. And indeed we could have used Option here instead. However, Demographic and its subtypes communicate our model better.

On the findDemographic method:

• Note that the cityMap instance variable in Simulator gives you a reference to currently active map, which is a CityMap object that contains Demographic objects in a grid pattern.
• This method is pretty simple to implement once you find the right tools in the documentation of Simulator and/or CityMap.

On the dissatisfiedResidents method:

• A citizen’s satisfaction depends on whether the percentage of similar citizens among the citizen’s neighbors is high enough. The desired percentage, which the end user sets with a slider in the GUI, is available to you as a number between 0 and 100 in the variable similarityDesired.
• Every address does not have the same number of neighbors. Note the details in the Scaladocs.
• Try to split the method’s overall task in subtasks. For instance, one subtask could be to examine whether the neighborhood of an address is unsatisfactory.
• Consider writing auxiliary functions for the subtasks. You can define them either as private methods or as local functions within dissatisfiedResidents.
• Again, make use of what the CityMap object gives you. Keep in mind that a CityMap is a sort of Grid and has all the methods it inherits from its superclass.
• If you use division, remember that any and all decimals are discarded when you divide an Int by an Int.

On the moveResidents method:

• Make use of the two other methods you implemented.
• You may find Random.shuffle useful again (see Viinaharava above), as well as other methods in class Random (see Chapter 3.5).

Additional hint for moveResidents

Show the hintHide the hint

Here’s an outline of a solution:

1. Form a buffer that contains the addresses of all vacant homes.
2. Form a collection that contains the locations of all the unsatisfied residents, in random order.
3. Repeat for each unsatisfied resident: Pick a random address from the buffer of vacant homes. Move the resident to that address on the CityMap. In the buffer, replace that destination address with the vacated address.

Use the app

Run the simulator on the default settings. Press Single Step repeatedly to advance the simulation. Try Run, too. Note that the satisfaction threshold is set at 70%, meaning that the citizens are very easily dissatisfied with their neighborhood.

Try higher and lower values for the threshold.

It seems obvious that if the citizens demand a great number of neighbors similar to themselves, they end up living among their own demographic. Something that’s not equally obvious is how demanding the citizens need to be for the phenomenon to occur. Explore and find out.

Could we use a similar model to explain the “echo chambers” on social media?

What real-world factors are ignored by this model?

What would happen if one demographic cares about what their neighbors are like but the other is always or almost always satisfied? Or what if the citizens didn’t just set a minimum but also a maximum for the degree of similarity between themselves and their neighbors?

Submission form

A+ presents the exercise submission form here.

In case this assignment piqued your interest

The book Networks, Crowds, and Markets: Reasoning About a Highly Connected World, which is available as a free online edition, will tell you more about computational modeling of social, economic, and medical phenomena, among other things. The Schelling model we just used features in Chapter Four of the book.

Reimplementing Auctions with Inheritance

The rest of this chapter consists of an assignment that revisits our earlier auction-themed programs. The programming assignment itself is optional, but we highly recommend that you at least read what it’s about.

In Chapter 4.4, you presumably wrote FixedPriceSale and may have also written DutchAuction and EnglishAuction. These classes represents items put up for sale in a variety of ways. Then, in Chapter 5.3, we designed AuctionHouse to represent auction houses where all the items are sold in the traditional “English” style.

You can use your own earlier solutions as a basis for the upcoming assignment. If you didn’t do some or all of them, feel free to use the example solutions (FixedPriceSale, DutchAuction, EnglishAuction).

A new class hierarchy

Here’s how the existing classes relate to each other:

In other words: an AuctionHouse contains EnglishAuctions. The classes FixedPriceSale and DutchAuction are unconnected to the others.

In this assignment, you’ll refactor the classes. The purpose of refactoring is to improve program quality: you’ll modify FixedPriceSale-, EnglishAuction, and DutchAuction so that it’s easier to use them all in combination. At the same time, you’ll eliminate a great deal of redundant code. In this exercise, inheritance (Chapter 7.3) will be your main refactoring tool.

The goal is a hierarchy of classes that looks like this:

At the heart of our plan is the abstract class ItemForSale, which will serve as a generic superclass for items being sold in all sorts of ways. We’ll be able to use this superclass to write a more generic AuctionHouse class. We’ll also introduce an InstantPurchase class to capture what fixed-price items and Dutch-style auctions have in common.

Implement the refactoring

Implement ItemForSale, EnglishAuction, InstantPurchase, FixedPriceSale, DutchAuction, and AuctionHouse so that they match the documentation provided in project AuctionHouse2.

Instructions and hints

• We recommend implementing the classes in the order listed above.

• As you read the Scaladocs, be sure to note which classes and methods are abstract and which methods each class inherits from its superclass(es).

• Just like in Chapter 7.3: if a superclass already defines a concrete instance variable, don’t repeat the val in the subclass. For instance, the description variable is defined in the superclass ItemForSale, so don’t redefine it as a val in the subclasses, even though the subclasses do need a description as a constructor parameter.

• You can use the given test app to try some of the key methods. You’ll notice that the app object o1.auctionhouse.gui.TestApp generates a bunch of error messages to begin with, but they’ll vanish once you make the requested changes.

  

• In the AuctionHouse class, you’ll need to replace EnglishAuction with a more general type, but that’s the only change needed there.

Submission form

A+ presents the exercise submission form here.

Once you finish the assignment, pause for a moment to admire the results: inheritance turned the disconnected and redundant classes into a beautiful conceptual model. The definition of each concept (class) includes only what is necessary to distinguish it from related concepts.

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.

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 for this page

The assignment on Schelling’s model of social segregation is an adaptation of a programming exercise by Frank McCown.

Posting submission...

×

Identical submission

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

Cancel Submit