Assignment 6 – 60 Course Points
Students will learn about recursion and write two programs. One will recursively draw a ladder and the other will navigate 2 characters through paths.
Implementation Notes
- YOU MAY only update the methods with the WRITE YOUR CODE HERE line.
- COMMENT all extra testing print statements you have written from RecursiveLadder.java, FireboyAndWatergirl.java
- DO NOT add any instance variables to the RecursiveLadder.java, FireboyAndWatergirl.java class.
- DO NOT add any public methods to the RecursiveLadder.java, FireboyAndWatergirl.java class.
- DO NOT add/rename the project or package statements.
- DO NOT change the class name.
- DO NOT use System.exit()
Recursive Ladder (20 points)
Programming
In Recursive Ladder, write a recursive function createLadder that receives one parameter, an integer n containing the number of levels. The method createLadder returns a string with n levels, following these rules:
- Odd levels are denoted by |=|\n (rails/step followed by the newline character \n).
- Even levels are denoted by | |\n (rails followed by the newline character \n. The rails are separated by ONE space in between).
- The topmost level (n = 1) is the end of the ladder and is denoted by |-|\n (rails with a single dash in between, followed by the newline character \n).
- Levels are built starting from the bottom and up to the top (assume n, the number of levels, is greater than or equal to 1).
Examples below:
Notes:
- YOUR CODE MUST BE RECURSIVE
- Do not use loops (while, do/while, or for)
- Your code must return a string without extra spaces, commas or any other character that is not in the original string
- DO NOT print anything inside the createLaddermethod.
We provide a test client (main method) to test your createLadder method by providing an input number for the length of the ladder. Autolab will ignore your main method. It will ONLY test the recursive createLadder method
Executing and Debugging
First navigate to the directory/folder containing RecursiveLadder.java
- to compile: javac RecursiveLadder.java
- to execute: java RecursiveLadder #
By Kal Pandit and Mary Buist
Fireboy and Watergirl (40 points)
Overview
In this assignment, you will implement a recursive function using conditionals to check for safe paths forward. This assignment simulates the Fireboy and Watergirl game, and your program is meant to find a safe path by checking for any hazards and if so, moving the character back until they can find another path forward. This pattern continues until both characters find the exit.
In the original Fireboy and Watergirl game, both characters have hazards to avoid and diamonds to collect. In your program, both characters must avoid the green goo. Fireboy can walk through lava and will collect fire diamonds but must avoid water. Watergirl can walk through water and will collect water diamonds but must avoid lava.
Programming
Methods given to you:
main()
The input files contain the maze’s dimension d in the first line followed by d lines with d characters in each line. The meaning of the characters are below:
- ‘F’ = lava; only Fireboy can step here.
- ‘W’ = water; only Watergirl can step here.
- ‘N’ = neutral; both characters can step here.
- ‘G’ = green goo; neither character can step here.
The main function reads in the input file to create the char[][] maze array and populate it.
It also creates two arrays:
- fireboyVisited: boolean 2D array to represent fireboy’s visited path.
- watergirlVisited: boolean 2D array to represent watergirl’s visited path.
Then, it calls nextStep() for FIREBOY and then for WATERGIRL.
- The main method calls the nextStep method for Fireboy printing Fireboy’s final path.
- The main method calls the nextStep method for Watergirl printing Watergirl’s final path.
Method to be implemented by you:
nextStep()
This is a recursive function that determines if the current cell (row, col) can be visited by the hero, and then visits the neighboring cells. The nextStep method returns when no other step can be taken.
A cell can only be visited once.
- If a cell (row,col) has already been visited, then visitedMaze[row][col] is true.
Note: visitedMaze is a 2d array that represents the visited maze coordinates.
Base case – determine if the current cell can be visited:
- The hero input will be FIREBOY or WATERGIRL.
- The maze array is used to determine if the hero can step in the current cell (row, col) according to the following rules:
- ‘F’ = lava; only Fireboy can step here.
- ‘W’ = water; only Watergirl can step here.
- ‘N’ = neutral; both characters can step here.
- ‘G’ = green goo; neither character can step here.
- Ensure that (row, col) are within the maze array bounds.
- Ensure that (row, col) has not been visited yet.
- If the current cell (row, col) has been visited, then visitedMaze[row][col] is true.
- If the current cell (row, col) cannot be visited, return.
The recursive step – the nextStep method attempts a next step until no other step can be taken.
- Take the step, mark visitedMaze[row][col] true.
- Call nextStep() four times on neighboring cells in the following order
• Down: the cell immediately down the current cell.
• Left: the cell to the left of the current cell.
• Up: the cell above the current cell.
• Right: the cell to the right of the current cell.
Note:
You need to make sure that line endings are in the LF format. (Open the command palette (CTRL+SHIFT+P) -> type “Change All End Of Line Sequence” -> choose LF).
This pertains to the maze file and not the starter program.
After changing the line endings from CRLF to LF, you must resave the maze file.
Executing and Debugging
First navigate to the directory/folder containing FireboyAndWatergirl.java
- to compile: javac FireboyAndWatergirl.java
- to execute: java FireboyAndWatergirl maze#.txt
Example 1
javac FireboyAndWatergirl.java
java FireboyAndWatergirl maze1.txt
Steps taken by each of the heroes (this is for your reference, do NOT print the extra “Step that…” statements out):
Example 2:
javac FireboyAndWatergirl.java
java FireboyAndWatergirl maze2.txt
Steps taken by each of the heroes (this is for your reference, do NOT print the extra “Step that…” statements out):
By Sarah Benedicto and Juliania Shyprykevych
Submitting Guidelines
Implementation Notes
- YOU MAY only update the methods with the WRITE YOUR CODE HERE line.
- COMMENT all testing print statements you have written from RecursiveLadder.java, FireboyAndWatergirl.java
- DO NOT add any instance variables to the RecursiveLadder.java, FireboyAndWatergirl.java class.
- DO NOT add any public methods to the RecursiveLadder.java, FireboyAndWatergirl.java class.
- DO NOT add/rename the project or package statements.
- DO NOT change the class name.
- DO NOT use System.exit()
VSCode Extensions
You can install the VSCode extension pack for Java. Take a look at this tutorial.
We suggest:
Importing VSCode Project
- Download A6.zip from Autolab Attachments.
- Unzip the file by double clicking.
- Open VSCode
- Import the folder to a workspace through File > Open Folder
Before submission
Collaboration policy. Read our collaboration policy here.
Submitting the assignment. Submit RecursiveLadder.java and FireboyAndWatergirl.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.
Getting help
If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.
- Find instructors office hours here
- Find tutors office hours in Canvas -> Tutoring, RU CATS
- Find head TAs office hours here
- POST on Piazza in Canvas -> Piazza
- In addition to office hours we have the CSL (Coding and Social Lounge), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.
- Refer to our Programming Assignments FAQ for instructions regarding our assignments and policies.
- In addition to office hours we have the CSL (Coding and Social Lounge), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.
- Refer to our Programming Assignments FAQ for instructions regarding our assignments and policies.
Submitting
Write the program and submit on Autolab.
- We provide a zip file (find it under A6 on Autolab) containing the RecursiveLadder.java and FireboyAndWatergirl.java.
- For this assignment UPDATE and SUBMIT the corresponding file.
