Q : Warehouse

17Dec13

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 (Q; medium difficulty):

Warehouse

At the north pole, Santa has a big warehouse for storing the produced toys. The warehouse has a rectabgular base area of 100 x 50 meter. All contents inside the warehouse are placed within perfect cuboid boxes,. The dimensions and positions of the boxes are given.

Problem

Your task is to implement a program that reads the dimensions and positions for the storage boxes. If two boxes are placed at overlapping coordinates, the box that was specified first is placed first while the other one is located on top of the first one. Situation where one box would tip over are not considered. Your programm shall first read a number indicating the number of boxes, followed by lines of 5-tuples (seperated by space) indicating the boxes x-position, y-position inside the warehouse and the width, length and height dimensions of the box. The x and y position are at the center of the box, and the box’s width is aligned to the x-direction within the warehouse. Based on the placed boxes, your program shall print the height reached by the top of the boxes.

Example

Input

2
10 10 5 5 5 
11 11 4 4 2

Output

7

Solution (Q.java):

import java.util.Scanner;

class AABB
{
  public double m_originX, m_originY, m_halfWidth, m_halfHeight, m_top;

  public AABB( double p_originX, double p_originY, double p_halfWidth, double p_halfHeight )
  {
    m_originX = p_originX;
    m_originY = p_originY;
    m_halfWidth = p_halfWidth;
    m_halfHeight = p_halfHeight;
  }
}

public class Q
{
  public static void main( String p[] )
  {
    Scanner s = new Scanner( System.in );
    AABB boxes[] = new AABB[ s.nextInt() ];
    for( int i = 0; i < boxes.length; i ++ )
    {
      boxes[ i ] = new AABB( s.nextInt(), s.nextInt(), s.nextInt() / 2.0, s.nextInt() / 2.0 );
      final int h = s.nextInt();
      final AABB b = collision( boxes[ i ], boxes, i );
      if( b == null )
        boxes[ i ].m_top = h;
      else
        boxes[ i ].m_top = b.m_top + h;
      sortByTop( boxes, i );
    }
    double top = boxes[ 0 ].m_top;
    for( int i = 1; i < boxes.length; i ++ )
      if( boxes[ i ].m_top > top )
        top = boxes[ i ].m_top;
    System.out.println(( int )top );
  }

  private static boolean collision( double coordinateA, double halfDimensionA, double coordinateB, double halfDimensionB )
  {
    double d = coordinateA - coordinateB;
    if( d < 0 )
      d = -d;
    d -= ( halfDimensionA + halfDimensionB );
    return d < 0;
  }

  private static AABB collision( AABB box, AABB boxes[], int limit )
  {
    for( int i = 0; i < limit; i ++ )
      if( collision( box.m_originX, box.m_halfWidth, boxes[ i ].m_originX, boxes[ i ].m_halfWidth ) && collision( box.m_originY, box.m_halfHeight, boxes[ i ].m_originY, boxes[ i ].m_halfHeight ))
        return boxes[ i ];
    return null;
  }

  private static void sortByTop( AABB boxes[], int limit )
  {
    boolean sort_occurred;
    do
    {
      sort_occurred = false;
      for( int i = 0; i < limit; i ++ )
        if( boxes[ i ].m_top < boxes[ i + 1 ].m_top )
        {
          sort_occurred = true;
          final AABB b = boxes[ i ];
          boxes[ i ] = boxes[ i + 1 ];
          boxes[ i + 1 ] = b;
        }
    }
    while( sort_occurred );
  }
}

Testing:

2
10 10 5 5 5
11 11 4 4 2
7
Advertisements


No Responses Yet to “Q : Warehouse”

  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: