Skip to content

Instantly share code, notes, and snippets.

@ashbeats
Last active December 2, 2018 19:26
Show Gist options
  • Save ashbeats/7b4a3a8efce1956720b880e0dfa05990 to your computer and use it in GitHub Desktop.
Save ashbeats/7b4a3a8efce1956720b880e0dfa05990 to your computer and use it in GitHub Desktop.
<?php
/**
* Author: git@ashbeats
* Date: 12/2/2018
* Time: 2:45 AM
*/
/**
* Late night code after stumbling on https://youtu.be/IWvbPIYQPFM?t=537 and a ton of beers.
*
* Since the questioner was vague on the i/o, I'll assume it's a 2D Vector representing image pixels.
*
* I need to find the largest group of contiguous pixels. [ one or more sides touch a a pixel of the same color. ]
*
* <usage>
* $input[ 0 ][ 0 ] = 'a';
* $input[ 0 ][ 1 ] = 'b';
* $input[ 0 ][ 2 ] = 'b';
*
* $input[ 1 ][ 0 ] = 'c';
* $input[ 1 ][ 1 ] = 'c';
* $input[ 1 ][ 2 ] = 'b';
*
* $input[ 2 ][ 0 ] = 'c';
* $input[ 2 ][ 1 ] = 'a';
* $input[ 2 ][ 2 ] = 'c';
*
* $input[ 3 ][ 0 ] = 'c';
* $input[ 3 ][ 1 ] = 'c';
* $input[ 3 ][ 2 ] = 'a';
*
*
* $search = new ContiguousSearch( $input );
* foreach ( $search->find() as $value => $count ) {
* echo "\nPixel Value: '$value' has $count contiguous sides";
* }
*
* </usage>
*
*/
class ContiguousSearch
{
// note: using array keys as a mock hashtable as keys are O(1) in php
var $input2d = [];
var $width = [];
var $height = [];
function __construct($input2d)
{
$this->input2d = $input2d;
$this->width = count( $this->input2d );
$this->height = count( current( $this->input2d ) );
}
function get($x, $y)
{
return $this->input2d[ $x ][ $y ] ?? null;
}
function compareThyNeighbours($x, $y)
{
$referencePoint = $this->get( $x, $y );
$sides = [
$referencePoint === $this->get( $x + 1, $y ),
$referencePoint === $this->get( $x - 1, $y ),
$referencePoint === $this->get( $x, $y + 1 ),
$referencePoint === $this->get( $x, $y - 1 ),
];
return [
count( array_filter( $sides ) ), // todo - get rid of array filter but not much optimization headroom as it will still be O(4)
$referencePoint,
];
}
/**
* Find all contiguous pixels.
*
* @return array
*/
function find()
{
$response = [];
for ( $x = 0; $x < $this->width; $x++ ) {
for ( $y = 0; $y < $this->height; $y++ ) {
list( $match, $value ) = $this->compareThyNeighbours( $x, $y );
if ( $match > 0 ) {
$response[ $value ][] = $match;
}
}
}
$matches = [];
foreach ( array_keys( $response ) as $value ) {
$matches[ $value ] = count( $response[ $value ] );
}
return $matches;
}
}
# prep data
$input = [];
$input[ 0 ][ 0 ] = 'a';
$input[ 0 ][ 1 ] = 'b';
$input[ 0 ][ 2 ] = 'b';
$input[ 1 ][ 0 ] = 'c';
$input[ 1 ][ 1 ] = 'c';
$input[ 1 ][ 2 ] = 'b';
$input[ 2 ][ 0 ] = 'c';
$input[ 2 ][ 1 ] = 'a';
$input[ 2 ][ 2 ] = 'c';
$input[ 3 ][ 0 ] = 'c';
$input[ 3 ][ 1 ] = 'c';
$input[ 3 ][ 2 ] = 'a';
# execute
$search = new ContiguousSearch( $input );
foreach ( $search->find() as $value => $count ) {
echo "\n'$value' occupies at max, $count contiguous pixels";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment