CSC 143/Chapter 10

Chapter 10: ArrayLists

Sections:

10.1 ArrayLists

10.2 Comparable interface

10.3 Case study: Vocabulary comparison

Section 10.1: ArrayLists

10.1 Definitions

Definitions:

• Generic class
• Wrapper class
• Boxing
• Unboxing

10.1 Materials

Introduce ArrayList object the way you would introduce the Python list

• List: basic data type, very important
• Difference between list and array - memory allocation and element insertion
• Dynamic arrays

Array notation

• Wrapper class, everything is an object, treat primitive types as objects

What kind of things would you want to do with an ArrayList?

Basic basic operations:

• Get size

Other basic operations:

• Get item at index i
• Set item at index i
• Add item, add item at index i
• Remove item
• Modify item at index i

Now that we have defined these basic operations, we can move on to examples/algorithms/implementations.

Section 10.2: Comparable interface

10.2 Definitions

Definitions:

• Comparison function
• Natural ordering

10.2 Materials

First, need to mention unboxing: ArrayList<Integer> vs ArrayList<int>

• Unboxing is a really stupid side effect of Java's implementation
• Everything is an object. Except the primitive types. But everything is an object.

Comparison of objects

• extend idea behind o1.equals(o2) to comparisons
• lt/lte/gt/gte
• how to redefine comparison operator for our own objects

Section 10.3: Vocabulary comparison

10.3 Material

Some efficiency considerations

Version 1: compute vocabulary

• Add unique words to ArrayList, and sort

Version 2: compute overlap

• Number of matches between two sentences

Version 3: complete program

• so far, build vocab list for 2 files, compute overlap between them
• now, to deal with large files, print statistics (Nwords, Noverlapwords, Percent overlap)

Chapter 10 Summary

Deliverables

ArrayList

• Notation, how to use it
• Conceptualizing problems that can be easily resolved with ArrayList
• Adding/removing and looping over ArrayLists
• Wrapper classes

Comparable

• Natural ordering and compareTo() function
• Implementing the Comparable interface

Case study: Vocab comparison

• Count number of unique words
• Count overlap between two lists
• Compute statistics

Chapter 10 Homework

HW Questions

(Recommended) Self-check problems: #3, #4, #5, #6, #7, #13, #16, #18, #21

(Required) Exercises: #1, #6, #15, #17

(Required) Projects: #2

HW Details

Self-check:

• 3, 4, 5, 6 - string list
• 7 - populating list in a loop
• 13 - syntax
• 16, 18 - mystery
• 21 - comparison

Exercises:

• 1 - average number vowels
• 6 - move item to front
• 15 - filter with int range
• 17 - interleave

Projects:

• 2 - reverse lines and word order in file

Chapter 10 Code

Lecture Code

Removing plural words

• how to index items in a list
• how to add items to a list
• how to remove items from a list

Comparable Point

• implementing comparable interface

Worksheet Code

Prisoners' Dilemma

In this worksheet, you'll be implementing a game as a Java class. This game will be based on a very famous game called the Prisoners' Dilemma.

The game begins in a prison ward, where 2 prisoners are being held. 1 prisoner is a member of the notorious Rainbow Ponies Gang, and 1 prisoner is a member of the equally notorious Plaid Socks Gang - the mortal enemies of the Rainbow Ponies Gang. One night, the prisoners escape using a secret passageway. But they are in the high-security ward, so they are quickly rounded up by the guards.

The guards want to know how the prisoners escaped, but they know the prisoners would never tell the guards. But they know that members of the Plaid Socks Gang and the Rainbow Ponies Gangs are mortal enemies. So they devise a sneaky plan:

• Each prisoner is placed in a separate room, so they cannot communicate.
• Each player is asked, independently, whether they will confess and reveal the location of the secret passageway, or remain silent.
• Each player has two options, and so there are four possible outcomes:
  • If both players reveal the location of the secret passageway, they will have 6 years added to their sentence.
  • If one player reveals the location of the secret passageway, and the other does not, the silent player is severely punished (10 years added to their sentence) while the other player has no change in their sentence.
  • If both players remain silent, they will each have 1 year added to their sentence.

For your game, you will implement the Prisoners' Dillemma and run it many different times (once for each pair of prisoners that escape). At the end of running all of the rounds, you will see which gang wins, that is, ends up with the least extra time added to their sentences: the Plaid Socks, or the Rainbow Ponies. One round of your game consists of a pair of prisoners deciding whether to confess or not.

Implementation details for the PrisonersDilemmaGame class are given below:

Instance variables

• ArrayList (N elements, one element for each Rainbow Pony Gang prisoners) storing the confession decision (confess the location of the secret tunnel, or not)
• AraryList (N elements) storing Rainbow Pony prisoners' extra prison time (if any was added)
• ArrayList (N elements, one element for each Plaid Socks Gang prisoners) storing the confession decision
• ArrayList (N elements) storing Plaid Socks prisoners' extra prison time (if any was added)

Constructors:

• Default constructor, no arguments, should pick a random number of gang members between 100 and 200.

Methods:

• void runOneRound // runs a single Prisoners' Dilemma round (one pair of prisoners)
• void runGame // runs the game for all N rounds. If game has already started, this will run the game to completion.
• void gameSummary // prints a brief summary of the game (see below)
• void addOneRound // adds an additional round and runs it

Accessors:

• int getCurrentTurn // get the current turn
• boolean isGameStarted // checks if at least one turn has been run
• boolean isGameFinished // checks if all turns have been run

gameSummary method: if game is in progress:

RAINBOW PONIES: 15 years     PLAID SOCKS: 17 years
The Rainbow Ponies Gang is in the lead after 10 rounds!

If the game is finished:

RAINBOW PONIES: 95 years     PLAID SOCKS: 88 years
The Plaid Socks Gang has won after 101 rounds!

Chapter 10 Goodies

Puzzle 3

Caesar encoded with numbers in blocks of 8

Puzzles/Crypto Level 2/Puzzle 3