|
This is exercise 1-29 from The Algorithm Design Manual.
There are 25 horses. At most, 5 horses can race together at a time. You must
determine the fastest, second fastest, and third fastest horses. Find the
minimum number of races in which this can be done.
This is quite a famous puzzle question and involves some algorithmic thinking.
The first key to understanding for me was to focus on excluding horses who are
slower than at least 3 other horses. This lets you run a process of elimination
instead of a process of selection.
The second key for me was that you’re not just sorting individual horses but also
sorting sets by their fastest horse.
With those two points in mind, you can go through the process.
First we have to run 5 races to race all of the horses. Rather than label them
$a_1$, $b_2$ etc like other explanations, I’ve colour-coded the horses in each set.
This seems easier to think about for me.
After racing the 5 colour-coded sets, we’ve got 5 sets of horses where we know
the relative ordering within each set:
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
Because we can eliminate any horse that is slower than at least 3 other horses,
we can get rid of the last two horses in each group (the 4th and 5th positions),
leaving us with 15 horses:
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
Now we race the fastest (1st position) horse from each group in a sixth race:
1🐎︎ 1🐎︎ 1🐎︎ 1🐎︎ 1🐎︎
This sixth race does two things. It lets us identify the fastest single horse
overall, as it’s the fastest of the fastest. Less intuitively, but essential for
solving the puzzle, is that it lets us order the original 5 groups and eliminate
more horses.
Let’s say that the order of the sixth race was red, orange, purple, green and
blue. Red came first, so it’s the fastest overall horse. We can now also
incorporate this extra ranking across the groups:
1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
(Notice that we’ve “eliminated” the #1 red horse, as we know it’s the fastest
overall).
Remember that we can eliminate any horse that is slower than at least 3 other
horses. That means we can eliminate the green and blue groups entirely now,
because even their fastest horses were slower than at least the fastest red,
orange and purple horses:
1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
As you can see, we’re eliminating more and more horses with this “slower than 3”
rule. We can apply it further. We know the 3rd purple horse was slower than the
2nd and 1st purple horse. We also know the 1st purple horse was slower than the
1st orange horse. That’s 3 horses, so we can eliminate the 3rd purple horse:
1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
Similarly, we know the 2nd purple horse was slower than the 1st purple horse,
which was slower than the 1st orange horse and the 1st red horse. Again, 3 horses were faster,
so we can eliminate the 2nd purple horse too:
1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
We can eliminate one more horse with the “slower-than-3” rule: the 3rd orange
horse. It was beaten by the 2nd and 1st orange horses, which in turn were slower
than the 1st red horse. So the 3rd orange horse is eliminated:
1: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
2: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
3: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
4: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
5: 5🐎︎ 4🐎︎ 3🐎︎ 2🐎︎ 1🐎︎
Notice that we only have 5 remaining horses to sort now, and only the 2nd and
3rd overall positions to find. We just run a race with those 5 remaining horses
to find out:
3🐎︎ 2🐎︎ 1🐎︎ 2🐎︎ 1🐎︎
As it turns out in this example, the 1st purple horse and 2nd red horse take the
top two positions in this race. That means the final top three are the 1st red,
1st purple and 2nd red horse:
🐎︎ 🐎︎ 🐎︎
This takes a total of 7 races: the initial 5 groups, the fastest-of-fastest
race, and the surviving runners up race at the end.
See also
View post:
Algorithm Design Exercise 1-29: Finding the Fastest of 25 Horses
|