14

Meus filhos têm um tapete de alfabeto para brincar, algo assim:

Depois de meses com os ladrilhos do tapete dispostos aleatoriamente, cansei-me e coloquei todos os ladrilhos do tapete agrupados por seções, de acordo com as cores de fundo. Então, se as letras representam a cor de fundo, eu tenho um tapete como este:

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC

Portanto, para as cores A, B, C, D e E, sempre há uma maneira de conectar todos os ladrilhos com a mesma cor de fundo na horizontal ou na vertical no tapete. É o que chamo de um tapete adequadamente agrupado por cores . Você pode ver os grupos do exemplo anterior nas seguintes tabelas:

AA
A
A
AA
AAAA
AAAAAA

  BB
 BB
 B

    C
   CCC
  CCCC
  CCC
    CCCC
      CCC

     DDD
      D
      DD
     DD

        E
       EE
        E
       EE
        E

Além disso, existe apenas um grupo para cada cor, portanto, isso não seria válido:

ABA
ABA

Como os blocos de cores A não são agrupados em apenas um grupo. Isso também não seria válido porque os blocos não se conectam horizontal ou verticalmente:

AB
BA

O desafio

Dada uma matriz bidimensional de caracteres no intervalo ASCII imprimível (não precisa ser um quadrado desde que o tamanho de ambas as dimensões seja igual ou superior a 1), verifique se a matriz representa um tapete adequadamente agrupado por cores (cada caractere diferente na matriz representa uma cor diferente). A entrada pode estar em qualquer formato razoável, desde que represente uma matriz bidimensional de caracteres (matriz de caracteres 2D, matriz de seqüências de caracteres do mesmo comprimento etc.) e a saída deve ser um par de valores de verdade e falsey (0 / 1, 't' / 'f', verdadeiro / falso, desde que algo seja retornado e os valores de retorno sejam consistentes nas entradas).

Este é o código-golfe, portanto, pode ganhar o programa / função / método / lambda mais curto para cada idioma!

Exemplos

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

Meu tapete adequadamente agrupado por cores

(Eu ainda tenho que consertar essas fronteiras ...)

code-golf decision-problem grid matrix tiling Charlie
fonte

1

Por curiosidade, por que você não organizou o tapete em ordem alfanumérica? Nada a ver com o desafio é claro, me perguntando

caird coinheringaahing

4

@cairdcoinheringaahing porque então meu TOC em particular não ficaria satisfeito. :-)

Charlie

3

Seus filhos continuam a ser uma fonte de inspiração para os desafios de golfe código :-)

Luis Mendo

2

Por que as cores precisam ser representadas por caracteres e não por alguma outra entrada (como números inteiros ou até mesmo pixels)?

Jonathan Allan

2

falando de TOC, este desafio não será completa sem uma imagem do tapete devidamente agrupados

Jonah

6

MATL , 16 15 bytes

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

Entrada é uma matriz de caracteres 2D (com linhas separadas por ;). A saída é 0se a entrada for qualificada ou 1não.

Experimente online! Ou verifique todos os casos de teste .

Explicação

O código verifica essencialmente se cada caracter na entrada possui apenas um componente conectado, considerando a conectividade 4 (ou seja, sem diagonais).

Caracteres repetidos são processados repetidamente (que é mais golfista do que com desduplicação).

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
fonte

3

Befunge-93, 317 bytes

Editar: corrigido para contagem de bytes adequada. Também poderia ser jogado ainda mais

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 a verdade, 0 como a falsey

Experimente Online

Aqui está uma visualização do caminho que o ponteiro leva

Nota: isto é para uma versão antiga

Como funciona

Aqui estão alguns pseudocódigos rápidos e sujos

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

Basicamente, depois de armazenar a entrada, ela passa por tudo, verificando cada espaço. Quando encontra um espaço com um caractere, ele adiciona as coordenadas à pilha. Em seguida, verifica os espaços ao redor do mesmo caractere recursivamente, definindo cada espaço como 0. Quando a seção desse personagem estiver esgotada, ele verifica se esse personagem já teve uma seção. Nesse caso, retorne 0. Caso contrário, adicione-o à matriz de caracteres. Depois de percorrer toda a grade sem duplicatas, ele retorna 1.

Para pessoas familiarizadas com o Befunge, aqui está uma versão espaçada do 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.@

Brincadeira
fonte

para ser sincero, acho que você deve contar como 337 bytes. Caso contrário, como você especifica as dimensões do código no próprio arquivo? As novas linhas também devem contar.

NieDzejkob

@NieDzejkob Sim, desde então, mudei a forma como conto bytes e me conforme com o que o TIO diz. Também tive a contagem de linhas errada de qualquer maneira? Talvez amanhã eu tente reduzir um pouco mais o valor

Jo King

2

J, 66 bytes

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

cdefine um verbo que informa se uma matriz de zeros e uns é c onnected. Trata os únicos como um caso especial de verdade. Caso contrário, é necessária uma contagem ortogonal de vizinhos de cada célula, o sinal dessa contagem e a multiplicará pela matriz original: se esse produto for igual à matriz original, ele será conectado.

A contagem de vizinhos é obtida deslocando-se nas 4 direções e somando. A mudança de direção é alcançada usando o recurso " x-arg can by a table" de rotação / mudança|.

Finalmente, a resposta em si foi obtida através da criação de uma matriz uns / zeros para cada elemento exclusivo ~. da entrada e, em seguida, garantindo que todas essas matrizes estejam conectadas. Este é o verbo na segunda linha.

Experimente online!

Jonah
fonte

2

JavaScript (ES6), 114 bytes

Recebe entrada como uma matriz de seqüências de caracteres. Retorna 0ou 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 teste

Mostrar snippet 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 snippet

Formatado e 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
fonte

1

Wolfram Language (Mathematica) , 96 bytes

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

Experimente online!

Recebe a entrada como uma lista 2D de caracteres: por exemplo {{"A","B"},{"C","D"}},.

O personagem é \[Transpose].

Como funciona

Para cada personagem cna entrada, leva o Subgraphdo GridGraphdo mesmo Dimensionscomo a entrada que corresponde a cada Positionem que cocorre, e verifica se é uma ConnectedGraphQ.

Misha Lavrov
fonte

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

Experimente online!

TFeld
fonte

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(''))}

Sempre que um novo bloco de cores for encontrado, preencha os conectados com cadeias de caracteres vazias. Se o tapete estiver adequadamente agrupado por cores, todos os ladrilhos deverão ser preenchidos com cadeias vazias.

Código de teste

Mostrar snippet 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 snippet

yetirs
fonte

Como o seu programa recebe informações?

precisa

O tapete de alfabeto dos meus filhos está adequadamente agrupado por cores?

O desafio

Exemplos

Meu tapete adequadamente agrupado por cores

Respostas:

MATL , 16 15 bytes

Explicação

Befunge-93, 317 bytes

Como funciona

J, 66 bytes

JavaScript (ES6), 114 bytes

Casos de teste

Formatado e comentado

Wolfram Language (Mathematica) , 96 bytes

Como funciona

Python 2 , 247 bytes

JavaScript (ES6), 181 bytes

Código de teste