Zestaw punktów spełniony w kształcie arbor jest dwuwymiarowym zestawem punktów, w którym dla dowolnego prostokąta wyrównanego do osi, który można utworzyć za pomocą dwóch punktów w zestawie jako przeciwległych narożników, ten prostokąt zawiera lub dotyka co najmniej jednego innego punktu. Oto równoważna definicja z Wikipedii:

Mówi się, że zbiór punktów jest spełniony, jeśli zachowana jest następująca właściwość: dla dowolnej pary punktów, które nie leżą na tej samej linii poziomej lub pionowej, istnieje trzeci punkt, który leży w prostokącie rozciągniętym przez dwa pierwsze punkty ( w środku lub na granicy).

Poniższy obraz ilustruje tworzenie prostokątów. Ten zestaw punktów NIE jest spełniony, ponieważ ten prostokąt musi zawierać co najmniej jeszcze jeden punkt.

W sztuce ASCII ten zestaw punktów można przedstawić jako:

......
....O.
......
.O....
......

Niewielka modyfikacja może sprawić, że będzie to zadowalające:

......
....O.
......
.O..O.
......

Powyżej widać, że wszystkie prostokąty (których jest tylko jeden) zawierają co najmniej trzy punkty.

Oto kolejny przykład bardziej złożonego zestawu punktów, który jest spełniony w arborach:

W przypadku dowolnego prostokąta, który można narysować obejmującego dwa punkty, prostokąt ten zawiera co najmniej jeden inny punkt.

Wyzwanie

Biorąc pod uwagę prostokątną siatkę punktów (którą reprezentuję O) i pustą przestrzeń (którą reprezentuję .), wyprowadzaj prawdziwą wartość, jeśli jest zadowalająca, lub wartość falsey, jeśli nie jest. To jest golf golfowy.

Dodatkowe zasady:

• Można zdecydować się na znaki Oi .zamieniłem się z żadną inną parą znaków ASCII. Po prostu określ, jakiego mapowania znaków używa Twój program.
• Siatka zawsze będzie prostokątna. Dopuszczalny jest końcowy znak nowej linii.

Więcej przykładów

Arborally zadowolony:

.OOO.
OO...
.O.OO
.O..O
....O

..O..
OOOO.
...O.
.O.O.
...OO

O.O.
..O.
OOOO
.O.O
OO..

...
...
...

...
..O
...

O.....
O.O..O
.....O

OOO.OO

Niezadowolony z arborally:

..O..
O....
...O.
.O...
....O

..O..
O.OO.
...O.
.O.O.
...OO

O.....
..O...
.....O

Ślimaki , 29 30 39 bajtów

!{t\Oo\.+c\.,\O!{t\O{w!(.,~}2

Działa poprzez wykreślenie 2 boków prostokąta, a następnie sprawdzenie, czy jest jakiś kwadrat zawierający O, tak że podróżowanie w linii prostej od kwadratu w 2 głównych kierunkach spowoduje uderzenie w bok prostokąta.

Drukuje maksymalnie 1 i pole siatki, jeśli dane wejściowe są „zadowalające pod względem arborowym”; w przeciwnym razie 0.

Oracle SQL 11.2, 364 344 bajty

WITH v AS(SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y FROM DUAL WHERE'O'=SUBSTR(:g,LEVEL,1)CONNECT BY LEVEL<=LENGTH(:g))SELECT a.*,b.*FROM v a,v b WHERE b.x>a.x AND b.y>a.y MINUS SELECT a.*,b.*FROM v a,v b,v c WHERE((c.x IN(a.x,b.x)AND c.y>=a.y AND c.y<=b.y)OR(c.y IN(a.y,b.y)AND c.x>=a.x AND c.x<=b.x))AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

: g to siatka jako ciąg znaków
: w to szerokość siatki

Nie zwraca wiersza jako prawdziwego, zwraca prostokąty, które nie spełniają kryteriów, jako fałsz

Nie grał w golfa

WITH v AS
(
  SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y,SUBSTR(:g,LEVEL,1)p 
  FROM   DUAL 
  WHERE  'O'=SUBSTR(:g,LEVEL,1)
  CONNECT BY LEVEL<=LENGTH(:g)
)
SELECT a.*,b.*FROM v a,v b
WHERE b.x>a.x AND b.y>a.y
MINUS
SELECT a.*,b.*FROM v a,v b,v c
WHERE((c.x IN(a.x,b.x) AND c.y>=a.y AND c.y<=b.y) OR (c.y IN(a.y,b.y) AND c.x>=a.x AND c.x<=b.x))
  AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

Widok v oblicza współrzędne każdego punktu O.
Pierwsza część minus zwraca wszystkie prostokąty, klauzula where zapewnia, że ​​punkt nie może być sparowany ze sobą.
Druga część szuka trzeciego punktu w każdym prostokącie. Ten punkt musi mieć jedną współrzędną, x lub y, równą tej współrzędnej dla jednego z dwóch punktów definiujących prostokąt. Druga współrzędna tego trzeciego punktu musi znajdować się w zakresie ograniczonym przez tę współrzędną dla każdego punktu definiującego prostokąt.
Ostatnia część klauzuli where zapewnia, że ​​trzeci punkt nie jest jednym z dwóch punktów definiujących prostokąt.
Jeśli wszystkie prostokąty mają co najmniej trzeci punkt, wówczas pierwsza część minus jest równa drugiej części, a zapytanie nic nie zwraca.

MATL , 38 bajtów

Ti2\2#fh!XJ"J@-XKtAZ)"@K-@/Eq|1>~As2>*

Wykorzystuje tablicę znaków 2D jako dane wejściowe, z wierszami oddzielonymi przez ;. Tak więc pierwszym przykładem jest

['......';'....O.';'......';'.O..O.';'......']

Pozostałe przypadki testowe w tym formacie są następujące.

• Arborally zadowolony:

  ['.OOO.';'OO...';'.O.OO';'.O..O';'....O']
  ['..O..';'OOOO.';'...O.';'.O.O.';'...OO']
  ['O.O.';'..O.';'OOOO';'.O.O';'OO..']
  ['...';'...';'...']
  ['...';'..O';'...']
  ['O.....';'O.O..O';'.....O']
  ['OOO.OO']
  

• Niezadowolony z altanki:

  ['..O..';'O....','...O.';'.O...';'....O']
  ['..O..';'O.OO.';'...O.';'.O.O.';'...OO']
  ['O.....';'..O...';'.....O']
  

Wypróbuj online! Możesz także zweryfikować wszystkie przypadki testowe jednocześnie .

Wyjaśnienie

Kod najpierw pobiera współrzędne znaków Ona wejściu. Następnie używa dwóch zagnieżdżonych pętli. Zewnętrzna pętla wybiera każdy punkt P (2-krotność swoich współrzędnych), porównuje ze wszystkimi punktami i utrzymuje punkty, które różnią się od P w dwóch współrzędnych. Są to punkty, które mogą tworzyć prostokąt z P. Nazwij je zbiorem R.

Pętla wewnętrzna wybiera każdy punkt T z R i sprawdza, czy prostokąt zdefiniowany przez P i T zawiera co najmniej 3 punkty. Aby to zrobić, odejmuje P od wszystkich punktów; to znaczy przesuwa początek współrzędnych do P. Punkt znajduje się w prostokącie, jeśli każda ze współrzędnych podzielona przez odpowiednią współrzędną T znajduje się w zamkniętym przedziale [0, 1].

T          % push "true"
i          % take input 2D array
2\         % modulo 2: gives 1 for 'O', 0 for '.'
2#f        % row and column coordinates of ones. Gives two column arrays
h!         % concatenate horizontally. Transpose. Each point is a column
XJ         % copy to clipboard J
"          % for each column
  J        %   push all points
  @-       %   subtract current point (move to origin)
  XK       %   copy to clipboard K
  tA       %   logical index of points whose two coordinates are non-zero
  Z)       %   keep only those points. Each is a column
  "        %   for each column (point)
    @K-    %     push that point. Subtract all others
    @/     %     divide by current point
    Eq|1>~ %     true if in the interval [0,1]
    A      %     true if that happens for the two coordinates
    s      %     sum: find out how many points fulfill that
    2>     %     true if that number is at least 3
    *      %     multiply (logical and). (There's an initial true value at the bottom)
           %   end
           % end
           % implicit display

PHP, 1123 bajty , 851 bajtów , 657 bajtów

(początkujący php)

<?php
$B=array_map("str_split",array_map("trim",file('F')));$a=[];$b=-1;foreach($B as $c=>$C){foreach($C as $d=>$Z){if($Z=='O'){$a[++$b][]=$c;$a[$b][]=$d;}}}$e=array();foreach($a as $f=>$l){foreach($a as $g=>$m){$h=$l[0];$i=$l[1];$j=$m[0];$k=$m[1];if($h!=$j&&$i!=$k&&!(in_array([$g,$f],$e,1)))$e[]=[$f,$g];}}$A=array();foreach($e as $E){$n=$E[0];$o=$E[1];$q=$a[$n][0];$s=$a[$n][1];$r=$a[$o][0];$t=$a[$o][1];$u=($q<$r)?$q:$r;$v=($s<$t)?$s:$t;$w=($q>$r)?$q:$r;$X=($s>$t)?$s:$t;$Y=0;foreach($a as $p){$x=$p[0];$y=$p[1];if($x>=$u&&$x<=$w&&$y>=$v&&$y<=$X){$Y=($x==$q&&$y==$s)||($x==$r&&$y==$t)?0:1;}if($Y==1)break;}if($Y==1)$A[]=1;}echo count($A)==count($e)?1:0;

wyjaśnienie (kod skomentowany):

<?php
//read the file
$lines=array_map("str_split",array_map("trim",file('F'))); // grid in file 'F'

//saving coords
$coords=[]; // new array
$iCoord=-1;
foreach($lines as $rowIndex=>$line) {
    foreach($line as $colIndex=>$value) {
        if ($value=='O'){
            $coords[++$iCoord][]=$rowIndex;//0 is x
            $coords[$iCoord][]=$colIndex;  //1 is y
        }
    }
}

/* for each point, draw as many rectangles as other points
 * without creating 'mirror' rectangles
 */ 
$rectangles=array();

foreach ($coords as $point1Index=>$point1) {
     //draw
     foreach ($coords as $point2Index=>$point2) {
            $point1X=$point1[0];
            $point1Y=$point1[1];
            $point2X=$point2[0];
            $point2Y=$point2[1];
            //if not on the same line or on the same column, ...
            if ($point1X!=$point2X &&   // same line
                $point1Y!=$point2Y &&   // same column
                !(in_array([$point2Index,$point1Index],$rectangles,true)) //... and if no 'mirror one' already
             ) $rectangles[]=[$point1Index,$point2Index]; //create a new rectangle
     }
 }

//now that we have rectangles and coords
//try and put a third point into each
$tests=array();
foreach ($rectangles as $rectangle) {
    $pointA=$rectangle[0];    // points of the rectangle
    $pointB=$rectangle[1];    // __________"____________
    $xA=$coords[$pointA][0];
    $yA=$coords[$pointA][1];
    $xB=$coords[$pointB][0];
    $yB=$coords[$pointB][1];
    $minX=($xA<$xB)?$xA:$xB;
    $minY=($yA<$yB)?$yA:$yB;
    $maxX=($xA>$xB)?$xA:$xB;
    $maxY=($yA>$yB)?$yA:$yB;

    $arborally=false;
    foreach ($coords as $point) {
        $x=$point[0];
        $y=$point[1];
        if ($x>=$minX &&
            $x<=$maxX &&
            $y>=$minY &&
            $y<=$maxY) {
                $arborally=($x==$xA&&$y==$yA) || ($x==$xB&&$y==$yB)?0:1; //same point (pointA or pointB)
        }     
        if ($arborally==true) break;//1 found, check next rectangle
    }
    if ($arborally==true) $tests[]=1;//array of successes

}

echo count($tests)==count($rectangles)?1:0; //if as many successes than rectangles...

?>

C, 289 bajtów

a[99][99],x,X,y,Y,z,Z,i,c;main(k){for(;x=getchar(),x+1;x-10||(y=0,i++))a[y++][i]=x;for(;X<i;X++)for(x=0;a[x][X]-10;x++)for(Y=X+1;Y<i;Y++)for(y=0;a[y][Y]-10;y++)if(x-y&&!(a[x][X]-79||a[y][Y]-79)){c=0;for(Z=X;Z<=Y;Z++)for(z=x<y?x:y;z<=(x>y?x:y);)a[z++][Z]-79||c++;c-2||(k=0);}putchar(k+48);}

Wymaga końcowego znaku nowej linii, co jest dozwolone (bez nowego wiersza kod byłby o dwa bajty większy). Wyjścia 0 (niezadowolony z arborum) lub 1 (zadowolony z arborum).