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łek1
, kosztuje 2 zapałki2
, kosztuje 5 zapałek3
, kosztuje 5 zapałek4
, kosztuje 4 zapałki5
, kosztuje 5 zapałek6
, kosztuje 6 zapałek7
, kosztuje 3 zapałki8
, kosztuje 7 zapałek9
, 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-1
Jest to prawidłowy wynik do wygenerowania10
). 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+5
lub-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ą.
źródło
Odpowiedzi:
Python2, 1̶9̶8̶ ̶b̶y̶t̶e̶s̶ 182 bajty dzięki math_junkie
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óbe
mutatywny, będzie dawał nieprawidłowe wyniki, jeśli zostanie wywołany wiele razy na sesję. Aby to naprawić, użyjf(n, e=[(0,'')])
zamiast po prostuf(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:
źródło
PHP, 241 bajtów
Wersja online
Awaria
Sposób z nieco lepszą wydajnością
Obsługa liczb całkowitych ujemnych
Wersja z ujemnymi liczbami całkowitymi
źródło
$e+="6255456376"[$i[$s++]];
.