Serial Implementation

You will implement a single-threaded Rust solution for Counting Codes.

You will not need to come up with a solution to the problem; reference solutions in C and C++ are given in the reference folder. You should compile, test, and benchmark the binaries like you would for your Rust solutions.

$ gcc -O3 reference/countingcodes.c -o countingcodes_c$ g++ -O3 reference/countingcodes.cpp -o countingcodes_cpp

The reference solution given uses a recursive, brute-force, backtracking algorithm. You do not need to modify the algorithm used; a 1-1 translation of the code will suffice.

Observe the following hints:

• You will find it helpful to structure your Rust solution similar to the C++ solution.
• Use equivalent Rust types for the C++ data structures, eg. Vec for std::vector.

Scoped and Atomic

You will implement a multi-threaded Rust solution for Counting Codes. Read the following carefully:

1. The provided algorithm computes the solution through brute-force:

   For each possible digit d from 1 to 9,

   for (int d = 1; d <= 9; d++) {
   
   godbolt
   

   the digit is placed onto the grid if possible,

   inrow[i][d] = true;
   B[i][j] = d;
   
   godbolt
   

   then the count with the placed digit is computed through recursion

   cnt += backtrack(i, j+1);
   
   godbolt
   

2. A simple multi-threaded solution will be to spawn a new thread for each recursive call.

   This requires cloning the data structures used (with the placed digit), then spawning a thread that takes ownership of the new data structure to solve.

3. Your solution needs to keep track of total count generated by all of the threads spawned.

   Use an atomic integer for this purpose. The atomic can be safely shared and passed to all threads spawned.

4. Your solution needs to know when all threads have finished brute-forcing their subtask.

   This means all threads should be spawned in a std::thread::scope. The scope should be created in your main function, and the first thread (running the task representing the entire problem) is spawned in the scope. Since a scope implicitly joins all threads spawned in the scope before returning, after the scope ends the value of the atomic integer will be the final count (the solution).

5. Your solution should limit the number of threads spawned to avoid the overhead associated with creating too many threads.

   Use an integer to track the current recursion depth; fallback to a regular recursive call once the depth reaches a certain level.

Regular Threads

Implement a multi-threaded solution that uses regular threads that should provide a speedup over the scoped atomic version. Read the following carefully:

1. Notice how after spawning off all tasks (or finishing all recursive calls), the thread currently in backtrack has no more work to do.
2. Therefore, a simplification of your multi-threaded solution would be to spawn regular threads when spawning new tasks, placing their handles into a vector.
3. After spawning all tasks (or finishing all recursive calls), the thread should join all handles to obtain the final counts from the tasks spawned.
4. The backtrack function can then return the count directly, similar to the serial implementation.

Task Parallelism

The rayon crate provides high-level abstractions for data parallelism, which we will use to parallelize the tasks the algorithm performs. This is primarily achieved with parallel iterators, which you will use in this version of your Counting Codes solution. Read the following carefully:

1. From your Regular Threads implementation, a thread is spawned for each task, with the handles to each thread placed in a vector.
2. This version should instead place the task itself into the vector.
3. After all tasks are created, use a parallel iterator provided by rayon to run all tasks in parallel, summing the counts returned by the tasks.

Requirements

• You must benchmark the release (optimized) version of your implementations.
• You should benchmark with the 4x4_zero test, as it runs long enough to prevent noise yet short enough as to not require a coffee break each run.
• Your serial implementation must be at most 1.5x slower than the provided C and C++ implementations.
• Your slowest parallel implementation must be at least 2x faster than your serial implementation.