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
loopbe 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.
Task:
Declare two arrays
int[] windSpeed
andint[] windDirection
.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.
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 arraywindDirection
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.
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.
Task:
Write a new method
isProbablyApproaching(String[] signs)
that returnstrue
if there are four of the same abbreviation in the array consecutively in a row. Remember that strings are compared usingequals(…)
.The array passed must not be
null
, and no element in the array must benull
.
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 arraypoints
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. Withsize
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 benull
; 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 |
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 ));
}
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.
Task:
Write a method
int[] shuffleDice()
that returns anint
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 })
returnstrue
.isHomogeneous( new int[]{ 1, 1, 1, 2, 2 } )
returnsfalse
.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 })
returnstrue
.isFullHouse(new int[]{ 1, 1, 1, 1 })
returnsfalse
.printDiceValues(shuffleDice())
returns2 × ⚁, 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.
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.
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.
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.
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 ofboolean
values, but must be called at least with one argument.If all arguments are
true
, the return is alsotrue
; if one of theboolean
values isfalse
, the method shall returnfalse
.Since a vararg is internally an array,
null
may be passed — this must lead to an exception.
Example:
allTrue(true, true, true)
returnstrue
.allTrue(true)
returnstrue
.allTrue(true, false)
returnsfalse
.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.
Task:
Write a method
fourLast(int... numbers)
that places all numbers containing a4
after the numbers that do not have a4
. The order of the numbers without4
must not change, the numbers with a4
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 arraynumbers
so that1
and2
are before44
,4
and43
in the array. The2
must not come before the1
later.fourLast( 4, 4, 44, 1234 )
returns the array automatically generated by the compiler with the entries, for example in the order4
,4
,44
,1234
.