ECE2810J — Data Structures and Algorithms

ECE2810J — Data Structures and Algorithms Programming Assignment 3 Instructor: Yutong Ban

 — UM-SJTU-JI (Fall 2024)

Notes

Submission: on JOJ

• Due at Dec 1st, 2024, by 23:59

1 Introduction n this assignment, you are tasked with implementing a C++ solution to a simplified version of the “sokoban” game,where the objective is to push specific boxes to designated target positions on a grid. The challenge lies in devising anefficient strategy to navigate the grid, avoiobstacles, and ensure that all required boxes reach their target locations.Your program should be able to handle various configurations of boxes, walls, and goals, ensuring the correct boxes arepushed to their intended destinations. This project is C++ only, no other language is allowed.

2 Programming Assignment

2.1 Read Map

The map is designed as a grid where each cell is either a walkable path, a wall, or a point of interest (like the startingpoint or a box). The first line of the file defines the dimensions of the map in terms of columns and rows. The rest ofthe file specifies the content of each cell in the grid,using a series of symbols to represent different elements:

• . - Path: This represents a walkable path where the player can move freely. Boxes can also be pushed acrossthis type of cell.

• # - Wall: This represents an impassable barrier. Neither the player nor the boxes can pass through these cells.
• S - Starting Point: This is where the player begins. Each map should contain exactly one S character.
• B - Box’s Original Position: The initial position of a box.
• T - Target Position for Boxes: The destination cell for a box.
• R - Box at Target Position: This indicates that a box has been successfully pushed to its target positionTo ensure a valid and challenging map, the following constraints must be met:

(1) The outermost boundary of the map must be composed entirely of walls (#) to prevent the player or boxes fromexiting the map area.

(2) Each map must contain exactly one starting point (S).

(3) For test cases of the first part on JOJ, the number of boxes (B) will be less or equal to 8 and the result of rowstimes columns should be less or equal to 800.(4) For test cases released on Canvas, it can be very complicated.The player can move in four cardinal directions:

• Up1• Down

• Left
• RightThe player can push a box if it is adjacent in one of these directions, and if the cell behind the box in that direction isa path (.). Boxes can only be pushed. In other words, they cannot be pulled. Only one box can be pushed at a time,and the player must move to the former box’s position after pushing it.Below is an example of a map configuration file. In this example, the map size is specified on thefirst line as 11 10,indicating 10 rows and 11 columns. The outer boundary is composed of walls (#), while inner cells define paths, thestarting point, box positions, and target positions.

2.2 Search routes Help the player to find the shortest route to push all the boxes to the expected place. Please notice that it is possiblethat there are multiple boxes and multiple target positions. The player should push all the boxes to the target positions.

2.3 Show the route The task requires the program to display the player’s route on the map, detailing each movement step-by-step. Eachstep should be represented by a character indicating the direction moved:

• U for up
• R for right
• L for left
• W for downFor instance, given the map configuration shown, the route may look like:DRURRUURUURRDDDLLLDDRRRURULLLDLDRULLLUUULUURDRRURDDDDDLLLUUULURRRURDDDDULDThis format will be used as the return value of the solve functionprovided in the template code.

Bonus Requirements

(1) Display the map, player, boxes, and other elements at each step using the same format as the input map. Storeall the map state in a file, ensuring it is clear and easy to read.2(2) Use a graphical interface to visually represent each step, showing the map, player, boxes, and other elements intheir updated positions. The output should bedisplayed as an animation, with each step shown for a brief periodbefore transitioning to the next step.

2.4 Unsolvable Maps

In some cases, a map configuration may be unsolvable due to the positioning of walls or boxes, creating an impassethat prevents the player from reaching all targets. Such configurations are referred to as “invalid maps.” 代写ECE2810J — Data Structures and Algorithms This occurswhen one or more boxes are placed in positions from which they cannot be moved to their designated target cells.A map is considered invalid if:

• There is more than one starting point or no starting point.
• There are more boxes than target positions.
• A box is surrounded by walls or other boxes in a way that makes it immovable.
• Any box is placed in a corner or against a wall where it has no path to the target position.The following example demonstrates a typical invalid map layout:

In this map: The box (B) is located next to walls on two sides, which prevents it from being moved toward the targetposition (P).When the program encounters such a configuration, it should recognize the situation as unsolvable and output amessage as “No solution!” The program should thenterminate without attempting to find a solution or display a route.3 Input / Output As mentioned above, the input map is stored in a file. To test your program, you can use the following command toread the map from a file:1./main < inputMap.txtFor submission on JOJ, the output (i.e. the return value of the function) should either be “No solution!” or the routeto push all the boxes to the target positions.If you have implemented the first bonus requirements, you should first display the steps in the format mentioned above,

and then display the map at each step. We highly recommend you to store the map at all steps in a file. For example,if the output is stored in a file named output.txt, you can use the following command:3./main < inputMap.txt > output.txtIf you have implemented the second bonus requirements, you should display the map in a graphical interface.

4 Submission

(1) For part 1 on JOJ, submit your source code in one file named sokoban.hpp. Your source code should include afunction named solve and a function named read_map.

(2) For part 2 on JOJ, put the detailed route output in the answers part in sokoban.hpp. The test cases will bereleased on canvas, which may take a long time for your program to run. Please notice that part 2 and bonuswill be graded if and only if you can pass 80 percent of the test cases in part 1.

(3) Submit the source code on Canvas along with a corresponding Makefile to compile the source code. A sampleMakefile is provided on Canvas, which you may modify as needed. Your code submitted on Canvas should beable to compile successfully and output the detailed routewith the corresponding input file.

(4) (Optional) If you have implemented the first bonus requirement, you also need to submit the output files onCanvas. The naming format should match the original filename. For example, if the input file is named big_1.in,the output file should be named big_1_detail.out. Failure to follow the correct naming format will result inan invalid submission.

(5) (Optional) If you have implemented the second bonus requirement. You may come to the TA’s office hoursto demonstrate your program. The due date will be the same. The TA will give you a score based on thedemonstration.

5 Implementation Requirements and Restrictions

5.1 Requirements

• You must make sure that your code compiles successfully on a Linux operating system with g++ and the options-std=c++1z -Wall -Wextra -Werror -pedantic -Wno-unused-result -Wconversion -Wvla.

• You can use any header file defined in the C++17 standard. You can use cppreference as a reference.

5.2 Memory Leak

You may not leak memory in any way. To help you see if you are leaking memory, you may wish to call valgrind, whichcan tell whether you have any memory leaks. (You need to install valgrind first if your system does not have thisprogram.) The command to check memory leak is:valgrind --leak-check=full <COMMAND>You should replace <COMMAND> with the actual command you use to issue the program under testing. For example, if

you want to check whether running program

./main < input.txtcauses memory leak, then <COMMAND> should be “./main < input.txt”. Thus, the command will bevalgrind --leak-check=full ./main < input.txt45.3 Code Quality

6 Grading

6.1 Correctness We will use the test cases on JOJ and Canvas to verify the correctness of your code. This section will have a totalscore of 100 points.

6.2 Code Quality Bad code quality will lead to a deduction of up to 20 points.

6.3 Bonus For the first bonus requirement, you can get up to 10 points. For the second bonus requirement, you can get up to30 points. Please notice that bonus will be graded if and only if all the small test cases are passed. What’s more, thetotal score will not exceed 130 points.

7 Late Policy Same as the course policy.

8 Honor Code Please DO NOT violate honor codeSome behaviors that are considered as cheating:

• Reading another student’s answer/code, including keeping a copy of another student’s answer/code
• Copying another student’s answer/code, in whole or in part
• Having someone else write part of your assignment
• Using test cases of another student5• Testing your code with another one’s account (Testing chances are limited)Post your code to github

9 Acknowledgement This programming assignment is designed based on ENGR1510J Lab 3.6