0
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Could you please provide more information? For example, input format and some test cases. \$\endgroup\$
    – ProgramFOX
    Jun 23, 2014 at 8:15
  • 1
    \$\begingroup\$ How do you measure "fastest"? \$\endgroup\$
    – justhalf
    Jun 23, 2014 at 8:27
  • \$\begingroup\$ 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. \$\endgroup\$
    – Howard
    Jun 23, 2014 at 8:27
  • \$\begingroup\$ @justhalf lowest total time \$\endgroup\$ Jun 23, 2014 at 8:30
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – justhalf
    Jun 23, 2014 at 8:32

1 Answer 1

1
\$\begingroup\$

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)):
        for free in range(len(swimmers)):
            for back in range(len(swimmers)):
                if len(set([fly,breast,free,back])) > 3:
                    current = swimmers[fly]['Fly'] + swimmers[breast]['Breast'] + swimmers[free]['Free'] + swimmers[back]['Back']
                    if current < bestTime:
                        bestTime = current

print bestTime
\$\endgroup\$
3
  • \$\begingroup\$ 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' \$\endgroup\$ Jun 23, 2014 at 17:45
  • 1
    \$\begingroup\$ Yeah, a set has no duplicate values, so the length of a set created from a list L, gives us the number of unique elements in L. It was the first idea I had, but I guess it can be done in a great deal of ways. But I have no hopes of my solution being faster than other brute force attempts. I sort of gave up on improving asymptotical performance and just went for legibility. \$\endgroup\$ Jun 23, 2014 at 17:57
  • \$\begingroup\$ it takes a little more code, but one way I found to speed it up was to create a fly list, a back list, a breast list, and a free list and then sorting each stroke to only the fastest 5. I guess it would cut way down on the amount of brute forcing needed. You still then loop 4 times as you've done here. \$\endgroup\$ Jun 23, 2014 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.