Compactez un programme Befunge

17

Befunge est un langage de programmation ésotérique bidimensionnel. L'idée de base est que les commandes (à un caractère) sont placées sur une grille à deux dimensions. Le flux de contrôle parcourt la grille, exécute les commandes qu'il passe et change de direction lorsqu'il frappe une flèche ( >^<v). Les commandes sont basées sur la pile; voir cette liste . Voir aussi http://esolangs.org/wiki/Befunge .

La spécification pour Befunge-98 est disponible.

Problème

Écrivez un programme qui transforme un programme Befunge en une représentation plus compacte. Par exemple, le programme suivant s'imprime 0:

>   0   v

>   @   .

^       <

Dans ce cas, il pourrait être compacté sans changer le comportement du programme en supprimant des rangées d'espaces, pour donner

>0v
>@.
^ <

Des transformations plus sophistiquées pourraient faire pivoter ou refléter des séquences de commandes et éliminer les commandes de flux de contrôle inutiles afin de compacter le programme. Par exemple, avec ce programme:

>12345v
      6
v....7<
.
.
.
@

vous pourriez rentrer la fin du programme dans le trou:

>12345v
>...@ 6
^....7<

Pour le premier exemple, le programme le plus compact possible est

>0.@

Vous pouvez utiliser toutes les transformations tant que le programme de sortie donne le même résultat.

Programmes d'entrée

Les programmes d'entrée sont des programmes Befunge-98 valides.

Vous pouvez supposer que le programme d'entrée est déterministe. Autrement dit, il n'utilise pas de commandes qui lisent l'état externe: les commandes d'entrée utilisateur &et ~, le randomiseur ?et les commandes de code auto-modifiables pet g.

Vous pouvez supposer que le programme d'entrée se termine.

Notation

Ce n'est pas un golf de code, mais un problème pour écrire un programme qui exécute le golf de code.

L'entrée est un ensemble de cas de test (programmes Befunge qui satisfont aux restrictions d'entrée ci-dessus). Le score total est la somme des scores des cas de test.

Score pour chaque cas de test

Le score est l'aire de la coque convexe des cellules non vides du programme de sortie, où chaque cellule est traitée comme un carré dont les quatre coins sont des points de réseau dans le plan cartésien. Par exemple, un programme de

>   v
 @  <

obtient un score de 9,5.

Si votre programme ne se termine pas dans une quantité raisonnable de temps et de mémoire sur une entrée particulière, le score est celui du programme d'entrée. (Cela est dû au fait que vous pourriez ajouter trivialement un wrapper de limitation de temps qui génère le programme d'entrée inchangé si votre programme ne se termine pas à temps.)

Si le programme de test élémentaire a un résultat différent (ou ne se termine pas) après le traitement avec votre programme, le score est le score du programme d'entrée plus une pénalité de 100 points.

Escargot mécanique
la source
8
Qu'est-ce qui empêche d'exécuter le programme jusqu'à son terme et d'écrire un programme Befunge qui imprime la même sortie?
Keith Randall
5
Est-ce que "get" et "put" sont autorisés? Si vous autorisez "put" (code auto-modifiable), il sera difficile de faire quoi que ce soit.
Keith Randall
2
D'où commence l'exécution? En haut à gauche? Si oui, pouvez-vous expliquer la sortie du 2ème exemple? .signifie un entier de sortie, mais si vous commencez en haut à gauche, il n'y a pas d'entier dans la pile à sortir.
elssar
1
@elssar yes, génère .un entier. Mais aussi, quand il n'y a pas assez de paramètres sur la pile, befunge prétend qu'il y a une quantité suffisante de zéros à la place. Ainsi, le deuxième exemple sortirait 000.
daniero
@KeithRandall: L'écriture d'un nouveau programme avec la même sortie ne fonctionne que pour les programmes avec une sortie courte. get pne sont pas autorisés (désolé, oubliés; modifiés).
Escargot mécanique

Réponses:

12

J'ai passé un long trajet en avion à coder celui-ci. J'ai écrit un pseudo compilateur befunge qui exécute le programme befunge, extrait les blocs de base et les présente dans une représentation compacte.

Lien vers le programme .

Lorsqu'il est exécuté sur ce programme de 99 bouteilles:

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<
                    ,:
                    ^_ $$ @

Il génère la sortie suivante:

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#     <
    >$$@    

En fait, il n'est pas beaucoup plus compact que la source, mais il fera probablement mieux sur des programmes plus grands / plus clairsemés.

Le programme est présenté avec une zone de routage à gauche et le contenu du bloc de base à droite. Un bloc de base est généralement disposé sur un nombre pair de rangées de sorte que l'entrée et la sortie jouxtent la zone de routage. À la fin de chaque bloc de base, le gadget #^_vet les variantes, disposés de droite à gauche, effectuent la branche conditionnelle et acheminent le flux en colonnes. Au début de chaque bloc de base, ces colonnes sont acheminées dans les lignes du bloc de base de destination.

De plus, si la sortie est courte, elle génère simplement la sortie explicitement, comme ceci:

"output">:#,_@

Je n'ai rien fait pour optimiser les blocs de base eux-mêmes, juste la mise en page. Faire.

Alors où sont les tests?

Keith Randall
la source
1
le lien du code source semble être de 500 en ce moment. Mauvaise configuration du serveur?
John Dvorak
1
@JanDvorak: en effet. Fixé.
Keith Randall
1

Sed, 5 caractères

Donc, même s'il ne s'agit pas de codegolf, voici une solution qui aura un assez bon rapport longueur de code / score, mais pas nécessairement un bon score.

/^$/d

Il supprime simplement les lignes vides.

daniero
la source
10
Votre code n'est pas correct! Vous ne pouvez pas simplement supprimer des lignes vides. Je ne peux pas écrire de code 2D en commentaire. Mais considérons un cas où la direction est vers le bas et une chaîne constante est lancée ( "). Chaque ligne vierge doit être traitée comme un espace. Si nous imprimons cette chaîne, le code que vous avez généré n'a pas ces espaces en sortie!
saeedn
3
Regardez le code dans ideone.com/BdcRcf Il devrait s'imprimer b a. Mais après votre raccourcissement, il s'imprimera ba.
saeedn