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.
Write a program that transforms a Befunge program into a more compact representation. For example, the following program prints
> 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
You may use any transformations as long as the output program gives the same result.
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
~, the randomizer
?, and the self-modifying code commands
You may assume the input program terminates.
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.