DEV Community

Can you solve the fastest horse 🐴 algorithm problem?

kapeel kokane on December 27, 2019

In this week's article, we dig into something different. Let us look at an algorithm problem wherein there are multiple approaches but just one o...

Read full post

Idan Arye • Dec 28 '19

Start by grouping them into 5 groups - a, b, c, d and e - and have each group race within itself. Let's say these are the results:

a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
a4 b4 c4 d4 e4
a5 b5 c5 d5 e5

Obviously any horse ranked fourth or fith within its own group cannot be in the top 3, leaving us with:

a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3

Now, pick the fastest horse of each group and let them race among each other. Without loss of generality, assume a1 finished first, then b1, then c1, then d1 and finally e1.

d1 and e1 cannot be in the top 3, and we can also eliminate the rest of the d and e groups (which are slower than d1 and e1):

a1 b1 c1
a2 b2 c2
a3 b3 c3

c1 cannot be the fastest horse, nor can it be the second fastest - at most it can be third, because a1 and b1 are faster than it. This means c2 and c3 can at most be fourth and fith - which we do not care about:

a1 b1 c1
a2 b2
a3 b3

Similarly, we can eliminate b3 - but not b2 because it can still be third (if the first trio is a1 b1 b2):

a1 b1 c1
a2 b2
a3

This leaves us with 6 horses. But we already know that a1 is the fastest of them all - so we can just make the other five race to determine second and third place.

A total of 7 races.

Idan Arye • Dec 28 '19

OK, I watched the video and they used the same solution. I was hoping to also see a proof that this solution is indeed minimal - but there wasn't.

Can we prove this? I've given it some thought and I think I can prove that this is impossible with 6 or less races.

We will deal with different arrangements of the first 5 races:

The simplest case is where 19 or less horses participated in these first 5 races. This means we have only one more race and 6 or more horses, so at least one horse will not participate in any race - which is obviously a wrong solution.

The case where 20 horses participated in the first 5 races is also simple - if the final race will have these 5 horses, we will not be able to compare them to the 20 horses from the first 5 races, so this arrangement is also wrong.

The case where all 25 horses participated in the first 5 races. This means these 5 races were disjoint. Here we need to split the sixth race:

If we pick the first horse of each group, we won't know how the second and third places of that final race are compared to the second and third places of the original group of the winning horse - so this solution is wrong.
If we pick a different horse from at least one group, and that horse does not reach first place - we won't be able to tell how the leading horse of that group compares to the winner of the last race, so this solution is also wrong.

The case where between 21 and 24 horses participated in the first 5 races. Let N be the number of horses who did not participate. For each such horse, there is a link between two groups of 5 horses (one horse that participated in both). At best this link turns these two groups into a single group where we know the order (same horse finished last in one group and first in the other). This means that the horses from the first 5 races can be grouped to 5-N groups. Each of the horses that did not participate is a group of a single horse - so in total we have N+(5-N)=5 groups. Note that:

We need to pick a horse from each such group - or else we won't be able to compare the group that wasn't chosen with the other groups.
We must pick the fastest horse of each group - because if we pick another horse and it isn't the first we won't be able to determine which horse is the fastest.
At least one group has more than one horse. Now - since we can compare the second horse of the group with more than one horse with the second horse of the final race - we can't determine the total second place, and this case is also a wrong solution.

We have shown that with 6 races, not only is it impossible to determine the top 3 horses - it is also impossible to determine the top 2! I suspect the number 3 was chosen because you can't find more than that with only 7 races - but the proof for that is left as an exercise to the reader.

BudPrager • Dec 28 '19 • Edited

Given there is no constraints on what information we can gather from each race, and no constraints on assumptions. The only constraint is the number of tracks we have to use.

We can do this in five races providing we can time the races and each horse runs it's fastest every time it runs.

Split the horses into 5 groups and ensure that every horse runs at least once.

Time the horses and the 3 fastest times give you the 3 fastest horses.

kapeel kokane • Dec 28 '19

I'm sorry, should have mentioned timing the horses was not an option 🙈

BudPrager • Dec 28 '19 • Edited

Yeah I was working outside of the spirit of the question, but these are the kinds of assumptions you should ask about in an interview when not specified, it shows an ability to think outside the box.

3cho0 • Dec 27 '19 • Edited

7 races? That doesn't seem right.
Split the 25 horses into 5 arbitrary groups of 5. For each group, determine the fastest horse. Race each group. You now have 5 horses, each the fastest of their group. Race those 5 horses to determine the fastest horse overall - a total of 6 races.

EDIT: I misread the question statement, so the above answer is incorrect. Sorry about that. I would still encourage you to solve my question down below (it's easy and fun!), though it gets a little trickier when you want to know the j fastest horses instead of just the fastest :)

3cho0 • Dec 27 '19

Another fun, but simple exercise:
Find a closed formula that will answer this question for an arbitrary number of horses k and an arbitrary number of racetracks n.
Hint: Look at cases where n divides k first :)

Idan Arye • Dec 28 '19

But you need the top 3, not just the top 1.

3cho0 • Dec 28 '19

Yes. Please read my post and learn from my silly mistakes :)

Joseph Watson • Jan 3 '20 • Edited

So each horse runs the given race in the exact same amount of time every time (individually, not collectively)? There exists absolutely zero overlap of +/- of average time between horses such that given the same two horses, horse one could beat horse two or just as easily vice versus? That’s the only way you can say the generalized solution holds. And once you realize that you understand how unrealistic the problem in general is. It’s just academic nonsense.

Brad • Dec 31 '19

I remember going over this problem in class, it was a good time and we eventually came up with the same solution as stated by @idanarye . There was caveat that was brought up that should be mentioned and that's we shouldn't have a way to track individual race horse times.

Otherwise I could solve this problem by stating "time every horse using a stop watch", thus 5 races are the minimum to "get the speed" of every horse.

The stop-watch approach is 0 fun, but it is worth pointing out a missing constraint could totally change the problem.

I love puzzles/problems like this as they wreck your brain, and yet make your really think 😄

Warisul Imam • May 19 '20

Here's the solution I thought of. Assuming we're not allowed to measure the speed and judge whether a horse is fast or not depending on whether it finishes first or not.
Conduct five races with groups of 5 horses and eliminate the last two finishers from each group, which will leave us with 15 horses. Repeat the process again - but this time it takes three races - and we are left with 9 horses. Repeat the process again - eliminate last 2 horses from the group of 5 and last 1 horse from thr group of 4 - and we're left with 6 horses, 2 races taken. And finally, take 5 from these, get the top 3 (1 race taken) and race it with the other one left and eliminate the last one leaving with 3 horses(another race taken).

Means a total of 12 races. Now lemme check the video...
Happy Coding!

Warisul Imam • May 19 '20

Appears I actually got it right😅... Yeah tell me I looked at the solution or read it in the comments all you want...

Happy Coding🤗