# Find the fastest swim relay (shortest path of unique nodes and types)

fastest relay time = lowest possible total integer value of (a freestyle swimmers time) + (1 breastroke swimmers time) + (another backstroke swimmers time) + (another butterfly swimmers time)

• Each swimmer must be unique to the relay (no duplicates)
• Each stroke must be used once

Input Data: array of dictionaries, where each single dictionary represents a swimmer's swim times for each stroke. Each dictionary has the named properties of 'fly','back','breast','free':

Example Input:

[
{'Fly': 10, 'Breast': 48.26, 'Free': 28.43, 'Back': 34},
{'Fly': 47.51, 'Breast': 24, 'Free': 28.47, 'Back': 10},
{'Fly': 26, 'Breast': 46.44, 'Free': 10, 'Back': 30},
{'Fly': 37.81, 'Breast': 10, 'Free': 24, 'Back': 49},
{'Fly': 38.31, 'Breast': 29, 'Free': 20, 'Back': 10}
]


Example Output:

40


(this is an easy case where the best relay is simply the fastest person in each stroke; other times you might need to have the 3rd fastest breastroker swim breastroke in order to get the lowest overall time!)

Example Measurement of a relay using the first 4 swimmers in the data set above:

swimmer 1 swims fly and his time is 10
total += 10
swimmer 2 swims back and his time is 10
total += 10
swimmer 3 swims fly and his time is 10
total += 10
swimmer 4 swims breast and his time is 10
best relay total for these 4 people = 40


Output Data: should be a single float or integer value representing the total time of the best relay. (a legal relay includes a fly swimmer, a back swimmer, a breast swimmer, and a free swimmer, each leg of the relay swam by a unique swimmer)

EDIT: brute force vs dynamic parameter removed.

• Could you please provide more information? For example, input format and some test cases. Jun 23, 2014 at 8:15
• How do you measure "fastest"? Jun 23, 2014 at 8:27
• The problem statement reads like it requires a brute force solution in order to find an optimal combination - although I do not have a ready proof. Jun 23, 2014 at 8:27
• @justhalf lowest total time Jun 23, 2014 at 8:30
• @StrikePricer: Yes, my question is exactly "How do you measure which one has the lowest total time?" Is it run on your computer? On some online compiler? On what kind of input? How big is the biggest input? Jun 23, 2014 at 8:32

Meh, I'm no Python programmer by any stretch of the imagination. Hell, some would even hesitate to call me a programmer. But as nobody else has answerred this, why not post my solution? If anything else, it was fun just to brush up on the very Python basics:

swimmers = [{'Fly': 10, 'Breast': 48.26, 'Free': 28.43, 'Back': 34},
{'Fly': 47.51, 'Breast': 24, 'Free': 28.47, 'Back': 10},
{'Fly': 26, 'Breast': 46.44, 'Free': 10, 'Back': 30},
{'Fly': 37.81, 'Breast': 10, 'Free': 24, 'Back': 49},
{'Fly': 38.31, 'Breast': 29, 'Free': 20, 'Back': 10}]

bestTime = float('inf')

for fly in range(len(swimmers)):
for breast in range(len(swimmers)):

• does this line: if len(set([fly,breast,free,back])) > 3: help you check for uniqueness? your solution is almost exactly what I did, except I used a function to check a "relay" array for uniqueness (ie each swimmers being unique): `def unique_values(g): s = set() for x in g: if x in s: return False s.add(x) return True' Jun 23, 2014 at 17:45