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?
