Introduction

Check the Assignment 1 grade on the ZINC Online Submission System. There are 20 test cases in total, each worth 5%. E.g. score of 20/20 on ZINC means full marks for Assignment 1. Your submission record will state all test case failures (if any) and their expected values. If you are unable to see the test case failure details, please check back later, as the ZINC Web GUI Student View might be desynchronized from the server database.

1. Read the list of common errors and appeal cases, and follow their sub-instructions (if applicable).
2. No partial credit within a test-case. Each test-case is only a binary 0% for failed or 5% for passed.
3. Check the GTest code in the section below for more details of what each test-case is doing.
4. Send an email to the TA in-charge, CHANG Bing Yen, bychang@connect.ust.hk, with the subject header "COMP2012H PA1 Grade Appeal".
5. State which test-case(s) you wish to appeal (refer to the list in the section below). Clearly state your reasoning for why your code should have passed those test-case(s).
6. You may propose changes to your source code. Attach your code snippet with the proposed changes in your email. However, such changes are subject to a grade deduction at the discretion of the TA in-charge, proportional to the magnitude of change, with a 5% deduction being the minimum.
7. The TA in-charge reserves the right to reject any and all source code changes, as the solution has already been released.
8. DO NOT attach any .exe/executable file(s) in your email.
9. Appeal deadline is 30 October 2020 Friday 23:59 HKT. No late appeals will be processed.
10. Finalized scores will be uploaded to Canvas after all appeals are processed.

1. Uninitialized variables will have garbage (random) values in C++. Sometimes it will be 0, sometimes it will not. In that case, your program may generate different results on different machines or different runs if your logic depend on an uninitialized value. If you have assumed them to be 0 or something specific (e.g. a very large value), your code is faulty and will get random results.
2. If your function doesn't have a return statement for some cases, the returned value is undefined (can be random) for those cases.
3. Retrieving values from deleted/unallocated dynamic memory, or index out-of-bounds, may not always crash your program but may give random values.
4. Compilation errors will result in 0 marks for this assignment. This should not occur as revealed test cases were already provided to test your code on ZINC. Exceptions will only be given for compilation errors that are the fault of the TA's testing code.
5. Runtime errors and crashes due to incorrect memory access / memory allocation / memory deallocation / missing variable initialization / missing return values / out-of-bound array access / etc, may not occur all the time on all machines. However, even though you may not encounter the error/crash when you test your program, if your program crashes during any of the test cases on ZINC, the corresponding test cases will be considered as failed and will receive 0 marks.
6. Runtime crashes due to point 5 above, or due to timeouts (infinite loop / infinite recursion / runtime taking too long) of the whole GTest, will only be regraded if you can debug, fix, and report it in your email appeal with attached code snippet. The corresponding test-case(s) where the runtime crash occured will still be considered as originally failed and will receive 0 marks, but you can recover your marks for the rest of the test-cases.

• This is due to a runtime crash or timeout of GTest. This means that your score of PA1 is 0. Please see points 5 and 6 of the Common Errors and Appeals section above for more instructions on how to recover your marks. Note that you can refer to the released solution to help you debug. You may also download the GTest code and run it yourself.

Local Solver One Cell Per Function Call

If you have implemented your local_solver() to immediately return when it finds one possible hidden cell to reveal/flag, the current GTest would fail the last three local_solver() test cases, as it is expecting each function call to find all possible hidden cells to reveal/flag in the whole grid, not only the first one encountered.

1. If you have already sent an appeal email following the general procedures, then you don't need to do anything else. Please wait for the TA in-charge to process your grade appeal and send you a reply.
2. If you have other appeal cases but haven't sent an email before, please follow the general grade appeal procedures listed in the previous section.
3. If you only wish to appeal this case, send an email to the TA in-charge, CHANG Bing Yen, bychang@connect.ust.hk, with the subject header "COMP2012H PA1 Grade Appeal, Local Solver One Cell per Function Call". All other grade appeal cases within that email will be ignored.
4. The TA in-charge will verify that your ZINC submission code can pass a modified GTest test-case. This test-case will replace the three local_solver() test cases (not replacing the CompletelyHiddenGrid test-case, which you should have passed anyway).
5. If you pass the modified GTest test-case, you will recover your local_solver() marks for those three replaced test-cases, but subject to a 5% penalty. This would be equivalent to passing 2 of those 3 test-cases. Your finalized grade for local_solver() will only be a maximum of 15%/20%, assuming you have also passed the CompletelyHiddenGrid test-case.
6. You may download and run the modified GTest code yourself in the section below. This test-case runs local_solver() on a General Grid but only checks the final grid state.

• While it is technically true that the PA1 description for Task 3 did not explicitly state to reveal and flag all possible hidden cell candidates per iteration, it should be obvious from the output parameters of int cells_to_reveal[MAX_CELLS][2] and int cells_to_reveal[MAX_CELLS][2] both being such large arrays, as well as the presence of the int num_cells[2] output parameter.
  • For the case of only returning one cell per function call, instead we only need int cell_to_reveal[2] and int cell_to_flag[2]. We can also replace int num_cells[2] with bool is_reveal_or_flag[2].
• Returning only one cell per function call is also an inefficiency, as every function call has a runtime overhead cost. Also, while both implementations theoretically have the same O(num_grid_cells^2) runtime in the worst case, the solution's implementation is O(num_grid_cells) runtime in the average case where there are more than one possible hidden cell candiates per iteration.
  • For example, let's say there is one hidden cell to flag, and one hidden cell to reveal, and both these cells are at the bottom-right of the grid. The one-cell-per-function-call return will traverse the whole grid twice in total (once for each function call to find those two cells), while the solution implementation will only traverse the whole grid once in total (doesn't immediately return when finding the first cell, so can find the second cell).
  • The worst case runtime for the solution implementation would only occur if the hidden cells are "chained", meaning that revealing/flagging a hidden cell then only provides enough information to reveal/flag the subsequent hidden cells, so the local_solver() function has to return first in order to call reveal() and/or flag() for one cell, before calling local_solver() again. This is then similar behavior as the one-cell-per-function-call implementation, implying that the one-cell-per-function-call implementation's average case runtime and worst case runtime are equivalent.
• This 5% Grade Penalty is chosen so as to be analogous to failing enumerate_possibilities() Optimization test-case.

Grading Scheme

Each Task Function has 1 test-case per 5% of score, for a total of 20 test-cases. Passing a test-case is worth 5%, while failing a test-case is 0%, with no partial credit within a test-case.

Solution & Test Cases

• Solution: PA1_solution.zip
• Task 7 No Recursion: PA1_Task7_no_recursion.cpp
• GTest Code: pa1_gtest_code.zip
• GTest Modified Local Solver Test Case: PA1_GTest_local_solver_one_cell.cpp
• GTest Library for Windows: pa1_gtest_windows.zip

1. Extract pa1_gtest_windows.zip into any convenient folder.
2. Place your PA1.cpp into that convenient folder.
3. You should now have these files and subdirectories inside that convenient folder:
   • PA1.h
   • PA1.cpp
   • PA1_sol.h
   • PA1_sol.cpp
   • PA1_GTest.cpp
   • .\include\gtest\ (various subdirectories and files)
   • .\lib\libgtest.a
   • .\lib\libgtest_main.a
4. In a terminal, navigate to that convenient folder, and run the following g++ commands:
   • g++ -std=c++11 -pedantic -Wall -Wextra -g -c PA1.cpp -o PA1.o
   • g++ -std=c++11 -pedantic -Wall -Wextra -g -c PA1_sol.cpp -o PA1_sol.o
   • g++ -std=c++11 -pedantic -Wall -Wextra -g "-I.\\include" -c PA1_GTest.cpp -o PA1_GTest.o
   • g++ "-L.\\lib" -o PA1_GTest.exe PA1.o PA1_sol.o PA1_GTest.o -lgtest -lgtest_main
5. Things to try if you get compilation errors:
   • Replace with full directory pathnames ("-IC:\\Desktop\\convenient_folder\\include" , "-LC:\\Desktop\\convenient_folder\\lib") if relative pathnames fail to parse.
   • If you get "declaration not found in scope" errors related to gtest-*.h during Step 3, try replacing -std=c++11 with -std=c++0x, -std=gnu++0x, or -std=gnu++11.
   • If you are still having compilation errors, it might be a version difference with the MinGW compiler. Please try reinstalling according to the VS Code setup in Lab1.
6. Run PA1_GTest.exe. Note that there is no pause after output, so the terminal may close automatically.
7. To run the modified test-case for Local Solver, just replace PA1_GTest.cpp with PA1_GTest_local_solver_one_cell.cpp, as well as the relevant compilation commands.

To congifure googletest for other platforms, please refer to the googletest make documentation. You'll need to compile the googletest library files libgtest.a and libgtest_main.a specifically for your platform.

1. Reveal.NonZeroCell
2. Reveal.ZeroCell
3. Flag.Toggle
4. LocalSolver.CompletelyHiddenGrid
5. LocalSolver.SimpleReveal
6. LocalSolver.SimpleFlag
7. LocalSolver.GeneralGrid
8. ClassifyHiddenCells.CompletelyHiddenGrid
9. ClassifyHiddenCells.PartiallyRevealedGrid
10. HasSatisfiableNeighborConstraints.InsufficientPossibleFlags
11. HasSatisfiableNeighborConstraints.TooManyFlags
12. RecordPossibility.InvalidRecord
13. RecordPossibility.ValidRecord
14. EnumeratePossibilities.SimpleGrid
15. EnumeratePossibilities.ResetHidden
16. EnumeratePossibilities.Optimization
17. EnumeratePossibilities.GeneralGrid
18. HandleConstrainedCells.RevealAndOrFlag
19. HandleUnconstrainedCells.RevealAndOrFlag
20. GlobalSolver.GeneralGrid

Statistics

• Total: 20
• Average: 17.7
• Standard Deviation: 3
• Median: 19
• Minimum: 5
• Maximum: 20

• Total: 100
• Average: 88.5
• Standard Deviation: 14.9
• Median: 95
• Minimum: 25
• Maximum: 100

• Total: 8
• Average: 7.1
• Standard Deviation: 1.2
• Median: 7.6
• Minimum: 2
• Maximum: 8