Compact a Befunge program
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  &lt;
&gt;v"bottles of beer on the wall"+910&lt;
,:
^_ $                             :.v
            &gt;v"bottles of beer"+910&lt;
            ,:
            ^_ $                     v
&gt;v"Take one down, pass it around"+910&lt;
,:
^_ $                           1-v
                                 :
        &gt;v"bottles of beer"+910.:_          v
        ,:
        ^_ $                          ^
                    &gt;v" no more beer..."+910&lt;
                    ,:
                    ^_ $$ @


It generates the following output:

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


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"&gt;:#,_@


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

So where are the tests?