Esta questão é inspirada na capa do livro "Godel, Escher, Bach":
O desafio aqui é escrever uma função que diga se três letras dadas podem produzir uma escultura 3D que pode ser lida de três lados.
Para este exercício, as únicas letras que você pode usar são 26 bitmaps de 5px * 5px:
Ou em binário (A a Z):
01110 11110 01111 11110 11111 11111 11111 10001 11111 11111 10001 10000 10001 10001 01110 11110 01110 11110 01111 11111 10001 10001 10001 10001 10001 11111
10001 10001 10000 10001 10000 10000 10000 10001 00100 00100 10010 10000 11011 11001 10001 10001 10001 10001 10000 00100 10001 10001 10001 01010 01010 00010
10001 11110 10000 10001 11100 11110 10011 11111 00100 00100 11100 10000 10101 10101 10001 10001 10001 11111 01110 00100 10001 01010 10001 00100 00100 00100
11111 10001 10000 10001 10000 10000 10001 10001 00100 10100 10010 10000 10001 10011 10001 11110 10011 10010 00001 00100 10001 01010 10101 01010 00100 01000
10001 11110 01111 11110 11111 10000 11111 10001 11111 11100 10001 11111 10001 10001 01110 10000 01111 10001 11110 00100 01110 00100 01010 10001 00100 11111
A escultura é formada por três letras na seguinte ordem:
- letra uma em cima,
- letra dois à esquerda
- letra três à direita
- a parte inferior da letra um está vinculada ao topo da letra dois.
Exemplo:
Sua função pode aceitar como entrada três letras maiúsculas (três caracteres ou três strings de uma letra) e gerar um booleano (verdadeiro / falso ou 0/1) informando se a escultura correspondente pode existir.
Exemplo:
f("B","E","G") // true (because if you "sculpt out" B on top + E on the left + G on the right, and watch the three sides of the sculpture, you'll see exactly B, E and G as they are defined)
f("B","G","E") // false (because if you "sculpt out" B on top + G on the left + E on the right, and watch the three sides of the sculpture, you won't see a complete G and a complete E. Their shapes bother each other)
Nota: você pode retornar verdadeiro mesmo que a escultura contenha "pixels voadores" (cubos ou grupo de cubos que não estão anexados a nada).
Aplicam-se brechas padrão.
Mais precisamente, você não pode usar entrada externa além das três letras e não pode codificar as 17576 possíveis respostas no seu código-fonte
A resposta mais curta em caracteres em qualquer idioma vence!
Diverta-se :)
Respostas:
Mathematica 423
Eu adicionei uma seção chamada "Como funciona o bloqueio".
Ungolfed
(* Os dados binários do alfabeto são armazenados como uma única string em
s
. Osvars
importa e os converte em uma matriz.)Exemplo
O cubo é
{"B", "G", "E"}
válido? (ou seja, as três letras se projetam corretamente nas paredes?)Ilustrações
As figuras abaixo mostram como a BGE é renderizada. A linha superior das figuras tem perspectivas ortogonais, como se o espectador estivesse posicionado a distâncias infinitas do cubo. A linha inferior mostra a aparência dos blocos de perto. As figuras 3D podem ser giradas manualmente para inspecionar com precisão onde os cubos de unidades individuais estão posicionados.
Ocorre um problema com a letra "G". Não há nada conectando a serifa ao restante da carta.
No entanto, o BEG deve funcionar bem.
Como funciona o bloqueio?
Por favor, desculpe-me se isso parecer óbvio, mas talvez algumas pessoas desejem visualizar como as letras interferem umas nas outras, cancelando seus pixels 3D.
Vamos seguir o que acontece com a letra G, na renderização do cubo BGE.
Vamos prestar atenção especial ao voxel (pixel 3D ou cubo unitário) abaixo. Esse é o pixel que desaparece no cubo BGE. É o pixel correspondente à Linha 4, Coluna 5 na matriz de bits e no gráfico da matriz correspondente.
No plano xy, o pixel corresponde ao disco cinza no ponto (5,2). Mas como vamos trabalhar em 3D, precisamos considerar as 5 posições no eixo de (5,1,2) a (5,5,2). Se algum desses pixels sobreviver à escultura pelas letras B e E, poderemos ver o pixel de interesse na projeção 3D na parede.
As letras interferem quando os pixels são removidos do bloco sólido. À esquerda, a seta preta representa a escultura de pixels, correspondente ao bit no canto inferior direito; ele tem o valor 0 para a letra B. A remoção remove o pixel em (5,1,2), junto com os diretamente acima e abaixo dele. Ainda faltam quatro pixels para serem contabilizados.
Mas, como mostra o painel direito, a letra E esculpe os pixels restantes de interesse, (5,2,2) (5,3,2), (5,4,2) e (5,5,2). (Isso se deve ao fato de a letra E ter bits iguais a 0 na quarta linha, da coluna 2 à coluna 5.) Como resultado, nenhum pixel permanece entre os necessários para garantir a sombra no ponto (5). , 2) na parede oposta (para a letra G). Em vez disso, haverá um ponto brilhante correspondente a um buraco na letra G! O cubo BGE não é bom porque renderiza incorretamente G.
Golfe 423 caracteres
A função
h
teve o mesmo papel quevalidQ
no código não-Golped. A função de renderização,,perspective
não está incluída porque não contribui para o desafio e não é exigida por ele.fonte
Prolog,
440, 414O programa é chamado assim:
Prolog
parecia ser uma boa escolha, pois é fácil representar o problema na lógica de primeira ordem. TambémProlog
fornece funcionalidade potente para resolver esse tipo de problema.No entanto, como o código é golfado, acho que devo adicionar alguma explicação.
Versão levemente golfe
As coordenadas correspondentes aos pixels em cada lado dos dados podem ser facilmente convertidas em um sistema de coordenadas 3D. Eu uso
T
,L
eR
para cima (1), à esquerda (2) e lateral direita (3).u
ev
são usados para as coordenadas nas imagens:(u,v) -> (4-v, ?, u)
(u,v) -> (?, v, u)
(u,v) -> (u, v, ?)
Os resultados para cada pixel ativo (ou seja, preto) são combinados com um conjunto de "pixels 3D" que podem ser ativados sem alterar a aparência do objeto desse lado. A interseção dos conjuntos para cada lado é composta por pixels 3D, que podem ser ativados sem a adição de pixels, que obstruiriam a visualização (ou seja, olhando de pelo menos um lado, haveria um pixel que não deveria estar lá).
Tudo o que resta é verificar para cada lado, se há um pixel na interseção que bloqueia a visualização, onde é necessário.
Isso leva aos predicados do programa:
c : verifica o pixel na imagem de uma letra. A cadeia de caracteres pode parecer um pouco estranha, mas é apenas uma maneira compacta de armazenar os dados da imagem. É simplesmente uma sequência de caracteres com os seguintes valores (notação hexadecimal):
Cada um desses caracteres armazena os dados de 3 linhas de pixel na (s) imagem (s) da letra (= 15 pixels). Os pixels também são reordenados para que os dados sejam armazenados em um local e não divididos em várias linhas, como os dados do OP.
Formulação matemática
Dados de entrada
Conversão de pixel em um caractere para o conjunto de pixels 3D que obstruem a visualização desse pixel
Pixels que podem ser adicionados com segurança (sem obstruir a exibição no lugar errado)
Verifica para cada lado, se os pixels que precisam ser obstruídos podem ser obstruídos com segurança
Combinação de verificações para cada lado
fonte
J -
223197191 carvãoUma função que usa uma lista de três caracteres como argumento.
Esse golfe depende muito de um recurso poderoso de J chamado rank , que nos dá as operações de "esculpir" e "assistir" das operações quase de graça. Para simplificar um pouco, a classificação se refere à dimensionalidade de um substantivo ou dos argumentos naturais de um verbo.
J possui matrizes multidimensionais e é óbvio que, digamos, uma matriz 3D pode ser interpretada como uma única matriz 3D, ou como uma lista de matrizes, ou uma matriz 2D de vetores, ou uma matriz 3D de escalares. Portanto, toda operação em J pode ter sua aplicação controlada, através de como se espalhar sobre o argumento. A classificação 0 significa aplicar nos escalares, a classificação 1 significa aplicar nos vetores e assim por diante.
Isso se torna muito poderoso quando você introduz funções diádicas (dois argumentos), porque se as formas dos dois argumentos (após contabilizar a classificação) são agradáveis, J fará alguns ciclos implícitos:
Quando todas as suas formas são agradáveis e você mesmo pode especificar a classificação, existem várias maneiras de combinar argumentos. Aqui, mostramos algumas das maneiras pelas quais você pode multiplicar uma matriz 2D e uma matriz 3D.
Você notará que isso não está realmente gravado nas letras na orientação solicitada, apenas as escreve, mas é conveniente para a lógica de classificação. A menos que revertamos ou rotacionemos as letras antes de aplicá-las, elas não funcionarão corretamente. Mas corrigir coisas assim ocuparia caracteres preciosos; portanto, codificaremos as letras de modo que, quando J as esculpir naturalmente, algumas faces triplas estarão nas orientações corretas e nas posições relativas. Acontece que a solução mais curta é girar todas as formas de letras um quarto de volta no sentido anti-horário. Considerando a terceira dimensão de J para representar o eixo da frente para trás, o diagrama bruto abaixo mostra por que esse esquema funciona.
Figura A: Os três lados do cubo em que J esculpe. Figura B: Os três lados que têm as letras orientadas como a pergunta.
Essa opção de codificação salva 12 caracteres em relação ao método anterior e torna a coisa toda mais organizada. O golfe real cria o cubo a partir do
"1
e"2
esculpe com alguma lógica descolada, devido a uma otimização não relacionada.Então temos que verificar os rostos. Desde que codificar o bloco como 1s e 0s, podemos simplesmente somar ao longo de cada eixo da maneira que queremos (estes são a
+/"1
,+/"2
e,+/
bits), ajuste a booleans (0<
), e depois compará-los todos diretamente para o original 90 ° - virou letras.O esquema de compactação codifica cada linha de 5px de cada letra como a representação base 32 de um número binário. Ao explorar vários açúcares sintáticos e sobrecargas do operador,
".'1b',"#:
é a maneira mais curta de transformar a lista de caracteres em números de base 36. Bem, tecnicamente, a base 32, mas J acha que é unário, então quem está contando?O uso está abaixo. Observe que cadeias de caracteres são matrizes de caracteres em J; portanto, uma lista de três itens
'A','B','C'
pode ser escrita'ABC'
para abreviar. Além disso, os booleanos são 1/0.fonte
Pitão,
687682671Ligue para
v
:Tudo abaixo é da minha versão ungolfed anterior, que inclui funções úteis de desenho. Sinta-se livre para usá-lo como um ponto de partida.
Ligue
valid
para executá-lo:No momento, o código está configurado para testar a validade
B E G
e imprimir as faces resultantes:Ao executá-lo
B G E
, podemos ver que o G está incorreto:fonte
g=[[0 for j in s]for i in s]
pode ser reduzido parag=map(list,[[0]*5]*5)
. Além disso, você pode evitar o recuo blocos se eles são uma única instrução:if c[e]:g[e[a]][e[a-2]]=1
.Python 3 + numpy, 327C
Esta solução de golfe precisa de uma biblioteca externa, numpy, que é bastante popular, então eu acho que é bom usá-la.
A string unicode está em 41 caracteres, enquanto a mesma coisa na resposta do prólogo do @ fabian é 44.
O mais interessante aqui é que a indexação da matriz numpy. In
a[ix]
,ix
pode ser uma matriz booleana com a mesma forma quea
. É o mesmo que dizera[i, j, k] where ix[i, j, k] == True
.Versão Ungolfed
Script para compactar tabela
fonte