Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Bert Bates wrote:Hi Mert,
Welcome to JavaRanch!
This is a nice puzzle! I don't know the answer but I can imagine these are roughly the steps I'll follow:
1 - Find a solution for fewer apples, maybe I'll start with 6 apples. For this step I won't worry about the "fewest" weighings.
2 - Try to find a more efficient approach for 6 apples
3 - From those two, perhaps have a theory about "the most" efficient way.
4 - Generalize that approach for N apples.
Bert
ocjp 6 — Feeding a person with food is a great thing in this world. Feeding the same person by transferring the knowledge is far more better thing. The reason is the amount of satisfaction which we get through food is of only one minute or two. But the satisfaction which we can get through the knowledge is of life long.
Mohana Rao wrote:Try to solve this puzzle yourself in the it end's up with great algorithm. You might face this type of question in interview too. First try out possible better solutions you can give.
mert sari wrote:my best algorithm is as following:
...
mert sari wrote:my best algorithm is as following:
step 1: from 15 apples , create randomly 5 groups that each group has 3 apples.
step 2: sort each group.
step 3: then we are going to find the heaviest apple in two weighings from the heaviest 5 apples of each of five groups.
step 4: then we are going to find the second heaviest apple in one weighing from 3 heaviest remaining apples (this is not obvious, you should try it and you will see there are 3 remaining apples to decide the second heaviest apple)
step 5: then again as step 4, we can find third heaviest apple in one sorting.
now, in worst case , there would be 4 apples to decide the fourth heaviest apple and we again start from step 3 , and so on, there will be totally 21 weighings.
i could not write code of this algorithm, it is really complicated. Can anyone have any idea how to write it?
and i am not sure if this is the best algorithm.
what do you think?
mert sari wrote:
I want to think of the case 22 weighings.
could you write it ? and then i will try it in my way.
Ryan McGuire wrote:
mert sari wrote:
I want to think of the case 22 weighings.
could you write it ? and then i will try it in my way.
There's the source code. Compile it and run it. As programmed, it will use random weights for the apples. If you run the program, say, 20 times, you should stumble upon a case that takes 22 comparisons.
Here's one initial list of apples weights that took 22 comparisons to order:
663, 55, 494, 671, 101, 776, 1, 524, 302, 696, 110, 446, 710, 427, 6
You could edit the Weights class to use this hard-coded list of weights instead of random numbers.
mert sari wrote:here the remaining 15 weighings
6: 776 > 663 >524
7: 776 > 710 > 696
8: 710 > 671 > 663
9: 696 > 671 > 427
10: 671 > 663 > 446 (before this weighing , there were 2 apples to test, i needed to add one more and there were 2 options 663 or 427, i added 663 since it is in third group while 427 is in fifth group, to sum up i add first one in the list.)
11: 663 > 427 > 101
12: 524 > 494 > 446
13: 524 > 494 > 427 ( i did not choose 446 instead of 494, since 494 is heavier than 446 due to previous weighing)
14: 494 > 446 > 302 ( there were 2 apples to test and i did the similar selection as explained above )
15: 446 > 101 > 55
16: 446 > 427 > 101
17: 427 > 302 > 110
18: 302 > 101 > 6
19: 110 > 101 > 1
no need to decide next one , 101 is heaviest one among 4 remaining apples since 101 > 1 , 101 > 6 , 101 > 55 .
20: 55 > 6 > 1