### Author Topic: [ENDED] Code Golf Contest #12: Befunge Numbers  (Read 9452 times)

0 Members and 1 Guest are viewing this topic.

#### JWinslow23

• Coder Of Tomorrow
• LV7 Elite (Next: 700)
• Posts: 556
• Rating: +43/-6
• I make quality calculator games...when I have time
##### [ENDED] Code Golf Contest #12: Befunge Numbers
« on: October 05, 2014, 02:04:29 pm »
Time to completely redesign everything.

NEXT: Here
PREVIOUS: Here

Challenge 12: Befunge Numbers

Problem

Say someone (I'm looking at you, harold ) wanted to make a Befunge program for a Code Golf competition that printed a number. In Befunge, arithmetic works in a form of RPN. For example, 34+ pushes a 3, pushes a 4, then adds (in essence, push 7). But to push numbers greater than 9, calculations must be done on numbers less than or equal to 9. For example, 99*76*+ pushes 123.

Your mission, should you choose to accept it, is to make a program that displays an optimal expression for pushing a number (minimum 0, maximum 999,999) onto the Befunge stack using only the numbers, addition (+), and multiplication (*). I shall give test cases when available, but keep in mind, there is more than one solution for any number above 9.

October 12, 2014, 1:00 AM EST

If any further clarification is needed, contact me. I'll try to push you to figure it out.

C#
 Rank User Size Date Code 1 harold 375 10/7/2014 7:53:28 AM Spoiler For Spoiler: using System;namespace B{class P{static void Main(string[]args){int l=int.Parse(args[0])+1,i=0,j,k,x;string[]n=new string[l];for (;i<10;i++)n=""+i;for(;i

C++
 Rank User Size Date Code 1 harold 361 10/7/2014 8:21:25 AM Spoiler For Spoiler: #include using namespace std;#define Z(p,q){k=n[j].length()+n.length()+1;if(k

Golfscript
Rank
User
Size
Date
Code1
harold
140
10/7/2014 7:49:12 AM
Spoiler For Spoiler:
~:l;9,{1+`}%10:x;{x l>}{.[.,,{1+}%]zip.[{~\;.x\%!\1=!*},.{~\;-1*}$]zip{~~;\~;+"*"+}%\[.{~\;-1*}$]zip{~~;\~;+"+"+}%+{,}$[(\;]+1x+:x;}until)\; SysRPL Rank User Size Date Code1 3298 147.5 10/8/2014 11:09:47 AM Spoiler For Spoiler: :: COERCE BINT10 OVER#> case #>$
NULL$SWAP NDUPN BINT10 ONE_DO INDEX@ #>$ INDEX@ #1+UNPICK_
LOOP
#1+' ::
JINDEX@ INDEX@ 'REVAL
'R SWAPROT #0<> case2DROP
#3+PICK INDEX@ #4+PICK
&$SWAP >T$ DUPLEN$JINDEX@ #1+DUP #4+PICK DUPNULL$? 4ROLLROT LEN\$ #<
ORNOT case2DROP #1+UNPICK_
;
OVER BINT10 DO
INDEX@ ONE_DO
ZEROOVER EVAL #- CHR_+
DUP EVAL #/ CHR_*
LOOP
LOOP SWAP#1- NDROP
;

Java
Rank
User
Size
Date
Code1
3298
334
10/8/2014 11:09:47 AM
Spoiler For Spoiler:
class G{static String[]a;static void r(String s,int n){if(a[n]==""||s.length()<a[n].length())a[n]=s;}public static void main(String[]c){int n=Integer.parseInt(c[0]),i=n,j=10;a=new String[n+1];for(;i>=0;--i)a=i>9?"":""+i;for(;j<=n;++j)for(i=1;i<j;++i){r(a[j-i]+a+"+",j);if(j%i==0)r(a[j/i]+a+"*",j);}System.out.println(a[n]);}}

C
Rank
User
Size
Date
Code1
3298
433
10/8/2014 11:09:47 AM
Spoiler For Spoiler:
#include<stdio.h>
#include<malloc.h>
int n,j=10,i,*a;p(int n){if(n<10)printf("%i",n);else{p(a[n=4*n-39]);p(a[n+1]);printf("%c",a[n+2]);}}r(int m,int o){int s=(m>9?a[4*m-40]:0)+(i>9?a[4*i-40]:0)+1,k=4*j-40;if(a[k]==0||a[k]>s){a[k]=s;a[k+1]=m;a[k+2]=i;a[k+3]=o;}}main(int c,char**v){n=strtol(v[1],0,0);i=4*n-36;if(n<10)p(n);else{a=calloc(i,sizeof(int));for(;j<=n;++j)for(i=1;i<j;++i){r(j-i,43);if(j%i==0)r(j/i,42);}p(n);}printf("\n");}

Language Ranking
 Rank Lang User Size Date1 Golfscript harold 140 10/7/2014 7:49:12 AM2 SysRPL 3298 147.5 10/8/2014 11:09:47 AM3 Java 3298 334 10/8/2014 11:09:47 AM4 C++ harold 361 10/7/2014 8:21:25 AM5 C# harold 375 10/7/2014 7:53:28 AM C 3298 433 10/8/2014 11:09:47 AM
« Last Edit: June 11, 2015, 08:56:36 am by pimathbrainiac »
Did you know that "Ammonia Gas" rearranged is "As Omnimaga"?
Click here for the only set of games you'll ever need
= ?

#### Juju

• Incredibly sexy mare
• Coder Of Tomorrow
• LV13 Extreme Addict (Next: 9001)
• Posts: 5730
• Rating: +500/-19
• Weird programmer
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #1 on: October 05, 2014, 02:30:32 pm »
Welp, this one is interesting. By the way, do we have to include . (print stack) and @ (end of program) so it outputs a valid Befunge program?
« Last Edit: October 05, 2014, 02:32:22 pm by Juju »

Remember the day the walrus started to fly...

I finally cleared my sig after 4 years you're happy now?

This signature is ridiculously large you've been warned.

The cute mare that used to be in my avatar is Yuki Kagayaki, you can follow her on Facebook and Tumblr.

#### harold

• LV5 Advanced (Next: 300)
• Posts: 226
• Rating: +41/-3
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #2 on: October 05, 2014, 03:04:42 pm »
Note that optimal solutions are usually not unique (you can obviously switch the first and second operands of every operator, and that's not even all).
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

#### JWinslow23

• Coder Of Tomorrow
• LV7 Elite (Next: 700)
• Posts: 556
• Rating: +43/-6
• I make quality calculator games...when I have time
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #3 on: October 05, 2014, 03:37:08 pm »
Welp, this one is interesting. By the way, do we have to include . (print stack) and @ (end of program) so it outputs a valid Befunge program?
No, only the pushing to the stack is needed. Maybe we don't want to print the value, but we want to do arithmetic on it or something.
Did you know that "Ammonia Gas" rearranged is "As Omnimaga"?
Click here for the only set of games you'll ever need
= ?

#### Runer112

• Moderator
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #4 on: October 05, 2014, 08:36:47 pm »
How much harder would this problem be if any befunge operator was allowed? That would certainly be more interesting, but perhaps unreasonable.

#### harold

• LV5 Advanced (Next: 300)
• Posts: 226
• Rating: +41/-3
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #5 on: October 06, 2014, 04:49:38 am »
Probably undecidable in general, if in "any" is included the control flow operators and so on, there would be a huge class of programs that might output the number you want but you don't know if they even halt.

By the way here are a couple of test cases (you probably won't get the same answer of course)
1337 = 7379**2+* (9 characters)
9001 = 55589****1+ (11 characters)
12345 = 364888***9+*+ (13 characters)
987654 = 8885688***9+***6+ (17 characters)
9876532 = 2258885688***9+***5+**+ (23 characters)
9876543 = 789**4+56899****2+*7+ (21 characters)
53887677 = 365688**7+7899**7+*9+**9+*+ (27 characters) (lowest number that requires 27 characters)
98765432 = 489*2+6927779****5+**1+** (25 characters)
« Last Edit: October 07, 2014, 01:44:44 pm by harold »
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

#### 3298

• LV2 Member (Next: 40)
• Posts: 26
• Rating: +1/-0
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #6 on: October 07, 2014, 01:24:35 pm »
Well, the last four are beyond what JWinslow23 specified as the required range (0-999999). In theory my programs should get these results eventually (unless there's a bug I didn't find yet), but in reality my quadratic algorithm is apparently insufficient. The 50G is still crunching 1337 (at least 20 minutes have passed ... I won't test the others without a turbo-mode emulator!), the Java version did the 12345 within a minute and got an integer overflow after chewing the 987654 for 15 minutes or so, resulting in an ArrayIndexOutOfBoundsException. I got a segfault from the C version at 987654 (though immediately) after it did 12345 in what felt like 20 seconds. I'll see what I can do to fix them up.
Is there an algorithm with better complexity than O(n^2)?

#### harold

• LV5 Advanced (Next: 300)
• Posts: 226
• Rating: +41/-3
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #7 on: October 07, 2014, 01:42:21 pm »
I don't know, actually I think my algorithm also runs in O(n2), but might have a lower constant factor I guess?
Basically I make all the minimal expressions up to and including the one that's necessary, and generating any one of them inspects O(n) things (products and sums). I did the higher ones with more trickery (costs more code so that's not the version I submitted) to avoid testing most sums.
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

#### 3298

• LV2 Member (Next: 40)
• Posts: 26
• Rating: +1/-0
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #8 on: October 07, 2014, 02:12:26 pm »
Okay, I just found some code on StackOverflow by someone with your name, so I'm going to assume that's you. I'm also guessing that your current approach is pretty much the same as in those programs (without the fancy acceleration for huge numbers). My approach is similar, but I'm trying all combinations of numbers j, i < n where j>=i (cuts the time spent in half, this is possible due to commutativity), and then I generate j+i and j*i.
As it seems, this generates way too many numbers beyond n (which I usually discard, unless this integer overflow bites me).
It would have been nice if there was an O(n log n) algorithm, but the O(n^2) one will have to do. I'll subtract and divide instead of adding and multiplying then, I guess. That will at least avoid that integer overflow at 987654^2.

#### harold

• LV5 Advanced (Next: 300)
• Posts: 226
• Rating: +41/-3
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #9 on: October 07, 2014, 02:32:00 pm »
With the fancy trick, the loop that checks the products is the slowest part (benchmarking shows that part to take about 10 times as long as the loop that checks the sums), though I can't prove this bound, I would theorize that makes it O(n1.5) (obviously without the trick, checking the sums takes much longer since there are far more of them). I'll look into how (if at all) that could be improved.
« Last Edit: October 07, 2014, 02:34:27 pm by harold »
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

#### 3298

• LV2 Member (Next: 40)
• Posts: 26
• Rating: +1/-0
##### Re: Code Golf Contest #12: Befunge Numbers
« Reply #10 on: October 08, 2014, 05:03:07 am »
So I spent some time with SysRPL and the subtraction/division version. The good news is that it's working. The even better news is that it's shorter than the submitted version by 1 command (i.e. 2.5 bytes). The bad news is that it's still slow as hell: calculating "97*3*2+7*" takes 4720 seconds. Though in theory it would tackle everything up to 2^20-1=1048575, which is slightly more than what's needed. I'll submit it as soon as the Java and C versions are corrected as well.
Edit: Java done, size reduced by 3 bytes. C mostly done as well, though I have problems with creating a large array as a local variable (i.e. on the stack), which was the real cause of the segfault. so malloc it is ... as a result, the size increases by 12 bytes instead of decreasing.
Edit #2: About 100 minutes for Java and 21 for C at 987654 on my laptop, that's ... still slow, but acceptable for a single test case. But by using strtol I was able to reduce the size of the C version to 7 below the my first one. So all three programs are now smaller.
« Last Edit: October 08, 2014, 11:58:10 am by 3298 »