Programming

Write 1 coding assignment and submit on Autolab.

• We provide a zip file containing RURacing.java.
• For each problem UPDATE and SUBMIT the corresponding file.

Observe the following rules:

1. DO NOT add any import statements
2. DO NOT add the project statement
3. DO NOT change the class name
4. DO NOT change the headers of ANY of the given functions
5. DO NOT add any new class fields
6. DO NOT use System.exit()
7. ONLY print the result as specified by each problem. Observe the examples’ output, display only what the problem is asking for.
8. DO NOT print other messages, follow the examples for each problem.
9.  
10. ONLY print the result as specified by each problem. Observe the examples’ output and display only what the problem is asking for.
    
    1. DO NOT print other messages; follow the examples for each problem

RU Racing

Overview

This assignment will make you aware of runtime by tasking you with programming racers that move at different “speeds.” Each speed will correspond to the successful completion of one lap on a given raceway.

For example, a racer with an O(1) runtime will complete a full lap in a single step, demonstrating constant time complexity. In contrast, a racer with an O(n) runtime will take n steps to complete the lap, illustrating linear time complexity. Through this exercise, you will visually observe how different algorithmic efficiencies impact performance and understand the practical implications of various runtimes in algorithm design.

You are given different test tracks stored within “track” files as a set of points stored in plain text to construct raceways. These points will be drawn upon a 2D matrix (character array) where we will determine if racers are moving at the correct pace and direction.

The construction step of the 2D array will be delegated to a separate function, createRaceway().

NOTE – If you require a refresher on 2D arrays, you can refer to your lecture slides or notes. Princeton also offers an overview based on your book.

The 2D array will be interpreted in the following manner:

• Points on the array will be represented by x and y coordinates.
• The x-coordinate will be the column and the y-coordinate will be the row.
• Points will be stored in an (x, y) format.
• The top-left corner of the map will be (0, 0). The bottom-right corner will be (size – 1, size – 1).

An image of a 2D array with an embedded raceway and example coordinates is provided below:

From now on we will refer to this 2D matrix/array as a “map,” which includes all text characters. All characters that represent this map have been provided as constants (GRASS & ROAD). The ‘#’ character represents the road racers will run on, and the ‘.’ character represents grass (what racers should not run on).

Overview of Files Provided

• RURacing: Holds all of the functions to be written and that will be tested when running the racers on each track. Edit the empty function with your solution, but DO NOT edit the provided ones or the functions signatures of any function. This is the file you submit.
• Driver: A tool to test your RURacing implementation interactively. You are free to use this driver to test all of your functions. Feel free to edit this class, as it is provided only to help you test. It is not submitted and/or graded.
• StdIn and StdOut: libraries to handle input and output. Do not edit these classes.
• Track files: Files containing the coordinates to create any given track on the map. Feel free to manipulate them as they will not be submitted to Autolab.

RURacing.java

• DO NOT add new import statements.
• DO NOT change any of the function’s signatures.
• You are allowed to create helper methods if needed, but please ensure they are private (encapsulation!).

The class contains 0 instance variables.

readTrackFile – provided

Read the given coordinates from the track text files by using StdIn. The first integer in the file will represent the number of coordinates to read. Each coordinate comes as a pair of two integers separated by a space. All coordinates will be placed on a separate line. The first integer is the x-coordinate and the second integer is the y-coordinate. The coordinates should be returned in a one-dimensional array structured in the following manner: {x1, y1, x2, y2, …, xn, yn}. These coordinates represent the corners of the raceway and will be used to construct it:

Note – When you read an integer using StdIn, it does not read newline characters, which leaves them as leftover characters in the “input buffer.” Consequently, StdIn’s readInteger() method gets stuck when trying to read them later on, so make sure you call readLine() when you reach the end of a line to avoid any errors.

drawRoad – provided

Draw a road between two given points on a given map. The road should be a straight line between the two points (horizontal or vertical only). The points are provided as a set of 4 integers where the first two integers correspond to the first point and the last two correspond to the second. The road must be drawn using the ROAD constant. This method will exclude drawing diagonal lines. A 2D character array is passed into the method to draw the road on.

createRaceway – provided

Create a raceway by connecting a series of points that represent the raceway’s corners through roads. Before we begin we’ll need an area to place the raceway on. Therefore we will return the raceway on a 2D character array that you’re responsible for creating. The size of the 2D array will be determined by the largest integer contained within the points array + 1 due to the nature of 0-indexed arrays (e.g., {0, 0, 0, 4} would necessitate a grid of size of 5 because a size of 4 would be out of range for the array otherwise).

The points will be given as a list of xy-coordinates stored within a one-dimensional integer array (e.g., {1, 2, 1, 4} would represent two points: (1, 2) & (1, 4)). A road will be created by connecting two consecutive points using the drawRoad method.

To go over points we will utilize the sliding window method. When the first two points are connected via a road, make the next point in the array the new second point. Consequently, the previous second point will become the new first point. Connect the two points once again to form another road. This process will continue until we reach the last point in the array.

An example of the sliding window is provided below for further clarity:

printMap – provided

Print out the raceway to see what it looks like. Start from the first row (index 0 in the 2D map) and continue until the final row. We’ll print the raceway using the following rules:

• Separate each row into a new line
• Each character will have a space between them to make the final product easier to read.
• If a character is a 0, it will be replaced with a grass character when printed.
• If a character is not a 0, it will be printed as is.

Your final output for track0.in (with no racer) should look like the following:

Note – Since we have only been creating roads so far for the map, many other characters have been left with their default value of 0. This may appear as a space character in your terminal, but in reality, it is NULL. We could go through the effort of changing each one of these to a grass character, but a simple conditional expression solves the issue as seen above.

moveRacer – provided

This method will move a racer a certain distance within a given raceway. The racer will start at the given coordinates and follow a clockwise path (e.g., Right -> Down -> Left -> Up) through the raceway based on its current position. The racer should avoid running into the grass as that will count as a crash. When the method finishes moving the racer by the given distance, it will return the racer’s new position as an array of two integers.

This will come in handy when creating some of the more complicated racers, such as the racer with an O(log(n)) runtime.

Use the following characters to amend the map with a racer’s current position and direction: {‘>’, ‘v’, ‘<’, ‘^’}. For example, let’s say a racer’s current position is at (0, 0) in the previous track0 file and they move a distance of 1. We would then have to update the map correspondingly.

Notice the previous position is updated with the ROAD constant. This is so the raceway is not fully replaced with all directions and positions the racer took.

In this example, the ‘>’ character is used since the racer is going to the right. However, this will change as the racer reaches the end of the current road and reaches the corner (now assuming we are traveling a distance greater than 1). The expected behavior at that point would be the following:

This will continue until the racer travels the distance specified and its current position/direction will remain on the map until the next call to this method.

The reason we keep track of the racer’s position and direction in this manner is to avoid a racer getting stuck or looping at a specific point within the raceway. Imagine the racer is moving to the left, however it then sees the right direction contains a piece of road. The racer would then backtrack and get stuck in a loop since it believes the clockwise order right -> down -> left -> right. By keeping track of the direction it was going before, we can avoid this problem by double-checking the current direction and therefore avoiding going right.

Here is an example snippet of this methodology for further clarification (the same would apply when attempting to go upwards but with the ‘v’ character instead):

Racers – You implement these functions

This is a bit of a stretching for the imagination but for this assignment, count towards the running time each time the code prints:

• Racer is at: (x,y)

1. racer1 runs in O(1) and it prints a constant number of times.
2. racer2 runs in O(log n) and it prints log n times
3. racer3 runs in O(n) and it prints n times.
4. racer4 runs in O(n²) and it prints n² times.

Note: do not print any of the racers’ initial position. For every racer print the consecutive positions they move to within a given step (loop iteration).

1. racer1 – O(1)

This is the first racer. The racer will start at the top-left corner of every raceway (0, 0) and will move in lightening speed to reach the end of the raceway (i.e., the full length of the raceway).

• Since this racer moves in O(1) time, it will reach the end of the raceway in one step.
• Use the moveRacer() function to move the racer to a certain position.
• Once the racer has reached a full lap, print its final position only once.
  • Racer is at: (x,y)

All examples you’ll see below will be based on the first track file (track0):

Note – Notice the racer’s final position is presented with the ‘^’ character. This makes sense because the racer was traveling upwards before it completed its lap. It contrasts with the previous example where the racer began by traveling rightwards at the same position.

2. racer2 – O(log n)

Implement this method similarly to racer1 but instead with the runtime of O(log n).

The racer will start at the top-left corner (0, 0) and at each timestep will double the distance it moved in its previous step. The racer will stop once it reaches the end of the raceway. However, the racer may not go past the end of the raceway. The last position of the racer must only be printed once.

 

3. racer3 – O(n)

Implement this method similarly to racer1 and racer2 but instead with the runtime of O(n).

Program racer3 to zoom through the track at a linear speed. Ensure that the position of racer3 is displayed as it speeds through the track. Similarly to before utilize the moveRacer method to help you create this method.

4. racer4 – O(n²)

Program racer4 to zoom through the track at an O(n²) speed. This racer will start at the top-left corner as every other racer but stay at each consecutive position for n steps. So, racer4 will take n times longer than racer3 to complete the track. Ensure that the position of racer4 is displayed as it speeds through the raceway. Make sure you utilize the moveRacer to help you create this method. The ellipses below indicates more output after the snippit; your output should include all positions.

NOTE: This method runs n – 1 times per position, this is to introduce to you that n ⋅ (n – 1) still simplifies to O(n²) in big O notation (this is reflected in the image below).

IMPORTANT: Notice the final positions for all racers is only printed once. Also, we cannot include the full output of the above because of how long it is, however, the concept should come across that the racer is spotted at each position x times.

Implementation Notes

• YOU MAY ONLY update the methods with the “WRITE YOUR CODE BELOW” comment.
• COMMENT OUT all print statements from RURacing.java before submission
• DO NOT add new import statements.
• DO NOT add any instance variables to the RURacing class.
• DO NOT change any of the method signatures.
• DO NOT add any public methods to the RURacing class.
• DO NOT add/rename the project or package statements.
• DO NOT change the class RURacing name.
• YOU MAY add private methods to the RURacing class.
• DO NOT use System.exit()

Executing and Debugging

• You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
• How to debug your code. You will have to create a launch.json file and configure it correctly (Run -> Add Configuration).
• If you choose the Terminal:
• first, navigate to the RURacing directory/folder
• to compile: javac *.java
• to execute: java Driver

Before submission

Collaboration policy. Read our collaboration policy here.

Submitting the assignment

Submit RURacing.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.