Skip to content

Instantly share code, notes, and snippets.

/rect-area.php Secret

Created April 23, 2014 00:57
Show Gist options
  • Save anonymous/5fe120d31ab3765e6b04 to your computer and use it in GitHub Desktop.
Save anonymous/5fe120d31ab3765e6b04 to your computer and use it in GitHub Desktop.
<?php
/**
* rect-area.php
*
* @author Robert Bredlau
* @version $HeadURL$
*/
class proggy {
/**
* Number of rects
*
* @var int
*/
protected $m_num = 0;
/**
* Array of existing rect objects that do not collide with each other.
*
* @var rect[]
*/
protected $m_rects = array();
/**
* The total area
*
* @var double
*/
protected $m_area = 0;
/**
* @return proggy
*/
public function __construct() {
}
public function __destruct() {}
protected function init() {
$this->m_num = 0;
$this->m_rects = array();
$this->m_area = 0;
}
protected function execute_normal( $first_line ) {
$this->init();
$this->m_num = $first_line;
for( $n = 0; $n < $this->m_num; $n += 1 ) {
if( $this->m_validate ) {
list( $n1, $n2, $n3, $n4, $new_area ) = explode( ' ', trim( fgets( STDIN ) ) );
} else {
list( $n1, $n2, $n3, $n4 ) = explode( ' ', trim( fgets( STDIN ) ) );
}
$incoming = array( new rect( (double)$n1, (double)$n2, (double)$n3, (double)$n4 ) );
foreach( $this->m_rects as $k_exist => /** @var rect */ $existing ) {
$catcher = array();
while( ! empty( $incoming ) ) {
/** @var rect */
$other = array_shift( $incoming );
$divisions = $existing->split( $other );
if( $divisions === false ) {
// no collision, non intersecting
$catcher[] = $other;
} else if( empty( $divisions ) ) {
// fits entirely inside, so we throw it away
} else {
// intersection removed, $divisions is now N new rectangles to test
$incoming = array_merge( $incoming, $divisions );
}
}
$incoming = $catcher;
}
foreach( $incoming as /** @var rect */ $other ) {
$this->m_area += $area = $other->area();
if( $area !== 0 ) {
$this->m_rects[] = $other;
}
}
}
echo $this->m_area . PHP_EOL;
return $this->m_area;
}
public function execute() {
$start_tm = microtime( true );
$last_area = 0;
while( true ) {
$matches = array();
$first_line = trim( fgets( STDIN ) );
if( is_numeric( $first_line ) ) {
$last_area = $this->execute_normal( (int)$first_line );
} else if( preg_match( '/^[#](?P<expected>[0-9.]+)$/i', $first_line, $matches ) ) {
if( ((double)$last_area) !== ((double)$matches[ 'expected' ]) ) {
echo 'mismatch - ' . $last_area . ' versus expected ' . $matches[ 'expected' ] . PHP_EOL;
}
} else if( preg_match( '/^##$/i', $first_line, $matches ) ) {
break;
} else if( $first_line === 'a' ) {
$this->m_validate = true;
}
}
echo 'done in ' . number_format( microtime( true ) - $start_tm, 2 ) . ' s' . PHP_EOL;
}
}
class point {
public $x = 0;
public $y = 0;
public function x_delta( point $other ) {
return abs( $other->x - $this->x );
}
public function y_delta( point $other ) {
return abs( $other->y - $this->y );
}
public function __toString() {
return "({$this->x}, {$this->y})";
}
}
class rect {
CONST CORNER_TL = 1;
CONST CORNER_TR = 2;
CONST CORNER_BL = 4;
CONST CORNER_BR = 8;
CONST SIDE_TOP = 16;
CONST SIDE_BOTTOM = 32;
CONST SIDE_LEFT = 64;
CONST SIDE_RIGHT = 128;
CONST ENCLOSED = 256;
/**
* @var point
*/
public $tl = null;
/**
* @var point
*/
public $br = null;
/**
* Accepts:
* + no arguments
* + four arguments, each a coordinate: x1 y1, x2 y2
* + two arguments, each a point instance
* @return rect
*/
public function __construct() {
$this->tl = new point();
$this->br = new point();
$nargs = func_num_args();
$args = func_get_args();
if( $nargs === 4 ) {
foreach( $args as $k => $arg ) {
if( ! is_numeric( $arg ) ) {
throw new Exception( 'bad point argument; not numeric' );
}
switch( $k ) {
case 0:
$this->tl->x = $arg;
break;
case 1:
$this->tl->y = $arg;
break;
case 2:
$this->br->x = $arg;
break;
case 3:
$this->br->y = $arg;
break;
}
}
} else if( $nargs === 2 ) {
foreach( $args as $k => $arg ) {
if( ! ($arg instanceof point) ) {
throw new Exception( 'bad point argument; not instance of point' );
}
switch( $k ) {
case 0:
$this->tl = $arg;
break;
case 1:
$this->br = $arg;
break;
}
}
}
}
/**
* Returns the area of the rectangle.
*
* @return double
*/
public function area() {
return abs( $this->tl->x_delta( $this->br ) * $this->tl->y_delta( $this->br ) );
}
/**
* Determines if $other collides with this rectangle. If there is collision then $other
* is split into a number of non-colliding rectangles and the colliding rectangle is left out.
* If $collision is not specified then a call to $this->collision( $other ) will be made.
*
* Returns an array of non-colliding rectangles, returns an empty array if the entirety of $other
* fits in $this, returns false if there is no split to be made.
*
* @param rect $other
* @param [int] $collision
* @return rect[] | false
*/
public function split( rect $other, $collision = null ) {
if( $collision === null ) {
$collision = $this->collision( $other );
}
//
if( $collision <= 0 ) {
$rv = false;
} else if( self::ENCLOSED & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ),
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $this->br->y ),
new rect( $this->br->x, $this->tl->y, $other->br->x, $this->br->y )
);
} else if( self::CORNER_BL & $collision && self::CORNER_BR & $collision && self::CORNER_TL & $collision && self::CORNER_TR & $collision ) {
$rv = array();
} else if( self::CORNER_TR & $collision && self::CORNER_BR & $collision ) {
$rv = array( new rect( $other->tl->x, $other->tl->y, $this->tl->x, $other->br->y ) );
} else if( self::CORNER_TL & $collision && self::CORNER_BL & $collision ) {
$rv = array( new rect( $this->br->x, $other->tl->y, $other->br->x, $other->br->y ) );
} else if( self::CORNER_BL & $collision && self::CORNER_BR & $collision ) {
$rv = array( new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ) );
} else if( self::CORNER_TL & $collision && self::CORNER_TR & $collision ) {
$rv = array( new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y ) );
} else if( self::CORNER_TL & $collision ) {
$rv = array(
new rect( $this->br->x, $other->tl->y, $other->br->x, $this->br->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::CORNER_TR & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $this->br->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::CORNER_BL & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $this->br->x, $this->tl->y, $other->br->x, $other->br->y )
);
} else if( self::CORNER_BR & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $other->br->y )
);
} else if( self::SIDE_TOP & $collision && self::SIDE_BOTTOM & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $other->br->y ),
new rect( $this->br->x, $other->tl->y, $other->br->x, $other->br->y )
);
} else if( self::SIDE_LEFT & $collision && self::SIDE_RIGHT & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::SIDE_LEFT & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $this->br->x, $this->tl->y, $other->br->x, $this->br->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::SIDE_RIGHT & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y ),
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $this->br->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::SIDE_TOP & $collision ) {
$rv = array(
new rect( $other->tl->x, $other->tl->y, $this->tl->x, $this->br->y ),
new rect( $this->br->x, $other->tl->y, $other->br->x, $this->br->y ),
new rect( $other->tl->x, $this->br->y, $other->br->x, $other->br->y )
);
} else if( self::SIDE_BOTTOM & $collision ) {
$rv = array(
new rect( $other->tl->x, $this->tl->y, $this->tl->x, $other->br->y ),
new rect( $this->br->x, $this->tl->y, $other->br->x, $other->br->y ),
new rect( $other->tl->x, $other->tl->y, $other->br->x, $this->tl->y )
);
}
return $rv;
}
/**
* Calculates the collision of this rectangle with another. Returns an integer greater
* than zero if there is a collision. Use bitmask comparison of the return value against
* the CORNER_* class constants to determine which corners of $other are inside this
* rectable object.
*
* When rect::ENCLOSED bit is set it means $other encloses $this
*
* @param rect $other
* @return int
*/
public function collision( rect $other ) {
$rv = 0;
// Check for complete miss
if(
$other->br->x <= $this->tl->x // right side of other is completely to left of this
|| $other->tl->x >= $this->br->x // left side of other is completely to right of this
|| $other->br->y <= $this->tl->y // bottom side of other is completely above this
|| $other->tl->y >= $this->br->y // top side of other is completely below this
) {
// no op, complete miss
} else {
$ls = $other->tl->x >= $this->tl->x && $other->tl->x <= $this->br->x; // left side of other intersects
$rs = $other->br->x >= $this->tl->x && $other->br->x <= $this->br->x; // right side of other intersects
$ts = $other->tl->y >= $this->tl->y && $other->tl->y <= $this->br->y; // top of other intersects
$bs = $other->br->y >= $this->tl->y && $other->br->y <= $this->br->y; // bottom of other intersects
$ls ? ($rv |= self::SIDE_LEFT) : false;
$rs ? ($rv |= self::SIDE_RIGHT) : false;
$ts ? ($rv |= self::SIDE_TOP) : false;
$bs ? ($rv |= self::SIDE_BOTTOM) : false;
$ls && $ts ? ($rv |= self::CORNER_TL) : false; // top left corner intersection test
$rs && $ts ? ($rv |= self::CORNER_TR) : false; // top right corner intersection test
$ls && $bs ? ($rv |= self::CORNER_BL) : false; // bottom left intersection test
$rs && $bs ? ($rv |= self::CORNER_BR) : false; // bottom right intersection test
$other->tl->x <= $this->tl->x && $other->tl->y <= $this->tl->y && $other->br->x >= $this->br->x && $other->br->y >= $this->br->y ? ($rv |= self::ENCLOSED) : false;
}
return $rv;
}
public function __toString() {
return "{$this->tl}, {$this->br} area( " . $this->area() . " )";
}
}
$p = new proggy();
$p->execute();
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment