1. Arrays

Arrays are important data structures that also appear indirectly in Java, for example in the enhanced for loop or variable argument lists. This chapter includes exercises on creating arrays, traversing arrays, and questions about algorithms, such as how to search for elements in an array.

Prerequisites

  • be capable of creating, accessing, and filling arrays

  • traverse arrays using an enhanced for loop

  • be able to use both one-dimensional and multidimensional arrays

  • be capable of constructing variable argument lists

  • understand the utility methods of the Arrays class

Data types used in this chapter:

1.1. Everything has a type

Before we look at accessing elements, let’s take a closer look at types. It is critical to understand the distinction between object type and reference type.

1.2. One-dimensional arrays

An array is a collection of homogeneous elements. One-dimensional arrays contain the elements directly and no other sub-arrays.

1.2.1. Loop arrays and output wind speed, wind direction ⭐

Captain CiaoCiao is sailing across the sea, the wind is blowing from all sides. He must always keep the wind speed and direction in mind.

Windy

Task:

  1. Declare two arrays int[] windSpeed and int[] windDirection.

  2. Fill both arrays each with three integer random numbers (in principle the number should be arbitrary), where the wind speed can range between 0 and (less than) 200 km/h and the wind direction can range between 0 and (less than) 360 degrees.

  3. Run a loop over the array and output all pairs comma separated.

Example:

  • For example, if the array windSpeed contains the values {82, 70, 12} and the array windDirection contains the values {12, 266, 92}, the output to the screen should be:

    Wind speed 82 km/h and wind direction 12°, Wind speed 70 km/h and wind direction 266°, Wind speed 12 km/h and wind direction 92°

Keep in mind that the segments are separated by commas and that there is no comma at the end.

1.2.2. Detect continuous revenue growth ⭐

At the end of a month, Captain CiaoCiao receives a report of the sales he and his crew have generated. The profit on any given day is recorded on the monthly list. It follows this format:

//                Day    1,    2,   3,    4,    5 ... up to a maximum of 31
int[] dailyGains  = { 1000, 2000, 500, 9000, 9010 };

Captain CiaoCiao is happy with the numbers, and he wants to pay a reward when gains have increased over 5%. From 1000 to 2000 is a whopping 100% jump, from 500 to 9000 is as well, but not from 2000 to 500, nor from 9000 to 9010.

Detect continuous revenue growth

Task:

  • Write a method int count5PercentJumps(int[]) that returns the number of sales jumps. A sales jump is given if the sales were 5% higher than the previous day.

  • The passed array must not be null, or an exception will be thrown.

1.2.3. Array of points ⭐

What is the expected output?

Point[] points = { null, null, null, null };
Point p = new Point();
p.setLocation( 1, 2 );
points[ 0 ] = p;
p.setLocation( 3, 4 );
points[ 1 ] = p;
Point q = points[ 1 ];
q.setLocation( 5, 6 );
points[ 2 ] = points[ 3 ] = q;
System.out.println( Arrays.toString( points ) );

1.2.4. Search consecutive strings and determine if Salty Snook is coming ⭐

Captain CiaoCiao watches the flags of passing ships because he is waiting for Salty Snook. He looks at each flag and knows that Salty Snook never comes alone, but moves in a convoy of four ships. He doesn’t know the flags themselves, only that they all have the same inscription.

Search consecutive strings and determine if Salty Snook is coming

Task:

  • Write a new method isProbablyApproaching(String[] signs) that returns true if there are four of the same abbreviation in the array consecutively in a row. Remember that strings are compared using equals(…​).

  • The array passed must not be null, and no element in the array must be null.

Example:

String[] signs1 = { "F", "DO", "MOS", "MOS", "MOS", "MOS", "WES" };
System.out.println( isProbablyApproaching( signs1 ) );   // true

String[] signs2 = { "F", "DO", "MOS", "MOS", "WES", "MOS", "MOS" };
System.out.println( isProbablyApproaching( signs2 ) );  // false

1.2.5. Reverse an array ⭐

Charlie Creevey does the finances for Captain CiaoCiao. However, rather than sorting the income in ascending order, he sorted it in descending order. As a result, the list must be flipped.

To flip an array means to swap the first element with the last element, the second with the second to last, and so on.

Task:

  • Write a new static method reverse(…​) that flips a given array:

    public static void reverse( double[] numbers ) {
      // TODO
    }
  • The operation should be in place, that is, it should change the array passed. We do not want to create a new array inside the method reverse(…​).

  • An exception will be thrown if null is passed.

Example:

  • { } → { }

  • { 1 } → { 1 }

  • { 1, 2 } → { 2, 1 }

  • { 1, 2, 3 } → { 3, 2, 1 }

The representation in the curly braces is purely symbolic.

1.2.6. Find the nearest cinema ⭐⭐

The class java.awt.Point represents points with x/y coordinates. This data type is excellent for positions.

The new movie »Under the flag of the buccaneers« is playing in the cinema, and Captain CiaoCiao must see it. But where is the nearest movie theater?

Task:

  • Given a set of Point objects in an array points for the cinema positions.

    Point[] points = { new Point(10, 20), new Point(12, 2), new Point(44, 4) };
  • Write a method double minDistance(Point[] points, int size) that returns the distance of the point that has the smallest distance to the zero point. With size we can specify how many array elements should be considered, allowing the array to be larger in theory.

  • A passed null is not allowed, also the points themselves must not be null; an exception must be raised.

  • What should we change if the return type is Point, implying that the point itself should be returned with the shortest distance?

Examine the Javadoc for java.awt.Point to see if the point can calculate distances to other coordinates.

1.2.7. Raid the candy store and share fairly ⭐⭐

Captain CiaoCiao and his children Junior and Jackie are robbing a candy store. The candy is displayed on a long shelf, and each item is labeled with its weight. The information is available as an array:

int[] values = { 10, 20, 30, 40, 50 };

Junior and Jackie are on opposite ends of the shelf, on the left and right, and because Captain CiaoCiao loves both kids equally, they should end up taking home the same amount. Captain CiaoCiao points to candy on the shelf, so all the products to the left of it go to Junior, and all the products to the right of the position (including the one shown) go to Jackie.

Captain CiaoCiao knows what’s on the shelf, but he doesn’t know where the same total will appear to the left and right.

Deviations of 10% are acceptable for children. We want to use the following formula for the relative difference for the difference:

private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}
Raid the candy store and share fairly

Task:

  • Write a method int findSplitPoint(int[]) that finds the index in the array where left and right can be fairly split. Any solution will do, not all solutions are necessary.

  • A method must return -1 if there is no fair split.

Examples:

  • 10 + 20 + 30 + 40 ≈ 40 + 50 because 100 ≈ 90, and the index for the return is 4.

  • 10 20 30 40 100 results in -1 because there is no valid partitioning.

1.3. Enhanced for loop

If arrays are to be run from the first element, an enhanced for loop with an invisible loop counter can be used for this purpose. This saves code.

In the following tasks, in some places it is possible to use an extended for loop.

1.3.1. Numbers well shuffled ⭐⭐

In the dice cup of Bonny Brain there are five game dice with the numbers 1 to 6. With a hearty shake and a mighty toss, the dice be spillin' onto the table like treasure from a loot chest, revealing their fateful numbers for all to see.

Numbers well shuffled

Task:

  • Write a method int[] shuffleDice() that returns an int array with 5 random numbers that are between 1 and 6.

  • Write a method isHomogeneous(int[] values) that tests if all values in the array are equal. (The word homogeneous means uniform/similar/equal). In principle, the array may be of any size.

  • Write a method int[] occurrences(int[] values), which returns a new array of size 6, which indicates which number occurs how often.

  • Write a method isFullHouse(int[] values) that checks if three dice have the same value and two other dice have a different same value. For example, {1, 1, 1, 2, 2} is such a case.

  • Write a method void printDiceValues(int[] points) that writes the dice numbers to the screen as follows:

    • the numbers are sorted in ascending order

    • the numbers are grouped together

    • instead of the eyes as simple numbers on the screen, use the Unicode symbols ⚀ (Unicode character U+2680), ⚁ (U+2681), ⚂ (U+2682), ⚃ (U+2683), ⚄ (U+2684), ⚅ (U+2685).

We can assume that the methods are always called with correct values, so the array is never null, the number of elements is always correct, and the values are always in the valid ranges.

Examples:

  • isHomogeneous(new int[]{ 1, 1, 1, 1 }) returns true.

  • isHomogeneous( new int[]{ 1, 1, 1, 2, 2 } ) returns false.

  • occurrences( new int[]{ 1, 1, 2, 3, 4 }) returns an array with the values {2, 1, 1, 1, 0, 0}.

  • isFullHouse(new int[]{ 1, 1, 1, 2, 2 }) returns true.

  • isFullHouse(new int[]{ 1, 1, 1, 1 }) returns false.

  • printDiceValues(shuffleDice()) returns 2 × ⚁, 2 × ⚃, ⚅.

1.3.2. Draw mountains ⭐⭐

Preparing for the upcoming treasure hunt, Captain CiaoCiao and her crew must traverse mountains and hills. Before the journey, she is provided with information about the altitude and wishes to gain a preview of the terrain’s topography.

Draw mountains

Task:

  • Write a program with a method printMountain(int[] altitudes) that converts an array of altitude meters into an ASCII representation.

  • The altitude has to be represented by a multiplication sign * at exactly this altitude from a baseline. The heights can be arbitrary, but not negative.

Example:

  • The array { 0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 3, 2, 2, 1, 0 } shall be represented as:

    5          *
    4         * *
    3      ***   *
    2    **       **
    1  **           *
    0 *              *

    The first column is for clarification and does not need to be implemented.

Optional extension:

  • Instead of *, use the symbols /, \, -, and ^ to indicate whether we are ascending, descending, on a plateau, or at the top.

    5          ^
    4         / \
    3      --/   \
    2    -/       -\
    1  -/           \
    0 /              \

1.4. Two- and multidimensional arrays

An array in Java can contain references to other arrays, and this is how you define multidimensional arrays in Java. In Java, there are no true two-dimensional arrays; two-dimensional arrays are nothing more than arrays that reference sub-arrays and the sub-arrays could be of different lengths.

1.4.1. Check mini-sudoku for valid solution ⭐⭐

Since mugging is quite exhausting, Bonny Brain needs a balance and engages in Sudoku. A Sudoku game consists of 81 squares in a 9×9 grid. The grid can be divided into nine blocks, each block is a two-dimensional array of size 3 × 3. In each of these blocks, each number from 1 to 9 must occur exactly once — none may be missing.

Check mini sudoku for valid solution

Task:

  • Write a program that tests a two-dimensional array of nine elements to see if all numbers from 1 to 9 occur.

  • Missing elements are to be reported.

Example:

  • The following array is a valid Sudoku assignment:

    int[][] array = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };
  • The following array is not a valid Sudoku assignment:

    int[][] array = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 8 } };

    The error could be reported something like: Missing 9.

1.4.2. Enlarge image ⭐⭐

Captain CiaoCiao is looking for the treasure of one-eyed Billy. The treasure map is small, and his eyes are getting worse. Help him enlarge the map and find the treasure.

Images are often stored in memory as triples of red-green-blue values, where the individual values can range from 0 to 255. Since there are no colors in grayscale images, only one value is needed instead of three.

Enlarge image

Task:

  • Given a two-dimensional integer array with values from 0 to 255; the array mentally represents a grayscale image.

  • Write a method int[][] magnify(int[][] array, int factor) that returns a new array and scales the image by the given factor. So, an image of size 2 × 3 and factor 2 becomes an image of size 4 × 6. Image pixels are simply doubled, no interpolation of values is desired.

Example:

  • Assume the following array:

    { {1, 2, 3},
      {4, 5, 6} }

    Then, after doubling, it follows:

    { {1, 1, 2, 2, 3, 3},
      {1, 1, 2, 2, 3, 3},
      {4, 4, 5, 5, 6, 6},
      {4, 4, 5, 5, 6, 6} }

1.5. Variable argument lists

Java allows methods to which you can pass any number of arguments. They are called vararg methods. A vararg parameter may only be at the end of a parameter list and is an array. When called with variable arguments, the compiler automatically creates a new anonymous array and passes it to the method.

1.5.1. Create SVG polygons with variable number of coordinates ⭐

Bonny Brain wants to draw a map for her next place of work, and it should always look good printed and on any resolution because every detail matters. The best technology for this is SVG.

SvgVargPolygon

In SVG there are different primitives, for example for lines, circles, or rectangles. There is also an XML element for polylines. Example:

<polygon points="200,10 250,190 160,210" />

Task:

  • Declare a Java method printSvgPolygon(…​) to which we can pass any number of coordinate pairs. What errors could occur when passing them?

  • The method should print a matching SVG output to the screen for the passed pairs.

Example:

  • In printSvgPolygon( 200, 10, 250, 190, 160, 210 ), 200,10 is a coordinate pair, 250,190 is as well, as is 160, 210. The screen output should be: <polygon points="200,10 250,190 160,210" />.

Optional: study the example at https://tutego.de/go/trysvgpolygon. Copy the self-generated SVG into the web interface.

1.5.2. Check for approval ⭐

Captain CiaoCiao gets feedback from his crew members about an order. All members can vote yes or no.

Task:

  • We are looking for a vararg method allTrue(…​) that can accept any number of boolean values, but must be called at least with one argument.

  • If all arguments are true, the return is also true; if one of the boolean values is false, the method shall return false.

  • Since a vararg is internally an array, null may be passed — this must lead to an exception.

Example:

  • allTrue(true, true, true) returns true.

  • allTrue(true) returns true.

  • allTrue(true, false) returns false.

  • allTrue(true, null) returns an exception.

  • allTrue() cannot be compiled and must give a compiler error.

1.5.3. Help, tetraphobia! Put all fours last ⭐⭐

Bonny Brain meets befriended pirates in Hong Kong and finds that many suffer from tetraphobia and have a superstitious fear of the number 4. The accountant must now put all numbers with a 4 to the back.

tetraphobia

Task:

  • Write a method fourLast(int... numbers) that places all numbers containing a 4 after the numbers that do not have a 4. The order of the numbers without 4 must not change, the numbers with a 4 can be anywhere at the end.

  • fourLast(…​) should return the passed array.

  • The argument null must lead to an exception.

Example:

  • int[] numbers = {1, 44, 2, 4, 43}; fourLast(numbers); modifies the array numbers so that 1 and 2 are before 44, 4 and 43 in the array. The 2 must not come before the 1 later.

  • fourLast( 4, 4, 44, 1234 ) returns the array automatically generated by the compiler with the entries, for example in the order 4, 4, 44, 1234.