Identificar conjuntos de puntos satisfechos arboralmente

14

Un conjunto de puntos satisfactoriamente arboralmente es un conjunto de puntos 2D de tal manera que, para cualquier rectángulo alineado con un eje que se pueda formar utilizando dos puntos en el conjunto como esquinas opuestas, ese rectángulo contiene o toca al menos otro punto. Aquí hay una definición equivalente de Wikipedia:

Se dice que un conjunto de puntos se satisface arboralmente si se cumple la siguiente propiedad: para cualquier par de puntos que no se encuentren en la misma línea horizontal o vertical, existe un tercer punto que se encuentra en el rectángulo atravesado por los dos primeros puntos ( ya sea dentro o en el límite).

La siguiente imagen ilustra cómo se forman los rectángulos. Este conjunto de puntos NO se satisface arboralmente porque este rectángulo necesita contener al menos un punto más.

ingrese la descripción de la imagen aquí

En el arte ASCII, este conjunto de puntos se puede representar como:

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

Una ligera modificación puede hacer que esto esté satisfecho:

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

Arriba, puede ver que todos los rectángulos (de los cuales solo hay uno) contienen al menos tres puntos.

Aquí hay otro ejemplo de un conjunto de puntos más complejo que se satisface arboralmente:

ingrese la descripción de la imagen aquí

Para cualquier rectángulo que se pueda dibujar que abarque dos puntos, ese rectángulo contiene al menos otro punto.

El reto

Dada una cuadrícula rectangular de puntos (que represento con O) y un espacio vacío (con el que represento .), genera un valor verdadero si se satisface arboralmente, o un valor falsey si no lo es. Este es el código de golf.

Reglas adicionales:

  • Puede elegir tener los caracteres Oe .intercambiarlos con cualquier otro par de caracteres ASCII imprimibles. Simplemente especifique qué mapeo de caracteres usa su programa.
  • La cuadrícula siempre será rectangular. Se permite una nueva línea final.

Más ejemplos

Arboralmente satisfecho:

.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

No Arboralmente Satisfecho:

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

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

O.....
..O...
.....O
code-golf geometry grid PhiNotPi
fuente
1
Entonces, ¿no se nos permite tomar la entrada como una lista de coordenadas en lugar de ASCII? Si no, ¿puedo tomar la entrada como una lista 2D de enteros (0 y 1) para representar los puntos?
Denker
¿Puede la cuadrícula tener 0 área?
feersum

Respuestas:

7

Caracoles , 29 30 39 bytes

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

Funciona trazando 2 lados del rectángulo y luego verificando si hay algún cuadrado que contenga una O tal que viajar en línea recta desde el cuadrado en 2 direcciones cardinales resulte en golpear un lado del rectángulo.

Imprime el máximo de 1 y el área de la cuadrícula si la entrada está "satisfecha de forma arboral"; de lo contrario 0.

Feersum
fuente
3

Oracle SQL 11.2, 364 344 bytes

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 es la cuadrícula como una cadena
: w es el ancho de la cuadrícula

No devuelve ninguna línea como verdadera, devuelve los rectángulos que no coinciden con los criterios como falso

Sin 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 vista v calcula las coordenadas de cada punto O.
La primera parte del signo menos devuelve todos los rectángulos, la cláusula where asegura que un punto no se puede emparejar consigo mismo.
La segunda parte busca un tercer punto en cada rectángulo. Ese punto debe tener una coordenada, x o y, igual a esa coordenada para uno de los dos puntos que definen el rectángulo. La otra coordenada de ese tercer punto debe estar en el rango delimitado por esa coordenada para cada uno de los puntos que definen el rectángulo.
La última parte de la cláusula where asegura que el tercer punto no es uno de los dos puntos que definen el rectángulo.
Si todos los rectángulos tienen al menos un tercer punto, entonces la primera parte del signo menos es igual a la segunda parte y la consulta no devuelve nada.

Jeto
fuente
2

MATL , 38 bytes

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

Esto utiliza una matriz de caracteres 2D como entrada, con filas separadas por ;. Entonces el primer ejemplo es

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

El resto de los casos de prueba en este formato son los siguientes.

  • Arboralmente satisfecho:

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

  • No satisfecho con el arboral:

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

Pruébalo en línea! También puede verificar todos los casos de prueba a la vez .

Explicación

El código primero obtiene las coordenadas de los caracteres Oen la entrada. Luego usa dos bucles anidados. El bucle externo selecciona cada punto P (2-tuplas de sus coordenadas), se compara con todos los puntos y mantiene puntos que difieren de P en las dos coordenadas. Esos son los puntos que pueden formar un rectángulo con P. Llámalos conjunto R.

El bucle interno selecciona cada punto T de R y verifica si el rectángulo definido por P y T incluye al menos 3 puntos. Para hacer eso, resta P de todos los puntos; es decir, mueve el origen de las coordenadas a P. Un punto está en el rectángulo si cada una de sus coordenadas dividida por la coordenada correspondiente de T está en el intervalo cerrado [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
fuente
Me gustaba más Don Muesli, ¿por qué lo cambiaste? :(
Denker
@DenkerAffe :-) Bueno, volví a mi nombre real. El otro fue divertido, pero fue pensado como temporal
Luis Mendo
1
Este no es el hombre de la vida real, ¡necesitamos más diversión aquí! :)
Denker
@DenkerAffe Puedo volver a ese nombre, oa algún otro, en el futuro. ¿Qué tal Denim Soul? :-D
Luis Mendo
1
... y también tienes que esperar 30 días (creo)
Stewie Griffin
2

PHP, 1123 bytes , 851 bytes , 657 bytes

(novato 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;

explicación (código comentado):

<?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
fuente
1

C, 289 bytes

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

Requiere una nueva línea final, que está permitida (sin la nueva línea, el código sería dos bytes más grande). Salidas 0 (no satisfecho con el arboral) o 1 (satisfecho con el arboral)

MIllIbyte
fuente