Home‎ > ‎Parallel Computing‎ > ‎Taxi Paths‎ > ‎

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
Comments