Compact a Befunge program

Question

Befunge is a 2-dimensional esoteric programming language. The basic idea is that (one-character) commands are placed on a 2-dimensional grid. Control flow walks across the grid, executing commands it passes over, and changing direction when it hits an arrow (>^<v). Commands are stack-based; see this list. See also http://esolangs.org/wiki/Befunge.

The specification for Befunge-98 is available.

Problem

Write a program that transforms a Befunge program into a more compact representation. For example, the following program prints 0:

>   0   v

>   @   .

^       <

In this case, it could be compacted without changing the program's behavior by removing rows of spaces, to give

>0v
>@.
^ <

More sophisticated transformations could rotate or mirror sequences of commands and eliminate unnecessary control-flow commands in order to compact the program. For example, with this program:

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

you might tuck the end of the program into the hole:

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

For the first example, the most compact program possible is

>0.@

You may use any transformations as long as the output program gives the same result.

Input programs

Input programs are valid Befunge-98 programs.

You may assume that the input program is deterministic. That is, it does not use commands that read external state: the user input commands & and ~, the randomizer ?, and the self-modifying code commands p and g.

You may assume the input program terminates.

Scoring

This is not a code golf, but a problem to write a program that performs code golfing.

The input is a set of test cases (Befunge programs that satisfy the input restrictions above). The total score is the sum of the scores for the test cases.

Score for each test case

The score is the area of the convex hull of the non-empty cells in the output program, where each cell is treated as a square whose four corners are lattice points in the Cartesian plane. For example, a program of

>   v
 @  <

gets a score of 9.5.

If your program does not terminate in a reasonable amount of time and memory on a particular input, the score is that of the input program. (This is because you could trivially add a time-limiting wrapper that outputs the input program unchanged if your program doesn't terminate in time.)

If the test-case program has a different result (or fails to terminate) after processing with your program, the score is the score of the input program plus a penalty of 100 points.

Answer 1

I spent a long plane ride coding this one up. I've written a pseudo befunge compiler which runs the befunge program, extracts basic blocks, and lays them out in a compact representation.

Link to the program.

When run on this 99 bottles program:

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

It generates the following output:

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

It actually isn't much more compact than the source, but it will probably do better on larger/sparser programs.

The program is laid out with a routing area on the left and basic block contents on the right. A basic block is usually laid out in an even number of rows so the entrance and exit adjoin the routing area. At the end of each basic block, the gadget #^_v and variants, laid out right-to-left, do the conditional branch and route flow into columns. At the start of each basic block, these columns are routed into the rows for the destination basic block.

In addition, if the output is short it just generates the output explicitly, like this:

"output">:#,_@

I haven't done anything to optimize the basic blocks themselves, just the layout. Todo.

So where are the tests?

Answer 2

Sed, 5 chars

So, even if this is not codegolf, here's a solution that will have a rather good codelength to score ratio, but not necessarily a good score.

/^$/d

It simply removes blank lines.