When I loaded YouTube recently, one of the suggested videos was entitled “How To Solve Google’s 25-Horses Interview Question” by MindYourDecisions. The video cover image contained the text:
“What is the best way to find the 3 fastest horses? You can race 5 horses at a time, but you do not have a watch.”
– MindYourDecisions on YouTube
I did not watch the video since I thought this might be a fun exercise in BASIC. Instead, I fired up the excellent XRoar emulator and began writing a simple program that raced horses.
I started with an array big enough to hold the speed of 25 horses:
DIM H(24)
In Color BASIC, arrays are base-0, so that represents H(0) to H(24).
Next I initialized the array with a unique speed value by simply going through the loop and assigning each horse a speed of 0 to 24:
FOR I=0 TO 24:H(I)=I:NEXT
My next step was to randomize the entries, so I looked back on an earlier article I posted about Random BASIC shuffling. I implemented the suggested from James Jones to swap values in this array:
FOR I=0 TO 24 IF I/5=INT(I/5) THEN PRINT J=I+INT(RND(25-I)-1) T=H(I) H(I)=H(J) H(J)=T PRINT H(I); NEXT
Now I had an array of 25 horse speeds — H(0) to H(24) — that contains a random selection of values 0 (slowest) to 24 (fastest).
If you wanted to just find the fastest horse, you could simply scan the array and remember the fastest entry you found. At the end of the scan, you know the fastest horse. Something like this:
FH=-1:FS=-1 FOR I=0 TO 24 IF H(I)>FS THEN FH=I:FS=H(I) NEXT PRINT "FASTEST HORSE IS";FH
…but since this question requires racing no more than five horses at a time, I had to split that up in to code that would run five races of five horses, then a sixth race that raced the winners of each of the five races.
This is not the solution to the question, but it was a fun exercise. Here is the messy program I came up with. It will first print out the speeds of all 25 horses (five per line, matching how they will be raced) and then run the five races and final race of the winners:
0 ' HORSES1.BAS
1 '
2 ' 25 horses
3 ' Race up to 5 at a time
4 ' Find the fastest horse
5 '
10 ' H(x) - horse speed
15 DIM H(24)
20 '
21 ' Initialize each speed
22 '
25 FOR I=0 TO 24:H(I)=I:NEXT
30 '
31 ' Randomize
32 '
35 FOR I=0 TO 24
40 IF I/5=INT(I/5) THEN PRINT
45 J=I+INT(RND(25-I)-1)
50 T=H(I)
55 H(I)=H(J)
60 H(J)=T
65 PRINT H(I);
70 NEXT
75 PRINT:PRINT "RACE!"
100 '
101 ' Find fastest horse
102 '
105 DIM FH(4)
110 '
111 ' Race five sets of five
112 ' FH(x) - fastest horse
113 ' FS(x) - and its speed
114 '
115 FOR R=0 TO 4
120 FH(R)=-1:FS=-1
125 PRINT R;"-";
130 FOR I=R*5 TO R*5+4
135 PRINT I;
140 IF H(I)>FS THEN FH(R)=I:FS=H(I)
145 NEXT
150 PRINT "=";FH(R)
155 NEXT
160 '
161 ' Race the five winners
162 '
165 FH=-1:FS=-1
170 PRINT " F -";
175 FOR I=0 TO 4
180 PRINT FH(I);
185 IF H(FH(I))>FS THEN FH=FH(I):FS=H(FH)
190 NEXT
195 PRINT "=";FH
200 PRINT "WINNER IS HORSE";FH
500 END
And the result (also messy) looks like this:
But this isn’t the solution we are looking for.
The question was what is the fastest way to find the fastest three horses. I found the fastest by running six races. I expect the solution is simple, but I do not know it.
I thought I’d share this here and see if anyone else wants to work on it.
Any takers?
If you don’t want possible hints on a solution, don’t read this.
A major factor is that we don’t know the absolute speed of any of the horses which means it’s not necessarily as easy as it might otherwise be. I don’t know what the really clever solution is, and I haven’t watched the referenced video. There is, however, a very simple solution: one can select groups of 5 horses, race them, and then keep only the three fastest in each group. The naïve method will knock 2 horses out of the running for each race, no matter which 5 horses you select each time, meaning that with 25 horses, you need to run 11 races. For relatively small inital group sizes, this is probably as good as any other way.
However, you can probably do better than that by keeping track of which horses are faster than other horses based on your observations from each race and you can use that information to build some sort of graph or something that shows relative horse speed and use that to exclude more than two horses from the answer through strategic selection of the horses to race. (“faster-ness” is transitive, after all. If A is faster than B and B as faster than C, then A is faster than C.) I haven’t worked out the exact sequence that would make the most sense, but it would probably make an interesting challenge to write the code to keep track of it. (Note that it could conceivably be useful to run a race that includes horses that have already been eliminated as potential winners.)
A fun problem to think about. Here’s what I’ve come up with:
Put the horses into 5 groups of 5 horses each. Race each group and put the winner of each group into a winner group and race them. We’ll call the winner of that race A₁, second place B₁, third C₁ and D₁, E₁ for 4th and 5th place.
Then name the horses in the groups they came from with numbers indicating where the placed in the original races:
A₁ A₂ A₃ A₄ A₅
B₁ B₂ B₃ B₄ B₅
C₁ C₂ C₃ C₄ C₅
D₁ D₂ D₃ D₄ D₅
E₁ E₂ E₃ E₄ E₅
From the winner race alone we know that D₁ and E₁ cannot be in the top 3 as there are 3 horses faster than them. And they are faster than the other “D” and “E” horses so that eliminates those two groups.
C₁ could be in the top 3 but C₂..₅ cannot as we know at least A₁, B₁ and C₁ are faster.
In the B group B₁ and B₂ could, at best, be second and third overall.
And finally, in the A group A₂ and A₃ might also be second and third. And we know that A₁ is in first place.
Luckily (as often happens in these problems) we have only 5 horses remaining that could be second or third fastest overall. Race A₂, A₃, B₁, B₂ and C₁. The winner of that final race will be second overall then second place will be third overall.
That’s 7 races: 5 group races, 1 winner race and a runner-up race.
Another way to consider that grid of horses is to look at diagonal slices:
A₁
B₁ A₂
C₁ B₂ A₃
etc.
The each slice from left to right is a “could be in that place” set. The first slice are the only horses that could be in first place overall. That’s only A₁ so it must be first overall. In the second slice we have the horses that could be in second place overall: B₁ and A₂. And in the third are the horses that could be in third place overall: C₁, B₂ and A₃.
But keep in mind that, except for first overall, any horse could place lower than their slice indicates. They cannot place higher. Maybe it would be better to call them “at best” slices rather than “could” slices.
Let me code this up in Color BASIC and see what happens.