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

0 Members and 1 Guest are viewing this topic.

Offline JWinslow23

  • Coder Of Tomorrow
  • LV7 Elite (Next: 700)
  • *******
  • Posts: 556
  • Rating: +43/-6
  • I make quality calculator games...when I have time
    • View Profile
[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 :P ) 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. :P

C#
RankUserSizeDateCode
1harold37510/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++
RankUserSizeDateCode
1harold36110/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
« 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
= ?

Offline Juju

  • Incredibly sexy mare
  • Coder Of Tomorrow
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 5730
  • Rating: +500/-19
  • Weird programmer
    • View Profile
    • juju2143's shed
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?
THEGAME
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.

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.

Offline JWinslow23

  • Coder Of Tomorrow
  • LV7 Elite (Next: 700)
  • *******
  • Posts: 556
  • Rating: +43/-6
  • I make quality calculator games...when I have time
    • View Profile
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
= ?

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
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.

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.

Offline 3298

  • LV2 Member (Next: 40)
  • **
  • Posts: 26
  • Rating: +1/-0
    • View Profile
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)?

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.

Offline 3298

  • LV2 Member (Next: 40)
  • **
  • Posts: 26
  • Rating: +1/-0
    • View Profile
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. ;)

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.

Offline 3298

  • LV2 Member (Next: 40)
  • **
  • Posts: 26
  • Rating: +1/-0
    • View Profile
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 »