wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes 25 horses to win, place, show Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "25 horses to win, place, show" Watch "25 horses to win, place, show" New topic
Author

25 horses to win, place, show

Rovas Kram
Ranch Hand

Joined: Aug 08, 2003
Posts: 135
I was asked this in an interview:

Given 25 horses and one 5-lane horse track, how many races must you run to determine the 3 fastest horses? You can not time the horses - no stop watch is available.
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
Lucky 7 is the answer...

I will let someone come up with why that is...

Eric
[ September 13, 2004: Message edited by: Eric Pascarello ]
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
you know what's a really goofy expression? "Don't look a gift horse in the mouth"


I've heard it takes forever to grow a woman from the ground
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
Race 1 to 5:
------------
run 5 horses in each and we would have 5 fastest horses.

Race 6:
-------
Make those 5 again. We would know Fastest and Slowest horse according to who finishes first and who finishes last.

Race 7:
-------
Make remaining three horses run again. Again see who was fastest and who was slowest. Now, forget who was slowest. Rest two are second fastest.

Result:
-------
from race 6: We find fastest horse
from race 7: We find second and third number horses ...

does this work?

regards
maulin
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
up until race 7 you are right....
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
yea.. i realized that

still working...
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923



http://home.arcor.de/hirnstrom/bewerbung
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
okay...

my friend solved it. so i won't write solution myself

regards,
maulin
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
I did this while watching the Monday Night Game...

http://www10.brinkster.com/a1ien51/JavaRanch/horseRace.html

I wanted to prove that my proof worked..

(there is no validation to see if numbers repeat)

Eric
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11160
    
  16

run 5 horses in each and we would have 5 fastest horses.

I may be missing something, but i have a problem with this statement. what happens if in the first race, the 5 fastest (of the entire 25) race together? In other words, EVERY horse in race 1 is faster than EVERY horse in race 2? you have just eliminated the real 2nd and 3rd fastest horse.

Or can you explain what i am missing?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
look at my link above, you see that in race 7, the 2nd and 3rd get placed in that race and that is how the problem you spotted gets fixed.

Eric
[ September 14, 2004: Message edited by: Eric Pascarello ]
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11160
    
  16

ok, now it makes sense. i had a little problem getting your link to open (it was just slow), but now i see it.

thanks
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
The host is acting up today!

I am posting a written out solution in a minute or two...
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
This race assumes one thing - The horses run the same speed everytime. This is a BIG assumption since this is never the case!

Lets do the simpliest senario: Horses are numbered with the way they should finish (1,2,3,...25)

The First Five races are run with the groups
Race 1: 1-5
Race 2: 6-10
Race 3: 11-15
Race 4: 16-20
Race 5: 21-25

Results
R1: 1,2,3,4,5
R2: 6,7,8,9,10
R3: 11,12,13,14,15
R4: 16,17,18,19,20
R5: 21,22,23,24,25

The first place horse from every race (1-5) is set to race in the 6th race.

Race 6: 1,6,11,16,21

Results:
R6: 1,6,11,16,21

Since no other horse beat #1 then it is number one, but you are not able to determine 2nd and 3rd place. The following figure shows why.



Horse #2 and #3 lost to horse #1 - since they lost by two spots they may be capable of beating #6 and #11
Horse #7 lost to horse #6. Since that is the case horse #7 is possibly the 3rd fastest horse.

Now looking at the figure, the horses in green have the ability to finish 2nd or 3rd.
The horses in yellow have the ability to finish in 3rd place.

Therefore the Race number seven is made up of the green and yellow horses (2,3,6,7,11)

If horse 2 wins the 7th race - that means horse 7 can not be in 3rd but 3,6,or 11 can be.
If horse 6 wins the 7th race - that means horse 3 can not be in 3rd but 2,7,or 11 can be.

Hope this makes any sense!

Eric
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
4, maybe 3.

Assume the track runs North/South. Divide the horses into three groups. Group A has ten horses. Group B has ten horses. Group C has five horses.

Race 1: Take the Group A horses. Line up 5 horses facing North at one end of the track, and line up five other horses facing South at the other end. Have them race towards the middle at the signal. Select the top three horses, mark them as A1, A2, and A3, and stow them away. Name them such that A1 is faster than A2 is faster than A3.

Race 2: Take the Group B horses. Line up 5 horses facing North at one end of the track, and line up five other horses facing South at the other end. Have them race towards the middle at the signal. Select the top three horses, mark them as B1, B2, and B3, and stow them away. Name them such that B1 is faster than B2 is faster than B3.

Race 3: Take the Group C horses. Line them up facing North at one end of the track, and line up A2, A3, B1, B2, and B3 on the other end. Have them race towards the middle at the signal. Select the top three horses.

if any of the A* horse were winners, and you know that A1 is faster then that horse, you can stop here, swap in A1, and you're done.

If there were no A* horses, then you need a fourth race between A1 and B1, B2, and B3.


Java Regular Expressions
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
lol....someone took the rules of racing and changed them...lol

You are looking for horses to get killed in the making of the race!

If I ever what o use this problem statement, I would specify full length of the course with enough room for one horse in each lane.


Eric
Helen Thomas
Ranch Hand

Joined: Jan 13, 2004
Posts: 1759
Originally posted by Joseph George:
you know what's a really goofy expression? "Don't look a gift horse in the mouth"


"..unless you have a good lawyer."


Le Cafe Mouse - Helen's musings on the web - Java Skills and Thrills
"God who creates and is nature is very difficult to understand, but he is not arbitrary or malicious." OR "God does not play dice." - Einstein
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
Originally posted by Eric Pascarello:
lol....someone took the rules of racing and changed them...lol

You are looking for horses to get killed in the making of the race!

If I ever what o use this problem statement, I would specify full length of the course with enough room for one horse in each lane.


Eric


And you very well might. As the problem is stated, I think it's an exercise is strict logic: that is, don't assume you know the length of the track, don't assume that races must be run in this direction or that, etc. Take what's given: you have access to the horse, the track, and no timing mechanism.

You need to identify the fastest three horses by running as few races on the track as possible(I suppose, technically, that there's no reason to run them on the track: however, we don't know that we have access to any other running area, so we can't logically assume that we do).

The dead horse issue, for example, could be addressed by measuring off n paces from the center( towards each direction) from the middle of the track, whatever n needs to be.

I usually love puzzles like this: moreso when I get an unexpected solution.
[ September 14, 2004: Message edited by: Max Habibi ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
The dead horse issue, for example, could be addressed by...

Normally we'd want to beat it for a while too, right?


"I'm not back." - Bill Harding, Twister
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
Well, by Max's logic, I could do it in 1 race. Divide the track into 25 equal length segments. The horse to cover his segment the fastest gets first place, and so on.
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
but that loic assumes that the horses run the same spped the whole length which would not be the case!
Nick George
Ranch Hand

Joined: Apr 04, 2004
Posts: 815
The original proposition asked for the FASTEST horse. It didn't ask for the fastest horse over 300 miles or the fastest horse over 3 feet. Nor was any length ever specified. Thus, I will define fastest in the only reasonable way in this instance: covers an arbitrary distance in with the lowest elapsed time.
Suhaasi Karnik
Greenhorn

Joined: Mar 15, 2004
Posts: 23
If you make use of only half the length of the track, then it would'nt be a good indicator of the winner. The standard racing distance ought to be maintained. Hence I feel that you have to run seperate races.
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

When we answer such a question we have to keep as close as possible to reality, I guess.

Of course assuming the order of fastest horses to be the same, no matter how often they run, and in which combination, is unnatural, but has to be accepted.

While there are places, where the horses run clockwise, and other, where they run counter-clockwise, it's allways depending on the arena, where they are running. (Berlin: clockwise, i.e.)

A race, where half of them run the one direction, and the other one in the opposite, hasn't been seen too.

Some arenas arent only ovals, but have special starting-lanes, leading into the oval:

Making starts into opposite direction impossible.

You allways have to find the right balance between reality and model, to solve the problem.
Max Habibi
town drunk
( and author)
Sheriff

Joined: Jun 27, 2002
Posts: 4118
Originally posted by suhaasi karnik:
If you make use of only half the length of the track, then it would'nt be a good indicator of the winner. The standard racing distance ought to be maintained. Hence I feel that you have to run seperate races.


But we really have no idea how long the given track is, what type of racing it's appropriate for, etc. Generally speaking, these sorts of puzzles are designed to test logical thinking: they designed to test our ability to differentiate assumptions from givens. But, as Stefan said, there must be some basis of reality: for example, no one said the horses were awake, but we've all assumed it.

I really think these puzzles are most amusing when we amuse ourselves. If you're satisfied with your answer under whatever premise you find acceptable, or it you're satisfied with another's answer under whatever premise you've found acceptable, then you'll probably get a grin out of it, which is worthwhile.

All best,
M
[ September 15, 2004: Message edited by: Max Habibi ]
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
I am really surprsed on the all o the ways it can be attacked, shows you how you could make the person that asked you this confused as hell! LOL
Maxim Katcharov
Ranch Hand

Joined: Sep 07, 2004
Posts: 113
Unfortunatley, I managed to spoil it for myself by scrolling down before I decided if I wanted to give it a shot. I'll try to make this interesting for myself then... I'll see if I can figure out how this problem would extend to more "fastest horses". If you'd like to join in on my fun, please do:

5/25:1 - 6
5/25:2 - 7 (last race: 2 horses)
5/25:3 - 7
5/25:4 - ?
...
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Max: I agree that a unconventional solution is ok, if you enjoy it, but perhaps because I went to some horseraces for some time, I have a more restricted idea of the rules, than a person, who only knows horseraces from sayings, stories or TV.

Horses like to run in groups, and have the tendency, to follow each other, and run in the same direction, which would make it really complicated, to let them start in opposite directions.

If the question had been on crocodile-races, I would have had much less problem with such a solution
Rovas Kram
Ranch Hand

Joined: Aug 08, 2003
Posts: 135
I like the solution that seeks to eliminate those horses that are not in the top 3. For easy book keeping, let's start our elimination process after the 6th race - the race between the 1st place horses of the first five races.

I'm calling any of the first 5 races round 1.
6th race elimination:
1st - 2 horses - the 4th and 5th from its race in the first round
2nd - 3 horses - the 3rd, 4th, and 5th from its race in the first round
3rd - 4 horess - the 2nd, 3rd, 4th, and 5th from its race in the first round
4th - 5 horses - all from its race in the first round
5th - 5 horses - all from its race in the first round

That totals 19 horses eliminated leaving 6 horses. The 1rst place horse is indeed the fastest horse so that leaves 5 horses for the 7th race.
[ September 20, 2004: Message edited by: Rovas Kram ]
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
Originally posted by Maxim Katcharov:
Unfortunatley, I managed to spoil it for myself by scrolling down before I decided if I wanted to give it a shot. I'll try to make this interesting for myself then... I'll see if I can figure out how this problem would extend to more "fastest horses". If you'd like to join in on my fun, please do:

5/25:1 - 6
5/25:2 - 7 (last race: 2 horses)
5/25:3 - 7
5/25:4 - ?
...


I think 4 is 8 without really thinking about it and 5 would be 9. I did not really sit down and calulate the possibility.

Eric
Rovas Kram
Ranch Hand

Joined: Aug 08, 2003
Posts: 135
I say 4 is 10.
Maxim Katcharov
Ranch Hand

Joined: Sep 07, 2004
Posts: 113
Assume theres a hefty entry fee, so racing less horses against each other is better, so you'd have to say "in the last race, only X horces need to race".

At 4 it gets hard to understand because you have the chance to try something completley different from the first method used to solve this, so share your solution
Rovas Kram
Ranch Hand

Joined: Aug 08, 2003
Posts: 135
Hi Max,

I'm assuming that you're addressing me. My solution for determining the fastest 4 horses is similar to my solution for 3 horses. Except after 6 races, I can only reduce the number of horses down to 10. Again the winner of race 6 is the fastest horse so that leaves 9 horses. I run these remaining horses in races 7 & 8(round 2) and then winners of those races(2 horses) in race 9.

After the 9th race elimination:
1st - all horses after 3rd place in round 2
2nd - all horses after 2nd place in round 2

That leaves 5 horses. The 1st place horse is the 2nd fastest horse so I run the 4 remaining horses in race 10 to determine 3rd and 4th fastest horses.
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    6
I sat down for 2 minutes and came up with this, can anyone see a problem in this logic?

To determine the 4th place horse, you need to run 1 more race.

This race can contain between 2 to 4 horses depending on where the heats the fastest horses were in.
  • Take Horse that finished 3rd in the 7th Race
  • *Take the Horse that finshed after the 1st place horse in its first race
  • *Take the Horse that finshed after the 2nd place horse in its first race
  • Take the Horse that finshed after the 3rd place horse in its first race

  • * - Note these may be the 2nd and 3rd places horses therefore they can be excluded since we already know their position.

    The winner of this race is the 4th fastest horse.

    You can keep repeating the same sort of logic for each position I think...

    Eric
    Rovas Kram
    Ranch Hand

    Joined: Aug 08, 2003
    Posts: 135
    Hi Eric,

    Assuming your race 7 is as I explained it for determining the 3 fastest horses, your logic is flawed because race 7 excludes horses one of which maybe the forth fastest horse. Your erroneous logic is why I prefer the process of elimination - seek to eliminate and the results will take care of themselves.
    [ September 22, 2004: Message edited by: Rovas Kram ]
    Eric Pascarello
    author
    Rancher

    Joined: Nov 08, 2001
    Posts: 15376
        
        6
    I did not read your explaination, I am going on my explaination up top since I know it works and wrote a program to prove it.

    The 3rd horse in the 7th race can only be the 4th fastest horse since 3 other horses finished before them.

    My way deals with elimination.

    When I am sitting at home tonight I will try to write a program that solves 1 - 25 with my logic...

    Eric
    Rovas Kram
    Ranch Hand

    Joined: Aug 08, 2003
    Posts: 135
    Eric,

    I read your explanation and it's basically the same as mine for finding the 3 fastest horses. For the fastest 4 horses, you work from the results of the same race 7 - maybe you've got it right.
    Marc Peabody
    pie sneak
    Sheriff

    Joined: Feb 05, 2003
    Posts: 4727

    The dead horse issue??? Hmm... good idea. Kill 22 of the horses and only 1 race is needed. Uggh, I feel like such a horrible person.
    Maybe kill just 20? I'm still not feeling much better.

    Actually, if you take out 22 you wouldn't need to race at all because the problem doesn't state that you have to put the three in order.
    What would an interviewer think of such an answer?
    [ September 23, 2004: Message edited by: Marc Peabody ]

    A good workman is known by his tools.
    Maxim Katcharov
    Ranch Hand

    Joined: Sep 07, 2004
    Posts: 113

    # Take Horse that finished 3rd in the 7th Race
    # *Take the Horse that finshed after the 1st place horse in its first race
    # *Take the Horse that finshed after the 2nd place horse in its first race
    # Take the Horse that finshed after the 3rd place horse in its first race


    Perhaps you meant something different, but what happens if in the first race, the three finalists are in the same "original" heat? This would exclude the other horses except for the one after the third finalist. I'm guessing you mean take the horses that finished after the three of the 6th heat?

    I'm a bit stuck by that, and the whole problem in general, so I'll have a go at the logic... after the 7 races, you have the following.


    Each number is placed beside a horse which may possibly be a horse that places as that number...



    Say the original 7 give us the following results



    'A' may actually be in a position to be faster than #4.

    After 6 races, we know that '1' is #1. After 7 races, we know that '1', 2, 3, 4 and 5 are their respective places. However, when the fourth place needs to be determined, 'A' needs to be raced against '4', because it cant be said that A is slower... we only know that '4' is not in third place... this extends to horses 5 and 6 as well. So apart from the losers (4/5/6) there are now 4 more horses (A/B/C/D) competing for fourth place. This means that at the end of the 7th race, 7 horses need to be compared for 4th place. We can race '4' against A B C D, and if '4' wins, we know that 4 is #4. If 4 loses, all we know is that either A B C or D is fas... hah, and there's the solution in 8 moves, as 3 of those 7 have already been compared! How simple it seems now compared to 15 minutes ago...

    - On the final race, race horses A, B, C and D (as in the above diagram) against the horse placing fourth in the 7th race.

    I wonder if I should perhaps delete all my fumbling and gloriously declare this solution (and hope I didn't mess up somewhere...)
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: 25 horses to win, place, show
     
    Similar Threads
    Questions to ponder . . .
    I am addicted to
    This Weeks GiveAway:
    Just curious...
    Kathy and Bert's bit parts at an Icelandic Horse Show