Last active
June 29, 2021 12:35
-
-
Save sagittaracc/cc4a58716987e444dfb845a70b4df00d to your computer and use it in GitHub Desktop.
Remove islands (Google interview)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
require 'Map.php'; | |
$map = new Map([ | |
[1, 1, 0, 0, 0, 0, 0, 1], | |
[0, 1, 0, 0, 1, 1, 1, 0], | |
[1, 0, 1, 0, 0, 0, 0, 0], | |
[1, 0, 0, 1, 1, 0, 1, 1], | |
[0, 0, 1, 1, 1, 0, 0, 1], | |
]); | |
$map->goOverTopBorder(fn($i, $j) => $map->removeIslandAt($i, $j)); | |
$map->goOverBottomBorder(fn($i, $j) => $map->removeIslandAt($i, $j)); | |
$map->goOverLeftBorder(fn($i, $j) => $map->removeIslandAt($i, $j)); | |
$map->goOverRightBorder(fn($i, $j) => $map->removeIslandAt($i, $j)); | |
$map->output(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class Map | |
{ | |
private $map; | |
function __construct($map) | |
{ | |
$this->map = $map; | |
} | |
public function get($i, $j) | |
{ | |
return isset($this->map[$i][$j]) ? $this->map[$i][$j] : null; | |
} | |
public function set($i, $j, $value) | |
{ | |
$this->map[$i][$j] = $value; | |
} | |
public function rowCount() | |
{ | |
return count($this->map); | |
} | |
public function colCount() | |
{ | |
return count($this->map[0]); | |
} | |
private function goOverPath($index, $direction, $callback) | |
{ | |
$start = 0; | |
$end = $direction === 'horizontal' ? $this->colCount() : $this->rowCount(); | |
for ($i = $start; $i < $end; $i++) { | |
if ($direction === 'horizontal') { | |
$callback($index, $i); | |
} | |
else if ($direction === 'vertical') { | |
$callback($i, $index); | |
} | |
else { | |
break; | |
} | |
} | |
} | |
public function goOverTopBorder($callback) | |
{ | |
$this->goOverPath(0, 'horizontal', $callback); | |
} | |
public function goOverBottomBorder($callback) | |
{ | |
$bottomRowIndex = $this->rowCount() - 1; | |
$this->goOverPath($bottomRowIndex, 'horizontal', $callback); | |
} | |
public function goOverLeftBorder($callback) | |
{ | |
$this->goOverPath(0, 'vertical', $callback); | |
} | |
public function goOverRightBorder($callback) | |
{ | |
$rightColumnIndex = $this->colCount() - 1; | |
$this->goOverPath($rightColumnIndex, 'vertical', $callback); | |
} | |
public function removeIslandAt($i, $j) | |
{ | |
if ($this->get($i, $j) === 1) { | |
$this->set($i, $j, 0); | |
$this->removeIslandAt($i, $j - 1); | |
$this->removeIslandAt($i, $j + 1); | |
$this->removeIslandAt($i - 1, $j); | |
$this->removeIslandAt($i + 1, $j); | |
} | |
} | |
public function output() | |
{ | |
foreach ($this->map as $row) { | |
echo implode(' ', $row) . "\n"; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment