Practice problems for lecture 3

Goals:

• Practice with arrays.
• Practice with conditionals and for-loops.

Problem 1: CircleCountry (CircleCountry.java)

Circle Country is a country that contains several circular-shaped districts. Some districts may be situated inside other districts, but their borders do not intersect or touch. Zara is a resident of Circle Country. When she travels between two locations, she always tries to cross the fewest number of district borders as possible because crossing borders is usually a laborious task.

Imagine Circle Country as an infinite plane. You are given int[] x and int[] y and int[] r, where (x[i], y[i]) are the coordinates of the i-th district's center and r[i] is its radius. Zara is currently at point (x1, y1) and she needs to get to point (x2, y2). Neither of these points lies on a district border. Your task is to return the minimal number of district borders she must cross to get to her destination.

Constraints

• x will contain between 1 and 50 elements, inclusive.
• x, y and r will each contain the same number of elements.
• Each element of x and y will be between -1000 and 1000, inclusive.
• Each element of r will be between 1 and 1000, inclusive.
• x1, y1, x2 and y2 will be between -1000 and 1000, inclusive.
• No two circumferences will have common points.
• The points (x1, y1) and (x2, y2) will not lie on any of the circumferences.

Coming up with a solution

Consider the four colored circles and two points (one white, one black) diagrammed here. For each circle, the table is filled in so that the last column indicates whether that circle must be crossed in connecting the black point to the white point. Some of the table is filled in. Before starting to write code, complete the rest of the table related to # circles crossed for the points.

Helper methods

Developing helper methods can be a “helpful” practice of abstraction while programming and problem solving. A helper method isolates a piece of code apart from the method you're writing, often so that you can call the helper method more than once. Suppose you have a helper method isInside in the class CircleCountry - a starter for the method is shown below.

public boolean isInside(int x, int y, int cx, int cy, int r) { 
    // return the result of testing whether the square of the distance
    // from (cx, cy) to (x, y) is less than the square of the radius
    // fill this in here
}

Partial solution

Based on the table you filled in and ideas you developed for the isInside helper method, consider this partial solution:

int crosses = 0; 
// loop through all circles
for (int k = 0; k < x.length; k++) { 
    // if exactly one of (x1,y1) and (x2,y2) is inside circle k 
    // (specified by x[k], y[k], and r[k]) then increment crosses
    // fill this in here
} 
return crosses; 

Here are some examples you can use to test your code.

Example 1

{0}
{0}
{2}
-5
1
5
1
Returns: 0

Example 2

{0,-6,6}
{0,1,2}
{2,2,2}
-5
1
5
1
Returns: 2

Example 3

{1,-3,2,5,-4,12,12}
{1,-1,2,5,5,1,1}
{8,1,2,1,1,1,2}
-5
1
12
1
Returns: 3

Example 4

{-3,2,2,0,-4,12,12,12}
{-1,2,3,1,5,1,1,1}
{1,3,1,7,1,1,2,3}
2
3
13
2
Returns: 5

Problem 2: Access Level (AccessLevel.java)

In many computer systems and networks, different users are granted different levels of access to different resources. In this case, you are given int[] rights, indicating the privilege level of each user to use some system resource. You are also given int minPermission, which is the minimum permission a user must have to use this resource.

You are to return a String indicating which users can and cannot access this resource. Each character in the return value corresponds to the element of rights with the same index. 'A' indicates the user is allowed access, while 'D' indicates the user is denied access.

Constraints

• rights will contain between 0 and 50 elements, inclusive.
• Each element of rights will be between 0 and 100, inclusive.
• minPermission will be between 0 and 100, inclusive.

Example 1

{0,1,2,3,4,5}
2
Returns: "DDAAAA" because the first two users don't have sufficient privileges but the remainder do.

Example 2

{5,3,2,10,0}
20
Returns: "DDDDD" because no one has sufficient access.

Example 3

{}
20
Returns: "" because there are no users to check.

Example 5

{12,3,1,50,10}
1
Returns: "AAAAA" because all users have sufficient access.

Example 5

{34,78,9,52,11,1}
49
Returns: "DADADD" because 78 and 52 are greater than or equal to 49.

Coding your solution

Submission is not required, but once you understand the problems it should be fun to code your solutions!

1. Download the starter file practice03.zip (download here), double-click to unzip it, and then drag the practice03 folder to your cs201 folder.
2. Launch VS Code and open the folder practice03.
3. Edit CircleCountry.java to implement your solution to Problem 1.
4. Edit AccessLevel.java to implement your solution to Problem 2.