14
\$\begingroup\$

Explanation

Befunge is a two-dimensional program that uses stacks.

That means, to do 5 + 6, you write 56+, meaning:

56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)

However, as the intelligent of you have observed, we cannot push the number 56 directly into the stack.

To do so, we must write 78* instead, which multiplies 7 and 8 and pushes the product into the stack.

Details

Input can be taken in any format, meaning it can be STDIN or not, at the programmer's discretion.

The input will be a positive integer (no bonus for including 0 or negative integers).

The output will be a string consisting of only these characters: 0123456789+-*/ (I would not use % modulo.)

The goal is to find the shortest string that can represent the input, using the format described above.

For example, if the input is 123, then the output would be 67*99*+. The output should be evaluated from left to right.

If there are more than one acceptable outputs (e.g. 99*67*+ is also acceptable), any one can be printed (no bonus for printing all of them).

Further Explanation

If you still do not understand how 67*99*+ evaluates to 123, here is a detailed explanation.

stack    |operation|explanation
          67*99*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      9     push 9 to stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack

TL;DR

The program needs to find the shortest string that can represent the input (number), using the format specified above.

Notes

This is a challenge, so the shortest code in bytes wins.

Disambiguation

The - can either be x-y or y-x, at the programmer's discretion. However, the choice must be consistent within the solution. Likewise for the /.

Sample program

Lua, 1862 bytes (try it online)

Since I am the author, I will not golf it at all.

Explanation:

This uses the depth-first search method.

More about depth-first search: here.

The program:

local input = (...) or 81

local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, a+b)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        table.insert(temp, s..'0')
        table.insert(temp, s..'1')
        table.insert(temp, s..'2')
        table.insert(temp, s..'3')
        table.insert(temp, s..'4')
        table.insert(temp, s..'5')
        table.insert(temp, s..'6')
        table.insert(temp, s..'7')
        table.insert(temp, s..'8')
        table.insert(temp, s..'9')
        table.insert(temp, s..'+')
        table.insert(temp, s..'-')
        table.insert(temp, s..'*')
        table.insert(temp, s..'/')
    end
    for i=1,#temp do
        if input == eval(temp[i]) then
            print(temp[i])
            return
        end
    end
    samples = temp
end

Bonus

A cake for you if you use Befunge (or any variant of it) to write the code.

\$\endgroup\$
  • 3
    \$\begingroup\$ It may be hard to decide, given an answer, if it always produces the sortest string. One idea would be to generate a large set of say 30--50 numbers and score by the sum of all output string length. However, I'm not sure how to combine that score with code length \$\endgroup\$ – Luis Mendo Mar 30 '16 at 13:42
  • 4
    \$\begingroup\$ Subset of this. \$\endgroup\$ – Addison Crump Mar 31 '16 at 15:34
  • 2
    \$\begingroup\$ Copying over my thoughts from chat: "I thought about it but I'd argue that the subset makes things a lot simpler because 1) no hex, 2) no floats, 3) no duplication and 4) positive only" \$\endgroup\$ – Sp3000 Mar 31 '16 at 16:28
  • 1
    \$\begingroup\$ @CoolestVeto this one is different enough to invalidate the old answers. \$\endgroup\$ – Rɪᴋᴇʀ Mar 31 '16 at 17:03
  • 1
    \$\begingroup\$ @CoolestVeto I think the other challenge should be closed as a duplicate of this one. \$\endgroup\$ – mbomb007 Mar 31 '16 at 21:25
4
\$\begingroup\$

Python 2, 278 bytes

My best solution, which everytime gives shortest answer. (but very slow)

def e(c):
 s=[];x,y=s.append,s.pop
 while c:
  d,c=c[0],c[1:]
  if"/"<d<":":x(d)
  else:a,b=y(),y();x(str(eval(b+d+a)))
 return int(y())
def g(v):
 s="0123456789+-*";t=list(s)
 while 1:
  for x in t:
   try:
    if e(x)==v:return x
   except:0
  t=[x+y for x in t for y in s]

Python 2, 437 bytes

This solution is longer, but very fast (not brute force). And I'm quite sure, that it always return shortest possible result.

r=range;l=len;a=input()
def f(n):
 if n<=9:return str(n)
 for d in r(9,1,-1):
  if n%d==0:return f(n/d)+"%d*"%d
 h=sum(map(int,list(str(n))))%9
 return f(n-h)+"%d+"%h
m={x:f(x) for x in r(a*9)}
for b in m:
 if a-b in m and l(m[b])+l(m[a-b])+1<l(m[a]):m[a]=m[a-b]+m[b]+"+"
 if a+b in m and l(m[b])+l(m[a+b])+1<l(m[a]):m[a]=m[a+b]+m[b]+"-"
 if b!=0 and a%b==0 and a/b in m and l(m[b])+l(m[a/b])+1<l(m[a]):m[a]=m[a/b]+m[b]+"*"
print m[a]
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! Hope you'll have a great time here. \$\endgroup\$ – Leaky Nun Mar 30 '16 at 14:31
  • 1
    \$\begingroup\$ @pbochinak I think I might have found a valid one. f(6551) returns 25*8*9*7+9*8+ (13 characters), while 9999***52*- (11 characters) is a better one. Verified with my own eval function above (in the question). \$\endgroup\$ – Leaky Nun Mar 30 '16 at 15:47
  • 4
    \$\begingroup\$ @pbochniak As the comment before mine points out, this answer is invalid in its current state. It is recommended to temporarily delete it while you're working on a fix (if nothing else, to prevent it from attracting downvotes). \$\endgroup\$ – Dennis Mar 30 '16 at 18:38
  • 1
    \$\begingroup\$ your while can just be while c: \$\endgroup\$ – Ven Mar 31 '16 at 12:14
  • \$\begingroup\$ You can use ; to separate assignments to variables (which saves bytes in indented blocks), ven's tip, get rid of whitespace between a symbol and anything else, and t can go. \$\endgroup\$ – CalculatorFeline Mar 31 '16 at 12:49
4
\$\begingroup\$

Perl, 134 133 132 128 bytes

Includes +5 for -Xlp (2 extra because the code contains ')

Run with the target number on STDIN:

perl -Xlp befour.pl <<< 123

befour.pl:

@1{1..9}=1..9;$.+=2,map{for$a(%1){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}%1until$\=$1{$_}}{

It has no artificial limits and is conceptually somewhat efficient but has terrible run times nevertheless even though I sacrificed a few bytes to speed it up. Generating a length 11 solution (e.g. target number 6551) takes about 5 hours on my system.

Sacrificing 7 more bytes makes the speed somewhat more bearable.

@1{1..9}=1..9;$.+=2,map{for$a(@a){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}@a=keys%1until$\=$1{$_}}{

17 minutes for a length 11 solution, about 5 hours for a length 13 solution. The first number that needs length 15 is 16622 which takes about 2 days. The first number that needs length 17 is 73319.

Notice that it assumes that division returns an integer by truncating towards 0 (per the befunge 93 specification)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What do the dollar-signs do? (I don't speak Perl at all) \$\endgroup\$ – Leaky Nun Mar 31 '16 at 14:13
  • 1
    \$\begingroup\$ @KennyLau $ accesses the scalar value. Where in most languages you would write a=4, perl will use $a=4. But is also used for a scalar access of more complex variables. E.g. $a{$b} fetches from hash (map, dictionary)%a the scalar value keyed on $b \$\endgroup\$ – Ton Hospel Mar 31 '16 at 14:42
2
\$\begingroup\$

C, 550 545 bytes

#define L strlen
#define y strcpy
#define t strcat
char c[9999][99];i=1,k=3;main(j){for(;i<10;i++)*c[i]=i+'0';for(;k--;){
for(i=1;i<9999;i++)for(j=1;j<=i;j++)*c[i]&&*c[j]&&(i+j>9998||*c[i+j]&&
L(c[i+j])<L(c[i])+L(c[j])+2||t(t(y(c[i+j],c[i]),c[j]),"+"),
i*j>9998||*c[i*j]&&L(c[i*j])<L(c[i])+L(c[j])+2||t(t(y(c[i*j],c[i]),c[j]),"*"));
for(i=9999;--i;)for(j=i;--j;)*c[i]&&*c[j]&&(*c[i/j]&&
L(c[i/j])<L(c[i])+L(c[j])+2||t(t(y(c[i/j],c[i]),c[j]),"/"),
*c[i-j]&&L(c[i-j])<L(c[i])+L(c[j])+2||t(t(y(c[i-j],c[i]),c[j]),"-"));}
scanf("%d",&i);printf("%s",c[i]);}

550 545 bytes after deleting the unnecessary newlines (all but the three newlines after the preprocessing directives).

@Kenny Lau - It can receive as input an integer between 1 and 9998, but I think that the range of input for which an optimal solution is computed is smaller than 9998. On the other hand, both ranges can be extended, if the memory allows it.

The program cannot push onto the stack any number higher than 9998. (9998 can be modified.) I ran the program in a different version, iterating over the outer loop (the one with k) for as long as there is improvement for any number between 1 and 9998 (as in Dijkstra's algorithm). After three iterations there is no improvement. So to save bytes, I hardcoded k=3.

To extend the range, two things are necessary - modifying the constants 9999 and 9998, running it with a variable number of iterations over the outter loop for as long as there is improvement, to see how long it takes until no improvement takes place, then modify the constant k=3 to that value.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Hope you'll have a great time here. \$\endgroup\$ – Leaky Nun Mar 30 '16 at 16:37
  • \$\begingroup\$ This passes my 6551 test perfectly. What is the effective range of this program? \$\endgroup\$ – Leaky Nun Mar 30 '16 at 16:40
  • \$\begingroup\$ I believe it is 9999. Can you please add this information to your solution? \$\endgroup\$ – Leaky Nun Mar 30 '16 at 16:41
  • \$\begingroup\$ It should be 9998. Also, you can eat some bytes by initializing i, j, and k before main(). \$\endgroup\$ – Leaky Nun Mar 30 '16 at 16:48
  • 1
    \$\begingroup\$ @Kenny Lau - Thank you for the edit. About extending the range, I noticed that it actually takes a little more to extend the range. I included that information in the answer. \$\endgroup\$ – mIllIbyte Mar 30 '16 at 17:18
2
\$\begingroup\$

Python 2, 284 bytes

Disclaimer: Takes freaking forever for some values ... but should be guaranteed to always return the shortest string, and has no artificially imposed range limit ... even works on negative values. :)

def f(v):
 i,z=0,'+-*/'
 while 1:
  s=('%x'%i).translate(__import__('string').maketrans('abcd',z),'ef');t=s;q=[];a,p=q.append,q.pop;i+=1
  try:
   while t:
    o,t=t[0],t[1:]
    if o in z:n,m=p(),p();a(eval(`m`+o+`n`))
    else:a(int(o))
   if p()==v and not q:return s
  except:pass

Algorithm:

  • Start with i = 0
  • Take the string representing the hex value of i, and replace abcd with +-*/ respectively, and remove any ef
  • Attempt to process string as postfix notation (RPN)
  • If successful, and result matches input value, return the string used.
  • Otherwise, increment i and try again.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "[t]akes [...] forever for some values" Have you tested it? What values? \$\endgroup\$ – Leaky Nun Mar 31 '16 at 13:44
  • \$\begingroup\$ @KennyLau I just wrote a test that's calculating f(i) from 0 <= i <= 6551 (to capture the 6551 value you used to invalidate @pbochniak 's original submission). Right now, it's been running for only a few minutes, and here's the last output from the test: 91 : 49+7* 3.020 s (total 108.174 s, worst 89: 5.827 s) Update - it just finished with value 92: 92 : 149+7*+ 258.761 s (total 366.935 s, worst 92: 258.761 s) \$\endgroup\$ – Ken 'Joey' Mosher Mar 31 '16 at 16:47
  • \$\begingroup\$ @KennyLau : Test has been running over an hour, and only up to value 113 ... see full test output here (pastebin) if you're interested ... \$\endgroup\$ – Ken 'Joey' Mosher Mar 31 '16 at 17:49
2
\$\begingroup\$

Python 2, 182 bytes

n=input()
L=[[[],""]]
while 1:
 s,c=L.pop(0);L+=[[s+[i],c+`i`]for i in range(10)]+(s[1:]and[[s[:-2]+[eval(`s[-2]`+o+`s[-1]`)],c+o]for o in"/+-*"[s[-1]==0:]])
 if[n]==s[-1:]:print c;E

So obscenely slow, I've left it running for an hour on input 221 and it still hasn't terminated. A great deal of the slowness is because I'm using a list as a queue for a breadth-first search, and .pop(0) is O(n) for lists.

L is just a queue containing (stack, code to reach stack) pairs. At each step, digits are always added, and operators are performed if the stack has at least two elements. Division is only performed if the last element is not 0, although I have a strong suspicion that division is never necessary (although I have no way of proving it, but I have checked this is the case up to 500).

The program terminates via a NameError after printing the result (eventually).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What is the ;E at the end doing? \$\endgroup\$ – Leaky Nun Mar 31 '16 at 15:32
  • \$\begingroup\$ @KennyLau That's the NameError for termination, since E is not defined anywhere else \$\endgroup\$ – Sp3000 Mar 31 '16 at 15:33
  • \$\begingroup\$ Wow, such cleverness. \$\endgroup\$ – Leaky Nun Mar 31 '16 at 15:38
1
\$\begingroup\$

CJam, 79

ri:M;A,:s:L;{L2m*{s,Y=},{~:A+AS*~!"/+-*">\f{\+}~}%Y2+:Y;_L@+:L;{S*~M=},:R!}gR0=

Try it online

This is horribly inefficient, but given enough memory and time, it eventually works. 123 runs out of memory with 16GB, but 120 and 125 are ok.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pyth - 35 bytes

Brute force. A weird thing is that the new implicit input actually hurts my score because it seems to be working for .v pyth_eval also.

.V1IKfqQ.x.v+jd_T\;N^s+"+-*/"UTbhKB

Try it online here.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Python 3, 183 bytes

e,n=enumerate,input()
v=list('0123456789')+[' '*n]*n*2
for i,s in e(v):
 for j,t in e(v):
  for o,k in zip('+*-',(i+j,i*j,i-j)):
   if 9<k<2*n:v[k]=min(v[k],s+t+o,key=len)
print(v[n])

Speed isn't totally unreasonable (123, 221, 1237, 6551 finish on the order of seconds or minutes). Changing the if statement to if j<=i and <k<2*n speeds it up more, at the cost of 9 more bytes. I left out division (/), because I can't see how it would be needed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hint: division is needed. \$\endgroup\$ – Leaky Nun May 1 '16 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.