03/02/2018

[Java] Make bricks and make chocolate problems

Among some exercises offered by Google, I found a couple interesting ones that are a bit harder to code cleanly than I would have thought: makeBricks and makeChocolate.

The basic idea is the same in both cases but the return value in one case is a simple yes/no while in the second case is a number:

We want to make a row of bricks that is goal meters long. We have a number of small bricks (1 meter each) and big bricks (5 meters each). Return true if it is possible to make the goal by choosing from the given bricks. - Yes they said inches but this is 2018 and we like our metric system :)

and

We want make a package of goal kilos of chocolate. We have small bars (1 kilo each) and big bars (5 kilos each). Return the number of small bars to use, assuming we always use big bars before small bars. Return -1 if it can't be done.

At first glance we think we might need the modulus operator, but then there are many cases and our if statements start to grow.. this is usually a sign we are writing code that might work right, but could also be reduced to fewer lines. Although we also should consider that legibility might trump conciseness :)

In the bricks case, we simply want to know "can we make it?". Therefore a good approach is to identify the cases where we CAN'T make it, they are only 2:
  • we don't have enough bricks overall
  • we don't have enough small bricks to cover the last meters

And that's it:

 public boolean makeBricks(int small, int big, int goal) {  
  int small_len = 1, big_len = 5;  
    
  //don't have enough bricks overall  
  if(goal > big * big_len + small) return false;  
    
  //we know we have enough length overall, but do we have enough  
  //small bricks to finish up - even replacing missing long bricks?  
  int big_miss = goal % big_len;  
    
  if(big_miss <= small) return true;  
    
    
  return false;  
 }  


For the cakes instead, we need to know how many small units do we need. This could also mean that we use 5 small units to replace a missing long unit, and that's where it gets confusing again; the breakdown is:

  1. how many big bars do i need
  2. after using up all the available bars I have, how many small ones do I need, either to finish up or replace missing big bars
And that's it again:

 public int makeChocolate(int small, int big, int goal) {  
   int small_len = 1, big_len = 5;  
     
   //how many big ones do we need  
   int big_miss = goal / big_len;  
     
   int big_tot;  
     
   //and how many big ones do we actually have, are they enough?  
   if(big_miss <= big) big_tot = big_miss * big_len;  
   else big_tot = big * big_len;  
   
   //how many small ones do we need - even replacing missing big ones?  
   int small_miss = goal - big_tot ;  
     
   //do we have enough small ones?  
   if(small_miss <= small) return small_miss;  
     
   return -1;  
 }  

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.