In November I rediscovered the coding contest from Facebook after some years. This was after a period of returning to algorithm study also in the first stages of the contest is more about understanding the problem than knowing algorithms. I solved one of the problem from the qualifications round which is written below. In the next round I looked a bit over one of the problem and figured it out a solution but I didn’t finalize it.

The problem from the sounds like that:

 

You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.

You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.

Input

The first line of the input consists of a single number T, the number of test cases.

Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either “.” symbolizing a white cell, or “#” symbolizing a black cell. Every test case contains at least one black cell.

Output

For each test case i numbered from 1 to T, output “Case #i: “, followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.

Constraints

1 ≤ T ≤ 20
1 ≤ N ≤ 20

 

And my solution was:

function fromTxtToArray($filename) {
    $fh = fopen($filename, "rb");
    $data = fread($fh, filesize($filename));
    fclose($fh);
    $array = explode("\n",$data);
    array_pop($array);
    $rows = $array[0];
    unset($array[0]);
    return array('rows' => $rows, 'data' => $array);
}

function Square($input) {
    $square = array();
	$response = 'NO';
    $size = array_shift($input);
    foreach ($input as $keyRow => $row) {
        if (isset($square['size']) && $square['size'] > 1) {
        	if($response == 'YES' && substr_count($row, '.') != $size) {
        		return 'NO';
        	}
        	if($row != $input[$square['row']] && $response == 'NO') {
        		return 'NO';
        	}
        	//we have a square
        	if ($keyRow - $square['row'] == $square['size'] - 1) {
        		//square
        		$response = 'YES';
        	}
        	continue;
        }
        $cols = str_split($row);
        //detect a possible square and define its coordinates
        foreach ($cols as $keyCol => $col) {
            if (($col == '#') && empty($square)) {
                $square['row'] = $keyRow;
                $square['col'] = $keyCol;
                $square['size'] = 1;
                $response = 'YES';               
                continue;
            }

            if ($col == '#' && $cols[$keyCol - 1] == '#') {
            	$square['size']++;
            	$response = 'NO';
            } elseif ($col == '#') {
            	return 'NO';
            }
        }
    }

    return $response;
}

$source = fromTxtToArray('square_detector.txt');

$i = 0;
$output = '';
$case = array();
$cases = array();
foreach ($source['data'] as $k => $v){
    if(is_numeric($v)) {
        if($k > 1) array_push($cases, $case);
        $case = array();
    }
    $case[] = $v;
}
array_push($cases, $case);

do{
    $output .= 'Case #' . ($i + 1) . ': ' . Square($cases[$i])."\n";
    //die;
    $i++;
}while($i < $source['rows']);

$fp = fopen('output_square_detector.txt', 'w');
fwrite($fp, $output);
fclose($fp);
echo $output;