F : Gift boxes

06Dec13

I recently participated in the Advent Programming Contest 2013 organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt), wherein – as I’d recently received from Udacity a certificate for Introduction to Programming : Problem Solving with Java (CS046) – I challenged myself to program my solutions to the problems posed by the contest using only Java (I’d used C and C++ when I’d participated in the contest in 2012); I solved eighteen of the problems posed by the contest, achieving a rank of 10th (out of 155 participants).

As submissions of solutions to the contest are now closed, I’m posting here the solutions I submitted to the contest.

Problem (F; easy difficulty):

Gift boxes

Santa’s elves pack the Christmas gifts into standardized boxes. The nominal size of a gift box is 10x20x30 cm3. All available gift boxes have the same proportions and have either double or half of the volume of another box.

Problem

Your task is to implement a program that reads the dimensions of an object and responds with the dimensions of the smallest standardized gift box where the object fits in (for simplicity, the object is placed aligned to the box walls, so no diagonal placing). Input and output is given in the format axbxc, where a,b, and c are numbers, rounded to two decimals given in centimeter. Trailing zeroes after the comma should not be printed. Output numbers must always be sorted in ascending order (a<b<c). The programm shall terminate upon reading an empty line.

Example

Input (my Rubik’s cube, a book and a broomstick)

5.4x5.4x5.4
16x24x2.8
2x2x120

Output

6.3x12.6x18.9
10x20x30
40x80x120

Solution (F.java):

import java.util.Scanner;
import java.text.DecimalFormat;

public class F
{
  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    String l = s.nextLine();
    double g[] = new double[ 3 ];
    DecimalFormat dF = new DecimalFormat();
    dF.setDecimalSeparatorAlwaysShown( false );
    dF.setMinimumFractionDigits( 0 );
    dF.setMaximumFractionDigits( 2 );
    while( l.length() > 0 )
    {
      int i = l.indexOf( 'x' );
      g[ 0 ] = Double.parseDouble( l.substring( 0, i ));
      int k = l.indexOf( 'x', i + 1 );
      g[ 1 ] = Double.parseDouble( l.substring( i + 1, k ));
      g[ 2 ] = Double.parseDouble( l.substring( k + 1, l.length()));
      sort( g );
      double b[] = { 10, 20, 30 };
      double v = b[ 0 ] * b[ 1 ] * b[ 2 ];
      boolean box_found = false;
      do
      {
        if( aIsBiggerThanB( g, b ))
        {
          v *= 2;
          b = boxDimensionsFromVolume( v );
        }
        else
        {
          v /= 2;
          b = boxDimensionsFromVolume( v );
          if( aIsBiggerThanB( g, b ))
          {
            box_found = true;
            v *= 2;
            b = boxDimensionsFromVolume( v );
          }
        }
      }
      while( !box_found );
      System.out.println( dF.format( b[ 0 ] ) + "x" + dF.format( b[ 1 ] ) + "x" + dF.format( b[ 2 ] ));
      l = s.nextLine();
    }
  }

  private static void sort( double p[] )
  {
    boolean sort_occurred;
    do
    {
      sort_occurred = false;
      for( int i = 0; i < p.length - 1; i ++ )
        if( p[ i ] > p[ i + 1 ] )
        {
          sort_occurred = true;
          final double d = p[ i ];
          p[ i ] = p[ i + 1 ];
          p[ i + 1 ] = d;
        }
    }
    while( sort_occurred );
  }

  private static boolean aIsBiggerThanB( double a[], double b[] )
  {
    for( int i = 0; i < a.length; i ++ )
      if( a[ i ] > b[ i ] )
        return true;
    return false;
  }

  private static double[] boxDimensionsFromVolume( double v )
  {
    v /= 6;
    final double d = Math.cbrt( v );
    return new double[]{ d, d * 2, d * 3 };
  }
}

Testing:

5.4x5.4x5.4
6.3x12.6x18.9
16x24x2.8
10x20x30
2x2x120
40x80x120
Advertisements


No Responses Yet to “F : Gift boxes”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: