# Express a number with only 0-9 and the four operations

## 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 /.

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


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.

• 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 Commented Mar 30, 2016 at 13:42
• Subset of this. Commented Mar 31, 2016 at 15:34
• 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" Commented Mar 31, 2016 at 16:28
• @CoolestVeto this one is different enough to invalidate the old answers. Commented Mar 31, 2016 at 17:03
• @CoolestVeto I think the other challenge should be closed as a duplicate of this one. Commented Mar 31, 2016 at 21:25

# 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]

• Welcome to PPCG! Hope you'll have a great time here. Commented Mar 30, 2016 at 14:31
• @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). Commented Mar 30, 2016 at 15:47
• @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). Commented Mar 30, 2016 at 18:38
• your while can just be while c:
– Ven
Commented Mar 31, 2016 at 12:14
• 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. Commented Mar 31, 2016 at 12:49

# Perl, 134133132 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)

• What do the dollar-signs do? (I don't speak Perl at all) Commented Mar 31, 2016 at 14:13
• @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 Commented Mar 31, 2016 at 14:42

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

• Welcome to PPCG! Hope you'll have a great time here. Commented Mar 30, 2016 at 16:37
• This passes my 6551 test perfectly. What is the effective range of this program? Commented Mar 30, 2016 at 16:40
• I believe it is 9999. Can you please add this information to your solution? Commented Mar 30, 2016 at 16:41
• It should be 9998. Also, you can eat some bytes by initializing i, j, and k before main(). Commented Mar 30, 2016 at 16:48
• @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. Commented Mar 30, 2016 at 17:18

# 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.
• "[t]akes [...] forever for some values" Have you tested it? What values? Commented Mar 31, 2016 at 13:44
• @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) Commented Mar 31, 2016 at 16:47
• @KennyLau : Test has been running over an hour, and only up to value 113 ... see full test output here (pastebin) if you're interested ... Commented Mar 31, 2016 at 17:49

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

• What is the ;E at the end doing? Commented Mar 31, 2016 at 15:32
• @KennyLau That's the NameError for termination, since E is not defined anywhere else Commented Mar 31, 2016 at 15:33
• Wow, such cleverness. Commented Mar 31, 2016 at 15:38

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

# 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


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

• Hint: division is needed. Commented May 1, 2016 at 5:19