Single-Threaded Implementation The insight to efficient single-threaded implementation is that all paths to point (X,Y) can be divided into the following classes:
Moreover, all moves in a particular class can be easily enumerated as permutations of moves. Moreover, total number of paths in a particular class can be calculated arithmetically by the following formula: N(x, y, d) = (x + y + d)! / (x! + y! + d!) (1) Moreover, all paths in a particular class have equal length. And yes, it's the same classes that defined in the problem statement, so we don't really need to calculate path statistics during path enumeration. All this allows us to create quite efficient implementation. OK, a line of code worths thousands words: // enumeration of possible moves: horizontal, vertical and diagonal enum move_t {move_x, move_y, move_d}; // path class struct path_class_t { int x_count; int y_count; int d_count; }; // calculates total path count for a class size_t calculate_path_count(size_t x, size_t y, size_t d) { return factorial(x + y + d) / factorial(x) / factorial(y) / factorial(d); } // main computations procedure void calculate(size_t x, size_t y, std::map<path_class_t, size_t>& classification, std::vector<std::vector<move_t>>& path_set) { // first calculate classification and total path count size_t total_path_count = 0; for (size_t d = 0; d <= std::min(x, y); d += 1) { size_t count = calculate_path_count(x - d, y - d, d); total_path_count += count; path_class_t pc = {y - d, x - d, d}; classification[pc] = count; } // then enumerate all paths for each class path_set.resize(total_path_count); std::vector<move_t>* path_pos = &path_set[0]; for (size_t d = 0; d <= std::min(x, y); d += 1) { std::vector<move_t> path; generate_recursive(x - d, y - d, d, path, path_pos); } } // recursive enumeration of all possible permutations void generate_recursive(size_t x, size_t y, size_t d, std::vector<move_t>& path, std::vector<move_t>*& path_pos) { if (x == 0 && y == 0 && d == 0) { // if all moves are exhausted, then we have reached the destination point path.push_back(move_end); *path_pos++ = path; path.pop_back(); } else { if (x) { // if not all 'x' moves are exhausted, then move in 'x' direction path.push_back(move_x); generate_recursive(x - 1, y, d, path, path_pos); path.pop_back(); } if (y) { // if not all 'y' moves are exhausted, then move in 'y' direction path.push_back(move_y); generate_recursive(x, y - 1, d, path, path_pos); path.pop_back(); } if (d) { // if not all 'd' moves are exhausted, then move in 'd' direction path.push_back(move_d); generate_recursive(x, y, d - 1, path, path_pos); path.pop_back(); } } } Next page: Speeding Up |