Problèmes et solution Intel threading challenge 2010 apprenti

 

Problèmes et solutions de l'Intel Threading challenge 2010 niveau Apprenti

 

En plus des problèmes, vous trouverez ci-dessous tous les codes des gagnants ainsi que leur explications pour la partie "Apprenti" du concours de programmation parallèle Intel Threading challenge 2010. N'hésitez pas à venir en discuter sur nos forums et ainsi donner votre avis sur ceux-ci.


Niveau "Apprenti "

Problème 1 - Connected Components

A graph is a construct containing a set of nodes (or vertices) and a set of edges defined by the two nodes that are connected by the edge.  If there is no ordering of the nodes that defines an edge, the graph is undirected. A path exists between two nodes in a graph if there is a sequence of nodes in which successive nodes are connected by edges in the graph.

We call a graph connected if there is a path from any node to any other node in the graph. If a graph is not connected, it will be made up of connected components, that is, a set of connected subgraphs with no shared nodes between any two subgraphs.

Problem Description: Write a threaded program to compute the number of connected components and the maximum and minimum number of nodes from among the connected subgraphs within an input graph. The command line to your application will contain the name for the input file containing the graph.

Input file description: The file will contain a number of lines containing edges within the graph to be considered. Nodes will be represented by three capital letters in the range 'A' to 'Z'.  An input line will contain six capital letters, the first three being one node and the second three being the other node defining the edge.  End of File (EOF) will signify the end of the graph input.

Output: The total number of connected components within the input graph and the number of nodes found in the largest and smallest connected components are to be printed to stdout. For easy checking, output should be labelled.

Command line example: compcalc.exe testgraph.txt

Input file example: testgraph.txt

AAABBB
RRRTTT
AAAKKK
AAAZZZ
ZZZBBB
SSSRRR
TTTSSS
BBBKKK
KKKZZZ

Output example:

Total number of connected components:   2

Maximum sized connected component:   4

Minmum sized connected componet:   3

Timing: The total time for execution of the application will be used for scoring. (For most accurate timing results, submission codes would include timing code to measure and print this time to stdout, otherwise an external stopwatch will be used.)

 


Premier  Gagnant: pbialas Code

Second  Gagnant: jbosh Code

Troisième  Gagnant: groberts82 Code


Problème 2 - Prime Array

Prime Array Search


A word search puzzle constructs an array of letters with words embedded in the array using consecutive letters along any horizontal, vertical, or diagonal line. For example, given the 3x3 letter array...

|S A T|

|O E H|

|B E E|

...there are eleven English words to be found {A, AH, EH, EH, HE, BEE, BET, SAT, SEE, SOB, THE}.

A Prime Array is an MxN tabular structure populated by single-digit integers. By concatenating consecutive digits along any horizontal, vertical, or diagonal line, multi-digit numbers can be formed with the intent to construct prime numbers. The traditional prime array problem is to find such arrays that have the most prime numbers contained within.For example, given the 2x2 array...

|1 3|

|7 9|

...there are 11 primes to be found {3, 7, 13, 17, 19, 31, 37, 71, 73, 79, 97}.

This problem combines prime arrays and word search puzzles.Problem Description: Write a threaded code that finds an example of a prime array that has the maximum number of primes hidden within it for a given array size. The following three restrictions for constructing arrays and counting primes must be observed:

1. Multiple digit prime numbers can only be constructed by reading consecutive numbers from top to bottom (vertical) or left to right (horizontal and diagonal).  In the 2x2 prime array example given above, this would disqualify 31, 37, and 97 from being counted in the total. The number 73 is counted since it is read diagonally from left to right.

2. Only the digits 1..9 are to be used.

3. The total number of instances of a given digit within an array can be no more than one greater than the number of times any other digit is included. For the 2x2 case, a digit cannot appear more than once. In a 3x3 case, the following example is not considered a legitimate instance since the '1' digit appears twice, which is two more times than '8' appears (zero times).

| 1 1 3 |

| 7 5 4 |

| 9 2 6 |


Besides finding one example with the maximum number of primes that can be found contained in the array, a count of the number of other array configurations that also have the same number of primes must be computed.

Input: Two numbers will be given on the command line of the application.  These will correspond to the number of rows and columns, respectively, of the array to be constructed.  The range of values for both row and column values will be 1 to 10, inclusive.

Output: Output will be to stdout and must include one example of an array of the given size that contains the maximum number of hidden primes, the number of primes found in the array, a list of the primes that can be found within the printed array, and the number of total array configurations that have this maximum number of primes.

Output Example (from input '3 3'):

Example of the   3 x 3 case

8 2 3

4 5 7

6 1 9

20 primes are hidden in the array

{2 3 5 7 23 61 19 41 59 53 17 37 79 823 457 619 251 379 859 653 }

1 total array configurations share this maximum number of primes

Timing: The total time for execution of the application will be used for scoring. (For most accurate timing results, submission codes would include timing code to measure and print this time to stdout, otherwise an external stopwatch will be used.)

 


Premier  Gagnant: Rui Diao (doraemonok) Code

Second  Gagnant: archie314 Code

Troisième  Gagnant: jbosh Code

Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.