Exercise 1 (for discussion)#

Determine which kind of behavior would be displayed by each of the following (stack, queue). Justify your answers.
a) Names of tutors at St Custard’s Tutorial College where tutor first to be laid off (made redundant) is a longest-serving tutor.
b) Names of employees at Fosdyke’s Mill where employee first to be laid off (made redundant) is most recently taken on.
c) letters awaiting sorting in a postal sorting office.

Exercise 2 – Fortress Patience#

The rules of Fortress Patience are shown on the next page.
a) Get familiar with how the game is played - see the rules on the web page, but ask your tutor if anything is unclear.
b) Spot which card arrangement(s) might involve a …stack? …queue? …list? …array?
For any stack you find, identify the top of the stack.
For any queue you find, identify the front and back of the queue.

Check your answers with your practical tutor to see if you’re right, before continuing.

Exercise 3 – Set-up#

Create a new, empty project. Be careful to untick the box that asks you if you want to create a main class. Download the practical start code from the Students Website and paste it into the /src file of your new project.

You should now have the project ready to go. The files it contains are as follows:

• Patience.java – the main file (no need to look at this file)
• Card.java – a class to represent a playing card (look, but don’t alter)
• CardStack.java – a class representing an arrangement of playing cards with stack-like behavior (look, but don’t alter)
• Rules.java – where you will write the code for the rules of the game
• Controller.java – the class that draws and controls the visual display (no need to look at this file)
• GameDisplay.java – the class that specifies the user interaction with the game and how the stacks are to be displayed
• StackDisplayInfo.java – a container class that stores details of how to display the stacks graphically
• PictureCards.java – a class that provides drawing methods for J,Q,K cards (no need to look at this file)

Try compiling and running the program – if it asks you to set a main class, just select Patience as the main class. The program should compile and run ok, and produce a random layout of cards for the game, but it won’t allow any cards to be moved yet.

Exercise 4 – Code Inspection#

a) Take a look at the Card class, see how it represents a card, and see what methods it has. It’s well-commented, so you should be able to understand everything, but ask your practical tutor if there’s anything you’re unclear about.

b) Similarly, take a look at the CardStack ¹ class. You should find standard stack methods available.

c) The Rules class is where you’re going to be writing code. Part of this class shuffles and deals the cards (this bit is written for you), and you are going to write the code to allow card moves according to the rules of Fortress Patience.

Within the Rules class, notice the data structures foundations and rows used to hold the arrangements of cards. Here’s a diagram to show you which part of the layout of cards corresponds to which bit of these two data structures:

d) You are going to be implementing the following two methods in the Rules class:

• moveRowCardToFoundationIfPossible
  called every time called the user tries to move the uppermost card of a row to one of the foundation piles
• moveRowCardToRowIfPossible
  called every time the user tries to move the uppermost card of a row to another row

Look at their descriptions, in particular their pre-conditions and post-conditions, and check that you are clear about what each method is supposed to do.
Run the program again, trying to clicking on cards in attempts to move them, and watch what appears in the Output window – you should see it state when it is calling one of these methods. That should help to make it clear when one of these methods is being called.

Exercise 5 – Moving cards#

A good place to start is to write code to move the cards, without worrying about whether a move is allowed or not according to the rules of the game. So, for each of the two methods listed above, implement a simple move of the correct card to where the user tried to move it to, ignoring the rules for now.
Test your code by running the program and checking that the card does move in the right fashion.
Hint:

• You’ll have to think how to refer to where the card is going from, and how to refer to where the card is going to. You’ll also have to think about which operation(s) might be useful for removing a card from where it is currently, and how you can move the card to the correct destination.

Exercise 6 – Card moves between rows#

Now change your code for the moveRowCardToRowIfPossible method so that it incorporates the rules for moving the uppermost card of a row onto another row, only moving the card when it’s supposed to move according to the rules of Fortress Patience.
Hints:

• Make sure you are clear about what the rules say for a card move in between rows. If you are not sure about what the rules say, ask your tutor.
• Try implementing the restriction on card colors first, then worry about their ranks. Look carefully at what the rules say about card rankings!
• You’ll have two cases to deal with: when the destination row is empty, and when there’s one or more cards there already.
• Note the preconditions for some of the stack methods, and be careful that you don’t call a method with the precondition “The stack is not empty” when the stack is, in fact, empty. If you do violate the precondition, what happens?
• You may find it helpful to write a method to find out whether the rank of one card is one higher than the rank of another card (remember the “wraparound” rule).
• Try and test whether your method works, by running the program and trying lots of card moves between rows. Be sure to check not only that a card gets moved from the correct row to the correct destination row when it is supposed to be, but also check that when a card is NOT supposed to move, that it does indeed remain unmoved.
• Also test what happens when you try and move a card to an empty row. As you’ve not yet implemented rules for moving of cards to foundation piles, you should be easily able to move all the cards in a row out of the way to empty it and thus test this aspect of your code.

Exercise 7 – Card moves to foundation piles#

Now change your code for the moveRowCardToFoundationIfPossible method that moves a card from a row to a foundation pile, and incorporate the rules about suit-matching (not color-matching this time!) and rank when adding to a non-empty foundation. (For the moment, allow any card to be moved to an empty pile: the restrictions on moving a card to an empty pile are addressed in the exercise below.)
Hints: see the hints for the previous exercise, and test similarly.

Exercise 8 – Card moves to foundation piles#

Further change your code for the moveRowCardToFoundationIfPossible method so that it also incorporates the restriction for moving a card from a row to an empty foundation pile: a card can’t be moved to an empty foundation pile if there is already a foundation pile for that suit.
Hint:

• You will need to be creative to think of how you can examine the other foundation piles and figure out whether there is already a foundation pile for the relevant suit.

Exercise 9 - Enjoy a nice game of Fortress Patience ☺︎#

1
/** This method is called when the user tries to move the uppermost
2
  * card of the r-th row, to the f-th foundation pile.
3
  *
4
  * Pre:  0<=r<10    (i.e. the index of the row is within range)
5
  *       && 0<=f<4    (i.e. the index of the foundation is within range)
6
  *       && !rows[r].isEmpty() (i.e. there is at least one card in the row)
7
  *
8
  * Post: If the rules permit, the uppermost card of the r-th row
9
  *       been moved onto the f-th foundation pile, leaving all other
10
  *       cards where they were.
11
  *       If the rules do not permit this move, all cards are left
12
  *       exactly where they were before.
13
  */
14
    public void moveRowCardToFoundationIfPossible(int r, int f) {
15
        // Pre-conditions guaranteed by caller: r in range, f in range, and rows[r] not empty
16
        CardStack source = rows[r];
17
        CardStack dest = foundations[f];
18
        if (source.isEmpty()) return; // defensive
19

20
        Card top = source.peek();
21

22
        // If destination foundation is empty: any card may be placed
23
        // provided there is not already a foundation pile for that suit.
24
        if (dest.isEmpty()) {
25
            // check other foundations for same suit
26
            for (int i = 0; i < foundations.length; i++) {
27
                if (!foundations[i].isEmpty()) {
28
                    Card ft = foundations[i].peek();
29
                    if (ft.getSuit() == top.getSuit()) {
30
                        // there's already a foundation pile for this suit
31
                        return;
32
                    }
33
                }
34
            }
35
            dest.push(source.pop());
36
            return;
37
        }
38

39
        // Otherwise, can place if same suit and rank is one higher than foundation top
40
        Card destTop = dest.peek();
41
        if ((top.getSuit() == destTop.getSuit())
42
            && isOneHigher(top, destTop)) {
43
            dest.push(source.pop());
44
        }
45
    }
46

47

48
/** This method is called when the user tries to move the uppermost
49
  * card of the r1-th row, onto the uppermost end of the r2-th row.
50
  *
51
  * Pre:  0<=r1<10    (i.e. the index of the source row is within range)
52
  *       && 0<=r2<10  (i.e. the index of the destination row is within range)
53
  *
54
  * Post: If the rules permit, the uppermost card of the r1-th row has
55
  *       been moved onto the uppermost end of the r2-th row, leaving all other
56
  *       cards where they were.
57
  *       If the rules do not permit this move, all cards are left
58
  *       exactly where they were before.
59
  *
60
  */
61
    public void moveRowCardToRowIfPossible(int r1, int r2) {
62
        // Pre-conditions guaranteed by caller: r1 and r2 are within 0..9
63
        CardStack source = rows[r1];
64
        CardStack dest = rows[r2];
65

66
        // nothing to do if source empty
67
        if (source.isEmpty()) return;
68

69
        Card moving = source.peek();
70

71
        // Case 1: destination empty. In Fortress Patience only a King may be placed
72
        if (dest.isEmpty()) {
73
            if (moving.getRank() == Card.KING) {
74
                dest.push(source.pop());
75
            }
76
            return;
77
        }
78

79
        // Case 2: destination non-empty. Build down by same color,
80
        // and the destination top must differ in rank by exactly 1 (wraparound allowed)
81
        Card destTop = dest.peek();
82
        // colors must be the same
83
        if (!moving.getColour().equals(destTop.getColour())) return;
84

85
        // rank must differ by exactly 1, with wraparound (K<->A)
86
        if (isAdjacentRank(moving, destTop)) {
87
            dest.push(source.pop());
88
        }
89
    }
90

91
    /** Returns true if card a's rank is exactly one higher than card b's rank.
92
      * Accounts for wraparound: Ace is considered one higher than King.
93
      */
94
    private boolean isOneHigher(Card a, Card b) {
95
        int ra = a.getRank();
96
        int rb = b.getRank();
97
        if (ra == rb + 1) return true;
98
        // wraparound: Ace (1) is one higher than King (13)
99
        if ((ra == Card.ACE) && (rb == Card.KING)) return true;
100
        return false;
101
    }
102

103
    /** Returns true if the ranks of a and b differ by exactly 1, accounting for wraparound.
104
      * Examples: (7,6)->true, (5,6)->true, (A,K)->true, (A,2)->true.
105
      */
106
    private boolean isAdjacentRank(Card a, Card b) {
107
        int ra = a.getRank();
108
        int rb = b.getRank();
109
        if (Math.abs(ra - rb) == 1) return true;
110
        // wrap cases: Ace (1) adjacent to King (13)
111
        if ((ra == Card.ACE && rb == Card.KING) || (ra == Card.KING && rb == Card.ACE)) return true;
112
        return false;
113
    }

Introduction#

In this week’s exercise, we will create code to represent graphs that have features resembling those found on social networking sites like Facebook.

This uses the idea of a “friendship graph” to let you explore representing graphs and doing some useful things with graphs. For example, here’s an (undirected) graph depicting friendships between various people:

For simplicity, all people in the example graphs you’ll use will have different names.

Exercise 1 – Warm-up#

As you will shortly be using adjacency matrices, remind yourself of the concept by stating the adjacency matrix for the above graph:

Exercise 2 – Project set-up#

Set yourself up a project from the existing sources supplied on the Students Website, in the usual way.

You’ve been supplied with four code files:

• NotFacebook.java – the main program where you’ll write code to call various methods on sample graphs
• FriendsGraph.java – a class for representing (undirected) graphs where the nodes are people and the edges are friendships between people.
• Node.java – a small container class for representing a node of the graph (which you do not need to alter)
• GraphUtilities.java – a class for reading in graphs from files and drawing them on the screen (you don’t need to alter the code in this file).

Run the program (the main method is in the NotFacebook class), to check that the project is set up ok. You’ll be asked to select a file containing a description of a graph.
You have been supplied with three sample graphs, in files graph1.txt, graph2.txt and graph3.txt, so choose one of those. You should find that the nodes of the graph above are displayed, but none of the edges!
Note: for the following exercises, do not change the data structures supplied; use the ones provided for you in the code you’ve been given.

Exercise 3 – Adding Edges#

Getting the edges to appear requires two steps:

1. First, implement the private addEdge(int node1, int node2) method of the FriendsGraph class (the empty body of the method is supplied for you already).
   To do this, you’ll need to look carefully through the FriendsGraph class and see how the nodes and edges are stored using an adjacency matrix, and how the other addEdge method of the FriendsGraph class works. You may need to also look up and remind yourself of how two-dimensional arrays are declared and used in Java: as you will see, the adjacency matrix is a two-dimensional array.

1
private void addEdge(int node1, int node2) {
2
    // simple bounds check to help catch incorrect usage
3
    if (node1 < 0 || node1 >= size || node2 < 0 || node2 >= size) {
4
        throw new IndexOutOfBoundsException("Node index out of bounds: " + node1 + " -> " + node2);
5
    }
6
    adjacencyMatrix[node1][node2] = true;
7
}

2. To make the edges appear, also implement the following method of the FriendsGraph class:

1
/** Returns true if there is an edge from the first node to the second.
2
  *
3
  * @pre           0 < node1, node2 < size
4
  * @param node1   the source node of the queried edge
5
  * @param node2   the target node of the queried edge
6
  * @return        true iff there is an edge node1 -> node2
7
  */
8
public boolean edgeFrom(int node1, int node2)

1
public boolean edgeFrom(int node1, int node2) {
2
    // simple bounds check to help catch incorrect usage
3
    if (node1 < 0 || node1 >= size || node2 < 0 || node2 >= size) {
4
        throw new IndexOutOfBoundsException("Node index out of bounds: " + node1 + " -> " + node2);
5
    }
6
    return adjacencyMatrix[node1][node2];
7
}

Check that your methods work ok by viewing all three sample graphs.

Exercise 4 – Finding the index of a node#

Add to the FriendshipGraph class a method with the following signature and specification.

1
/**
2
 * Get the index of a node
3
 * @param name name of a person in the graph
4
 * @return the index of the node that represents the named
5
 * person, if they are in the graph, otherwise -1
6
 */
7
public int getNodeIndex(String name)

1
public int getNodeIndex(String name) {
2
    Integer idx = nodeMap.get(name);
3
    return (idx == null) ? -1 : idx;
4
}

Note that you can make use of the nodeMap field.

Exercise 5 – Friendship Testing#

Add to the FriendGraph class a method with the following signature and specification.

1
/** Returns true precisely when the two people are in
2
  * the graph and are listed as friends.
3
  * @pre             true
4
  * @param person1   the first person
5
  * @param person2   the second person
6
  * @return          true if these two people are friends
7
  *                  in the graph
8
  */
9
public boolean areFriends(String person1, String person2)

1. Now test your method by writing several tests in the main method of the NotFacebook class, like this:

1
if (g.areFriends("Remi","Victoria"))
2
    System.out.println("Remi and Victoria are friends.");
3
else
4
    System.out.println("Remi and Victoria are not friends.");

Please note that these tests are best placed before the line

1
        GraphUtilities.showGraph(g);

so that the results of your tests will be visible at the same time as the graph pop-up window.

1
public boolean areFriends(String person1, String person2) {
2
    int idx1 = getNodeIndex(person1);
3
    int idx2 = getNodeIndex(person2);
4
    if (idx1 == -1 || idx2 == -1) return false;
5
    return edgeFrom(idx1, idx2);
6
}

Exercise 6 - Depth-First Traversal#

Create a new class GeneralUtilities, and add a method, with the following signature

1
/**
2
 * Perform a depth first traversal of a graph, printing out the
3
  * name of each node visited
4
  * @param g Graph to be traversed
5
  * @param startName Name of the first person to be printed out
6
 */
7
public static void depthFirstTraversal(FriendsGraph g, String startName)

that uses a recursive algorithm to traverse the graph in a depth-first way, printing out all the names of the people found in the graph. (Using System.out.println statements to do this is fine). An easy way to do that would be to use a modified version of the dft algorithm described in the lecture slides, with the following signature

1
private static void dft(FriendsGraph g, int i, Set<Integer> visited)

The parameter i is the index of a node in the graph, and the Set visited is used to keep track of which nodes have been visited. You can then implement the depthFirstTraversal method by simply calling the dft method with argument i set to be the index of the node with the specified name, and visited to an empty HashSet.

Modify the NotFaceBook class so that it calls this method immediately before the line GraphUtilities.showGraph(g);

N.B. we want a recursive solution to this problem.

Also N.B. You should not implement these methods in the FriendsGraph class.

1
public static void depthFirstTraversal(FriendsGraph g, String startName) {
2
    if (g == null) return;
3
    int startIdx = g.getNodeIndex(startName);
4
    if (startIdx == -1) {
5
        System.out.println("depthFirstTraversal: start node '" + startName + "' not found in graph.");
6
        return;
7
    }
8
    Set<Integer> visited = new HashSet<Integer>();
9
    dft(g, startIdx, visited);
10
}
11
private static void dft(FriendsGraph g, int i, Set<Integer> visited) {
12
    System.out.println(g.getNode(i).getName());
13
    visited.add(i);
14
    for (int j : g.getAdjacentNodes(i)) {
15
        if (!visited.contains(j)) {
16
            dft(g, j, visited);
17
        }
18
    }
19
}

Optional Exercise 7 – Mutual Friends (more challenging!)#

Within the GeneralUtilities class create a method specified as follows:

1
/**
2
 * Returns a list of mutual friends of two people in a graph
3
 *
4
 * @param g The graph
5
 * @param person1 Name of first person
6
 * @param person2 Name of second person
7
 * @return a list of names of the mutual friends of the two
8
 * people, empty if one person is not in the graph or they have
9
 * no mutual friends
10
 *
11
 */
12
public static List<String> mutualFriends(FriendsGraph g, String person1, String person2

Mutual friends are people who are friends of both the given people. For example, in the graph on page 1, Lena and Victoria are the mutual friends of Guillaume and Tosan.
Include a few tests in the main method of the NotFacebook class to print out various lists of mutual friends for various people in (and not in) the graphs, and include a comment containing a copy-and-paste of your output from running the program, noting which graph it was that you were using.

1
public static List<String> mutualFriends(FriendsGraph g, String person1, String person2) {
2
    List<String> result = new ArrayList<String>();
3
    if (g == null) return result;
4
    int idx1 = g.getNodeIndex(person1);
5
    int idx2 = g.getNodeIndex(person2);
6
    if (idx1 == -1 || idx2 == -1) return result;
7

8
    // iterate over neighbors of idx1 and check if also neighbor of idx2
9
    for (int neigh : g.getAdjacentNodes(idx1)) {
10
        if (g.edgeFrom(idx2, neigh)) {
11
            result.add(g.getNode(neigh).getName());
12
        }
13
    }
14
    return result;
15
}