3
\$\begingroup\$

I am trying to go through the problems on CodeChef and came across this problem:

In Byteland they have a very strange monetary system. Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit). You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins. You have one gold coin. What is the maximum amount of American dollars you can get for it?

I approached it using the following algorithm:

  1. Check if the total amount on gold coin is greater than (Total/2)+(Total/3)+(Total/4), return total amount on gold coin.

  2. Otherwise, recursively evaluate the maximum total amounts for (Total/2),(Total/3) and (Total/4) and return the sum total of these maximums.

My attempt:

public class ByteLandGold{

public static void main(String[] args){
        System.out.println("Printing the bytelandian equivalent for:");
        int byteLandCoin = Integer.parseInt(args[0]);
        System.out.println(ByteLandianConversion(byteLandCoin));
}


private static int ByteLandianConversion(int goldCoinAmount){
        int halfValue = (goldCoinAmount/2);
        int thirdValue = (goldCoinAmount/3);
        int fourthValue = (goldCoinAmount/4);


        int totalIntermediate = halfValue + thirdValue + fourthValue;
        if(goldCoinAmount > totalIntermediate)
                return goldCoinAmount;
        else{
                int maxHalfPortion = ByteLandianConversion(halfValue);
                int maxThirdPortion = ByteLandianConversion(thirdValue);
                int maxFourthPortion = ByteLandianConversion(fourthValue);
                return maxHalfPortion+maxThirdPortion+maxFourthPortion;
        }
}
}

One thing that I see in my code is that the recursive steps are calculating the overlapping sub-problems repeatedly. What would be one way to ensure that doesn't happen? Can somebody go through my code and give me some pointers on how to optimize it further and what can I change this snippet to solve it in a better way?

\$\endgroup\$
5
\$\begingroup\$

If you don't want to recompute the overlapping sub-problems, you could use a cache.

Create the cache in your class:

private HashMap<int, int> resultCache = new HashMap<int, int>();

Then check it at the top of the function:

if (resultCache.contains(goldCoinAmount)) return resultCache.get(goldCoinAmount);

And before returning a result, cache it:

if(goldCoinAmount > totalIntermediate)
    resultCache.put(goldCoinAmount, goldCoinAmount);
    return goldCoinAmount;
else{
    int maxHalfPortion = ByteLandianConversion(halfValue);
    int maxThirdPortion = ByteLandianConversion(thirdValue);
    int maxFourthPortion = ByteLandianConversion(fourthValue);

    int result = maxHalfPortion+maxThirdPortion+maxFourthPortion;
    resultCache.put(goldCoinAmount, result);
    return result;
}

Otherwise, your code is really fairly straightforward and thus fairly readable/maintainable. Readability is far more important than raw performance most of the time.

\$\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.