Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
6  
What's to prevent running the program to completion and writing a Befunge program that prints the same output? –  Keith Randall Jan 2 '13 at 4:04
5  
Are "get" and "put" allowed? If you allow "put" (self-modifying code), it will be hard to do anything. –  Keith Randall Jan 2 '13 at 4:07
2  
Where 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 Jan 3 '13 at 13:30
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 Jan 4 '13 at 21:20
    
@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 Jan 7 '13 at 5:37

2 Answers 2

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?

share|improve this answer
    
the source code link seems to be 500 right now. Server misconfiguration? –  Jan Dvorak Jul 12 '13 at 5:05
    
@JanDvorak: indeed. Fixed. –  Keith Randall Jul 12 '13 at 5:21

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.

share|improve this answer
5  
Your 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 Feb 22 '13 at 5:51
2  
Look at the code in ideone.com/BdcRcf It should print b a. But after your shortening, it will print ba. –  saeedn Feb 22 '13 at 6:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.