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.

Python 2, 278 bajtów

Moje najlepsze rozwiązanie, które za każdym razem daje najkrótszą odpowiedź. (ale bardzo wolno)

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 bajtów

To rozwiązanie jest dłuższe, ale bardzo szybkie (nie brutalna siła). I jestem całkiem pewien, że zawsze zwraca najkrótszy możliwy wynik.

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]

Perl, 134 133 132 128 bajtów

Obejmuje +5 za -Xlp(2 dodatkowe, ponieważ kod zawiera ')

Uruchom z numerem docelowym na 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{$_}}{

Nie ma żadnych sztucznych ograniczeń i jest koncepcyjnie dość wydajny, ale mimo to ma straszne czasy działania, mimo że poświęciłem kilka bajtów, aby go przyspieszyć. Wygenerowanie rozwiązania o długości 11 (np. Numer docelowy 6551) zajmuje około 5 godzin w moim systemie.

Poświęcenie 7 dodatkowych bajtów sprawia, że ​​prędkość jest nieco bardziej znośna.

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

17 minut dla roztworu o długości 11, około 5 godzin dla roztworu o długości 13. Pierwsza liczba, która potrzebuje długości 15, to 16622, co zajmuje około 2 dni. Pierwsza liczba, która potrzebuje długości 17, to 73319.

Zauważ, że zakłada, że ​​dzielenie zwraca liczbę całkowitą przez obcięcie w kierunku 0 (zgodnie ze specyfikacją befunge 93)

C, 550 545 bajtów

#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 bajtów po usunięciu niepotrzebnych nowych linii (wszystkie oprócz trzech nowych linii po dyrektywach wstępnego przetwarzania).

@Kenny Lau - Może przyjmować jako dane wejściowe liczbę całkowitą od 1 do 9998, ale myślę, że zakres danych wejściowych, dla których obliczane jest optymalne rozwiązanie, jest mniejszy niż 9998. Z drugiej strony oba zakresy można rozszerzyć, jeśli pamięć pozwala na to.

Program nie może wypchnąć na stos żadnej liczby większej niż 9998. (9998 można zmodyfikować.) Uruchomiłem program w innej wersji, iterując po zewnętrznej pętli (tej z literą k), dopóki istnieje poprawa dla dowolnej liczby od 1 do 9998 (jak w algorytmie Dijkstry). Po trzech iteracjach nie ma poprawy. Aby zaoszczędzić bajty, zapisałem na stałe k = 3.

Aby rozszerzyć zakres, konieczne są dwie rzeczy - zmodyfikowanie stałych 9999 i 9998, uruchomienie go ze zmienną liczbą iteracji w pętli zewnętrznej tak długo, jak długo istnieje poprawa, aby zobaczyć, ile czasu zajmuje, dopóki nie nastąpi poprawa, a następnie zmodyfikuj stałą k = 3 na tę wartość.

Python 2, 284 bajtów

Zrzeczenie się: Trochę wariuje na zawsze dla niektórych wartości ... ale należy zagwarantować, że zawsze zwróci najkrótszy ciąg i nie ma sztucznie narzuconego ograniczenia zasięgu ... działa nawet na wartości ujemne. :)

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

Algorytm:

• Zacząć od i = 0
• Weźmy ciąg reprezentujący wartość hex ii wymienić abcdz +-*/odpowiednio i usuńef
• Próba przetworzenia ciągu jako notacji Postfix (RPN)
• Jeśli się powiedzie, a wynik odpowiada wartości wejściowej, zwróć użyty ciąg.
• W przeciwnym razie zwiększ ii spróbuj ponownie.

Python 2, 182 bajty

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

Tak nieprzyzwoicie powolny, że pozostawiłem go działający przez godzinę na wejściu 221i nadal się nie skończył. Duża część powolności polega na tym, że używam listy jako kolejki do pierwszego wyszukiwania szerokości i .pop(0)dotyczy ona O(n)list.

Lto tylko kolejka zawierająca (stack, code to reach stack)pary. Na każdym etapie cyfry są zawsze dodawane, a operatory są wykonywane, jeśli stos zawiera co najmniej dwa elementy. Podział jest wykonywany tylko wtedy, gdy ostatni element nie jest równy 0, chociaż mam silne podejrzenie, że podział nigdy nie jest konieczny (chociaż nie mam możliwości, aby to udowodnić, ale sprawdziłem, że tak jest w przypadku 500).

Program kończy się NameErrorpo wydrukowaniu wyniku (ewentualnie).

CJam, 79

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

Wypróbuj online

Jest to okropnie nieefektywne, ale biorąc pod uwagę wystarczającą pamięć i czas, w końcu działa. 123 zabrakło pamięci z 16 GB, ale 120 i 125 są w porządku.

Pyth - 35 bajtów

Brutalna siła. Dziwną rzeczą jest to, że tak naprawdę nowy domniemany wkład boli mój wynik, ponieważ wydaje się, że działa .vrównież dla pyth_eval.

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

Wypróbuj online tutaj .

Python 3, 183 bajtów

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

Prędkość nie jest całkowicie nierozsądna (123, 221, 1237, 6551 kończy się w kolejności sekund lub minut). Zmiana ifinstrukcji w celu if j<=i and <k<2*nprzyspieszenia jej jeszcze bardziej kosztem 9 bajtów więcej. Pominąłem div ( /), ponieważ nie widzę, jak byłoby to potrzebne.