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 diagonalenum move_t {move_x, move_y, move_d}; // path classstruct path_class_t{    int x_count;    int y_count;    int d_count;}; // calculates total path count for a classsize_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 procedurevoid calculate(size_t x, size_t y, std::map& classification, std::vector>& 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* path_pos = &path_set;    for (size_t d = 0; d <= std::min(x, y); d += 1)    {        std::vector path;        generate_recursive(x - d, y - d, d, path, path_pos);    }} // recursive enumeration of all possible permutationsvoid generate_recursive(size_t x, size_t y, size_t d, std::vector& path, std::vector*& 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