Win a copy of Penetration Testing Basics this week in the Security forum!

A Hard Puzzle

mert sari
Greenhorn
Posts: 6
hi guys,
i am a newbie around here.
i have a very hard puzzle (at least i think it is hard).
i could not solve it.

here the puzzle:
-------------------------------------------------------------
there are 15 apples. Each of them has different weight. You want to sort them. You have a friend who will help you. He will sort 3 apples which you gave him and he will just tell you the order of these 3 apples . He will not tell anything about the weights of the 3 apples.
What is the minimum number of weighings to sort these 15 apples?

-------------------------------------------------------------

Bert Bates
author
Sheriff
Posts: 8900
5
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

mert sari
Greenhorn
Posts: 6
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

Hi Bert,

i have been trying to solve this puzzle for two months. i have done all you said before. the results?
i tried your first step and i found it for 6 apples with 6 weighings.
then i found a better way and it was 5 weighings.
also i tried it for 9 apples, and it requires 9 weighings with my method.
i tried to generalize it , but i am never sure if it is the solution. My solution is so ugly. it does not look like a solution. i guess my result was 21 weighings.
if you want , i can summarize my method.

Mohana Rao Sv
Ranch Hand
Posts: 485
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
Greenhorn
Posts: 6
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.

you are right. on the other hand there must be someone who can solve this puzzle, therefore i wanted to share it with you.
i am really tired now
as i said before, i have been fighting with this puzzle all month. Every day i try something new, but i could not come up with a good algorithm. i hope i will, but i want to hope someone will sooner

Sagar Kale
Ranch Hand
Posts: 188
Well following is one ( may be worst ) working possibility. Note that this solution is not the best or fastest algorithm. To find better algorithm you will have to combine this solution with other sorting algorithms.

Divide 15 into 8 groups

First group will contain only 1 apple and other seven groups will contain two apples and then make combination of 3 apples step by step.

Original List

50 ---------- 30 100 ---------- 10 150 ---------- 20 40 ---------- 140 110 ---------- 80 60 ---------- 70 130 ---------- 120 90

30 ---------- 50 100
10 ---------- 50 100 ---------- 30 150
10 ---------- 50 100 ---------- 30 150 ---------- 20 40
10 ---------- 50 100 ---------- 30 150 ---------- 20 40 ---------- 110 140
10 ---------- 50 100 ---------- 30 150 ---------- 20 40 ---------- 110 140 ---------- 60 80
10 ---------- 50 100 ---------- 30 150 ---------- 20 40 ---------- 110 140 ---------- 60 80 ---------- 70 130
10 ---------- 50 100 ---------- 30 150 ---------- 20 40 ---------- 110 140 ---------- 60 80 ---------- 70 130 ---------- 90 120

10 ---------- 30 100 ---------- 50 150
10 ---------- 20 100 ---------- 50 150 ---------- 30 40
10 ---------- 20 100 ---------- 50 150 ---------- 30 40 ---------- 110 140
10 ---------- 20 100 ---------- 50 150 ---------- 30 40 ---------- 110 140 ---------- 60 80
10 ---------- 20 100 ---------- 50 150 ---------- 30 40 ---------- 110 140 ---------- 60 80 ---------- 70 130
10 ---------- 20 100 ---------- 50 150 ---------- 30 40 ---------- 110 140 ---------- 60 80 ---------- 70 130 ---------- 90 120

10 ---------- 20 50 ---------- 100 150
10 ---------- 20 30 ---------- 100 150 ---------- 40 50
10 ---------- 20 30 ---------- 100 150 ---------- 40 50 ---------- 110 140
10 ---------- 20 30 ---------- 100 150 ---------- 40 50 ---------- 110 140 ---------- 60 80
10 ---------- 20 30 ---------- 100 150 ---------- 40 50 ---------- 110 140 ---------- 60 80 ---------- 70 130
10 ---------- 20 30 ---------- 100 150 ---------- 40 50 ---------- 110 140 ---------- 60 80 ---------- 70 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 150 ---------- 50 100
10 ---------- 20 30 ---------- 40 150 ---------- 50 100 ---------- 110 140
10 ---------- 20 30 ---------- 40 150 ---------- 50 100 ---------- 110 140 ---------- 60 80
10 ---------- 20 30 ---------- 40 150 ---------- 50 100 ---------- 110 140 ---------- 60 80 ---------- 70 130
10 ---------- 20 30 ---------- 40 150 ---------- 50 100 ---------- 110 140 ---------- 60 80 ---------- 70 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 50 ---------- 100 150
10 ---------- 20 30 ---------- 40 50 ---------- 100 150 ---------- 110 140
10 ---------- 20 30 ---------- 40 50 ---------- 100 150 ---------- 110 140 ---------- 60 80
10 ---------- 20 30 ---------- 40 50 ---------- 100 150 ---------- 110 140 ---------- 60 80 ---------- 70 130
10 ---------- 20 30 ---------- 40 50 ---------- 100 150 ---------- 110 140 ---------- 60 80 ---------- 70 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 50 ---------- 100 150 ---------- 110 140
10 ---------- 20 30 ---------- 40 50 ---------- 60 150 ---------- 110 140 ---------- 80 100
10 ---------- 20 30 ---------- 40 50 ---------- 60 150 ---------- 110 140 ---------- 80 100 ---------- 70 130
10 ---------- 20 30 ---------- 40 50 ---------- 60 150 ---------- 110 140 ---------- 80 100 ---------- 70 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 50 ---------- 60 110 ---------- 140 150
10 ---------- 20 30 ---------- 40 50 ---------- 60 80 ---------- 140 150 ---------- 100 110
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 140 150 ---------- 100 110 ---------- 80 130
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 140 150 ---------- 100 110 ---------- 80 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 100 150 ---------- 110 140
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 150 ---------- 110 140 ---------- 100 130
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 150 ---------- 110 140 ---------- 100 130 ---------- 90 120

10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 110 ---------- 140 150
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 100 ---------- 140 150 ---------- 110 130
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 140 150 ---------- 110 130 ---------- 100 120

10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 110 150 ---------- 130 140
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 100 150 ---------- 130 140 ---------- 110 120

10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 100 130 ---------- 140 150
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 100 110 ---------- 140 150 ---------- 120 130

10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 100 110 ---------- 120 150 ---------- 130 140
10 ---------- 20 30 ---------- 40 50 ---------- 60 70 ---------- 80 90 ---------- 100 110 ---------- 120 130 ---------- 140 150

Note that this could be worst possibility in terms of speed like bubble sort, but it will give you starting point to think ahead, may be by combining with other sorting algorithms you will be able to find better one.

mert sari
Greenhorn
Posts: 6
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?

Ryan McGuire
Ranch Hand
Posts: 1083
4
mert sari wrote:my best algorithm is as following:
...

21 is the best I've found so far for n=15.

As an exercise I implemented a binary tree (either balanced or not, depending on a flag) algorithm to sort any number of apples. I also took a stab at a bubble sort variation. Those two algorithms took anywhere from 31 to 48 comparisons to sort the apples. In retrospect I see that there is just too many redundant comparisons to be optimal. e.g. Comparing B, C and D after I've already compared A, B and C. Once I know that, say, B is heavier than C, it's in efficient to involve those two apples in another comparison.

I do have an idea for modifying my bubble sort so that it devolves to mert's algorithm for n=15. I'll get back to you when I have working code.

Ryan McGuire
Ranch Hand
Posts: 1083
4
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?

In step 4, you say there are three candidate apples for the second-heaviest. I'm not convinced that's always true. Then again I may be missing something. Let me give an example:

Steps 1 & 2: Let's say...
A > B > C
D > E > F
G > H > I
J > K > L
M > N > O

Step 3:
D > A > G
J > D> M

So J is the first heaviest.

Step 4:
I see only two candidates for the second heaviest: D and K. All the other apples have at least one other apple that is known to be heavier:
A, E, F, G, and M have D
B and C have A
H and I have G
L has K
N and O have M

That's fine, we can compare D, K and some other apple to find the second heaviest. Did you have a way to pick that third apple in mind for you algorithm?

Ryan McGuire
Ranch Hand
Posts: 1083
4
Ok, I have the algorithm implemented enough to prove the concept. It uses mert's algorithm as a basis, but is generalized to any number of apples. Most of the time, sorting 15 apples requires 17-19 3-apple comparisons. I did get one run of random apple weights that required 22 comparisons, so it seems that either there's a hole in the 21-compare algorithm or I just don't understand the description of it.

I still have to neaten the coding a bit, get rid of some debug statments, make it all a bit more OO-ish, add more comments, and make the stopping condition work. Once I get that all fixed up, I'll post the Java code for people to poke at.

Ryan McGuire
Ranch Hand
Posts: 1083
4
• 1
As threatened:

A brief summary:
- For each apple, keep track of...
- - Whether it's been ordered as one of the X-heaviest yet ("used" in the Java code).
- - A list of unused apples that have been determined to be heavier.
- Step 1: Divide the apples into groups of three and order each group. Just to make life easy, I did them order 0, 1 and 2 make a group; 3,4,5; etc.
- Step 2: Find up to three apples that don't have any known heavier apples (the List<> of unused heavier apples has a count of 0).
- - If there were 0, we're done sorting.
- - If there was exactly 1, then it must be the heaviest of the "unused" apples. Mark it as "used" and remove from the lists of heavier apples you're keeping for the unused apples.
- - If there were exactly 2, then pick a third apple to use in the three-apple comparison below.
- - Compare the 3 you found and keep track of any heavier-then relations that you discover.
- Step 3: Go to Step 2.

Sure, the original problem was for 15 apples, but this algorithm is extensible to any number (even if N%3 != 0). Just set the howMany member to some other number. I ran this a bunch and the number of compares required for N=15 was usually 18-20, but I've seen occasional outliers of 16 or 22 comparison.

mert sari
Greenhorn
Posts: 6
i did not think it was programmable, but you did it.

i want to think of the case 22 weighings.
could you write it ? and then i will try it in my way.

thanks again

Ryan McGuire
Ranch Hand
Posts: 1083
4
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
Greenhorn
Posts: 6
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.

hi Ryan,

i tested the list above and with my method it requires 20 weighings.
please correct me if something is wrong in my summary.
here is the summary of the test

first we have 5 groups which are already sorted
55 < 494 < 663
101 < 671 < 776
1 < 302 < 524
110 < 446 < 696
6 < 427 < 710

here the remaining 15 weighings
776 > 663 >524
776 > 710 > 696
710 > 671 > 663
696 > 671 > 427
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.)
663 > 427 > 101
524 > 494 > 446
524 > 494 > 427 ( i did not choose 446 instead of 494, since 494 is heavier than 446 due to previous weighing)
494 > 446 > 302 ( there were 2 apples to test and i did the similar selection as explained above )
446 > 101 > 55
446 > 427 > 101
427 > 302 > 110
302 > 101 > 6
110 > 101 > 1
no need to decide next one , 101 is heaviest one among 4 remaining apples since 101 > 1 , 101 > 6 , 101 > 55 .
55 > 6 > 1

Ryan McGuire
Ranch Hand
Posts: 1083
4
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

Your walk through did help me find a bug in my algorithm.

Even once I fixed that bug, we still diverged at step 13 (for these particular inputs). After picking apples 7 and 13 (524 and 427), I see that all the other apples are known to be smaller than those two. In that case, I just use the lowest numbered apple. Since apple 0 is already out of the running, I used apple 1 (55). I see now that apple 2 (494) is a better choice because we already know that it's heavier than apple 1. I adjusted my algorithm so that it now makes that distinction. However there still seems to be a number of apples that have only one of 7 or 13 as necessarily being heavier: 2, 4, 8 and 14 (494, 101, 302 and 6). Always using the one with the lowest index (2 in this case) is as good a way as any to pick one, I suppose.

Anyhow, we now diverge at comparison 14. We both picked apples 2 and 8 (494 and 302) as the two obvious candidates. However I don't see how you chose apple 11 over apple 1 (446 over 55) to be the third one in the comparison. They've never been compared against each other directly and they have both been found to be lighter than apple 2. If you always go with with the lowest index, you should have used apple 1. Or are you using some other criteria to pick apple 11?

Anyhow, now that I found that first bug, my implementation is taking only 20 comparisons to sort those apples.

On a different subject...
My implementation uses separate code to do the first five comparisons. This is because the rest of the comparisons are done in a loop, which goes 0-14 to find comparison candidates. If we started using that loop from the initial state, it would still take 7 comparisons to get the heaviest apple but possibly then an additional 3 to get the second heaviest. (0-1-2, then 0-3-4, 0-5-6, 0-7-8, etc.). One way to make that loop work for the first five comparisons as well is to have the loop start at one higher than the previous highest index that was compared. e.g. After comparing 0-1-2, start looking for usable apples at index 3. This shouldn't cause any major differences except trying to match up the specific comparisons performed for a give set of inputs. e.g. That should one section of code work for what I'd previous labeled steps 1 AND 2.

I'll post the updated code when I have all the changes in.

Greenhorn
Posts: 16
I was interested in this problem because I wanted to practice and I was bored.

Borrowed the Weights class and the knownBigs idea from Ryan McGuire, and the algorithm from Mert Sari

Most solutions come in at 16-21 sorts, but the odd one out takes 22.

Example which requires 22 sorts for mine:
[645, 327, 511, 540, 133, 440, 754, 210, 195, 694, 976, 331, 245, 348, 897]

The heavy lifter for keeping the sorts down seems to be the adding of the 3rd item when there are 2 currently big items. Tried a few ways to get the 3rd, this seems to be a decent one, but I am interested in a better. Tempted to make a knownSmaller with the reverse mappings of knownBigger, and use it to find the next item with the largest amount of comparisons showing he is big, although necessarily not as big as the biggest.