It’s been a while since I offered a coding challenge, so let’s remedy this.
This one comes from this week’s Car Talk’s puzzler. Here is the short version of it:
A farmer has a forty pound stone that he uses to weigh food for his animals on a scale. One day, he loans the stone to his neighbor. A few days later, the neighbor returns the stone and apologizes to the farmer because his stone is now broken in four pieces. The farmer responds “Please don’t apologize, you have actually made my life easier because with these four pieces, I can now measure any weight between one and forty pounds”.
The question is: how much do these four individual pieces weigh?
I’m adding a few clarifications, which are not necessarily what the Car Talk guys meant (I don’t have the solution and I haven’t looked at any discussion on the subject):
- The four weights are integers.
- The weights we can measure between one and forty pounds are in one pound increment.
- They are measured in one session (otherwise, you could measure forty pounds with a one pound stone by performing forty measurements).
- If there is no solution (the farmer might be bad at math), show the four weights that allow to measure the most weights between one and forty pounds.
The challenge? Write a brute force solution to this puzzler in any language that you want. I don’t care if your solution is slow, fast, ugly or elegant as long as it works, and I suspect that certain languages will be very good for this puzzler
Bonus questions:
- Your solution should explain how exactly you use the stone pieces to measure each weight.
- Is there a formal way to solve this problem without using brute force?