14
1
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 code-golf 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.
Leaky Nun
Posted 2016-03-30T12:48:13.407
Reputation: 45 011
3It 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 – Luis Mendo – 2016-03-30T13:42:31.727
@DonMuesli See my sample solution. – Leaky Nun – 2016-03-30T13:48:04.840
What's the maximum possible input? – mbomb007 – 2016-03-30T16:55:05.977
@mbomb007 As large as is possible (just set a reasonable boundary). – Leaky Nun – 2016-03-30T16:57:01.580
@Mego Modified. – Leaky Nun – 2016-03-30T17:31:47.567
4
Subset of this.
– Addison Crump – 2016-03-31T15:34:01.340@CoolestVeto Well this gets more answer than that (but flag if you want). – Leaky Nun – 2016-03-31T15:42:47.350
@KennyLau Yeah, no, duplicates should never be around. – Addison Crump – 2016-03-31T16:23:06.270
2
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"
– Sp3000 – 2016-03-31T16:28:40.1431@CoolestVeto this one is different enough to invalidate the old answers. – Rɪᴋᴇʀ – 2016-03-31T17:03:03.363
@EasterlyIrk Both of those answers were invalidated by the old question's rule changes, the question, as it stands, is a subset of the current rules for that question. I think Sp3000's argument is good enough, though. – Addison Crump – 2016-03-31T17:05:02.177
1@CoolestVeto I think the other challenge should be closed as a duplicate of this one. – mbomb007 – 2016-03-31T21:25:52.077
In my opinion, the two challenges are different enough, and eventually the other should be closed. That's why I voted to reopen – edc65 – 2016-03-31T22:06:43.540
As an extra argument that this is not a duplicate: My perl solution is based on the fact that all operators are binary. It wouldn't work if one of the allowed operators is to duplicate the top of the stack – Ton Hospel – 2016-04-01T05:56:00.757
1All numbers below
2^32can be generated with a string of at most 29 characters (15 values and 14 operators) while forcing no overflow in the intermediate values. The lowest number needing the full 29 characters is676156706. – Ton Hospel – 2016-05-11T20:08:10.333