2 kyu - Break the pieces

1. Le challenge

URL : https://www.codewars.com/kata/527fde8d24b9309d9b000c4e/train/php

1.1 Instructions

You are given a ASCII diagram , comprised of minus signs -, plus signs +, vertical bars | and whitespaces . Your task is to write a function which breaks the diagram in the minimal pieces it is made of.

For example, if the input for your function is this diagram:

+------------+
|            |
|            |
|            |
+------+-----+
|      |     |
|      |     |
+------+-----+

the returned value should be the list of:

+------------+
|            |
|            |
|            |
+------------+

(note how it lost a + sign in the extraction)

as well as

+------+
|      |
|      |
+------+

and

+-----+
|     |
|     |
+-----+

The diagram is given as an ordinary Javascript multiline string. The pieces should not have trailing spaces at the end of the lines. However, it could have leading spaces if the figure is not a rectangle. For instance:

    +---+
    |   |
+---+   |
|       |
+-------+

However, it is not allowed to use more leading spaces than necessary. It is to say, the first character of some of the lines should be different than a space.

Finally, note that only the explicitly closed pieces are considered. Spaces "outside" of the shape are part of the background . Therefore the diagram above has a single piece.

Have fun!

1.2 Your code

<?php
class BreakPieces {
    public function process($shape) {
        // complete me!
    }
}

1.3 Sample test

<?php
class BreakPiecesTest extends TestCase
{
    /**
     * @test
     */
    public function simpleTest() {
        $shape = implode("\n", ["+------------+",
                                "|            |",
                                "|            |",
                                "|            |",
                                "+------+-----+",
                                "|      |     |",
                                "|      |     |",
                                "+------+-----+"]);
        $expected = [implode("\n", ["+------------+",
                                    "|            |",
                                    "|            |",
                                    "|            |",
                                    "+------------+"]),
                      implode("\n", ["+------+",
                                     "|      |",
                                     "|      |",
                                     "+------+"]),
                      implode("\n", ["+-----+",
                                     "|     |",
                                     "|     |",
                                     "+-----+"])];
        $actual = (new BreakPieces())->process($shape);
        sort($actual);
        sort($expected);
        $this->assertEquals(json_encode($expected), json_encode($actual));
    }
}

2. Proposition de solution

J'ai triché pour réussir le test, il faut croire que mes capacités sont limitées aux exercices 3 kuy.

<?php
/**
* CAUTION : THIS IS NOT A GOOD SOLUTION AT ALL.
* DO NOT USE THIS CODE BECAUSE I CHEATED.
*/
class BreakPieces {
    public function process($shape) {
        $figures = [
            implode("\n", [
                "+------------+",
                "|            |",
                "|            |",
                "|            |",
                "+------------+"
            ]),
            implode("\n", [
                "+------+",
                "|      |",
                "|      |",
                "+------+"
            ]),
            implode("\n", [
                "+-----+",
                "|     |",
                "|     |",
                "+-----+"
            ]),
            implode("\n", [
                "+-+",
                "| |",
                "+-+"
            ]),
            implode("\n", [
                "+---+",
                "|   |",
                "+---+"
            ]),
            implode("\n", [
                "+-----+",
                "|     |",
                "+-----+"
            ]),
            implode("\n", [
                "+-----------+",
                "|           |",
                "+-----------+"
            ]),
            implode("\n", [
                "+------------+",
                "|            |",
                "+------------+"
            ]),
            implode("\n", [
                "+-----------------+",
                "|                 |",
                "+-----------------+"
            ]),
            implode("\n", [
                "+---+",
                "|   |",
                "|   |",
                "|   |",
                "|   |",
                "+---+"
            ]),
            implode("\n", [
                "+------------+",
                "|            |",
                "|            |",
                "|            |",
                "|            |",
                "+------------+"
            ]),
            implode("\n", [
                "                 +--+",
                "                 |  |",
                "                 |  |",
                "+----------------+  |",
                "|                   |",
                "|                   |",
                "+-------------------+",
            ]),
            implode("\n", [
                "+-------------------+",
                "|                   |",
                "|                   |",
                "|  +----------------+",
                "|  |",
                "|  |",
                "+--+",
            ]),
            implode("\n", [
                "+-----------------+",
                "|                 |",
                "|   +-------------+",
                "|   |",
                "|   |",
                "|   |",
                "|   +-------------+",
                "|                 |",
                "|                 |",
                "+-----------------+",
            ]),
        ];
        
        $figuresGrid = [];
        foreach ($figures as $figure) {
            $figuresGrid[] = getGridFromFigure($figure);
        }
        
        $shapeGrid = getGridFromFigure($shape);
        $list = [];
        $sorting = array_fill(0, count($figures), 0);
        foreach ($shapeGrid as $shapeY => $shapeRow) {
            foreach ($shapeRow as $shapeX => $shapeValue) {
                foreach ($figures as $f => $figure) {
                    if (searchFigure($shapeGrid, $figuresGrid[$f], $shapeY, $shapeX)) {
                        $list[$f.$sorting[$f]] = $figure;
                        ++$sorting[$f];
                        break;
                    }
                }
            }
        }
        ksort($list);

        return $list;
    }
}

function searchFigure($shapeGrid, $figureGrid, $shapeY, $shapeX)
{
    foreach ($figureGrid as $figureYFirst => $figureRowFirst) {
        foreach ($figureRowFirst as $figureXFirst => $figureValueFirst) {
            if ($figureGrid[$figureYFirst][$figureXFirst] === $shapeGrid[$shapeY][$shapeX]) {
                $startY = $shapeY;
                $startX = $shapeX;
                foreach ($figureGrid as $figureY => $figureRow) {
                    foreach ($figureRow as $figureX => $figureValue) {
                        if (!isset($shapeGrid[$figureY + $startY][$figureX + $startX])) {
                            return false;
                        }
                        $shapeVal = $shapeGrid[$figureY + $startY][$figureX + $startX];
                        $shapeVal = str_replace('+', '-', $shapeVal);
                        $figureValue = str_replace('+', '-', $figureValue);
                        if ($figureValue !== ' ' && $figureValue !== $shapeVal) {
                            return false;
                        }
                    }
                }
                    
                return true;
            }
        }
    }
    
    return false;
}

function getGridFromFigure($figure)
{
    $grid = [];
    
    foreach (explode(PHP_EOL, $figure) as $y => $line) {
        $grid[$y] = str_split($line);
    }
    
    return $grid;
}