Single-Threaded Implementation

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:

    • paths with X horizontal moves, Y vertical moves and 0 diagonal moves

    • paths with X-1 horizontal moves, Y-1 vertical moves and 1 diagonal move

    • paths with X-D horizontal moves, Y-D vertical moves and D diagonal moves, where D=min(X,Y)

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