Nickolas's blog

By Nickolas, 13 years ago, translation, In English

So here goes an editorial for the round. For me Befunge is one of the languages in which it's much easier to write code than to read it (and debugging code written by someone else is a complete torture; that's why we don't have hacking in ULRs). That's why I'll post just the general idea of the solution and my own codes — the latter just to show that I can code in Befunge too.

A. Hexagonal numbers

&:2*1-*.@

A "consolation" problem, which requires only to understand the principles of working with stack. Read n, duplicate it, multiply the topmost copy by 2 and decrement the result. Now the stack contains two numbers n and 2n - 1; multiply them and print the result.

B. Gnikool Ssalg

> ~ : 25*- #v_ $ >:#,_ @
^           <

Here the easiest solution is to use the main stack property — elements are popped in reverse order compared to the order in which they were pushed. You can break the solution in two loops — in the first one you read input data till the end of line (#10) and keep the characters on the stack, and in the second one you print stack elements as long as it's not empty. To run a loop (as well as to do any conditional branching) one has to use commands _ and |, but remember that they delete from the stack the element they use to make a choice, so if you're going to need it later, duplicate it.

C. Decimal sum

0 &>: #v_ $. @
       >1- \ & + \v
   ^              <

A one-loop problem which requires tracking the current contents of the stack carefully. At the start of each loop iteration the stack contains two elements: the current sum (initialized with zero) and the quantity of numbers you still have to add (initialized by reading input). If the latter is non-zero, the instruction pointer goes into the loop body (second line of the program). There we decrement the counter and swap it with the current sum. After this we read the current number and add it to the sum. Finally we swap the top two elements of the stack again — and we're ready for the next iteration.

It was also possible to use a memory cell to store the loop counter, but I think it's an unnecessary over-complication.

D. Exponentiation

&30p & &32p 1 \ >:#v_ $. 25*, @
                   >1- \ 30g * 32g % \v
                ^                     <

The task becomes more complicated: this time on each iteration you have to juggle more than two numbers, so the stack alone is not enough — unlike some other stack-based languages, Befunge has no commands which allow access to stack elements buried deeper than top two positions. We'll have to use "memory" — program cells not occupied by useful commands. Commands p and g are meant for writing self-modifying code, but Befunge has no regular random-access memory, so one has to use whatever it has.

Usage of memory simplifies things: write a and c into memory, keep b on the stack as loop counter, and keep the current value of the power on the stack as well. In the loop body the required values are extracted from memory as needed, so that the stack doesn't get littered.

E. Tribonacci numbers

031p032p133p & > 31g 32g + 33g + 39*1-% 32g 31p 33g 32p 33p v
               | :-1                                        <
               > 31g . 25*,@

The same principle as in the previous problem, but a bit more memory manipulation; handle with care.

F. Prime factorization

& 211p > : 1 - #v_ 25*, @ > 11g:. /    v
                > : 11g %!|
                          > 11g 1+ 11p v
       ^                               <

Forget whatever code you write lightning-fast on any regular contest :-) and recall how you solved this a long time ago. The number itself is small enough, so you can check divisors up to n instead of sqrt(n). If you divide the number by the divisor you find, you're fine with not skipping composite divisors — they won't divide the number anyways. Finally, if a divisor is found, you don't have to find its degree immediately — it's enough not to increment it during this iteration, and you'll find it again on the next one. Keep n on the stack, store the current divisor in memory and perform actions in each branch carefully, and the problem will be solved.

G. CAPS LOCK ON

> ~ : 25*- #v_ 25* , @         >48*-v
            > :: "`"` \"{"\` * |    > , v
                               >    ^
^                                       <

This problem is very similar to CamelCase example from the given article about Befunge. It was even easier — you needn't care about the type of the previous character. The most complicated thing about it might be learning "greater than" operation and applying it to correct values.

H. Balanced brackets

v                > "ON" ,,   v
> ~ : 25*- #v_ $ |           > 25*, @
                 > "SEY" ,,, ^
            > : 58*- #v_ v
                      > \ : 58*- #v_v
                                  \ $
^                        <        <$<

Originally I intended to give strings which had three types of brackets in them, but by the time I've implemented the check for only one type, I realized that it was a pretty bad idea. Even with one type of brackets you have enough trouble implementing the check. There are two possible ways to solve the problem: store the opening brackets themselves on the stack (with several types of brackets it would be the only option) or store only the quantity of opening brackets which are not closed yet. The answer is "NO" in two cases: if the current bracket is closing and you have no opening brackets on the stack, or if the input data is over and you still have opening brackets left.

I. Array sorting

v
> 543** >     :#v_ $&>           :#v_ 1 > :0g >    :#v_ $ 1+: 543** `! #v_ 25*,@
        ^-1p0\0:<    ^-1 p0\+1 g0:&<          ^-1\.:\<
                                        ^                               <

Once again, forget about nice things like Arrays.sort() and recall counting sort. Befunge program is sized 25 x 80, the given numbers can vary between 1 and 60, so we can store the quantity of number i in a cell (0, i), if this part of the program (the first line) has no commands we'll need. The program will have three main loops — initializing memory with zeros, reading input and incrementing values in corresponding memory cells, and convering the resulting values into a sorted array.

J. Date calculation

56*1+ :10p :30p :50p :70p :80p :52*0p :62*0p 1- :2-20p :40p :60p :90p 92+0p v
v % *:*45 : &                                                               <
    >                      > 20g 1+ 20p v
> ! |             >         v
    > : 52*:* % ! |
                  > : 4 % !|
v                          <<           <
                         > . 00g . 25*, @
> $100p & > : 00g 0g ` ! |
                         > 00g 0g - 00g 1+ 00p v
          ^                                    <

This is another problem which is very easy in any high-level language and very ugly in Befunge. First of all we initialize some memory cells with quantities of days in months of a regular non-leap year. Next we read the year index, check whether it's leap and if needed change the number of days in February. Finally, we read the day index and in a loop decrement it by the number of days in the current month while incrementing the index of the current month as many times as possible. Just think how easy this problem would have been if our calendar was organized in a more regular way!

  • Vote: I like it
  • +64
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
wow!!!! great language!!! the hardest one ever on these contests!!! however thanks for these attractive contests!
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
It totally beyond my mind,I have never believe a language can be so funny.thanks to this contest.
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Re: Array Sorting: did you intentionally set the input size to 100 to defeat comparison-based implementations? My first instinct was to go with the counting sort too (mainly because I remembered it as the easiest way to implement sorting in Brainfuck) but I think it would have been nice to allow a variety of approaches.

For example, I have a nice solution using Gnome sort that only works with less than 80 elements because that's the number of cells in a single row. It's not very hard to change it to use a rectangular area of the board instead, but that does increase the implementation complexity somewhat. (The advantage of Gnome sort is that it only uses a single array index, which is easily kept on top of the stack.)

On an unrelated note, it's a shame that these Befunge programs are so hard to read, as I'm sure many competitors had quite creative solutions that are doomed to go unappreciated. That being said, I loved competing in an esoteric language for a change (I usually only do that in the CodeJam qualification round), and I regret showing up an hour to late for this (and as a result being unable to finish the last problem).
  • 13 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Not intentionally; I didn't realize anybody would be willing to go for comparison-based sorting, since I wasn't :-)
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    At least your programm passes if there are 80 elements... I don't know why i have tried to implement bubble sort) but it timelimits at 40 elements... While with java interpreter it runs well :) Scripting lanugages are so slow :(
    • 13 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Yes, the timelimit is problematic. If I modify my Gnome sort to work with larger input the added complexity makes it just barely too slow. But insertion sort runs in time (using the first two rows of the grid to store the array).

      For the befungee interpreter, the trick seems to be to make your loops as short as possible, eliminating any spaces, because skipping over whitespace takes times too.

13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
I surprised at this contest ;) Interesting language...Thx for solutions
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
just a note, for problem J you don't have to programmatically write the #days in each month to the source code, because after all, it is the source code so you can that data into your program directly using ascii chars to represent integers in the range 28-31
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Characters with these ASCII-codes are invisible (something-separators), and some Befunge interpreters might not work well with them. I tried to show code which is portable, if this word can be used for Befunge programs :-)
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      the ascii chars could be offset (which can be accounted for by modifying the code); for example the character '0' could represent 28 days, '1' could represent 29, etc.
      but yes you're correct of course.