# HW1: Sokoban
###### tags: `平行計算概論2021 spring`
[TOC]
## Change Log
* 3/9 fixed the path to sample testcase ... etc.
* 3/9 added explaination of srun -o
* 3/12 updated the interactive python program to support the '@' tile
* 3/12 the automatic judge system 'hw1-judge' is online
* 3/12 the link to the [scoreboard](https://apollo.cs.nthu.edu.tw/ipc21/scoreboard/hw1/) is updated
* 3/18 fixed typo
* 3/20 Change the build package from ninja to make
## Problem Description
“Sokoban (倉庫番, sōko-ban, “warehouse keeper”) is a puzzle video game in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.” – [Wikipedia](https://en.wikipedia.org/wiki/Sokoban)
You are asked to implement a solver for Sokoban and parallelize it with threads (either pthread or OpenMP; you can use std::thread as a pthread wrapper).
## Input Format
Input is given in a ASCII text file. The filename is given from the command line in argv[1].
Every line ends with a newline character \n. Each line represents a row of tiles; every character in the line represents a tile in the game.
The tiles are listed as follows:
* `o`: The player stepping on a regular tile.
* `O`: The player stepping on a target tile.
* `x`: A box on a regular tile.
* `X`: A box on a target tile.
* ` `: Nothing on a regular tile.
* `.`: Nothing on a target tile.
* `#`: Wall.
* `@`: Wall that is destroyed when a box is pushed through
Your program only need to deal with valid inputs. It is guranteed that:
* There is only one player, stepping on either a regular tile or a target tile.
* The number of target tiles are equal to the number of boxes.
* All tiles other than wall tiles are within an enclosed area formed by wall tiles.
* There is at least one solution.
## Input Example
1. This is a valid input:
```
#########
# xox..#
# #####
#########
```
2. This input is invalid because there are tiles outside of wall-enclosed area:
```
#########
# xox..#
# #####
##### #
```
3. This input is invalid because there are fewer target tiles than boxes:
```
#########
# xox .#
# #####
#########
```
## Output Format
You program should output a sequence of actions that pushes all the boxes to the target tiles, to stdout. (Do not output anything else to stdout, otherwise your output may be considered invalid. For debugging purposes, please output to stderr. However, it is advised that you remove the debug output from your submission as they may harm performance)
The output sequence should end with a newline characters \n, and contain only uppercase `W`, `A`, `S`, `D` characters:
* `W`: move the player up
* `A`: move the player left
* `S`: move the player down
* `D`: move the player right
It is not required that you output the solution with the least moves. Any sequence that solves the problem is valid.
## Output Example
Consider the following problem
```
#########
# xox..#
# #####
#########
```
A valid output is
```
DDAAASAAWDDDD
```
Another valid output is
```
DDAAADASAAWDDDD
```
<font color=red>Although the second solution takes more steps then the first one, both ouput are consider correct and will be accepted.</font>
## Execution
We will compile your code with the following command:
```bash=
g++ -std=c++17 -O3 -pthread -fopenmp hw1.cc -o hw1
```
We use ~~[ninja](https://ninja-build.org/manual.html#ref_lexer)~~ `Make` to build your code. The default ~~ninja~~ `Make` file for this homework is provided at `/home/ipc21/ta/hw1/Makefile`. If you wish to change the compilation flags, include `Makefile` in your submission.
~~To use ninja to build your code, make sure `build.ninja` and `hw1.cc` is in the working directory, then run `ninja` on the command line and it will build hw1 for you. To remove the built files, run `ninja -t clean`.~~
To use make to build your code, make sure `Makefile` and `hw1.cc` is in the working directory, then run `make` on the command line and it will build hw1 for you. To remove the built files, run `make clean`
Your code will be executed with a command equalviant to:
`srun -n1 -c${threads} ./hw1 ${input}`
Where ${threads} is the number of threads, and ${input} is the path to input file. Also, note that the time limit for each test case run is 30 seconds.
## Report
Answer the following questions, in either English or Traditional Chinese.
1. Briefly (< 100 words) describe your implementation.
2. What are the difficulties encountered in this homework? How did you solve them? (You can discuss about hard-to-optimize hotspots, or synchronization problems)
3. What are the strengths and weaknesses of pthread and OpenMP?
4. Which thread API (pythread or openmp) did you use to implement this homework? Why?
5. (Optional) Any suggestions or feedback for the homework are welcome.
## Submission
Upload these files to iLMS:
1. `hw1.cc` – the source code of your implementation.
~~2. `build.ninja` – optional. Submit this file if you want to change the build command.~~
2. `Makefile` - optional. Submit this file if you want to change the build command.
3. `report.pdf` – your report.
Please follow the naming listed above carefully. Failing to adhere to the names above
will result to points deduction. Here are a few bad examples: `hw1.c`, `HW1.cc`, `hw1.cpp`,
`report.docx`, `report.pages`.
## Grading
1. (40%) Correctness. Propotional to the number of test cases solved.
2. (30%) Performance. Based on the total time you solve all the test cases. For a failed test case, 75 seconds is added to your total time.
3. (30%) Report.
## Appendix
Please note that the spec, examples, and commands in this document may contain mistakes. If you are unsure about any of them, please feel free to raise a question on iLMS.
## Sample Testcases
The sample test cases are located at `/home/ipc21/ta/hw1/samples`.
## Playing The Game Interactively
You can play sokoban in the terminal with
```
home/ipc21/ta/hw1/play.py
```
For example, run
```
/home/ipc21/ta/hw1/play.py /home/ipc21/ta/hw1/samples/01.txt
```
to play the first sample input.
## Output validation
`/home/ipc21/ta/hw1/validate.py` can be used to validate your output. For example, the following command validates your answer for 01.txt when running 6
threads:
```
srun -c6 -o answer.txt ./hw1 01.txt
/home/ipc21/ta/hw1/validate.py 01.txt answer.txt
```
Noted that in the first command, the `-o` flag is used to redirect stdout to a file named `answer.txt`
You can also use:
```
srun -c6 ./hw1 01.txt | /home/ipc21/ta/hw1/validate.py 01.txt -
```
Here, `-` instructs `validate.py` to read your output from stdin.
## Automatic Judge
The `hw1-judge` command can be used to automatically judge your code against all sample test cases, it also submits your execution time to the [scoreboard](https://apollo.cs.nthu.edu.tw/ipc21/scoreboard/hw1/) so you can compare your performance with others.
To use it, run `hw1-judge` in the directory that contains your code `hw1.cc`. It will automatically search for `Makefile` and use it to compile your code, or fallback to the TA provided `/home/ipc21/ta/hw1/Makefile otherwise`. If code compiliation is successful, it will then run all the sample test cases, and show you the results as well as update the scoreboard.
```
Note: hw1-judge and the scoreboard has nothing to do with grading. Only the code submitted to iLMS is considered for grading purposes.
```
The judge supports -xpattern and -ipattern filters to exclude or include test cases. These filters are applied in the order they are specified. These filters support [glob(7)](https://man7.org/linux/man-pages/man7/glob.7.html) patterns. When multiple filters match a given test case, the later filter takes priority. For example, to skip 05.txt and 06.txt, you can run:
```
hw1-judge -x05.txt -x06.txt
```
To run only the case 02.txt:
```
hw1-judge '-x*' -i02.txt
```
## Judge Verdict Table
|Verdict | Explaination|
|------- | ------------|
|internal error| there is a bug in your code |
|time limited exceeded+|execution time > time limit + 10 seconds|
|time limited exceeded|execution time > time limit|
|runtime error|your program didn’t return 0 or is terminated by a signal|
|no output|your program did not produce an output|
|wrong answer|your output is incorrect|
|accepted|you passed the test case|
Google Drive
Gist
Clipboard
Sign in with Wallet
