Identifier des ensembles de points satisfaits sur le plan arborescent

14

Un ensemble de points satisfaits sur le plan arborescent est un ensemble 2D de points tels que, pour tout rectangle aligné sur l'axe qui peut être formé en utilisant deux points de l'ensemble comme coins opposés, ce rectangle contient ou touche au moins un autre point. Voici une définition équivalente de Wikipedia:

Un ensemble de points est dit satisfait sur le plan de l'arborescence si la propriété suivante est vérifiée: pour toute paire de points qui ne se trouvent pas tous les deux sur la même ligne horizontale ou verticale, il existe un troisième point qui se trouve dans le rectangle couvert par les deux premiers points ( soit à l'intérieur soit sur la limite).

L'image suivante illustre la formation des rectangles. Cet ensemble de points n'est PAS satisfait sur le plan arborescent car ce rectangle doit contenir au moins un point supplémentaire.

entrez la description de l'image ici

Dans l'art ASCII, cet ensemble de points peut être représenté comme:

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

Une légère modification peut rendre cette arborescence satisfaite:

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

Ci-dessus, vous pouvez voir que tous les rectangles (dont il n'y en a qu'un) contiennent au moins trois points.

Voici un autre exemple d'un ensemble de points plus complexe qui est satisfait sur le plan arborescent:

entrez la description de l'image ici

Pour tout rectangle pouvant être dessiné sur deux points, ce rectangle contient au moins un autre point.

Le défi

Étant donné une grille rectangulaire de points (avec laquelle je représente O) et un espace vide (avec lequel je représente .), affichez une valeur véridique si elle est satisfaite sur le plan arborescent, ou une valeur de falsey si ce n'est pas le cas. C'est du code-golf.

Règles supplémentaires:

  • Vous pouvez choisir d'avoir les caractères Oet .permutée avec une autre paire de caractères ASCII imprimables. Spécifiez simplement le mappage de caractères utilisé par votre programme.
  • La grille sera toujours rectangulaire. Une nouvelle ligne de fin est autorisée.

Plus d'exemples

Arboriquement satisfait:

.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

Non satisfaits sur le plan de l’arborescence:

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

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

O.....
..O...
.....O
code-golf geometry grid PhiNotPi
la source
1
Donc, nous ne sommes pas autorisés à prendre l'entrée comme une liste de coordonnées au lieu de ASCII? Sinon, puis-je prendre l'entrée comme une liste 2D d'entiers (0 et 1) pour représenter les points?
Denker
La grille peut-elle avoir une zone 0?
feersum

Réponses:

7

Escargots , 29 30 39 octets

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

Cela fonctionne en traçant les 2 côtés du rectangle, puis en vérifiant s'il y a un carré contenant un O de telle sorte que le déplacement en ligne droite du carré dans 2 des directions cardinales entraînerait de frapper un côté du rectangle.

Imprime le maximum de 1 et la zone de la grille si l'entrée est "satisfaite sur le plan de l'arborescence"; sinon 0.

feersum
la source
3

Oracle SQL 11.2, 364 344 octets

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 est la grille sous forme de chaîne
: w est la largeur de la grille

Renvoie aucune ligne comme véridique, renvoie les rectangles qui ne correspondent pas aux critères comme fausses

Non golfé

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));

La vue v calcule les coordonnées de chaque point O.
La première partie du moins renvoie tous les rectangles, la clause where garantit qu'un point ne peut pas être apparié avec lui-même.
La deuxième partie recherche un troisième point dans chaque rectangle. Ce point doit avoir une coordonnée, x ou y, égale à cette coordonnée pour l'un des deux points définissant le rectangle. L'autre coordonnée de ce troisième point doit être dans la plage délimitée par cette coordonnée pour chacun des points définissant le rectangle.
La dernière partie de la clause where garantit que le troisième point n'est pas l'un des deux points définissant le rectangle.
Si tous les rectangles ont au moins un troisième point, la première partie du moins est égale à la deuxième partie et la requête ne renvoie rien.

Jeto
la source
2

MATL , 38 octets

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

Cela utilise un tableau de caractères 2D en entrée, avec des lignes séparées par ;. Donc, le premier exemple est

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

Les autres cas de test dans ce format sont les suivants.

  • Arboriquement satisfait:

    ['.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']

  • Non satisfaits sur le plan de l’arborescence:

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

Essayez-le en ligne! Vous pouvez également vérifier tous les cas de test à la fois .

Explication

Le code obtient d'abord les coordonnées des caractères Odans l'entrée. Il utilise ensuite deux boucles imbriquées. La boucle externe sélectionne chaque point P (2-tuple de ses coordonnées), compare avec tous les points et conserve les points qui diffèrent de P dans les deux coordonnées. Ce sont les points qui peuvent former un rectangle avec P. Appelez-les ensemble R.

La boucle intérieure sélectionne chaque point T de R et vérifie si le rectangle défini par P et T comprend au moins 3 points. Pour ce faire, il soustrait P de tous les points; c'est-à-dire déplace l'origine des coordonnées vers P. Un point est dans le rectangle si chacune de ses coordonnées divisée par la coordonnée correspondante de T est dans l'intervalle fermé [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
Luis Mendo
la source
J'ai plus aimé Don Muesli, pourquoi l'avez-vous changé? :(
Denker
@DenkerAffe :-) Eh bien, je suis revenu à mon vrai nom. L'autre était amusant, mais il devait être temporaire
Luis Mendo
1
Ce n'est pas l'homme de la vraie vie, nous avons besoin de plus de plaisir ici! :)
Denker
@DenkerAffe Je reviendrai peut-être à ce nom ou à un autre à l'avenir. Que diriez-vous de Denim Soul? :-D
Luis Mendo
1
... et vous devez également attendre 30 jours (je pense)
Stewie Griffin
2

PHP, 1123 octets , 851 octets , 657 octets

(php débutant)

<?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;

explication (code commenté):

<?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...

?>
St3an
la source
1

C, 289 octets

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);}

Requiert un retour à la ligne, ce qui est autorisé (sans le retour à la ligne, le code aurait deux octets de plus). Sorties 0 (non satisfait à l'arborescence) ou 1 (satisfait à l'arborescence).

mIllIbyte
la source