14

Um conjunto de pontos satisfeito de forma arborizada é um conjunto de pontos 2D de modo que, para qualquer retângulo alinhado ao eixo que possa ser formado usando dois pontos no conjunto como cantos opostos, esse retângulo contenha ou toque em pelo menos um outro ponto. Aqui está uma definição equivalente da Wikipedia:

Diz-se que um conjunto de pontos é satisfeito de forma arborizada se a seguinte propriedade for válida: para qualquer par de pontos que não estejam na mesma linha horizontal ou vertical, existe um terceiro ponto que fica no retângulo estendido pelos dois primeiros pontos ( dentro ou no limite).

A imagem a seguir ilustra como os retângulos são formados. Esse conjunto de pontos NÃO é satisfeito de forma arborizada porque esse retângulo precisa conter pelo menos mais um ponto.

Na arte ASCII, esse conjunto de pontos pode ser representado como:

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

Uma leve modificação pode fazer com que isso seja satisfeito de forma arborizada:

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

Acima, você pode ver que todos os retângulos (dos quais existe apenas um) contêm pelo menos três pontos.

Aqui está outro exemplo de um conjunto de pontos mais complexo que é satisfeito de forma arborizada:

Para qualquer retângulo que possa ser desenhado com dois pontos, esse retângulo contém pelo menos um outro ponto.

O desafio

Dada uma grade retangular de pontos (que represento com O) e do espaço vazio (que represento com .), a saída de um truthy valor se for arborally satisfeito, ou um Falsey valor se ele não é. Isso é código-golfe.

Regras adicionais:

Você pode optar por ter os caracteres Oe .trocá-los por qualquer outro par de caracteres ASCII imprimíveis. Simplesmente especifique qual mapeamento de caracteres seu programa usa.
A grade sempre será retangular. Uma nova linha à direita é permitida.

Mais exemplos

Arborally satisfeito:

.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

Não está satisfeito de forma arborizada:

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

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

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

code-golf geometry grid PhiNotPi
fonte

1

Portanto, não podemos aceitar a entrada como uma lista de coordenadas em vez de ASCII? Caso contrário, posso usar a entrada como uma lista 2D de números inteiros (0 e 1) para representar os pontos?

Denker 31/03

A grade pode ter área 0?

feersum 31/03

7

Caracóis , 29 30 39 bytes

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

Ele funciona traçando dois lados do retângulo e, em seguida, verificando se existe algum quadrado contendo um O tal que viajar em uma linha reta a partir do quadrado em 2 das direções cardinais resultaria em acertar um lado do retângulo.

Imprime o máximo de 1 e a área da grade se a entrada for "satisfeita de forma arborizada"; caso contrário, 0.

feersum
fonte

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 é a grade como uma string
: w é a largura da grade

Retorna nenhuma linha como verdade, retorna os retângulos que não correspondem aos critérios como falso

Sem golfe

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

A vista v calcula as coordenadas de cada ponto O.
A primeira parte do menos retorna todos os retângulos, a cláusula where garante que um ponto não possa ser emparelhado com ele mesmo.
A segunda parte procura um terceiro ponto em cada retângulo. Esse ponto precisa ter uma coordenada, x ou y, igual à coordenada de um dos dois pontos que definem o retângulo. A outra coordenada desse terceiro ponto precisa estar no intervalo delimitado por essa coordenada para cada um dos pontos que definem o retângulo.
A última parte da cláusula where garante que o terceiro ponto não seja um dos dois pontos que definem o retângulo.
Se todos os retângulos tiverem pelo menos um terceiro ponto, a primeira parte do sinal de menos será igual à segunda parte e a consulta não retornará nada.

Jeto
fonte

2

MATL , 38 bytes

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

Isso usa uma matriz de caracteres 2D como entrada, com linhas separadas por ;. Então o primeiro exemplo é

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

O restante dos casos de teste neste formato são os seguintes.

Arborally satisfeito:

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

Não está satisfeito de forma arborizada:

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

Experimente online! Você também pode verificar todos os casos de teste de uma só vez .

Explicação

O código primeiro obtém as coordenadas dos caracteres Ona entrada. Em seguida, ele usa dois loops aninhados. O loop externo seleciona cada ponto P (2-tupla de suas coordenadas), compara com todos os pontos e mantém pontos que diferem de P nas duas coordenadas. Esses são os pontos que podem formar um retângulo com P. Chame-os de conjunto R.

O loop interno seleciona cada ponto T de R e verifica se o retângulo definido por P e T inclui pelo menos 3 pontos. Para fazer isso, subtrai P de todos os pontos; isto é, move a origem das coordenadas para P. Um ponto está no retângulo se cada uma de suas coordenadas divididas pela coordenada correspondente de T estiver no intervalo fechado [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
fonte

Gostei mais de Don Muesli, por que você mudou de volta? :(

Denker

@ DenkerAffe :-) Bem, voltei ao meu nome verdadeiro. O outro foi divertido, mas foi concebido como temporário.

Luis Mendo

1

Isso não é homem da vida real, precisamos de mais diversão aqui! :)

Denker 02/04

@ DenkerAffe Eu posso voltar para esse nome, ou para outro, no futuro. Que tal Denim Soul? :-D

Luis Mendo

1

... e você tem que esperar 30 dias também (eu acho)

Stewie Griffin

2

PHP, 1123 bytes , 851 bytes , 657 bytes

(php novato)

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

explicação (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
fonte

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

Requer nova linha à direita, o que é permitido (sem a nova linha, o código seria dois bytes maior). Saídas 0 (não satisfeito arboralmente) ou 1 (satisfeito arboralmente).

mIllIbyte
fonte

Identificar conjuntos de pontos satisfatoriamente arbóreos