Meta-tło

Zostało to ustawione jako pytanie na łamigłówkach , a natychmiastowa reakcja brzmiała: „no cóż, ktoś po prostu rozwiąże to za pomocą komputera”. Odbyła się debata na temat tego, jak skomplikowany musiałby być program do rozwiązania tego problemu. Cóż, „jak skomplikowany musi być ten program” jest właściwie definicją golfa kodowego , więc może PPCG może rozwiązać ten problem?

tło

Równanie zapałki jest zasadniczo normalny matematycznego, ale gdzie cyfry i operatorów są wykonane fizycznie przez umieszczanie zapałek na stole. (Główną istotną cechą zapałek jest tutaj to, że są one dość sztywne i mają stałą długość; czasami ludzie używają zamiast tego innych przedmiotów, takich jak waciki).

W przypadku tego wyzwania nie musimy definiować szczegółowych zasad dotyczących sposobu zestawiania zapałek (tak jak w przypadku wyzwania połączonego); zależy nam raczej na tym, ile zapałek będzie potrzebnych do przedstawienia wyrażenia, które będzie miało wartość dla podanej liczby.

Zadanie

Oto alfabet cyfr i operatorów matematycznych, z których każdy ma swój koszt w zapałkach:

• 0, kosztuje 6 zapałek
• 1, kosztuje 2 zapałki
• 2, kosztuje 5 zapałek
• 3, kosztuje 5 zapałek
• 4, kosztuje 4 zapałki
• 5, kosztuje 5 zapałek
• 6, kosztuje 6 zapałek
• 7, kosztuje 3 zapałki
• 8, kosztuje 7 zapałek
• 9, kosztuje 6 zapałek
• +, kosztuje 2 zapałki
• -, kosztuje 1 zapałkę
• ×, kosztuje 2 zapałki

(Można reprezentować ×jak *w wyjścia Twój program, jeśli chcesz, aby uniknąć konieczności używania znaków spoza ASCII. W większości kodowania, ×zajmuje więcej bajtów niż *, więc sobie wyobrazić, że większość programów będzie chciał skorzystać z tej swobody .)

Musisz napisać program, który przyjmuje nieujemną liczbę całkowitą jako dane wejściowe (za pomocą dowolnych rozsądnych środków ) i tworzy wyrażenie, które ocenia na tę liczbę całkowitą jako dane wyjściowe (ponownie za pomocą dowolnych rozsądnych środków). Ponadto, ekspresja może być nietrywialna: musi zawierać co najmniej jednego operatora +, -lub ×. Wreszcie wyrażenie, które wyprowadzasz, musi być najtańsze (lub powiązane z najtańszym) pod względem całkowitego kosztu zapałki, spośród wszystkich wyników, które w przeciwnym razie byłyby zgodne ze specyfikacją.

Wyjaśnienia

• Możesz tworzyć liczby wielocyfrowe, wypisując wiele cyfr z rzędu (np. 11-1Jest to prawidłowy wynik do wygenerowania 10). Aby być całkowicie precyzyjnym, wynikowa liczba jest interpretowana w postaci dziesiętnej. Ten rodzaj konkatenacji nie jest operacją, która działa na wyniki pośrednie; tylko na literach, które pojawiają się w oryginalnym wyrażeniu.
• Na potrzeby tego wyzwania. +, -i ×są operatorami infix; potrzebują kłótni po lewej i po prawej stronie. Nie wolno używać ich w pozycji prefiksu, takiej jak +5lub -8.
• Nie masz nawiasów (ani żadnego innego sposobu kontroli pierwszeństwa). Wyrażenie ocenia zgodnie z typowymi domyślnymi regułami pierwszeństwa (najpierw mnożą się, a następnie dodawanie i odejmowanie jest oceniane od lewej do prawej).
• Nie masz dostępu do żadnych operatorów matematycznych lub stałych innych niż te wymienione powyżej; Rozwiązania „myślenia lateralnego” są często akceptowane w Puzzling, ale nie ma sensu wymagać, aby komputer sam je wymyślił, a tutaj, w PPCG, podoba nam się obiektywność, czy rozwiązanie jest poprawne, czy nie.
• Obowiązują zwykłe reguły przepełnienia liczb całkowitych: twoje rozwiązanie musi być w stanie pracować dla dowolnie dużych liczb całkowitych w hipotetycznej (lub być może rzeczywistej) wersji twojego języka, w której wszystkie liczby całkowite są domyślnie nieograniczone, ale jeśli twój program zawiedzie w praktyce z powodu implementacji brak obsługi liczb całkowitych tak dużych, co nie unieważnia rozwiązania.
• Jeśli używasz tej samej cyfry lub operatora więcej niż jeden raz, musisz zapłacić jej koszt za każdym razem, gdy go używasz (ponieważ oczywiście nie możesz ponownie użyć tych samych fizycznych zapałek w dwóch różnych lokalizacjach na stole).
• Nie ma limitu czasu; dopuszczalne są brutalne siły. (Chociaż jeśli masz rozwiązanie, które jest szybsze niż brutalna siła, możesz opublikować je, nawet jeśli jest ono dłuższe; sprawdzanie, jak porównywane są alternatywne podejścia, jest zawsze interesujące.)
• Chociaż pisanie objaśnienia do kodu nigdy nie jest wymagane , prawdopodobnie jest to dobry pomysł; Rozwiązania do gry w golfa kodowego są często bardzo trudne do odczytania (szczególnie dla osób, które nie znają języka, w którym są napisane), i może być trudno ocenić (a tym samym zagłosować) rozwiązanie, chyba że rozumiesz, jak to działa.

Warunek zwycięstwa

Jako wyzwanie do gry w golfa , odpowiedzi z mniejszą liczbą bajtów są uważane za lepsze. Jednak, jak zwykle, nie krępuj się zamieszczać odpowiedzi z różnymi podejściami lub w określonych językach, nawet jeśli są bardziej szczegółowe niż niektóre inne języki; celem golfa jest naprawdę sprawdzenie, jak daleko można zoptymalizować dany program, a robienie tego w ten sposób daje nam wiele potencjalnych programów do optymalizacji. Nie zniechęcaj się więc, jeśli ktoś przedstawi rozwiązanie przy użyciu zupełnie innego podejścia lub zupełnie innego języka i otrzyma znacznie krótszą odpowiedź; być może Twoja odpowiedź jest lepiej zoptymalizowana i pokazuje więcej umiejętności, a wyborcy w PPCG często to doceniają.

Python2, 1̶9̶8̶ ̶b̶y̶t̶e̶s̶ 182 bajty dzięki math_junkie

def f(n,c=dict(zip('0123456789+-*',map(int,'6255456376212'))),e=[(0,'')]):
 while 1:
    v=(m,s)=min(e);e.remove(v)
    try:
     if eval(s)==n:return s
    except:0
    e+=[(m+c[x],s+x)for x in c]

Algorytm ten nie wyklucza wersji przedrostków +i -, ale będą one albo gorsze, albo równe i pojawią się później podczas wyszukiwania, ich odpowiedniki w postaci przedrostków . Ponieważ używa argumentu słowa kluczowego w sposób emutatywny, będzie dawał nieprawidłowe wyniki, jeśli zostanie wywołany wiele razy na sesję. Aby to naprawić, użyj f(n, e=[(0,'')])zamiast po prostu f(n). Zauważ, że cztery odstępy oznaczają tabulatory, więc będzie to działać tylko z Pythonem 2.

Mam też wersję bez golfa i zoptymalizowaną, która działa szybko nawet dla dość dużych liczb:

from heapq import heappop, heappush

def f(n):
    digits = list('0123456789')
    ops =['+','-','*','']
    costs = dict(zip(digits + ops, [6,2,5,5,4,5,6,3,7,6,2,1,2,0]))
    expressions = [(costs[d], abs(n - int(d)), int(d), d) for d in digits[1:]]
    seen = set()
    while 1:
        cost, d, k, expression = heappop(expressions)
        if d == 0:
            return expression
        for op in ops:
            if op in '+-' and k in seen:
                continue
            for digit in digits:
                if op and digit == '0':
                    continue
                expression1 = expression + op + digit
                k1 = eval(expression1)
                d1 = abs(n - k1)
                if d1 == 0:
                    return expression1
                heappush(expressions, (cost+costs[op]+costs[digit], d1, k1, expression1))
        seen.add(k)

PHP, 241 bajtów

Wersja online

function m($i){for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e;}foreach($r=range(0,2*$a=$argv[1])as$v)foreach($r as$w)$x[$v+$w]["$v+$w"]=$x[$v*$w]["$v*$w"]=1+$x[$v-$w]["$v-$w"]=m("$v")+m("$w")+1;echo array_search(min($x[$a]),$x[$a]);

Awaria

function m($i){
    for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e; #return the count of the matchstick for an integer
}

foreach($r=range(0,2*$a=$argv[1])as$v) # limit to an input to 300 in the online version
foreach($r as$w)
       $x[$v+$w]["$v+$w"]=  #fill the 2D array in the form [result][expression] = count matchsticks
       $x[$v*$w]["$v*$w"]=
       1+$x[$v-$w]["$v-$w"]=
       m("$v")+m("$w")+1;
echo $k=array_search(min($x[$a]),$x[$a]); # Output expression with a minium of matchsticks
echo"\t".$x[$a][$k]; #optional Output of the count of the matchsticks

Sposób z nieco lepszą wydajnością

function m($i){
for(;$s<strlen($i);)
$e+="6255456376"[$i[$s++]];return$e;} #return the count of the matchstick for an integer
foreach($r=range(0,2*$a=$argv[1])as$v)
foreach($r as$w){$c=m("$v")+m("$w")+1;
if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
if($a==$v*$w)$x["$v*$w"]=1+$c;
if($a==$v-$w)$x["$v-$w"]=$c;}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
    echo"\t".$x[$k]; #optional Output of the count of the matchsticks

Obsługa liczb całkowitych ujemnych

Wersja z ujemnymi liczbami całkowitymi

function m($i){
    $e=$i<0?1:0; # raise count for negative integers
    for($s=0;$s<strlen($i);)$e+=[6,2,5,5,4,5,6,3,7,6][$i[$s++]];return$e; #return the count of the matchstick for an integer
}
$q=sqrt(abs($argv[1]));
$l=max(177,$q);
$j=range(-$l,$l); # for second loop for better performance
foreach($r=range(min(0,($a=$argv[1])-177),177+$a)as$v) 
foreach($j as$w){$c=m("$v")+m("$w")+1;  
    if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
    if($a==$v*$w)$x["$v*$w"]=1+$c;
    if($a==$v-$w)$x["$v-$w"]=$c;
    if($a==$w-$v)$x["$w-$v"]=$c; # added for integers <0
}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
echo"\t".$x[$k]; #optional Output of the count of the matchsticks