Skip to content

Instantly share code, notes, and snippets.

@hiromi2424
Last active August 29, 2015 14:17
Show Gist options
  • Save hiromi2424/e282b41494b0b25f7e80 to your computer and use it in GitHub Desktop.
Save hiromi2424/e282b41494b0b25f7e80 to your computer and use it in GitHub Desktop.
例のアレ
<?php
foreach (range(1, 10) as $n) {
echo "calculating $n connection...\n";
$c = new Connection($n, $n === 1 ? null : $c);
echo 'got answer. connection patterns: ', count($c->answers), "\n";
}
class Connection {
public $n;
public $answers = [];
public $answerHashes = [];
public function __construct($n, Connection $prevConnection = null) {
if ($prevConnection) {
$this->prevConnection = $prevConnection;
} elseif ($n !== 1) {
$this->prevConnection = new self($n - 1);
}
$this->n = $n;
$this->resolve();
}
public function resolve() {
if ($this->n === 1) {
$this->answers = [
[
[
1
],
],
];
} else {
foreach ($this->prevConnection->answers as $answer) {
foreach ($answer as $i => $row) {
foreach ($row as $j => $exists) {
if (!isset($answer[$i + 1][$j])) {
$a = $answer;
$a[$i + 1][$j] = 1;
$this->addAnswer($a);
}
if (!isset($answer[$i][$j + 1])) {
$a = $answer;
$a[$i][$j + 1] = 1;
$this->addAnswer($a);
}
if ($i === 0) {
$a = $answer;
$a[$i - 1][$j] = 1;
$b = $this->shift($a, 1, 0);
$this->addAnswer($b);
}
if ($i === 1) {
if (!isset($answer[$i - 1][$j])) {
$a = $answer;
$a[$i - 1][$j] = 1;
$this->addAnswer($a);
}
}
if ($j !== 0) {
if (!isset($answer[$i][$j - 1])) {
$a = $answer;
$a[$i][$j - 1] = 1;
$this->addAnswer($a);
}
}
}
}
}
}
}
public function addAnswer($a) {
$hash = $this->hash($a);
if (!isset($this->answerHashes[$hash])) {
$this->answers[] = $a;
$this->answerHashes[$hash] = true;
}
}
public function hash($answer) {
$hash = 'a';
for ($i = 0; $i <= $this->n - 1; $i++) {
for ($j = 0; $j <= $this->n - 1; $j++) {
$hash .= isset($answer[$i][$j]) ? '0' : '1';
}
}
return $hash;
}
public function shift($answer, $di, $dj) {
$result = [];
foreach ($answer as $i => $row) {
foreach ($row as $j => $exists) {
$result[$i + $di][$j + $dj] = 1;
}
}
return $result;
}
public function dump($answers = null) {
if ($answers === null) {
$answers = $this->answers;
}
$n = 0;
foreach ($answers as $answer) {
$n++;
echo "answer$n:\n";
// print_r($answer);
for ($j = $this->n; $j >=0; $j--) {
for ($i = 0; $i <= $this->n; $i++) {
echo isset($answer[$i][$j]) ? '.' : ' ';
}
echo "\n";
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment