Skip to content

Instantly share code, notes, and snippets.

@sagittaracc
Last active November 8, 2022 11:17
Show Gist options
  • Save sagittaracc/4c7b0b04c04dc57b0144b9457f4cc776 to your computer and use it in GitHub Desktop.
Save sagittaracc/4c7b0b04c04dc57b0144b9457f4cc776 to your computer and use it in GitHub Desktop.
Matrix multiplication
<?php
class Cell
{
private $rowIndex;
private $colIndex;
public function __construct($rowIndex, $colIndex)
{
$this->rowIndex = $rowIndex;
$this->colIndex = $colIndex;
}
public function getRowIndex()
{
return $this->rowIndex;
}
public function getColIndex()
{
return $this->colIndex;
}
public function getUpCell()
{
return new Cell($this->rowIndex - 1, $this->colIndex);
}
public function getDownCell()
{
return new Cell($this->rowIndex + 1, $this->colIndex);
}
public function getLeftCell()
{
return new Cell($this->rowIndex, $this->colIndex - 1);
}
public function getRightCell()
{
return new Cell($this->rowIndex, $this->colIndex + 1);
}
public function isSameTo(Cell $cell)
{
return $this->getRowIndex() === $cell->getRowIndex() && $this->getColIndex() === $cell->getColIndex();
}
}
<?php
require 'Matrix.php';
$m1 = (new Matrix(2, 3))->load([
1, 1, 1,
1, 1, 1
]);
$m2 = (new Matrix(3, 2))->load([
1, 1,
1, 1,
1, 1
]);
$result = $m1->mult($m2);
echo is_null($result) ? "MULT() Failed" : $result->print();
<?php
class Matrix
{
private $rows = 0;
private $cols = 0;
private $data = null;
public function __construct($rows, $cols)
{
$this->rows = $rows;
$this->cols = $cols;
}
public function load($data)
{
if (count($data) === $this->rows * $this->cols) {
$this->data = $data;
}
else {
$this->rows = 0;
$this->cols = 0;
}
return $this;
}
public function index($i, $j)
{
$index = $this->cols * $i + $j;
return isset($this->data[$index]) ? $this->data[$index] : null;
}
public function cell(Cell $cell)
{
return $this->index($cell->getRowIndex(), $cell->getColIndex());
}
public function mult(Matrix $m)
{
if ($this->cols !== $m->rows) {
return null;
}
$result = new Matrix($this->rows, $m->cols);
$data = [];
for ($i = 0; $i < $this->rows; $i++) {
for ($j = 0; $j < $m->cols; $j++) {
$sum = 0;
for ($k = 0; $k < $this->cols; $k++) {
$sum += $this->index($i, $k) * $m->index($j, $k);
}
$data[] = $sum;
}
}
$result->load($data);
return $result;
}
public function hasWayOut(Cell $from, Cell $to, Cell $prev = null)
{
if ($from->isSameTo($to)) {
return true;
}
$case1 = $case2 = $case3 = $case4 = false;
if (is_null($prev) || !$from->getUpCell()->isSameTo($prev) && $this->cell($from->getUpCell()) === 1) {
$case1 = $this->hasWayOut($from->getUpCell(), $to, $from);
}
if (is_null($prev) || !$from->getDownCell()->isSameTo($prev) && $this->cell($from->getDownCell()) === 1) {
$case2 = $this->hasWayOut($from->getDownCell(), $to, $from);
}
if (is_null($prev) || !$from->getLeftCell()->isSameTo($prev) && $this->cell($from->getLeftCell()) === 1) {
$case3 = $this->hasWayOut($from->getLeftCell(), $to, $from);
}
if (is_null($prev) || !$from->getRightCell()->isSameTo($prev) && $this->cell($from->getRightCell()) === 1) {
$case4 = $this->hasWayOut($from->getRightCell(), $to, $from);
}
return $case1 || $case2 || $case3 || $case4;
}
public function print()
{
$s = '';
for ($i = 0; $i < $this->rows; $i++) {
for ($j = 0; $j < $this->cols; $j++) {
$s .= $this->index($i, $j) . ' ';
}
$s .= "\n";
}
return $s;
}
}
<?php
require 'Cell.php';
require 'Matrix.php';
$path = (new Matrix(5, 5))->load([
1, 1, 1, 1, 1,
0, 1, 0, 0, 1,
0, 1, 0, 0, 1,
0, 1, 0, 0, 1,
0, 0, 0, 0, 0
]);
$start = new Cell(0, 0);
$finish = new Cell(4, 4);
$wayOut = $path->hasWayOut($start, $finish);
var_dump($wayOut);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment