Welcome to the Friday edition of ProblemotD where we've now sold our startup and retired to a ranch with 25 horses. Luckily we've made friends with the right people and we're told to bring our best 3 race horses to the Kentucky Derby. Since we can only bring 3 horses we decide to race our horses against each other to see which ones are fastest.
The track that the horses will be racing on only has 5 starting gates which means only 5 horses can race each other at one time. This isn't a huge deal except that once we get to the track we realize our stop watch is broken. Now we can only tell what position each horse gets in each race (first - fifth). How many races will it take to find the 3 fastest horses?
For those interested in a programming challenge, instead of 25 horses write a program that solves for X number of horses.
Comments:
Carlos - 10 years, 8 months ago
DIdn't do any of the problems this week because i was in the Insanity Jam 2014, i just want to say to the creator: I appreciate the preview button :D Have a great weekend!
reply permalink
Max Burstein - 10 years, 8 months ago
No problem! What did you make at Insanity Jam?
reply permalink
Carlos - 10 years, 8 months ago
A disappointment... :)
http://jam.alamantus.com/insanity2014/viewtopic.php?id=254
You can see for yourself.
reply permalink
Fletcher - 10 years, 8 months ago
Race all horses and send the top 3 in each to the next round. We'll name the horses based on their heat and finishing location. First race horses are A1,A2,A3 based on finishing position. Second race will be B1,B2,B3 and so on.
Race A1,B1,C1,D1,E1. Take the 4th (D) and 5th (E) finishers and discard them along with their groups. We'll say for simplicity the horses finished A1 first through E1 last. Remove horses 2 and 3 from the 3rd place group (C2,C3) and the 3rd place horse from the 2nd place group (B3). None of those horses can be a top 3 thanks to the transitive property of horse racing at Logicland downs.
Our remaining horses at this point are A1,A2,A3,B1,B2,C1 with A1 being proven faster than all Ax and x1 horses. Therefore he's number 1. We need one more race to determine who is 2nd and third. We race A2,A3,B1,B2,C1. Take the top two finishers and put them behind A1 and you've got your horses.
5 races first round. 1 winners race. 1 to determine which horses are 2nd and 3rd. 7 total races.
reply permalink
Max Burstein - 10 years, 8 months ago
We have a winner! Well done
reply permalink
gulliverbear - 10 years, 8 months ago
Great explanation, thanks for the write-up!
reply permalink
btgrant - 10 years, 8 months ago
I had worked out a coding solution taking the top horse from each heat, but that also resulted an uneven distribution of horses in the last couple of rounds that I needed to account for. My solution always produces 3 horses at the end, so it meets that specific criteria, but I imagine the decision to take 3 horses from each race might eliminate the issues towards the end.
reply permalink