Wyjaśnienie
Befunge to dwuwymiarowy program, który wykorzystuje stosy .
Oznacza to, że aby zrobić 5 + 6, piszesz 56+, co oznacza:
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)
Jednak, jak zauważyli twoi inteligentni, nie możemy wepchnąć liczby 56bezpośrednio na stos.
Aby to zrobić, musimy napisać 78*zamiast, który mnoży 7i 8i popycha produkt na stosie.
Detale
Dane wejściowe mogą być pobierane w dowolnym formacie, co oznacza, że może być STDIN lub nie, według uznania programisty.
Dane wejściowe będą dodatnimi liczbami całkowitymi (bez premii za włączenie 0lub ujemne liczby całkowite).
Wyjście będzie ciąg składający się tylko z tych znaków: 0123456789+-*/(I byłoby nie skorzystać %. Modulo)
Celem jest znalezienie najkrótszego ciągu, który może reprezentować dane wejściowe, przy użyciu formatu opisanego powyżej.
Na przykład, jeśli dane wejściowe to 123, dane wyjściowe będą 67*99*+. Dane wyjściowe należy oceniać od lewej do prawej.
Jeśli istnieje więcej niż jeden akceptowalny wynik (np. 99*67*+Jest również akceptowalny), można wydrukować dowolny z nich (bez premii za wydrukowanie wszystkich).
Dalsze wyjaśnienia
Jeśli nadal nie rozumiesz, jak 67*99*+oceniać 123, oto szczegółowe wyjaśnienie.
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
Program musi znaleźć najkrótszy ciąg znaków, który może reprezentować dane wejściowe (liczbę), przy użyciu formatu określonego powyżej.
Notatki
To wyzwanie dla golfa , więc wygrywa najkrótszy kod w bajtach.
Ujednoznacznienie
-Może być albo x-yalbo y-x, według uznania programisty. Jednak wybór musi być spójny w ramach rozwiązania. Podobnie w przypadku /.
Przykładowy program
Lua, 1862 bajtów ( wypróbuj online )
Ponieważ jestem autorem, nie będę go w ogóle grał w golfa.
Wyjaśnienie:
This uses the depth-first search method.
Więcej informacji o wyszukiwaniu w pierwszej kolejności: tutaj .
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
Premia
Ciasto dla Ciebie, jeśli użyjesz Befunge (lub dowolnego jego wariantu) do napisania kodu.