8
\$\begingroup\$

Problem

There was an interesting problem on the dailyprogrammer subreddit:

A number of sailors (let's call it N) are stranded on an island with a huge pile of coconuts and a monkey. During the night, each sailor (in turn) does the following without the others knowing:

  • He takes one N'th (e.g. if N=5, one fifth) of the coconuts in the pile and hides them
  • The division leaves one coconut left over, which is given to the monkey.

In the morning, they split the remaining coconuts between them. This time the split is even. There's nothing left over for the monkey.

Your task: Given the number of sailors (N), how many coconuts were in the pile to begin with (lowest possible number)?

I was hoping to get feedback on my solution, and possibly suggestions as to better implementation.

  • I am not terribly satisfied with my use of a potential infinite while loop (replace with a for and an upper bound - if so, what's the upper bound)?
  • Should I type cast to double when I calculate the multiplier value?

Example

  • The solution for 2 sailors is 11 coconuts.
  • 11 => 11 / 2 (since first sailor takes 1/2 of coconuts) => 5 remainder 1 (which goes to the monkey)
  • 5 => 5 / 2 (since seconds sailor takes 1/2 of remaining coconuts) => 2 remainder 1 (which again goes to the monkey)
  • 2 can be split evenly between the 2 sailors

Implementation

public class CoconutCalculatorImpl implements CoconutCalculator {
    @Override
    public double calculateCoconuts(final long sailors) {
        long factor = 1;
        final double multiplier = (double) sailors / (double) (sailors - 1);
        while (true) {
            double baseValue = (factor * sailors);
            long counter = 0;
            while ((0 == baseValue % (sailors - 1)) & (counter < sailors)) {
                baseValue = (baseValue * multiplier) + 1;
                counter++;
            }

            if (counter == sailors) {
                return baseValue;
            }

            factor++;
        }

    }
}
\$\endgroup\$
1
\$\begingroup\$
  1. As you are dealing with whole numbers and remainders do not use floating point numbers. It's inaccurate and furthermore confusing because others may think that the result may be not a whole number.
  2. As the solutions will get very high very fast consider to use BigInteger
  3. During calculation make sure your divisions will always be without rest
  4. Avoid return statements within the loop. Programmers have to search for breaking conditions through the code if you do not provide them in the loop header. Beside readability unexpected return, break or continue statements cause serious problems when extending the code or applying refactorings like "extract method".
  5. Use lazy evaluation of boolean operators (&& instead of &). In complex evaluations you give other developers the chance to count on the evaluation and produce side effects.
  6. Separate responsibilities. Currently two algorithms are fighting against each other. One is providing a factor and the other is using the factor to try a calculation. But maybe the second algorithm is not satisfied by the factor what is evaluated during calculation. This should be modelled explicitly.

I am not a mathematician. Maybe there is a more efficient way (a shortcut) to calculate it. But I won't cover that.

So here is a refactored version. It's more verbose but it has less accuracy problems and shows the responsibilites of the two algorithms. They communicate through a result object that contains the calculated base value so far and the information if the method was satisfied by the factor given so the base value is a valid result.

    public static BigInteger calculateCoconuts(final long sailors) {

        long factor = 1;

        CalculationResult calculationResult = null;

        do {

            calculationResult = tryCoconutCalculation(sailors, factor);
            factor++;

        } while (!calculationResult.isSatisfied());

        return calculationResult.getBaseValue();

    }

    private static CalculationResult tryCoconutCalculation(final long sailors, long factor) {

        BigInteger factorBI = BigInteger.valueOf(factor);
        BigInteger sailorsBI = BigInteger.valueOf(sailors);
        BigInteger baseValueBI = factorBI.multiply(sailorsBI);

        long counter = 0;

        boolean satisfied = baseValueBI.remainder(sailorsBI.subtract(BigInteger.ONE)).equals(BigInteger.ZERO);

        while (satisfied && (counter < sailors)) {
            baseValueBI = baseValueBI.divide(sailorsBI.subtract(BigInteger.ONE)).multiply(sailorsBI).add(BigInteger.ONE);
            counter++;
            if (counter < sailors) {
                satisfied = baseValueBI.remainder(sailorsBI.subtract(BigInteger.ONE)).equals(BigInteger.ZERO);
            }
        }

        return new CalculationResult(baseValueBI, satisfied);
    }


    public static class CalculationResult {

        private BigInteger baseValue;
        private boolean satisfied;

        public CalculationResult(BigInteger baseValue, boolean satisfied) {
            super();
            this.baseValue = baseValue;
            this.satisfied = satisfied;
        }

        public BigInteger getBaseValue() {
            return baseValue;
        }

        public boolean isSatisfied() {
            return satisfied;
        }

    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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