Imprimir um retângulo Pentomino

16

Escreva um programa ou função que não aceite nenhuma entrada, mas imprima ou retorne uma representação textual constante de um retângulo feito dos 12 pentominós distintos :

12 pentominós

O retângulo pode ter qualquer dimensão e estar em qualquer orientação, mas todos os 12 pentominós devem ser usados ​​exatamente uma vez, para ter a área 60. Cada pentominó diferente deve ser composto por um caractere ASCII imprimível diferente (você não precisa usar o letras de cima).

Por exemplo, se você optar por gerar esta solução de retângulo pentomino 20 × 3:

Solução 3x20

A saída do seu programa pode ser algo como isto:

00.@@@ccccF111//=---
0...@@c))FFF1//8===-
00.ttttt)))F1/8888=-

Como alternativa, você pode achar mais fácil jogar golfe nesta solução 6 × 10:

000111
203331
203431
22 444
2   46
57 666
57769!
58779!
58899!
5889!!

Qualquer solução de retângulo serve, seu programa só precisa imprimir uma. (Uma nova linha à direita na saída está correta.)

Este ótimo site tem muitas soluções para várias dimensões de retângulo e provavelmente vale a pena procurá-las para garantir que sua solução seja a mais curta possível. Isso é código-golfe, a resposta mais curta em bytes vence.

Passatempos de Calvin
fonte
15
Bônus se for um "quine" em Piet.
mbomb007
@ mbomb007 Isso é praticamente impossível com apenas 12 blocos para jogar: P
Sp3000 10/15/15
Eu não acho que os espaços devam ser permitidos nas fronteiras. Mas, como são, posso omitir espaços à direita? Recebo um bônus se imprimir uma solução vertical 5x12 com um I sem espaços no final?
John Dvorak
@ Sp3000, que tal um programa Piet composto inteiramente de soluções retangulares pentomino?
John Dvorak
@JanDvorak Você não pode omitir espaços à direita se os tiver. São caracteres como o resto do ASCII imprimível.
Calvin's Hobbies

Respostas:

1

Pitão, 37 bytes

jc4.HC"&f3ªªwril3:[·)ÌDU[r)ÌDA»

Demonstração

Usa uma abordagem muito direta: use bytes hexadecimais como números. Converta para um número hexadecimal, base 256 codifica isso. Isso dá a seqüência mágica acima. Para decodificar, use a função de decodificador 256 base do Pyth, converta em hexadecimal, divida em 4 pedaços e entre em novas linhas.

isaacg
fonte
5

CJam (44 bytes)

Dado no formato xxd porque contém caracteres de controle (incluindo uma guia bruta, que é muito ruim com o MarkDown):

0000000: 2202 7e0d 8ef3 570d e085 e168 cf27 092c
0000010: a235 0c22 3235 3662 3562 332f 5f2c 2c2e
0000020: 7b32 2f27 412b 662b 7d7a 4e2a 

que decodifica para algo ao longo das linhas de

"MAGIC STRING"256b5b3/_,,.{2/'A+f+}zN*

Demonstração on-line levemente não-destruída, que não contém caracteres de controle e funciona muito bem com as funções da biblioteca de decodificação do URI do navegador.

O princípio básico é que, como nenhuma peça abrange mais de 5 linhas, podemos codificar um deslocamento de uma função linear do número da linha de maneira compacta (na base 5, de fato, embora eu não tenha tentado determinar se esse sempre seria o caso )

Peter Taylor
fonte
5

Bash + utilitários comuns do Linux, 50

xxd -s20 -p -c2 $0
#<30 bytes of binary data>

Para recriar isso a partir da base64 codificada:

base64 -d <<< eHhkIC1zMjAgLXAgLWMyICQwCiMiImaSaZlmkDAAMwSjRKNEqoGogYhRVVF7UXu7d3s= > pent.sh

Como existem 12 pentominós, suas cores são facilmente codificadas em hexagonais.

Resultado:

$ ./pent.sh
2222
6692
6999
6690
3000
3304
a344
a344
aa81
a881
8851
5551
7b51
7bbb
777b
$ 
Trauma Digital
fonte
4

J, 49 bytes

u:64++/\|:3#.inv 1377859090 1567813024 1337683230

Você pode escolher as letras de forma que os incrementos máximos entre as letras adjacentes verticalmente sejam 2. Usamos esse fato para codificar incrementos verticais na base3. Depois disso, criamos as somas em execução e adicionamos um deslocamento para obter os códigos ASCII das letras.

Definitivamente jogável. (Ainda não encontrei uma maneira de inserir números base36 de precisão estendidos, mas a base36 simples deve economizar apenas 3 bytes.)

Resultado:

AAA
ABA
BBB
DBC
DCC
DCC
DEE
DFE
FFE
FGE
FGG
GGH
HHH
IIH
JII
JJI
JKK
JKL
KKL
LLL

Experimente online aqui.

randomra
fonte
Muito agradável. Com a codificação base-256, a aplicação dessa diferença de codificação no CJam fornece 33 bytes ( versão de 48 bytes sem b256 ).
Peter Taylor
Isso é incrível! Ele também funcionaria com o 4x15, que funcionaria bem para compactar quatro números em um byte, se você armazenar dados de largura em vez de comprimento. Você precisaria de um layout que tenha o U pentomino voltado para o caminho certo. Há uma abundância no link na pergunta.
Level River St
@steveverrill Você precisaria de um deslocamento inicial para isso, porque haverá mais de 4 partes começando na primeira linha, portanto você não pode codificá-las na base4. Com esse deslocamento extra (por exemplo, 3#i.5qual é 0 0 0 1 1 1 ... 4 4 4), ele pode funcionar, mas provavelmente não será mais curto (pelo menos do jeito que tentei).
Random #
2

Microscript II , 66 bytes

Vamos começar com a resposta simples.

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"

Hooray impressão implícita.

SuperJedi224
fonte
1

Rubi

Rev 3, 55 bytes

i=1
'S, OJ1*$HCH(#%0'.bytes{|e|puts "%x"%i+=e*130&9011}

Como um desenvolvimento adicional da idéia da Randomra, considere a tabela de saída e diferença abaixo. A tabela de diferenças pode ser compactada como antes e expandida multiplicando por 65 = binário 1000001 e aplicando uma máscara 11001100110011. No entanto, Ruby não funciona previsivelmente com caracteres de 8 bits (tende a interpretá-los como Unicode).

Surpreendentemente, a última coluna é inteiramente uniforme. Por isso, na compactação, podemos executar uma mudança de direitos nos dados. Isso garante que todos os códigos sejam ASCII de 7 bits. Na expansão, simplesmente multiplicamos por 65 * 2 = 130 em vez de 65.

A primeira coluna também é totalmente uniforme. Portanto, podemos adicionar 1 a cada elemento (32 a cada byte) sempre que necessário, para evitar qualquer caractere de controle. O 1 indesejado é removido usando a máscara 10001100110011 = 9011 em vez de 11001100110011.

Solution 59 of document linked in question

Start0001

Out  Diff
2223 2222
2433 0210
2433 0000
4445 2012
6555 2110
6577 0022
6687 0110
6887 0200
8897 2010
aa99 2202
caa9 2010
cab9 0010
cbbb 0102
cdbd 0202
cddd 0020

Embora eu use 15 bytes para a tabela, eu realmente só uso 6 bits de cada byte, que é um total de 90 bits. De fato, existem apenas 36 valores possíveis para cada byte, ou seja, 2,22E23 de possibilidades no total. Isso caberia em 77 bits de entropia.

Rev 2, 58 bytes, usando a abordagem incremental de Randomra

i=0
'UPEIP@bPHPBETTEPRADT'.bytes{|e|puts "%x"%i+=e*65&819}

Finalmente, algo mais curto que a solução ingênua. A abordagem incremental de Randomra, com o método bytepacking de Rev 1.

Rev 1, 72 bytes, versão em golfe da rev 0

Algumas mudanças foram feitas na linha de base para acomodar uma reordenação do código por razões de golfe, mas ainda assim chegou mais do que a solução ingênua.

i=0
'UPUIYD&!)$&V*).);c+*'.bytes{|e|i+=1;puts "%x"%(i/2*273+(e*65&819))}

As compensações são codificadas em cada caractere da sequência mágica na base 4 no formato BAC, ou seja, com os 1s representando o símbolo da direita, os 16's representando o símbolo do meio e o símbolo da esquerda na posição 4. Para extraí-los, o código ascii é multiplicado por 65 (binário 1000001) para fornecer e BACBAC, em seguida, é adicionado com 819 (binário 1100110011) para fornecer .A.B.C.

Alguns dos códigos ascii têm o conjunto de 7 bits, ou seja, são 64 mais altos que o valor necessário, para evitar caracteres de controle. Como esse bit é removido pela máscara 819, isso é inconseqüente, exceto quando o valor de Cé 3, o que causa uma transição. Isso deve ser corrigido em um único local (em vez de gprecisarmos usá-lo c).

Rev 0, versão ungolfed

a= %w{000 010 000 201 100 100 011 021 110 120 011 112 111 221 211 221 122 123 112 222}
i=2
a.each{|e|puts "%x"%(i/2*273+e.to_i(16));i+=1} 

Resultado

111
121
222
423
433
433
455
465
665
675
677
778
888
998
a99
aa9
abb
abc
bbc
ccc

Explicação

Da solução a seguir, subtraio a linha de base, fornecendo o deslocamento que armazeno como dados. A linha de base é regenerada como um número hexadecimal no código por i/2*273(273 decimal = 111 hex.)

solution   baseline   offset
AAA        AAA        000
ABA        AAA        010
BBB        BBB        000
DBC        BBB        201
DCC        CCC        100
DCC        CCC        100
DEE        DDD        011
DFE        DDD        021
FFE        EEE        110
FGE        EEE        120
FGG        FFF        011
GGH        FFF        112
HHH        GGG        111
IIH        GGG        221
JII        HHH        211
JJI        HHH        221
JKK        III        122
JKL        III        123
KKL        JJJ        112
LLL        JJJ        222
Level River St
fonte
Parece basicamente a mesma abordagem que a minha, mas você conseguiu evitar o delta único de 4, que me forçou a codificar na base 5. Parece que escolhi o rótulo errado para as peças.
Peter Taylor
Vi sua resposta depois que publiquei a minha. Não posso seguir Cjam, mas pelo que você disse em sua resposta, é uma abordagem semelhante. Na verdade, eu tenho apenas um 3na tabela inteira (logo abaixo da parte inferior), então acho que aumentando a linha de base em pouco mais de 0,5 a cada linha, pode ser realmente possível usar a base 3. Sinta-se à vontade para tentar isso. (Por razões de golfe, parece que vou ter que mudar um pouco a linha de base, o que me dá um pouco mais de 3 e, infelizmente, parece que vai demorar 1 byte a mais que a ingênua solução em Ruby.)
Level River St
Caso não tenha ficado claro antes, minha intenção era parabenizá-lo por fazer um trabalho melhor do que eu, não acusá-lo de copiar. E não vou tentar usar uma taxa de crescimento de 2,5, porque não acho que isso supere a abordagem de codificação por diferença da randomra.
Peter Taylor
@ PeterTaylor obrigado, eu percebi que você estava me parabenizando. Por outro lado, você entrou primeiro com basicamente a mesma idéia e a tornou muito mais curta, então parabéns a você também. Com a abordagem da diferença da randomra, finalmente posso ficar mais curto que a solução ingênua. Também funcionaria bem em 4x15 (dado o layout correto do pentomino). É assim que eu faria em C ou em qualquer outro idioma que funcione bem com cadeias de caracteres de 8. bits. Como o Ruby suporta unicode, ele tenta interpretar cadeias de caracteres de 8 bits como unicode e pode fornecer algumas mensagens de erro irritantes.
Level River St
0

Foo, 66 bytes

"00.@@@ccccF111//=---\n0...@@c))FFF1//8===-\n00.ttttt)))F1/8888=-"
Teoc
fonte
Isso é caractere por caractere idêntico à solução Microscript II acima ... Suponho que esses idiomas estejam relacionados?
Darrel Hoffman
1
@DatrelHoffman não realmente, foo, basicamente, apenas imprime tudo em citações
Teoc