DEV Community

Discussion on: Can you solve the fastest horse 🐴 algorithm problem?

Collapse
 
idanarye profile image
Idan Arye

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.

Collapse
 
idanarye profile image
Idan Arye

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:

  1. 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.
  2. 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.
  3. 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.