Tips for golfing in Befunge

12

1

What general tips do you have for golfing in Befunge? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Befunge (e.g. "remove comments" is not an answer). Please post one tip per answer.

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

6

We've had a recent Befunge 93 topic, but I think it'd be better to generalise this topic instead. Would that be okay? (and maybe mark which tips are good for which version/s, in the same way that Python tips say whether or not they're Python 2/Python 3 specific)

– Sp3000 – 2015-05-09T19:15:01.857

I'm unsure if this should be changed to Befunge in general, but Befunge 93 is much less ideal for golfing than 98. – Justin – 2013-12-20T07:46:43.167

Answers

9

When using a multi-line loop, try to use as much of it as possible:

>1234....v
^        <

vs

>1234v
^....<

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

7

Need to drop a value after a conditional (e.g. because the other path depends on the value, but this one doesn't)? Instead of using >$ or $<, take advatage of the fact that you know the truth value of the variable and use _ instead to both change direction and pop stack.

Example

'* : v           >$ .. @          Prints number in binary followed by the original
                                  decimal number.
     > :2%\2/ :!#^_ \.

gets turned into

'* : v           _  .. @          Since we know that the topmost value on the stack
                                  will be 0, we combine `>$` into `_`.
     > :2%\2/ :!#^_ \.

FireFly

Posted 2013-12-20T07:44:48.267

Reputation: 7 107

6

Don't forget that 0 is always on the stack. For example, this means that, with an empty stack, g is equivalent to 00g and p is equivalent to 000p.

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

5

If you need to push a number larger than 15, use ' to fetch the ASCII value of the next character:

'*

to push 42 rather than:

4a*2+

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

Or, 67* works too – Doorknob – 2013-12-20T16:19:14.370

4@Doorknob Maybe I should have chosen a prime number to get my point across clearer, but 42 is such a great number. – Justin – 2013-12-20T21:42:17.630

2Note that this tip only applies to Befunge-96 and later. Befunge-93 did not support the ' instruction. – James Holderness – 2018-01-07T20:16:10.167

4

In Befunge-93, if the first thing you're pushing onto the stack is a string, you can often get away with dropping the opening quote. For example this:

"!iH",,,@

could be simplified to this:

!iH",,,@

Try it online!

What's happening is the interpreter first tries to execute the characters in the unquoted string. The ! performs a harmless not, and the i and H are not valid instructions, so they're ignored (although on some implementations you may get a warning).

When the " is encountered, that is considered the start of the string, but because there is no closing quote, it wraps all the way around the playfield until the " is encountered a second time. What ends up pushed onto the stack is then this:

,,,@  ···72 spaces···  !iH

Since we only care about the last few characters, though, none of that other stuff matters. So after the quote, we then finally get to execute the three , commands, writing out the message, and the @ command, which exits.

Note that this won't typically work in Befunge-98, since an unrecognised instruction will cause the interpreter to reflect instead of ignoring it.

James Holderness

Posted 2013-12-20T07:44:48.267

Reputation: 8 298

In Befunge-98 you can instead put the required string at the end of the line, like so; ",,,@!iH. Note that Pyfunge adds an extra space, while FBBI doesn’t. – Jo King – 2018-01-10T04:01:02.643

@JoKing I didn't want to suggest that, because, as you pointed out, the behaviour differs from one interpreter to the next. And even when it seems to work, it's inconsistent (note the extra space in FBBI in this case), so it's quite possibly a bug that may end up being fixed at some point.

– James Holderness – 2018-01-10T09:18:15.330

Hmm... I think the space might actually be part of the specification. I remember reading somewhere that multiple spaces will be skipped and counted as a single space. Example in both PyFunge and FBBI. FBBI seems to pad each line to the length of the longest line while PyFunge adds the extra spaces implicitly.

– Jo King – 2018-01-10T11:35:20.100

You're right - the spec does say that multiple spaces in a string should be treated as a single space. In fact that rule was specifically proposed to deal with the problem of wrapping strings in an infinite playfield (so PyFunge is clearly correct AFAIC). But the spec's description of the wrapping algorithm is somewhat open to interpretation, so I can understand why some implementations might do things differently. But the bottom line is this is a fairly complicated issue, and I think it would be better covered as a separate tip specific to Befunge-97/98. – James Holderness – 2018-01-10T21:37:03.340

4

In Befunge-93, it can often be advantageous to flatten a loop into a single line, with the loop section of code being executed in both directions.

For example, consider the code below, which outputs the letter a eight times:

"a"9>1-:#v_@
    ^\,:\<

This can flatten be flattened into a single line by interspersing the loop sequence with bridge instructions (#):

"a"9>1#\-#,:#:>#\_@

Try it online!

If you're just looking at the non-whitespace characters, you may get the impression that this is longer than the the original. But once you take into account the linefeed and the additional padding required in the two line version, you actually end up saving four bytes.

In this particular case, the code be compressed even further by noting that that sequence :#: can simply be replaced with :.

"a"9>1#\-#,:>#\_@

Try it online!

In fact, any time you have the same instruction repeated on either side of a # command, you can simplify that to just the one instruction, so this is something you should always be looking out for when flattening a loop.

To understand how this works, it can help to write out the loop sequence twice, once with all the characters following the # removed (i.e. what happens when executing left to right), and once with the characters preceding the # removed (i.e. executing right to left).

"a"9>1#\-#,:>#\_@
    >1  -  :>  _      ; executing left to right
    >  \  ,:  \_      ; executing right to left

You can clearly see now how this matches the original two line version of the code.

James Holderness

Posted 2013-12-20T07:44:48.267

Reputation: 8 298

4

Instead of using |, requiring another line (often with many extra spaces), try using j. For example:

01-`j@more code here

would stop if the number on top of the stack was negative and continue onward otherwise. If you need multiple characters, use n*j where n is the number of characters you need when the value passed to j is 0. Example:

01-`4*j01-*more code

which would negate a negative number.

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

Note that this tip only applies to Befunge-96 and later. Befunge-93 did not support the j instruction. – James Holderness – 2018-01-07T20:16:49.613

3

Output by exit code, where this is an allowed output form. If the challenge asks you to print one number, you can save a byte by ending the program with q instead of .@

pppery

Posted 2013-12-20T07:44:48.267

Reputation: 3 987

2Note that this tip only applies to Befunge-98 and later. In earlier versions of Befunge the q instruction had a different function (queue mode) or was not supported. – James Holderness – 2018-01-07T20:18:29.507

3

In Befunge-93, the character input command (~) can often be used as a shortcut for -1, since that is the value it returns on EOF.

As an example, the code below will output -1:

~.@

Try it online!

This is not recommended in production code, since when run in an interactive environment, the program would pause and wait for user input. And obviously if the user were to input something, the result would no longer be -1.

That said, the rule on PPCG is that a program may assume an empty input stream, and that's how it would typically be run on TIO.

Also note that you aren't necessarily precluded from using this trick just because your program needs to read something from the input stream. You just have to make sure you process your inputs up front, after which all future uses of ~ should return -1.

James Holderness

Posted 2013-12-20T07:44:48.267

Reputation: 8 298

2

Use the direction of the IP when dealing with _ or |, rather than using an extra character for !.

Real example (from this post):

#v~
,>:!#@_

Can be changed to

#v~
:<,_@#

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

2

Don't forget that 0k does not execute the next instruction. This means that instead of doing:

;some boolean test;!jv;code if false;
       ;code if true;<

You can save a character by doing

;some boolean test;kv;code if false;
      ;code if true;<

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

Note that this tip only applies to Befunge-98 and later. Earlier versions of Befunge did not support the k instruction. – James Holderness – 2018-01-07T20:19:46.820

1

When pushing small numbers onto the stack, you can probably figure out easily enough that 45* will get you 20, and 67* will get you 42. When it comes to larger numbers, though, you really need a program that can calculate the most efficient representation for you.

The easiest option for this is Mike Schwörer's online interface for BefunRep. You simply type in a number and it'll spit out an equivalent Befunge representation. It's not always the most optimal, but it's close enough, and it's almost certain to be better than anything you could come up with by hand.

The online system is limited to numbers in the range 0 to 16777215, so if you need anything larger than that, you'll want to download the standalone BefunRep utility and run the calculations yourself.

If you're programming in Befunge-98, another option to consider is Fungify. In general it isn't nearly as optimal as BefunRep, but for some of the lower numbers, where hex digits and single quote characters are most effective, it can sometimes produce better results.

James Holderness

Posted 2013-12-20T07:44:48.267

Reputation: 8 298

When pushing small numbers in Befunge 98, you'd use '. E.g. for 42: '* – Justin – 2017-11-29T04:29:12.050

@Justin I mentioned that in the last paragraph, but the whole point of this tip is you don't need to know a whole lot of these tricks for generating numbers if you just use a tool to do it for you. – James Holderness – 2017-11-29T10:57:51.983

1

Don't forget about the k operator. Instead of "!dlroW olleH",,,,,,,,,,,,@, do "!dlroW olleH"bk,@. Note that k does the operation on the cell that it is at so 9k, would print not 9 times but 10; 9 times with the k, and once with ,.

Justin

Posted 2013-12-20T07:44:48.267

Reputation: 19 757

1Note that this tip only applies to Befunge-98 and later. Earlier versions of Befunge did not support the k instruction. – James Holderness – 2018-01-07T20:19:12.693