Compact a Befunge program

17

2

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.

Mechanical snail

Posted 2013-01-01T23:39:53.280

Reputation: 2 213

8What's to prevent running the program to completion and writing a Befunge program that prints the same output? – Keith Randall – 2013-01-02T04:04:09.027

5Are "get" and "put" allowed? If you allow "put" (self-modifying code), it will be hard to do anything. – Keith Randall – 2013-01-02T04:07:45.963

2Where does the execution begin from? Top left corner? If so, can you explain the output of the 2nd example? . means output integer, but if you start from the top left, then there is not integer in the stack to output. – elssar – 2013-01-03T13:30:51.317

1@elssar yes, . outputs an integer. But also, when there isn't enough parameters on the stack, befunge pretends there is a sufficient amount of zeroes there instead. So the second example would output 000. – daniero – 2013-01-04T21:20:09.327

@KeithRandall: Writing a new program with the same output works only for programs with a short output. g and p are not allowed (sorry, forgot about those; edited). – Mechanical snail – 2013-01-07T05:37:52.663

@elssar: That was a typo; I meant the arrow to go to the right. Daniero explained correctly what was written. – Mechanical snail – 2013-01-07T05:38:38.230

@Mechanicalsnail oh, okay. Also, please edit the question and correct the typo – elssar – 2013-01-07T05:54:10.940

@elssar: Fixed. I thought I had fixed it a while ago, but apparently not. – Mechanical snail – 2013-02-07T09:04:41.803

is = (eval) to be allowed? It's hard to do any stack optimisations in presence of this instruction. () (load/unload semantics) is also problematic in this sense. Should we treat them as black boxes that don't overwrite the code? – John Dvorak – 2013-07-07T15:53:32.443

also, the jump instruction (pop a number and jump that many instructions) is truly lethal to any optimisation – John Dvorak – 2013-07-07T16:11:27.083

@JanDvorak: I did Befunge 93 - gp?&~. You're crazy to try Befunge 98 (nastiness abounds in many instructions, including =jk{}()). – Keith Randall – 2013-07-12T04:19:04.693

@KeithRandall supporting jk() is easy: any time I encounter one of ()=gijopsxy, I run away in terror. I will probably treat {}k as stack-blackboxes, which taint ("mess with horriby") the stack, but can still be layouted. ()=gijopsxy break layouting. I might add support for jkx with a constant argument, however, and y really only taints the stack, not layouting. My code is far from done, however – John Dvorak – 2013-07-12T05:40:03.933

Answers

12

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?

Keith Randall

Posted 2013-01-01T23:39:53.280

Reputation: 19 865

1the source code link seems to be 500 right now. Server misconfiguration? – John Dvorak – 2013-07-12T05:05:01.860

1@JanDvorak: indeed. Fixed. – Keith Randall – 2013-07-12T05:21:51.010

1

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.

daniero

Posted 2013-01-01T23:39:53.280

Reputation: 17 193

10Your code is not correct! You can not simply remove blank lines. I can not write a 2d code in comment. But consider a case that direction is toward down, and a constant string is started ("). Every blank line in the way should be treated as a space character. If we print out that string, the code you generated does not have that spaces in output! – saeedn – 2013-02-22T05:51:50.497

3

Look at the code in http://ideone.com/BdcRcf It should print b a. But after your shortening, it will print ba.

– saeedn – 2013-02-22T06:05:51.110