12
\$\begingroup\$

Problem Statement

In a school, chocolate bars have to be distributed to children waiting in a queue. Each Chocolate bar is rectangular in shape. Consider its side lengths are integer values.

The distribution procedure is as follows:

  1. If a bar is not square in shape, then the largest possible square piece of Chocolate is broken and given to the first child in queue.
  2. If bar is square in shape, then complete bar is given to the first child in queue.

Once a child receives his share of Chocolate, he leaves the queue. The remaining portion of the Chocolate bar is dealt in same fashion and the whole or a portion of it is given to the next child in the queue.

School has a carton of Chocolate bars to be distributed among the children all over the School. The Chocolate bars in the carton are of different sizes. A bar of length i and breadth j is considered to be different from a bar of length j and breadth i.

For every i such that M<=i<=N and every j such that P<=j<=Q (where M, N, P and Q are integers). Each Chocolate bar in carton is unique in length (i) and breath(j).

Given the values of M, N, P and Q (where M, N values are the ranges for length of Chocolate and P, Q values are the ranges for breadth of the chocolate). Find the number of children who will receive Chocolate from the carton.

Input Specification:

M, N, P, Q are of integer type (M, N values are the ranges for length of chocolate bar. P, Q values are the ranges for breadth of chocolate bar).

Output Specification:

Number of children who will receive Cadbury bar from the carton.

M = 5, N = 6, P = 3, Q=4 Here, i can be from 5 to 6 and j can be from 3 to 4. So the four bars will be in carton of sizes 5x3, 5x4, 6x3, 6x4.

First we choose a cadbury bar of size 5x3:

  • first child would receive 3x3 portion (remaining 2x3 portion)
  • next child would receive 2x2 portion (remaining 2x1 portion)
  • now the remaining portion are 2 square pieces of (1x1), which can be given to 2 more children

So the Cadbury bar with the size of 5x3 can be distributed to 4 children.

Similarly we can find out number of children for rest of the combinations (i.e. 5x4, 6x3, 6x4) in the given range as follows:

Chocolate Distribution Explanation!

Please let me know the corrections that I can make to improve the code.

public class CandidateCode {


    public int distributeChocolate(int input1,int input2,int input3,int input4){
        int[] chocolatelengthLimits = {input1,input2};
        int[] chocolatewidthLimits = {input3,input4};
        Set<Chocolate> chocolateCarton = makeSetOfChocolatesOutOfTheLimits(chocolatelengthLimits, chocolatewidthLimits);
        return getTotalNumberofChildrenThatCanBeFed(chocolateCarton);
    }

    private int getTotalNumberofChildrenThatCanBeFed(Set<Chocolate> chocolateCarton){
        int totalNumberOfChildrenThatCanBeFed = 0;
        for (Chocolate chocolate : chocolateCarton) {
            int childrenFedFromTheChocolate = numberOfChildrenThatCanBeFedFromTheChocolate(chocolate);
            totalNumberOfChildrenThatCanBeFed+=childrenFedFromTheChocolate;
        }
        return totalNumberOfChildrenThatCanBeFed;
    }

    private Set<Chocolate> makeSetOfChocolatesOutOfTheLimits(int[] lengthLimits,int[] widthLimits){
        Set<Chocolate> chocolates = new HashSet<Chocolate>();
        for(int i=0;i<lengthLimits.length;i++){
            for(int j=0;j<widthLimits.length;j++){
                Chocolate rectangle = new Chocolate(lengthLimits[i], widthLimits[j]);
                chocolates.add(rectangle);
            }
        }
        return chocolates;
    }

    private int numberOfChildrenThatCanBeFedFromTheChocolate(Chocolate chocolate){
        int numberOfChildren = 0;
        int chocolateBlocksToExhaust = chocolate.getNumberOfChocolateBlocks();
        while (chocolateBlocksToExhaust!=0){
            int chocolateBlocksThatCanBeExhausted = chocolate.numberOfBlocksOfTheLargestSquareThatCanbeFormedFromTheChocolate();
            chocolateBlocksToExhaust=chocolateBlocksToExhaust-chocolateBlocksThatCanBeExhausted;
            numberOfChildren++;
        }
        return numberOfChildren;
    }
}

class Chocolate {

    int length;
    int width;

    public Chocolate(int length,int width){
        this.length=length;
        this.width=width;
    }

    public int numberOfBlocksOfTheLargestSquareThatCanbeFormedFromTheChocolate(){
        return decreaseDimensionsMaximumMinusMinimum();
    }

    private int decreaseDimensionsMaximumMinusMinimum(){
        if(this.length>this.width) {
            this.length=this.length-this.width;
            return this.width*this.width;
        }
        if(this.width>this.length) {
            this.width=this.width-this.length;
            return this.length*this.length;
        }
        if(this.length==this.width){
            return this.length*this.width;
        }
        return 0;
    }

    public int getNumberOfChocolateBlocks(){
        return this.length*this.width;
    }

    //HashCode and Equals Methods here      
}
\$\endgroup\$
  • 11
    \$\begingroup\$ Children patiently waiting in a queue to receive differently sized pieces of chocolate? Whoever came up with that problem certainly never interacted with children before. ;) Anyway, great first question and welcome to this site. \$\endgroup\$ – I'll add comments tomorrow May 29 '16 at 12:03
  • \$\begingroup\$ @I'lladdcommentstomorrow thank you so much \$\endgroup\$ – Aditya Cherla May 29 '16 at 14:33
7
\$\begingroup\$

I'd try a more top-down approach. At the moment, you make a lot of internal information of a Chocolate object available to public in order to do some calculation and decision making outside that class.

Your method numberOfChildrenThatCanBeFedFromTheChocolate for example deals with blocks of chocolate. A block of chocolate is the atomic element a chocolate bar is made from. The problem here is that the question doesn't ask for chocolate blocks. Sure, the number of blocks and how they are positioned in a grid determines how often a square can be broken off the chocolate bar, but thinking about it in terms of blocks is a bottom-up way of thinking. I as the user of your class could not care less about blocks. The problem asks for squares, not blocks. Why do I have to deal with blocks when using your class?

If you model the data/code according to the question, you get a more top-down approach, which is more abstract, but easier to digest.

You have a chocolate bar in your hand. You can break off a square piece and be left with a different sized chocolate bar or nothing. You don't really care about the size of the square broken off or the remainder. All you really care about is how often you can perform that action until there's no chocolate bar remaining. Of course you have to care about it internally somehow, but again, this is top-down thinking. Look at how your class (its objects) should be used

Another idea that you can use to your advantage is information hiding. As it turns out, the logic is often concerned with what's the longer side and what's the shorter one. Then why not store exactly that information?

Here's a version of Chocolate.java that works with the ideas mentioned above:

public class Chocolate
{
    private int min;
    private int max;

    public Chocolate(int width, int height)
    {
        min = Math.min(width, height);
        max = Math.max(width, height);
    }

    public Chocolate remainderAfterSquareBreakoff()
    {
        if ((min == 1 && max == 1) || min == max)
        {
            return null;
        }

        return new Chocolate(max - min, min);
    }

    public static void main(String[] args)
    {
        Chocolate chocolate = new Chocolate(6, 3);

        int numberOfSquares = 0;

        do
        {
            ++numberOfSquares;

            chocolate = chocolate.remainderAfterSquareBreakoff()
        }
        while (chocolate != null);

        System.out.println("# squares: " + numberOfSquares);
    }
}

The two important things are:

  1. Count how often a square can be broken off until no remainder remains. This is very close to how you would break the chocolate in real life and is thus hopefully intuitive and easy to understand.
  2. The size of the chocolate is stored in terms of longest and shortest side, not width and length.

You use long descriptive names for your methods, which is good. But you have so much logic outside of the Chocolate class that you need many such long descriptive names to keep track of everything. That bloats the code and reduces readability. With only a few things exposed to public, the code becomes less bloated and you need fewer identifiers.

This is clearly not providing the same functionality that your code has. Most importantly, the following doesn't hold any more:

Each Chocolate bar in carton is unique in length (i) and breath(j).

By only storing them as longest and shortest side, the orientation is lost. I'd say the orientation is not necessarily necessary to solve the task at hand. The problem only arises if a Set should be used to store the Chocolate objects, because you cannot define an equals() method to distinguish two objects only by their max and min properties. If you put them into a different data structure that does not require uniqueness like ArrayList for example, everything is fine.

If you insist on uniqueness and the use of Set, you can add another property isLandscapeFormat which can then be used to distinguish between different orientations.

public class Chocolate
{
    private int min;
    private int max;

    private boolean isLandscapeFormat;

    public Chocolate(int width, int height)
    {
        min = Math.min(width, height);
        max = Math.max(width, height);

        isLandscapeFormat = width > height;
    }

And now for something completely different.

The above assumes that you don't care about what square is broken off the bar. It also makes it necessary to reassign the return value of the method to the chocolate object.

A more common approach for this call-method-until-null-is-returned structure is an iterator.

Here's a different version of Chocolate.java that incorporates that principle.

public class Chocolate
{
    private int min;
    private int max;

    public Chocolate(int width, int height)
    {
        setMinMax(width, height);
    }

    private void setMinMax(int a, int b)
    {
        min = Math.min(a, b);
        max = Math.max(a, b);
    }

    public boolean hasNextSquare()
    {
        return min > 0 && max > 0;
    }

    public Chocolate getNextSquare()
    {
        if (!hasNextSquare())
        {
            return null;
        }

        setMinMax(max-min, min);

        return new Chocolate(min, min);
    }

    public static void main(String[] args)
    {
        Chocolate chocolate = new Chocolate(5, 3);

        int numberOfSquares = 0;

        while(chocolate.hasNextSquare())
        {
            ++numberOfSquares;

            chocolate.getNextSquare();
        }

        System.out.println("# squares: " + numberOfSquares);
    }
}

The important differences are:

  1. The new method setMinMax, which I introduced because its logic is now necessary at multiple places in the class. Creating a method prevents duplicated code.
  2. The method hasNextSquare. As long as there is still one block remaining, a square can be broken off. As long as that's the case, this method will return true;
  3. getNextSquare, which breaks off the next square from the bar.
  4. The while loop to iterate over all the squares:

    while(chocolate.hasNextSquare())
    {
        ++numberOfSquares;
    
        chocolate.getNextSquare();
    }
    

    The idea is still the same: break off squares as long as that's possible. But now the square is explicitly returned and can be used in the program.

There are more fancy ways to create iterators, with an interface to be implemented, but for this simple example, I think it is sufficient to provide a hasNext() and getNext() method, which implicitly removes the returned object.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Wow! your code is even less than the half of what I've written.I have a lot to improve! \$\endgroup\$ – Aditya Cherla May 29 '16 at 14:58
4
\$\begingroup\$

First of all I see really nice approaches in naming your artefacts (classes, methods, parameters, vars). Furthermore you master the first step of programming: algorithmic thinking. As you have thought of naming you figured out most responsibilities so you followed the single responsibility principle.

Yes, there are some things to improve. But I see only one real big issue: the intention to implement hashcode and equals.

Hashcode and equals

I'd like to address hashcode and equals as there are intentions to implement them. If you do so you may have strange effects in the future. You can easily see what happens if your equals and hashcode methods base on length and width (and I guess it will) of your Chocolate:

public static void main(String[] args) {

    Set<Chocolate> set = new HashSet<>();
    Chocolate chocolate = new Chocolate(4, 8);
    set.add(chocolate);
    System.out.println(set.contains(chocolate)); // --> true
    chocolate.numberOfBlocksOfTheLargestSquareThatCanbeFormedFromTheChocolate();
    System.out.println(set.contains(chocolate)); // --> false

}

As length and/or width will mutate in the method "numberOfBlocksOfTheLargest..." a Chocolate cannot be found anymore within hash-based collections like Set or Map. Currently you aren't facing the problem because you only iterate over all elements that are within the Set and no hash-related operation is performed there.

Equals and hashcode should only base on immutable values. In this easy example you may get over it. In real applications you will face serious problems. In one of the projects I was in I saw objects occasionally diappearing during a serialization process. Objects that were available on a rich-client were not available anymore once they were sent over the network through serializing and deserializing. The problem was a weak implementation of equals and hashcode. They based on mutable values.

The only way your hashcode-method can be implemented without having these side-effects: return -1; (or any other constant). But this will hack the intention of hashcode as your performance of your contains()-method will be linear to the amount of objects the Set contains.

Naming

input1, input2, input3, ... you can do better ;-)

Your task was to simulate chocolate distribution. So why not changing the class name from "CodeCandidate" to ChocolateDistribution.

Multiple return statements

Try to use only one return statement per method. If you do that you can easily apply refactorings on it like extract method.

Code location

I would pass the chocolate carton into "ChocolateDistribution" instead of creating it inside.

Recursive algorithm

As the problem has a recursive nature I'd prefere a recursive solution. But that's only an opinion.

Privacy

length and width should be private.

Code

Here is the code resulting on my suggestions:

public class ChocolateDistribution {


    public int getTotalNumberofChildrenThatCanBeFed(Set<Chocolate> chocolateCarton){

        int totalNumberOfChildrenThatCanBeFed = 0;

        for (Chocolate chocolate : chocolateCarton) {
            int childrenFedFromTheChocolate = chocolate.getSquareChocolates().size();
            totalNumberOfChildrenThatCanBeFed+=childrenFedFromTheChocolate;
        }

        return totalNumberOfChildrenThatCanBeFed;
    }


}

class Chocolate {

    private int length;
    private int width;


    public Chocolate(int length,int width){
        this.length=length;
        this.width=width;
    }


    public Set<Chocolate> getSquareChocolates() {

        Set<Chocolate> chocolates = new HashSet<>();

        if (this.width > this.length) {
            int width = this.width - this.length;
            chocolates.add(new Chocolate(this.length, this.length));
            chocolates.addAll(new Chocolate(this.length, width).getSquareChocolates());
        } else if (this.length > this.width) {
            int length = this.length - this.width;
            chocolates.add(new Chocolate(this.width, this.width));
            chocolates.addAll(new Chocolate(length, this.width).getSquareChocolates());
        } else { // this.length == this.width
            chocolates.add(this);
        }

        return chocolates;
    }

}

Code in Action

public class Main {


    public static void main(String[] args) {

        Set<Chocolate> chocolateCarton = createChocolateCarton(5, 6, 3, 4);

        ChocolateDistribution chocolateDistribution = new ChocolateDistribution();

        System.out.println(chocolateDistribution.getTotalNumberofChildrenThatCanBeFed(chocolateCarton));

    }


    private static Set<Chocolate> createChocolateCarton(int lengthFrom, int lengthTo, int widthFrom, int widthTo){

        int[] lengthLimits = {lengthFrom,lengthTo};
        int[] widthLimits = {widthFrom,widthTo};

        Set<Chocolate> chocolates = new HashSet<Chocolate>();

        for(int i=0;i<lengthLimits.length;i++){
            for(int j=0;j<widthLimits.length;j++){
                Chocolate rectangle = new Chocolate(lengthLimits[i], widthLimits[j]);
                chocolates.add(rectangle);
            }
        }

        return chocolates;
    }

}

Finally

... there is no necessity to implement equals and hashcode.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ "Equals and hashcode should only base on immutable values"- I did'nt know that, I'll keep that in mind. \$\endgroup\$ – Aditya Cherla May 29 '16 at 16:46
  • 1
    \$\begingroup\$ Provide justification for "Try to use only one return statement per method" please? It seems to be an antiquated rule that has no relevance to Java. \$\endgroup\$ – 200_success May 29 '16 at 18:15
  • \$\begingroup\$ I already did. Methods that have multiple return-Statements are harder to refactor (extract method, several scope issues). Or the other way around: Code that has specific improvements may have the possibility to be improved more. The question is: Is code better if it has the intrinsic property to be easily improved? I see "extract method" mostly as an improvement but at least a neutral operation. So I answer this question with: Yes. I do not follow votes (X hundred people say so), I do follow logic. And if you tell me where my fallacy is I will adapt my opinion. \$\endgroup\$ – oopexpert May 29 '16 at 20:58
  • 2
    \$\begingroup\$ @oopexpert sometimes, what multiple return statements might hint to the developer is that a method is doing too much. ;) \$\endgroup\$ – h.j.k. May 30 '16 at 14:22
  • \$\begingroup\$ That really might be. But if this is so AND you want to extract this code in a separate method you will have a hard time to do that with standard refactoring mechanisms. \$\endgroup\$ – oopexpert May 30 '16 at 18:11
1
\$\begingroup\$

Your code contains a bug. Finding this bug is quite hard because the one test case from the instructions has a remarkable property:

  • the lengths of the bars vary from 3 to 4 (which is 2 numbers in total)
  • the breadths of the bars vary from 5 to 6 (which is also 2 numbers in total)

Your code in makeSetOfChocolatesOutOfTheLimits reads:

for (int i = 0; i < lengthLimits.length; i++) {
    for (int j = 0; j < widthLimits.length; j++) {
        Chocolate rectangle = new Chocolate(lengthLimits[i], widthLimits[j]);
        chocolates.add(rectangle);
    }
}

You pass the lengthLimits as an array of 2 numbers, which are the min and the max.

In the outer for loop, the variable i will first get the value 0 and then the value 1, and then stop. This is because the lengthLimits contains 2 numbers (min and max). It works in this one test case, but in general it is wrong.

If you passed {1, 5} as the length limits, you would expect that lengthLimits[i] goes from 1 to 5. Instead, it only ever becomes 1 or 5, but never 2, 3, 4.

To fix this, you have to change your code:

for (int i = lengthLimits[0]; i <= lengthLimits[1]; i++) {
    // ...
}

Making this bug is avoidable. An array, by definition, can be empty, it can contain a single element or two or many. You use it to always store exactly 2 elements. You don't need all this other flexibility. Therefore using an array is bad style. When using an array, it often makes sense to do something with each element in the array. That's something else you don't need here.

Therefore, instead of an array, it makes more sense to use a range of integers, since that matches the wording in the instructions. In Java this is written as IntStream lengthLimits = IntStream.rangeClosed(min, max). While it looks good at first, it is part of the Java Streams API, which is really hard to use and requires you to write more code than strictly necessary.

Therefore, the best way to loop over all possible lengths is still:

for (int length = minLength; length <= maxLength; length++) {
    // ...
}

It's the same code as above, just with better names. It's annoying to write the variable length 3 times in this simple loop. Another variant is:

for (int length : IntStream.rangeClosed(minLength, maxLength).toArray()) {
    // ...
}

It looks really complicated, but at least you cannot make typos in the length variable name anymore.


It's also possible to write this code without any objects at all. Since this is a simple numerical problem, this makes sense. For larger tasks and problems it's entirely sensible to define several classes, since otherwise the code gets too complicated to understand.

A possible variant that focuses on structurally simple code is:

import java.util.Objects;

public class Chocolate {

    /**
     * In how many square pieces is a chocolate bar split
     * if each time the largest possible square piece is cut off?
     */
    private static int pieces(int width, int height) {
        int large = Math.max(width, height);
        int small = Math.min(width, height);
        int pieces = 0;
        while (small != 0) {
            pieces += large / small;
            int nextSmall = large % small;
            large = small;
            small = nextSmall;
        }
        return pieces;
    }

    /**
     * Given a box containing all combinations of rectangular chocolate
     * bars in the given size ranges, in how many pieces will they be
     * split?
     */
    private static int pieces(int minWidth, int maxWidth, int minHeight, int maxHeight) {
        int pieces = 0;
        for (int width = minWidth; width <= maxWidth; width++) {
            for (int height = minHeight; height <= maxHeight; height++) {
                pieces += pieces(width, height);
            }
        }
        return pieces;
    }

    // In practice, using a proper unit testing framework is better than this ad-hoc code.
    private static void assertEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("Expected " + expected + ", got " + actual + ".");
        }
    }

    public static void main(String[] args) {
        assertEquals(4, pieces(5, 3));
        assertEquals(5, pieces(5, 4));
        assertEquals(2, pieces(6, 3));
        assertEquals(3, pieces(6, 4));
        assertEquals(7, pieces(1, 7));
        assertEquals(0, pieces(0, 1000));

        assertEquals(14, pieces(5, 6, 3, 4));
        assertEquals(30, pieces(1, 4, 2, 4)); // your code had returned 9
    }
}
|improve this answer|||||
\$\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.