Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

in this question OP has presented a site where some puzzle are available. He described the problem about solving them. I was curious is that really so problematic. The first one was really easy, so I tried next one this time from the end that should be the hardest one (puzzle).

And here I have some problem with understating it or probably I am messing something.

Let focus on the example:

Data:

M1      C1      C2      277317
M2      C2      C1      26247
M3      C1      C3      478726
M4      C3      C1      930382
M5      C2      C3      370287
M6      C3      C2      112344

Result:

617317
2 3 6

My problem is that relying on the assumption that

any one compound can be used in a chemical reaction to create any other compound

The solution could be

508878
2 6 5

Why ? In the content of the task, we do not have sad anything about that we have to start with compound one then from this get two then from two, three etc.

So the result should be to have all cheapest compounds, basing on the assumption we dont need to care how it was created. So this reduce our problem to structure like this.

M1      C2      277317
M2      C1      26247
M3      C3      478726
M4      C1      930382
M5      C3      370287
M6      C2      112344

And from this list we should pick the lowest cost for each compound.


So how did the achieve that solution, 2 3 6 ?

By me they have used to complex logic for that, their basic assumption was that

C1 -> C2 is the same as C2 -> C1 so they have used a rank (hash code)

17 * 37 * 1 * 2 == 17 * 37 * 2 * 1

(for this post i have used easier representation using the bit shift and bit-wise or that is more less the same)

M1    001 | 010 = 011  277317
M2    010 | 001 = 011  26247
M3    001 | 100 = 101  478726
M4    100 | 001 = 101  930382
M5    010 | 100 = 110  370287
M6    100 | 010 = 110  112344

After such operation the set of solution is reduced to this form

M1    3  277317
M2    3  26247
M3    5  478726
M4    5  930382
M5    6  370287
M6    6  112344

So now I don't have the information about compounds, but only a rank that provide the solution.

We had three compounds on start we have three ranks so is seams to be correct, and the result is the same that in the example (cost 508878 machines 2 6 5).


My observation is that the content of the puzzle is very funny but have a lot of holes in the limitation about the method that should be applied to achieve the result.

So concluding, what i am messing ?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

I believe this is what you missed:

Facebook's lab must acquire enough machinery to ensure it can create all the necessary compounds no matter what compounds are available on the market

In other words, you must have enough machines so you will be able to go from X -> Y for any compounds X and Y. In your solution, 2 6 5, if you are given C1 you can't create C2 or C3.

share|improve this answer
    
Yes, that is it. Lesson to learn, improve the English skills. –  Vash Oct 21 '11 at 8:11
add comment

If you assume that you only can change C1 once, C2 once and C3 once. Then you only have 2 possibilities:

1577986
1 4 5

or

617317
2 3 6

Where the second is the cheaper one, and the solution

share|improve this answer
    
I do not follow the logic, why not 123 or 456 for example ? I only change once there to ? –  Vash Oct 20 '11 at 16:10
    
Well, I think you are supposed to change one of C1, one of C2 and one of C3. So 123 doesn't work because you are changing C1,C2, and C1 again –  simpleBob Oct 21 '11 at 8:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.