language agnostic - Code Golf: reconoce las cajas de arte ascii

language-agnostic code-golf

Question

Llegué a esto hace un tiempo mientras hacía algún trabajo de estructura de datos, aunque sería un buen código de golf: dada una matriz bidimensional de caracteres que contiene rectángulos de arte ASCII, produzca una lista de coordenadas y tamaños para los rectángulos.

• Cualquier formato de entrada o salida trivially convertible está bien (por ejemplo: char **, lista de cadenas, líneas en entrada estándar, lista de cuatro entradas, estructura, cantidad fija +/- para el tamaño, etc.).
• Del mismo modo, la salida no necesita estar en un orden particular.
• No tiene que ser útil para entradas inválidas o rectángulos mal formados, pero no debe producir coordenadas de aspecto válido para un rectángulo que no está en la entrada.
• No hay dos rectángulos válidos que compartan a + (aunque + puede aparecer no solo como parte del rectángulo)
• Puede suponer que todos los rectángulos son al menos 3x3: cada lado tiene un - o | en eso.

Ejemplos:

" "
" +-+ | "
" | | /-"
" +-+ "
(2,1;3,3)
"+--+ +--+"
"| | | |"
"+--+ +--+"
(0,0;4,3), (6,0;4,3)
" +---+ "
"->|...| "
" +---+ "
(2,0;5,3)
"+-+ +--+ +--+"
"| | | | | |"
"+-+ | | + -+"
" | | "
" +--+ +-+ "
" +--+ | "
" +--+ +-+ "
(0,0;3,3), (4,0;4,5) # (2,5;4,2) is fine, but not needed

Answer 1

F #, 297 caracteres

Un poco cojo, pero simple.

let F a=
for x=0 to Array2D.length1 a-1 do
for y=0 to Array2D.length2 a-1 do
if a.[x,y]=''+'' then
let mutable i,j=x+1,y+1
while a.[i,y]<>''+'' do i<-i+1
while a.[x,j]<>''+'' do j<-j+1
printfn"(%d,%d;%d,%d)"x y (i-x+1)(j-y+1)
a.[i,y]<-'' ''
a.[x,j]<-'' ''
a.[i,j]<-'' ''

Busque un plus. Encuentra el de la derecha. Encuentra el que está debajo. Imprima la información de este rectángulo y anule las ventajas que ya utilizamos. Como cada ventaja es solo una parte de un rectángulo válido, eso es todo lo que tenemos que hacer.

Answer 2

XQuery (304 caracteres)

Aquí está mi solución:

declare variable $i external;let$w:=string-length($i[1]),$h:=count($i)for$y in 1 to$h,$x in 1 to$w,$w in 2 to$w+1 -$x,$h in 1 to$h where min(for$r in (0,$h),$s in 1 to$h return (matches(substring($i[$y+$r],$x,$w),''^/+-*/+$''),matches(substring($i[$y+$s],$x,$w),''^|.*|$'')))return ($x -1,$y -1,$w,$h+1,'''')

Puede ejecutar esto (con XQSharp ) configurando la variable $i para que sea la línea de la entrada

>XQuery boxes.xq "i=('' +-+'',''+-+-+'',''| | '',''+-+ '')" !method=text
2 0 3 2 0 1 3 3

Supongo que uno podría argumentar que declare variable $i external; simplemente está configurando la entrada y, por lo tanto, no se agrega al conteo, en cuyo caso 275 caracteres

Answer 3

Perl - 223 222 216

Versión Golfed (nuevas líneas no significativas):

$y=0;sub k{$s=$-[0];"($s,%i;".($+[0]-$s).",%i)"}while(<>){while(//+-+/+/g){
if(exists$h{&k}){push@o,sprintf k,@{$h{&k}};delete$h{&k}}else{$h{&k}=[$y,2]}}
while(//|.+?/|/g){++${$h{&k}}[1]if exists$h{&k}}++$y}print"@o/n"

La versión más antigua de-golfed:

# y starts at line zero.
$y = 0;
# Abuse Perl''s dynamic scoping rules
# to get a key for the hash of current rectangles,
# which indexes rectangles by x and width,
# and is also used as a format string.
sub k {
# The start of the current match.
$s = $-[0];
# $+[0] is the end of the current match,
# so subtract the beginning to get the width.
"($s,%i;" . ($+[0] - $s) . ",%i)"
}
# Read lines from STDIN.
while (<>) {
# Get all rectangle tops and bottoms in this line.
while (//+-+/+/g) {
# If line is a bottom:
if (exists $h{&k}) {
# Add to output list and remove from current.
push @o, sprintf k, @{$h{&k}};
delete $h{&k}
# If line is a top:
} else {
# Add rectangle to current.
$h{&k} = [$y, 2]
}
}
# Get all rectangle sides in this line.
while (//|.+?/|/g) {
# Increment the height of the corresponding
# rectangle, if one exists.
++${$h{&k}}[1] if exists $h{&k}
}
# Keep track of the current line.
++$y
}
# Print output.
print join", ",@o

Tenga en cuenta que esto no maneja las barras verticales basura a la izquierda de los rectángulos, es decir:

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

Producirá incorrectamente una altura de 2 para ambos. Esto se debe a que el patrón //|.+?/|/g comienza a buscar desde el comienzo de la línea. ¿Alguien tiene una sugerencia sobre cómo solucionar esto?

Answer 4

Python 2.6 - 287 263 254

a = [
"+-+ +--+ +--+",
"| | | | | |",
"+-+ | | + -+",
" | | ",
" +--+ +-+ ",
" +--+ | ",
" +--+ +-+ "
]
l=len
r=range
w,h=l(a[0]),l(a)
[(x,y,u,v)for x in r(0,w)for y in r(0,h)for u in r(x+2,w)for v in r(y+2,h)if a[y][x]==a[v][x]==a[y][u]==a[v][u]==''+'' and a[y][x+1:u]+a[v][x+1:u]=="-"*2*(u-x-1)and l([c for c in r(y+1,v-y)if a[c][x]==a[c][u]==''|''])==v-y-1]

evaluado a:

[(0, 0, 3, 3), (4, 0, 4, 5)]

Answer 5

C ( 204 186 caracteres)

 #include<stdio.h>
char H=7,W=14,*S =
"+-+ +--+ +--+"
"| | | | | |"
"+-+ | | + -+"
" | | "
" +--+ +-+ "
" +--+ | "
" +--+ +-+ ";
void main(){
#define F(a,r,t)if(*c==43){while(*(c+=a)==r);t}
char*c,*o,*e=S;while(*(c=e++))
F(1,45,F(W,''|'',o=c;F(-1,45,F(-W,''|'',c==e-1?
printf("%i,%i %i,%i/n",(c-S)%W,(c-S)/W,(o-c)%W+1,(o-c)/W+1):0;))))
}

El recuento de caracteres es el cuerpo de main (). Este código recorrerá la cadena con e hasta que llegue a la esquina superior izquierda de un posible rectángulo. A continuación, comprobará los bordes con c y utilizando o para realizar un seguimiento de la esquina inferior derecha.

La salida del programa es:

0,0 3,3
4,0 4,5
2,5 4,2

Answer 6

Ruby - 306 260 245 228 168

# 228 chars
g=->(s,u=''-''){o=[];s.scan(//+#{u}+/+/){o<<[$`,$`+$&].map(&:size)};o}
b=t.map{|i|i.split''''}.transpose.map{|s|g[s*'''',''/|'']}
(1...t.size).map{|i|i.times{|j|(g[t[i]]&g[t[j]]).map{|x,y|p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]}}}

produce

[0, 0, 3, 3]
[4, 1, 4, 3]
[10, 3, 3, 3]

para t =

["+-+ +--+",
"| | +--+ | |",
"+-+ | | + -+",
" +--+ +-+ ",
" +--+ | | ",
" +--+ +-+ "]

Explicación:

# function returns info about all inclusions of "+---+" in string
# " +--+ +-+" -> [[2,5],[7,9]]
g=->(s,u=''-''){o=[];s.scan(//+#{u}+/+/){o<<[$`,$`+$&].map(&:size)};o}
# mapping transposed input with this function
b=t.map{|i|i.split''''}.transpose.map{|s|g[s*'''',''/|'']}
# earlier here was also mapping original input, but later was merged with "analyse"
# "analyse"
# take each pair of lines
(1...t.size).map{|i|i.times{|j|
# find horizontal sides of the same length on the same positions
(g[t[i]]&g[t[j]]).map{|x,y|
# make output if there are correct vertical sides
p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]
}
}}
# yeah, some strange +/-1 magick included ,.)

¡Y una solución más directa de 168 caracteres!

t.size.times{|i|t[0].size.times{|j|i.times{|k|j.times{|l|p [l,k,j-l+1,i-k+1]if
t[k..i].map{|m|m[j]+m[l]}*''''=~/^/+/+/|+/+/+$/&&t[i][l..j]+t[k][l..j]=~/^(/+-+/+){2}$/}}}}

Answer 7

Perl, 167 165 159 caracteres

( 156 caracteres si no cuentas sldinping stdin a @a, solo elimina los últimos 3 caracteres y asigna una lista de cadenas que representan tu entrada a @ a)

Obtiene la entrada de stdin. Newlines no significativos, agregados para legibilidad. Observe el uso del operador +++ ; P

map{$l=$i++;while($c=//+-+/+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}/|.{$w}/|/;
print"($x,$l;",$w+2,",$c)/n"if$a[$c+++$l]=~/^.{$x}/+-{$w}/+/}}@a=<>

Sé liberal en lo que aceptas versión, 170 caracteres

map{$l=$i++;while($c=//+-*/+/g){pos=-1+pos;$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}/|.{$w}/|/;
print"($x,$l;",$w+2,",$c)/n"if$a[$c+++$l]=~/^.{$x}/+-{$w}/+/}}@a=<>

Sé conservador en lo que aceptas versión, 177 caracteres

map{$l=$i++;while($c=//+-+/+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}/|.{$w}/|/;print
"($x,$l;",$w+2,",$c)/n"if$c>1&&$a[$c+++$l]=~s/^(.{$x})/+(-{$w})/+/$1v$2v/}}@a=<>

Versión comentada:

@a=<>; # slurp stdin into an array of lines
$l=0; # start counting lines from zero
map{ # for each line
while(//+-+/+/g){ # match all box tops
$c=1; # initialize height
# x coordinate, width of box - sides
$w=$+[0]-2-($x=$-[0]);
# increment height while there are inner parts
# of a box with x and w coinciding with last top
# (look into next lines of array)
$c++ while $a[$l+$c]=~/^.{$x}/|.{$w}/|/;
# if there is a box bottom on line + height
# with coinciding x and w, print coords
# (after incrementing height)
print "($x,$l;",$w+2,",$c)/n"
if $a[$c+++$l]=~/^.{$x}/+-{$w}/+/
}
$l++ # line++
}@a

Caso de prueba Mega:

+--+ +-+ +-+ +++ +---+ +-+ +-+-+ +-++-+
|SO| | | | | +++ |+-+| | | | | | | || |
+--+ +-+-+-+ +++ ||+|| +-+ +-+-+ +-++-+
| | |+-+| | |
+-+-+-+ +---+ +-+
| | | |
+-+ +-+
++ +-+ ++ +-+ +- + +--+ +--+ +--+
|| +-+ ++ +-+-+ | | | | | | |
++ | | | | | | | | |
+-+ +--+ + -+ +--+ +--+

Answer 8

Scala 2.8 - 283 273 269 257

val a = Seq(
"+-+ +--+ +--+",
"| | | | | |",
"+-+ | | + -+",
" | | ",
" +--+ +-+ ",
" +--+ | ",
" +--+ +-+ "
)
// begin golf count
val (w,h) = (a(0).size-1,a.size-1)
for (
x <- 0 to w;
y <- 0 to h;
u <- x+2 to w;
v <- y+2 to h;
if Set(a(y)(x),a(v)(x),a(y)(u),a(v)(u)) == Set(43)
&& (x+1 to u-1).forall(t => (a(y)(t)<<8|a(v)(t)) == 11565)
&& (y+1 to v-1).forall(t => (a(t)(x)<<8|a(t)(u)) == 31868)
) yield (x,y,u-x+1,v-y+1)
// end golf count

evalúa a:

Vector((0,0,3,3), (4,0,4,5))

La expresión for evalúa a la respuesta (el objeto Vector), es por eso que conté solo esta parte (espacios blancos eliminados). Avísame si esta es la forma correcta de contar.

Cómo funciona

Las coordenadas de todos los rectángulos posibles (en realidad, solo> = 3x3) son generadas por la expresión for . Estas coordenadas se filtran al buscar el signo +, - y | en los bordes y esquinas de todos los rectángulos (la parte if de la expresión for ).

Answer 9

JavaScript - 156 caracteres *

También en http://jsfiddle.net/eR5ee/4/ ( solo haga clic en el enlace si usa Firefox o Chrome) o http://jsfiddle.net/eR5ee/5/ (adaptado a Safari y Opera):

var A = [
"+-+ +--+ +--+",
"| | | | | |",
"+-+ | | + -+",
" | | ",
" +--+ +-+ ",
" +--+ | ",
" +--+ +-+ "
]; // not counted
for(y=A.length;--y;)for(;m=//+-*/+/g(A[y]);){
for(w=m[0].length,z=y;A[--z][x=m.index]+A[z][x+w-1]=="||";);
/^/+-*/+$/(A[z].substr(x,w))&&alert([x,z,w,y-z+1])}

• Excluyendo líneas nuevas y espacios en blanco, que son completamente innecesarios.
• Aparentemente, Firefox y Chrome retienen el lastIndex de la primera expresión regular. Se necesitan cuatro personajes más para mantener a Safari y Opera fuera de un bucle infinito. Para que Internet Explorer funcione, se necesitarían catorce caracteres más para corregir tanto el error anterior como el de "Función esperada". Aparentemente, "... el método de ejecución de una expresión regular se puede llamar ... indirectamente (con regexp(str) )" (citado de la documentación de Mozilla) no se aplica a IE.

El código detecta todos los rectángulos 2x2 y más grandes si la parte inferior de un rectángulo no toca la parte superior o inferior de ningún otro rectángulo o un signo más o menos y ninguno se superpone.

El orden de los números en cada cuadro de alerta (que corresponde a un rectángulo) se deja , arriba , ancho , alto . El código genera un error si un rectángulo se extiende desde la parte superior, pero ya se han generado todas las coordenadas necesarias (según la especificación: "No tiene que ( sic ) nada útil para entradas no válidas o rectángulos mal formados ...")

Dado que la mayoría de los principales navegadores web implementan la etiqueta canvas, en varias líneas más de código, es posible dibujar los rectángulos detectados en la pantalla. http://jsfiddle.net/MquqM/6/ funciona en todos los navegadores excepto Internet Explorer y Opera.

Editar: eliminó una asignación de variable innecesaria Editar 2: evite arrojar errores con una entrada completamente válida (--y en lugar de y--), aclare los casos específicos que maneja el código

Answer 10

Python 2.6 (251 caracteres)

Llegué un poco tarde, de todos modos, un poco divertido. Python, usando expresiones regulares. Para guardar una declaración impresa y permanecer más corto que Fredb219, esto no imprimirá nada si lo ejecuta como un script, pero al escribir una línea a la vez en el intérprete, se mostrará el resultado. No es realmente sólido, no maneja cajas anidadas ni la mayoría de los casos son más complejos que los dados por DavidX. No he hecho pruebas, pero creo que es probable que muestre resultados en un orden incorrecto si ocurre algo "extraño".

import re
l,a,o=s.index("/n")+1,re.finditer,sorted
o(o(set((m.start(),m.end())for m in a(r''/+-* *-*/+'',s)for n in a(r''/|.+/|'',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

La entrada es una sola cadena, líneas (todas de la misma longitud) separadas por un carácter de nueva línea. Los resultados son las secciones de cadena de la parte superior e inferior de cada caja "buena", comenzando arriba a la izquierda. También permite cajas "rotas" (es decir, con un espacio en el medio de un lado, no sin un lado completo). ¡Esta era solo una manera de corregir un comportamiento no deseado creando muchos efectos secundarios completamente nuevos! :-)

entrada:

>>>s = """+-+ +--+ +--+
| | | | | |
+-+ | | + -+
| |
+--+ +-+
+--+ |
+--+ +-+ """

o:

>>>s = "+-+ +--+ +--+/n| | | | | |/n+-+ | | + -+/n | | /n +--+ +-+ /n +--+ | /n +--+ +-+ "

entonces:

>>>import re
>>>l,a,o=s.index("/n")+1,re.finditer,sorted
>>>o(o(set((m.start(),m.end())for m in a(r''/+-* *-*/+'',s)for n in a(r''/|.+?/|'',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

salida:

[(0, 3), (30, 33), (4, 8), (64, 68), (10, 14), (40, 44)]

entonces (0,3) parte superior de la primera caja (30,33) parte inferior de la misma caja, (4,8) parte superior de la segunda caja y así sucesivamente.