Test for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

instagram-unshredder.php

<?php
error_reporting(E_ALL);
ini_set('display_errors', '1');
ini_set('max_execution_time', 0);
ini_set('memory_limit', '256M');

/**
 * Test for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder
 *
 * @author Hans-Peter Buniat
 */
class Instagram {

    /**
     * The image to work on
     *
     * @var Imagick
     */
    private $_image;

    /**
     * The result image
     *
     * @var ressource
     */
    private $_result;

    /**
     * The image-height
     *
     * @var int
     */
    private $_iImageHeight;

    /**
     * The image-width
     *
     * @var int
     */
    private $_iImageWidth;

    /**
     * The image as vertical iterator
     *
     * @var array
     */
    private $_aIterator = array();

    /**
     * The detected shreds
     *
     * @var array
     */
    private $_aShreds = array(
        0
    );

    /**
     * Read the image to work on
     *
     * @param  string $sImage
     *
     * @return Instagram
     */
    public function read($sImage) {
        $this->_image = new Imagick($sImage);
        $this->_iImageHeight = $this->_image->getImageHeight();
        $this->_iImageWidth = $this->_image->getImageWidth();
        $this->_result = imagecreatefrompng($sImage);

        return $this;
    }

    /**
     * Get the resulting image
     *
     * @return void
     */
    public function get() {
        imagepng($this->_result);
    }

    /**
     * Detect the shreds and find the correct order
     *
     * @return Instagram
     */
    public function find() {
        $oIterator = $this->_image->getPixelIterator();

        // create a vertical iterator
        $aDistance = array();
        foreach ($oIterator as $iRow => $oPixels) {
            foreach ($oPixels as $iColumn => $oPixel) {
                $this->_aIterator[$iColumn][$iRow] = $oPixel->getHSL();
            }

            $oIterator->syncIterator();
        }

        unset($oIterator);

        // find the shred-edges - they have a much higher distance than normal pixel-columns
        $aDistance = $this->_getColumnDistance($this->_aIterator, false);
        $aIgnore = array(
            0,
            $this->_iImageWidth - 2,
            $this->_iImageWidth - 1
        );
        foreach ($aDistance as $iColumn => $fDistance) {
            if (in_array($iColumn, $aIgnore) === true) {
                continue;
            }

            // find the shreds .. this needs re-thinking ;)
            if ($fDistance > (0.775 * ($aDistance[$iColumn - 1] + $aDistance[$iColumn + 1])) or $fDistance > ($aDistance[$iColumn - 1] * 2)
                or ($fDistance > $aDistance[$iColumn - 1] and $fDistance > (0.825 * ($aDistance[$iColumn + 1] + $aDistance[$iColumn + 2])))) {
                $this->_aShreds[] = $iColumn;
            }
        }

        // get the first shred
        $fMax = $iFirst = 0;
        foreach ($aDistance as $iKey => $mValue) {
            if ($mValue > $fMax) {
                $fMax = $mValue;
                $iFirst = $iKey;
            }
        }

        $aFinal = array(
            $iFirst
        );

        // re-structure the shreds, to determine the length of a specifc shred
        $this->_aShreds = array_flip($this->_aShreds);
        ksort($this->_aShreds);
        $aDistance = $this->_aShreds;
        unset($aDistance[$iFirst]);

        // find every next shred to the first, second, .. shred
        while (count($aDistance) > 0) {
            $iCompare = end($aFinal);
            $iCompare = $this->_getNextShred($iCompare) - 1;
            $aColumnDistance = $this->_getColumnDistance($aDistance, $iCompare);
            asort($aColumnDistance);
            $iNext = key($aColumnDistance);
            $aFinal[] = $iNext;
            unset($aDistance[$iNext], $aColumnDistance);
        }

        // create the resulting image
        $iDestX = $iSrcX = $iDestY = $iSrcY = 0;
        $rResult = imagecreatetruecolor($this->_iImageWidth, $this->_iImageHeight);
        foreach ($aFinal as $iShred) {
            $iSrcWidth = $this->_getNextShred($iShred) - $iShred;
            imagecopy($rResult, $this->_result, $iDestX, $iDestY, $iShred, $iSrcY, $iSrcWidth, $this->_iImageHeight);
            $iDestX += $iSrcWidth;
        }

        $this->_result = $rResult;

        return $this;
    }

    /**
     * Get the next shred
     *
     * @param  int $iCurrent
     *
     * @return int
     */
    private function _getNextShred($iCurrent) {
        reset($this->_aShreds);
        foreach ($this->_aShreds as $iShred => $iKey) {
            if ($iShred === $iCurrent) {
                $iNext = key($this->_aShreds);
                if ($iNext === 0) {
                    $iNext = $this->_iImageWidth;
                }

                return $iNext;
            }
        }

        return 0;
    }

    /**
     * Compare columns to other columns
     *
     * @param  array $aIterator
     * @param  mixed $mCompare
     *
     * @return array
     */
    private function _getColumnDistance($aIterator, $mCompare) {
        $aResult = array();
        foreach ($aIterator as $iColumn => $mTemp) {
            $aResult[$iColumn] = 0;
            $iCompare = ($mCompare === false) ? ((($iColumn === 0) ? $this->_iImageWidth : $iColumn) -1) : $mCompare;
            foreach ($this->_aIterator[$iColumn] as $iRow => $aColors) {
                $aResult[$iColumn] += $this->_getEdgeDistance($aColors, $iCompare, $iRow);
            }
        }

        return $aResult;
    }

    /**
     * Get the edge-distance by using the: https://en.wikipedia.org/wiki/Sobel_operator with a simplified matrix
     *
     * @param  array $aColors
     * @param  array $iCompare
     * @param  array $iRow
     *
     * @return float
     */
    private function _getEdgeDistance($aColors, $iCompare, $iRow) {
        // create a distance value for the edge, using the: https://en.wikipedia.org/wiki/Sobel_operator
        $fUpLeft = $fDownLeft = 0;
        $fLeft = 2 * $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow]);
        if ($iRow > 0) {
             $fUpLeft = $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow - 1]);
        }

        if ($iRow < ($this->_iImageHeight - 1)) {
            $fDownLeft = $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow + 1]);
        }

        // calculating the distance
        return sqrt(pow((0 - ($fUpLeft + ($fLeft * 2) + $fDownLeft)), 2) + pow($fUpLeft - $fDownLeft, 2));
    }

    /**
     * Get the absolute distance between the color values of 2 pixel
     *
     * @param  array $aColorA
     * @param  array $aColorB
     *
     * @return float
     */
    private function _getColorDistance(array $aColorA, array $aColorB) {
        return pow($aColorA['hue'] - $aColorB['hue'], 2) + pow($aColorA['saturation'] - $aColorB['saturation'], 2) + pow($aColorA['luminosity'] - $aColorB['luminosity'], 2);
    }
}

$aOpts = getopt('i:');
if (empty($aOpts['i']) === true and empty($_GET['i']) !== true) {
    $aOpts['i'] = $_GET['i'];
}

try {
    if (empty($aOpts['i']) === true) {
        throw new Exception('IMAGE_IS_NEEDED');
    }

    $o = new Instagram();
    $o->read($aOpts['i'])->find();
    header('Content-type: image/png');
    $o->get();
}
catch (Exception $e) {
    var_dump($e);
}