Befunge é uma linguagem de programação esotérica bidimensional. A idéia básica é que os comandos (de um caracter) sejam colocados em uma grade bidimensional. O fluxo de controle percorre a grade, executando comandos pelos quais passa e mudando de direção quando bate em uma seta ( >^<v
). Os comandos são baseados em pilha; veja esta lista . Veja também http://esolangs.org/wiki/Befunge .
A especificação para Befunge-98 está disponível.
Problema
Escreva um programa que transforma um programa Befunge em uma representação mais compacta. Por exemplo, o seguinte programa é impresso 0
:
> 0 v
> @ .
^ <
Nesse caso, ele pode ser compactado sem alterar o comportamento do programa, removendo linhas de espaços, para fornecer
>0v
>@.
^ <
Transformações mais sofisticadas poderiam girar ou espelhar seqüências de comandos e eliminar comandos desnecessários de fluxo de controle para compactar o programa. Por exemplo, com este programa:
>12345v
6
v....7<
.
.
.
@
você pode colocar o final do programa no buraco:
>12345v
>...@ 6
^....7<
Para o primeiro exemplo, o programa mais compacto possível é
>0.@
Você pode usar qualquer transformação, desde que o programa de saída dê o mesmo resultado.
Programas de entrada
Programas de entrada são programas válidos do Befunge-98.
Você pode assumir que o programa de entrada é determinístico. Ou seja, ele não usa comandos que leem o estado externo: os comandos de entrada do usuário &
e ~
, o randomizador ?
e o código de modificação automática p
e g
.
Você pode assumir que o programa de entrada termina.
Pontuação
Este não é um código de golfe, mas um problema para escrever um programa que execute código de golfe.
A entrada é um conjunto de casos de teste (programas Befunge que atendem às restrições de entrada acima). A pontuação total é a soma das pontuações para os casos de teste.
Pontuação para cada caso de teste
A pontuação é a área do casco convexo das células não vazias no programa de saída, onde cada célula é tratada como um quadrado cujos quatro cantos são pontos de treliça no plano cartesiano. Por exemplo, um programa de
> v
@ <
obtém uma pontuação de 9,5.
Se o seu programa não terminar em uma quantidade razoável de tempo e memória em uma entrada específica, a pontuação será a do programa de entrada. (Isso ocorre porque você pode adicionar trivialmente um invólucro com limite de tempo que gera o programa de entrada inalterado se o programa não terminar a tempo).
Se o programa de caso de teste tiver um resultado diferente (ou falhar ao finalizar) após o processamento com o programa, a pontuação será a pontuação do programa de entrada mais uma penalidade de 100 pontos.
fonte
.
significa número inteiro de saída, mas se você começar do canto superior esquerdo, não haverá um número inteiro na pilha para saída..
gera um número inteiro. Mas também, quando não há parâmetros suficientes na pilha, o befunge finge que há uma quantidade suficiente de zeros lá. Portanto, o segundo exemplo seria exibido000
.g
ep
não são permitidos (desculpe, esqueci-os; editados).Respostas:
Passei uma longa viagem de avião codificando este. Eu escrevi um compilador pseudo-befunge que executa o programa befunge, extrai blocos básicos e os expõe em uma representação compacta.
Link para o programa .
Quando executado neste programa de 99 garrafas:
Ele gera a seguinte saída:
Na verdade, não é muito mais compacto que a fonte, mas provavelmente será melhor em programas maiores / mais esparsos.
O programa é apresentado com uma área de roteamento à esquerda e o conteúdo básico do bloco à direita. Um bloco básico é geralmente disposto em um número par de linhas, de modo que a entrada e a saída sejam adjacentes à área de roteamento. No final de cada bloco básico, o gadget
#^_v
e as variantes, dispostos da direita para a esquerda, executam a ramificação condicional e direcionam o fluxo para as colunas. No início de cada bloco básico, essas colunas são roteadas para as linhas do bloco básico de destino.Além disso, se a saída é curta, ela gera a saída explicitamente, assim:
Não fiz nada para otimizar os blocos básicos, apenas o layout. Façam.
Então, onde estão os testes?
fonte
Sed, 5 caracteres
Portanto, mesmo que isso não seja um codegolf, aqui está uma solução que terá uma boa relação comprimento de código para pontuação, mas não necessariamente uma boa pontuação.
Ele simplesmente remove as linhas em branco.
fonte
"
). Cada linha em branco no caminho deve ser tratada como um caractere de espaço. Se imprimirmos essa string, o código que você gerou não terá esses espaços na saída!b a
. Mas após o seu encurtamento, ele será impressoba
.