Objective

Input: a path of a directory containing test data Output: a valid test list, as good as possible, satisfying the requirements below

Requirements

Let N denote the number of files in the file list. The following conditions must be satisfied:

• If N ≤ 128, output must be one of the best test lists, i.e. there does not exist any other test list which is better than the output.
• If N > 128, output is generated using a greedy algorithm which will be mentioned later.
• Guarantee of consistency: For each file list, the program must output only one output regardless of which OS is used or which computer is used or how many times the program is executed.
• Guarantee of running time: The program must terminate within 1 second on my laptop (Pentium(R) Dual-Core CPU T4400 @ 2.20GHz × 2) for any test cases.

Algorithm for N ≤ 128

• Let L be a list of spec. Initially, L is empty.
• For each approved spec, add it into L.
• For each pair of relative paths in the file list, add its suffix spec into L.
• For each pair of relative paths in the file list, add its prefix spec into L.
• Let S be the best spec in L.
• Output the maximum test list of S.