Compactar um programa Befunge

17

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 pe 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.

Caracol mecânico
fonte
8
O que impede a execução do programa até a conclusão e a gravação de um programa Befunge que imprime a mesma saída?
precisa saber é o seguinte
5
"Get" e "put" são permitidos? Se você permitir "put" (código auto-modificável), será difícil fazer qualquer coisa.
precisa saber é o seguinte
2
De onde começa a execução? Canto superior esquerdo? Se sim, você pode explicar a saída do segundo exemplo? .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.
elssar
11
@elssar sim, .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 exibido 000.
Daniero
@KeithRandall: Escrever um novo programa com a mesma saída funciona apenas para programas com uma saída curta. ge pnão são permitidos (desculpe, esqueci-os; editados).
Caracol mecânico

Respostas:

12

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:

92+9*                           :. v  <
>v"bottles of beer on the wall"+910<
,:
^_ $                             :.v
            >v"bottles of beer"+910<
            ,:
            ^_ $                     v
>v"Take one down, pass it around"+910<
,:
^_ $                           1-v
                                 :
        >v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    >v" no more beer..."+910<
                    ,:
                    ^_ $$ @

Ele gera a seguinte saída:

92+9*:.019+"llaw eht no "v
v  _v# :"bottles of beer"<
>    ,:    v
^  _v#     <
    >$:.019+"reeb f"v
 v _  v#:"bottles o"<
 >     ,:  v
 ^ _  v#   <
      >$019+"dnuo"v
     v"pass it ar"<
     >" ,nwod eno"v
 v _    v#:"Take "<
 >       ,:v
 ^ _    v# <
        >$1-:v
 v _      v# <
 >         :.019+"reeb "v
  v_  v#   :"bottles of"<
  >        ,v
  ^_  v#   :<
      >    $019+"llaw"v
           v" on the "<
           >"reeb fo "v
^  _^#      :"bottles"<
          >019+"...r"v
v  _v#:" no more bee"<
>    ,:    v
^  _v#     <
    >$$@    

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 #^_ve 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:

"output">:#,_@

Não fiz nada para otimizar os blocos básicos, apenas o layout. Façam.

Então, onde estão os testes?

Keith Randall
fonte
11
o link do código-fonte parece ser 500 no momento. Configuração incorreta do servidor?
John Dvorak
11
@JanDvorak: de fato. Fixo.
Keith Randall
1

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.

/^$/d

Ele simplesmente remove as linhas em branco.

daniero
fonte
10
Seu código não está correto! Você não pode simplesmente remover linhas em branco. Não consigo escrever um código 2D no comentário. Mas considere um caso em que a direção está voltada para baixo e uma sequência constante é iniciada ( "). 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!
Saeedn
3
Veja o código em ideone.com/BdcRcf. Ele deve ser impresso b a. Mas após o seu encurtamento, ele será impresso ba.
Saeedn