[This is my write-up for Intel Threading Challenge 2010. You may download the code for Microsoft Visual C++ at the bottom of the page]
Problem Statement
Write a threaded program to generate, classify and count paths between the origin (0,0) and a given point on the Carteisan grid. Paths are made up of moving from one integral grid point to another. There are three potential moves between grid points: one point North (parallel to the x-axis), one point East (parallel to the y-axis) or Northeast (diagonal toward the destination). The destination coordinates for the paths will come from the command line along with a file name to write out all generated paths.
The classification of paths is based on the number of each move used within the path regardless of the order of the moves. For example, if the destination point is (5,4), a ‘2-3-1' path contains two moves North, three moves Northeast, and one move East. Two examples of this category would be ‘NNneneneE" and "EneNneneN".
Input Description: The input to the program will be two non-negative integers and a file name, all on the application's command line. The integers will be the x- coordinate and y-coordinate of the destination point. The file given will be used to hold the generated paths to the destination point from the origin point (0,0).
Output Description: There are two outputs to be generated by the application. The first is the count of the number of paths for each relevant path composition category and the total number of paths in each. The counts reported by the program are to be printed to stdout.
The second expected output is the generated paths within the given output text file, one path per line. To keep the length of the output lines equal to the Manhattan distance between the origin and the destination, one character is to be printed for a move North (‘N') or East (‘E') and two characters for a Northeast move (‘ne'). The upper case and lower case will allow a human reading the file to distinguish between one move North followed by a move East (‘NE') and a single move Northeast (‘ne'). In this way it is not necessary to put a space character between moves of a path, which will also keep the size of the file smaller.
Next page: Single-Threaded Implementation