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

0

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.

InfinteScroll

Posted 2014-06-23T08:14:40.430

Reputation: 103

Could you please provide more information? For example, input format and some test cases. – ProgramFOX – 2014-06-23T08:15:34.490

1How do you measure "fastest"? – justhalf – 2014-06-23T08:27:14.553

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. – Howard – 2014-06-23T08:27:23.223

@justhalf lowest total time – InfinteScroll – 2014-06-23T08:30:15.650

1@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? – justhalf – 2014-06-23T08:32:53.107

its a function in a python script i run on my terminal to score a swim meet. this function is run with about 30 swimmers for a single call. this function takes an array of swimmer objects and returns an integer representing the lowest time relay that could be formed – InfinteScroll – 2014-06-23T08:42:06.197

@Howard if no dynamic method is logically possible, then I apologize. :/ . I just assumed there had to be a better way than brute force (I guess I was wrong!). if one were to cull away most of the swimmers except the 4 best ones per each stroke, ___^4 would only be _____, which i guess would be more time acceptable for brute force... – InfinteScroll – 2014-06-23T08:46:54.640

@StrikePricer You can cut all swimmers which have 5th or worse time in all strokes. Unfortunately there is the case of ties and thus the "4" best ones can be more than 4 swimmers. – Howard – 2014-06-23T08:59:38.097

Python 2.7 or 3? – Christofer Ohlsson – 2014-06-23T11:06:00.627

Answers

1

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

Christofer Ohlsson

Posted 2014-06-23T08:14:40.430

Reputation: 1 014

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' – InfinteScroll – 2014-06-23T17:45:22.987

1Yeah, 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. – Christofer Ohlsson – 2014-06-23T17:57:10.260

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. – InfinteScroll – 2014-06-23T18:21:59.837

Asked: 2014-06-23T08:14:40.430

Viewed: 259 times

Active: 2014-06-23T17:30:56.893