[ENDED] Code Golf Contest #12: Befunge Numbers

[JWinslow23]

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.

Deadline
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<l;i++){x=99;for(j=2;j<i;j++){if(i%j==0){k=n[j].Length+n[i/j].Length+1;if(k<x){x=k;n=n[j]+n[i/j]+"*";}}}for(j=1;j<i;j++){k=n[j].Length+n[i-j].Length+1;if(k<x){x=k;n=n[j]+n[i-j]+"+";}}}Console.WriteLine(n[l-1]);}}}

C++

Rank	User	Size	Date	Code
1	harold	361	10/7/2014 8:21:25 AM	Spoiler For Spoiler: #include <string> using namespace std; #define Z(p,q){k=n[j].length()+n.length()+1;if(k<x){x=k;n=n[j]+n+#q;}} #define X(f);for(j=f;j<i;j++) int main(int c,char**v){int l=atoi(v[1])+1,i=0,j,k,x;string *n=new string[1<<20];for(;i<10;i++)n=to_string((_Longlong)i);for(;i<l;i++){x=99;n=""X(2)if(i%j==0)Z(/,*)X(1)Z(-,+);}puts(n[l-1].c_str());}

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

[Juju]

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?

[harold]

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).

[JWinslow23]

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.

[Runer112]

How much harder would this problem be if any befunge operator was allowed? That would certainly be more interesting, but perhaps unreasonable.

[harold]

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)

[3298]

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]

I don't know, actually I think my algorithm also runs in O(n²), 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.

[3298]

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]

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(n^1.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.

[3298]

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.