14

Mis hijos tienen una estera con el alfabeto para jugar, algo como esto:

Después de meses con los mosaicos de la alfombra colocados al azar, me cansé y coloqué todos los mosaicos de la alfombra agrupados por secciones de acuerdo con sus colores de fondo. Entonces, si las letras representan el color de fondo, tengo un tapete como este:

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC

Por lo tanto, para los colores A, B, C, D y E, siempre hay una manera de conectar todos los mosaicos con el mismo color de fondo, ya sea horizontal o verticalmente en el tapete. Eso es lo que yo llamo una alfombra debidamente agrupada por colores . Puede ver los grupos para el ejemplo anterior en las siguientes tablas:

AA
A
A
AA
AAAA
AAAAAA

  BB
 BB
 B

    C
   CCC
  CCCC
  CCC
    CCCC
      CCC

     DDD
      D
      DD
     DD

        E
       EE
        E
       EE
        E

Además, solo hay un grupo para cada color, por lo que esto no sería válido:

ABA
ABA

Porque los mosaicos de color A no se agrupan en un solo grupo. Esto tampoco sería válido porque los mosaicos no se conectan ni horizontal ni verticalmente:

AB
BA

El reto

Dado un conjunto de caracteres bidimensionales en el rango ASCII imprimible (no es necesario que sea cuadrado siempre que el tamaño de ambas dimensiones sea igual o mayor que 1), verifique si el conjunto representa una estera correctamente agrupada por colores (cada carácter diferente en la matriz representa un color diferente). La entrada puede estar en cualquier formato razonable siempre que represente una matriz de caracteres bidimensional (matriz de caracteres 2D, matriz de cadenas de la misma longitud, etc.), y la salida debe ser un par de valores de verdad y falsey (0 / 1, 't' / 'f', verdadero / falso, lo que sea siempre que se devuelva algo y los valores de retorno sean consistentes en todas las entradas).

Este es el código de golf, ¡así que puede ganar el programa / función / método / lambda más corto para cada idioma!

Ejemplos

A    truthy

AB
AB   truthy

AB
BA   falsey

ABCDE    truthy

ABCDC    falsey

**::dd22
***:d222
*:::::22    truthy

$$$%%%&&
$$%%&&&&
&&$$$%&&    falsey

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC   truthy

AABB
ABBA
AAAA    truthy

AAAB
AAAA
AAAA    truthy

Mi esterilla correctamente agrupada por colores.

(Todavía tengo que arreglar esas fronteras ...)

code-golf decision-problem grid matrix tiling Charlie
fuente

1

Por curiosidad, ¿por qué no organizarías el tapete en orden alfanumérico? Nada que ver con el desafío, por supuesto, solo me pregunto

caird coinheringaahing el

44

@cairdcoinheringaahing porque entonces mi OCD particular no estaría satisfecho. :-)

Charlie el

3

Sus hijos continúan siendo una fuente de inspiración para los desafíos de golf de código :-)

Luis Mendo

2

¿Por qué los colores tienen que estar representados por caracteres en lugar de alguna otra entrada (como enteros o incluso píxeles)?

Jonathan Allan

2

hablando de ocd, este desafío no estará completo sin una imagen de la alfombra debidamente agrupada

Jonás

6

MATL , 16 15 bytes

1e"G@=4&1ZI1>vzg

La entrada es una matriz de caracteres 2D (con filas separadas por ;). La salida es 0si la entrada califica, o de 1otra manera.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

El código verifica esencialmente si cada carácter en la entrada tiene solo un componente conectado, considerando la conectividad 4 (es decir, sin diagonales).

Los caracteres repetidos se procesan repetidamente (lo que es más elegante que la deduplicación).

1e       % Implicit input. Reshape into a row vector of chars
"        % For each char
  G      %   Push input again
  @      %   Push current char
  =      %   Equal (element-wise)? Gives a matrix of zeros and ones, where one
         %   represents the presence of the current char
  4      %   Push 4. This will indicate 4-connectivity
  &1ZI   %   Matrix with labels of connected componnents. Inputs are a number (4)
         %   to indicate connectivity, and a binary matrix. The output is a matrix
         %   the same size as the input where each connected componnent of ones
         %   in the input is replaced by a different integer starting at 1
  1>     %   Greater than 1 (element-wise)? The result is a matrix. If the result 
         %   is true for some entry the input doesn't qualify
  v      %   Concatenate vertically with results from previous iterations
  z      %   Number of nonzero/true values
  g      %   Logical. Converts nonzero to true
         % Implicit end. Implicit display. False / true are displayed as 0 / 1

Luis Mendo
fuente

3

Befunge-93, 317 bytes

Editar: corregido para el recuento de bytes adecuado. También se podría jugar más al golf

93+:10pv  +93p01+1g01_  [email protected]<
gp00g1+>00p~1+:93+`!#^_1-00g10
50p93+:vv_v#!:gg03:p02:<>40p#
!`g01: <>\ 1+:vvp05:+<@^p03_^#
v93$_v# !- g00<4v04g<^1<vp06:<
>+\!\>\ 3v> 40v0>g-v^<.g>:70vp
07_v#:<^ >#+0# g#\<  10\v4gg<^
!#v _$^  g03p <\ v1_#:^5>0g  -
   <    ^ g02p1< >-:#^_^#:g05
-1<   ^p\g06\0\+1:\g06\-1:\g06:\+1g06:g07

Imprime 1 como la verdad, 0 como la falsey

Pruébalo en línea

Aquí hay una visualización del camino que toma el puntero

Nota: esto es para una versión anterior

Cómo funciona

Aquí hay un pseudocódigo rápido y sucio

a = 2Darray() # from 12,12 down and to the right
arrayLocation = 12
x = arrayLocation #stored at 0,0
y = arrayLocation #stored at 1,0
i = input()       #stored in the stack
while (i != 0):
    if (i == 10):
        y++
        x = init
    else
        a[x][y] = i
        x++
    i = input

new.x = init    #stored at 2,0
new.y = init    #stored at 3,0

currentChar = 0    #stored at 4,0
chars = array()    #stored at 1,1 onwards
charnum = 0        #stored 5,0
ToCheck = array()  #stored in the stack

current.x = null   #stored at 6,0
current.y = null   #stored at 7,0

while (new.y < y):
    if (a[new] != 0)
        currentChar = a[new]
        toCheck[] = new
        while (toCheck)
            current = toCheck.pop()
            if (a[current] == currentChar)
                toCheck.append(adjacent(current))
                a[current] = 0
        foreach (chars as char)
            if (char == currentChar)
                return 0
        charNum++
        chars[charNum] = char
    new.x++
    if (new.x > x)
        new.x = init
        new.y++

return 1

Básicamente, después de almacenar la entrada, pasa por todo, verificando cada espacio. Cuando encuentra un espacio con un carácter, agrega las coordenadas a la pila. Luego verifica los espacios a su alrededor para el mismo personaje de forma recursiva, configurando cada espacio en 0. Cuando ha agotado la sección de ese personaje, verifica si ese personaje ya ha tenido una sección. Si es así, devuelva 0. Si no, agréguelo a la matriz de caracteres. Una vez que ha pasado por toda la cuadrícula sin duplicados, devuelve 1.

Para las personas familiarizadas con Befunge, aquí hay una versión separada del código

96+:10p    v    +69p01+1g01_v
`+96:+1~p00<+1g00pg01g00-1_^#
v                           <
>40p50p96+:v                ^
v    @.1<  >
>:10g `#^_30p:20p:30gg:#v_$>1+:00g-!#v_0   >30g+
v                       <  ^         >$96+1^
>40p30gv                   ^
       >:!#v_70p:60p:70gg40 g-!#v_$>
           v               ^     > ^
1:\g06\+1:g 07\g07\-1:\g07\ +1: <^p\g06\0\-
v          <               ^
>50gv   >5\g1+:50p40g\1p20g^
    >:!#^_:1g40g-!#v_1-
                   >0.@

Jo King
fuente

para ser honesto, siento que deberías contarlo como 337 bytes. De lo contrario, ¿cómo especifica las dimensiones del código dentro del archivo? Las nuevas líneas también deberían contar.

NieDzejkob

@NieDzejkob Sí, desde entonces he cambiado la forma en que cuento los bytes y me he conformado con lo que dice TIO. También tuve el recuento de líneas mal de todos modos? Quizás mañana intente acortarlo un poco más

Jo King

2

J, 66 bytes

c=.1=+/@,+.]-:]*[:*@+/((,|."1)0,.1 _1)&(|.!.0)
[:*/[:c"2[="_ 0~.@,

cdefine un verbo que indica si una matriz de unos y ceros se c onnected. Trata los singleton como un caso especial de verdad. De lo contrario, se necesita un recuento ortogonal vecino de cada celda, luego el signo de ese recuento, luego se multiplica con la matriz original: si ese producto es igual a la matriz original, entonces está conectado.

El recuento de vecinos se logra cambiando en las 4 direcciones y luego sumando. El cambio de 4 direcciones se logra utilizando la función " x-arg can by a table" de rotar / cambiar|.

Finalmente, la respuesta en sí se logra creando una matriz de unos / ceros para cada elemento único ~. de la entrada, y luego asegurando que todas esas matrices estén conectadas. Este es el verbo en la segunda línea.

Pruébalo en línea!

Jonás
fuente

2

JavaScript (ES6), 114 bytes

Toma la entrada como una matriz de cadenas. Devoluciones 0o 1.

a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

Casos de prueba

Mostrar fragmento de código

let f =

a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

console.log(f([ // 1
  "A"
]))

console.log(f([ // 1
  "AB",
  "AB"
]))

console.log(f([ // 0
  "AB",
  "BA"
]))

console.log(f([ // 1
  "ABCDE"
]))

console.log(f([ // 0
  "ABCDC"
]))

console.log(f([ // 1
  "**::dd22",
  "***:d222",
  "*:::::22"
]))

console.log(f([ // 0
  "$$$%%%&&",
  "$$%%&&&&",
  "&&$$$%&&"
]))

console.log(f([ // 1
  "AABBCDDDE",
  "ABBCCCDEE",
  "ABCCCCDDE",
  "AACCCDDEE",
  "AAAACCCCE",
  "AAAAAACCC"
]))

console.log(f([ // 1
  "AABB",
  "ABBA",
  "AAAA"
]))

console.log(f([ // 1
  "AAAB",
  "AAAA",
  "AAAA"
]))

Expandir fragmento

Formateado y comentado

a => (                            // given an array of strings a
  C = {},                         // C = object holding encountered characters
  F = x =>                        // F = recursive function taking x:
    !C[c = a[y][x]]               //   c = current character; is it a new one?
    | (g = v =>                   //   g = helper function taking v
        (a[y + v] || [])[x] == c  //       and testing whether a[y + v][x] == c
      )(-1)                       //   test a[y - 1][x]
    | g(1)                        //   test a[y + 1][x]
    | g(0, x--)                   //   test a[y][x - 1]
    | g(0, x += 2) ?              //   test a[y][x + 1]; if at least one test passes:
      a[y += !c] ?                //     increment y if c is undefined; if a[y] exists:
        F(C[c] = c ? x : 0)       //       update C, update x and do a recursive call
      :                           //     else:
        1                         //       all characters have been processed -> success
    :                             //   else:
      0                           //     invalid character detected -> failure
)(y = 0)                          // initial call to F, starting with x = y = 0

Arnauld
fuente

1

Wolfram Language (Mathematica) , 96 bytes

And@@(ConnectedGraphQ@Subgraph[GridGraph@Dimensions[t],Tr/@Position[c,#]]&/@(c=Join@@(t=#)))&

Pruébalo en línea!

Toma la entrada como una lista 2D de caracteres: por ejemplo, {{"A","B"},{"C","D"}} ,.

El personaje es\[Transpose] .

Cómo funciona

Para cada carácter cen la entrada, toma la Subgraphde la GridGraphde la misma Dimensionscomo la entrada que corresponde a cada Positionen el que cse produce, y comprueba si se trata de una ConnectedGraphQ.

Misha Lavrov
fuente

1

Python 2 , 247 bytes

def f(a):
 b=map(list,a.split('\n'));l=len(b[0])
 for c in set(a):i=a.find(c);g(b,i/l,i%l,c)
 print all(set(l)<={0}for l in b)
def g(a,i,j,c):
 if len(a)>i>-1<j<len(a[0])and a[i][j]==c:
	for x,y in(0,1),(0,-1),(1,0),(-1,0):g(a,i+x,j+y,c);a[i][j]=0

Pruébalo en línea!

TFeld
fuente

1

JavaScript (ES6), 181 bytes

(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}

Siempre que encuentre un nuevo mosaico de color, llene los conectados con cadenas vacías. Si el tapete está correctamente agrupado por colores, todos los mosaicos deben llenarse con cadenas vacías.

Código de prueba

Mostrar fragmento de código

const t =
(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}
;

const mat = s=>s.split('\n').filter(l=>l).map(l=>l.split(''));
console.log('true?', t(mat(`
A
`)));
console.log('true?', t(mat(`
AB
AB
`)));
console.log('false?', t(mat(`
AB
BA
`)));
console.log('true?', t(mat(`
ABCDE
`)));
console.log('false?', t(mat(`
ABCDC
`)));
console.log('true?', t(mat(`
**::dd22
***:d222
*:::::22
`)));
console.log('false?', t(mat(`
$$$%%%&&
$$%%&&&&
&&$$$%&&
`)));
console.log('true?', t(mat(`
AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC
`)));
console.log('true?', t(mat(`
AABB
ABBA
AAAA
`)));
console.log('true?', t(mat(`
AAAB
AAAA
AAAA
`)));

Expandir fragmento

yetirs
fuente

¿Cómo toma entrada su programa?

Stan Strum

¿La estera del alfabeto de mis hijos está correctamente agrupada por colores?

El reto

Ejemplos

Mi esterilla correctamente agrupada por colores.

Respuestas:

MATL , 16 15 bytes

Explicación

Befunge-93, 317 bytes

Cómo funciona

J, 66 bytes

JavaScript (ES6), 114 bytes

Casos de prueba

Formateado y comentado

Wolfram Language (Mathematica) , 96 bytes

Cómo funciona

Python 2 , 247 bytes

JavaScript (ES6), 181 bytes

Código de prueba