Calculator Community > Community Contests

[ENDED] Code Golf Contest #12: Befunge Numbers

(1/3) > >>

JWinslow23:
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#
RankUserSizeDateCode1harold37510/7/2014 7:53:28 AMSpoiler 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++
RankUserSizeDateCode1harold36110/7/2014 8:21:25 AMSpoiler 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
RankUserSizeDateCode1harold14010/7/2014 7:49:12 AMSpoiler For Spoiler: ~:l;9,{1+`}%10:x;{x l>}{.[.,,{1+}%]zip.[{~\;.x\%!\1=!*},.{~\;-1*}$]zip{~~;\~;+"*"+}%\[.{~\;-1*}$]zip{~~;\~;+"+"+}%+{,}$[(\;]+1x+:x;}until)\;
SysRPL
RankUserSizeDateCode13298147.510/8/2014 11:09:47 AMSpoiler 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
RankUserSizeDateCode1329833410/8/2014 11:09:47 AMSpoiler 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
RankUserSizeDateCode1329843310/8/2014 11:09:47 AMSpoiler 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
RankLangUserSizeDate1Golfscriptharold14010/7/2014 7:49:12 AM2SysRPL3298147.510/8/2014 11:09:47 AM3Java329833410/8/2014 11:09:47 AM4C++harold36110/7/2014 8:21:25 AM5C#harold37510/7/2014 7:53:28 AMC329843310/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:

--- Quote from: Juju 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?

--- End quote ---
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.

Navigation

[0] Message Index

[#] Next page