StickStack to bardzo prosty język programowania oparty na stosie, zawierający tylko dwie instrukcje:
|
wypycha długość stosu na stos-
wysuwa dwa górne elementy ze stosu i odsuwa ich różnicę (second topmost - topmost
)
Szczegóły języka
- Stos jest pusty na początku programu.
- Wszystkie instrukcje są wykonywane sekwencyjnie od lewej do prawej.
- Jeśli na stosie jest mniej niż 2 liczby,
-
instrukcja jest nielegalna. - Pod koniec wykonywania stos powinien zawierać dokładnie jedną liczbę .
Każda liczba całkowita może być generowana przez program StickStack. Na przykład:
|||--||-- generates the number 2 through the following stack states:
[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]
Aby ocenić kod StickStack, możesz skorzystać z tego narzędzia do oceny online (CJam) . (Dzięki za @Martin za kod.)
Zadanie
Powinieneś napisać program lub funkcję, która jako liczbę wyjściową podaje liczbę całkowitą lub zwraca ciąg znaków reprezentujący program StickStack, który wypisuje podaną liczbę.
Punktacja
- Twój wynik główny to całkowita długość programów StickStack dla poniższych przypadków testowych. Niższy wynik jest lepszy.
- Twoje zgłoszenie jest ważne tylko wtedy, gdy uruchomiłeś program na wszystkich testowych przypadkach i policzyłeś swój wynik.
- Drugi wynik (remis rozstrzygający) to długość programu lub funkcji generującej.
Wprowadź przypadki testowe
(Każda liczba to inny przypadek testowy).
-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730
Twój program powinien działać na wszystkich liczbach całkowitych (które może obsłużyć Twój typ danych), a nie tylko na danych przypadkach testowych. Rozwiązania dla numerów testowych nie powinny być zakodowane na stałe w twoim programie. Jeśli pojawią się wątpliwości co do twardego kodowania, numery testowe zostaną zmienione.
źródło
Odpowiedzi:
Python 2 - 5188
Dość wydajny pod względem czasowym i wydaje się (prawdopodobnie) optymalnym rozwiązaniem. Zauważyłem, że wzór taki jak
|||||-|||-|-|-|------
(optymalne rozwiązanie dla 25 osób)można określić jako
gdzie każda całkowita wartość na końcu jest sumą (wartość każdego poziomu pomnożona przez liczbę „|”). Na przykład powyżej mamy
-1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25
. Korzystając z tego, napisałem to rozwiązanie, które daje wyniki podobne do innych odpowiedzi, w bardzo trywialnym czasie.Uważam, że jest to optymalne rozwiązanie, ponieważ testuję każdą możliwą optymalną wysokość (faktycznie testuję o wiele więcej niż to konieczne) i jestem prawie pewien, że rozwiązanie zawsze obejmuje co najwyżej jedną warstwę z dwoma znakami „|” oprócz ostatniej (mogę zagwarantuj to dla liczb dodatnich, ale nie 100% pewności co do negatywów).
Oto kod, którego użyłem do przetestowania
źródło
Java, 5208
524053066152Jest to funkcja rekurencyjna, która zbliża się do celu, z podstawowymi przypadkami, gdy osiągnie wartość 5 (co często jest tylko jednym krokiem).
Zasadniczo, można uzyskać
(a*b)+(a/2)
na(a+b)*2
kije z prostego wzoru. Jeślia
jest nieparzysty, wynik będzie ujemny, co prowadzi do dziwnej logiki.Zajmuje to około minuty dla 2 31 -1, w rezultacie o długości 185 367. Działa prawie natychmiast dla wszystkich przypadków testowych. To
4*(sqrt|n|)
średnia ocena. Najdłuższy indywidualny przypadek testowy9730
, co daje stos o długości 397 kijów:Aktualizacja:
Znaleziono krótszy sposób dodawania / odejmowania od podstawowego wzorca. Z powrotem na czele (na razie)!
Z uprzężą i walizkami testowymi:
Gra w golfa (więcej) w mało prawdopodobnym przypadku dokładnego remisu.
źródło
JavaScript (ES6) 5296
6572Edytuj Jak powiedziałem w moim wyjaśnieniu, nie jestem dobry w rozwiązywaniu równań całkowitych. Moje przypuszczenie wartości b nie było tak dobre, więc poszerzyłem zakres wartości do wypróbowania.
I (wow) Teraz prowadzę.Edytuj 2 Poprawka błędu, te same wyniki. Mam pomysł, ale nie mogę go dopracować.
Bajty: ~ 460, dość golfa. Działa na 32-bitowych liczbach całkowitych, czas działania zbliżony do 0.
Kod to funkcja F (ukryta we fragmencie) poniżej.
Uruchom fragment, aby przetestować (w FireFox).
Pokaż fragment kodu
Wyjaśnienie
Na początek liczby dodatnie. Zacznij od „podstawy” (spróbuj w CJam, jeśli chcesz, spacje dozwolone)
Podsumowanie: 1 drążek, następnie b * 2 drążki, a następnie b * 2 kreski
Następnie spróbuj dodać jeden lub więcej „- |” w środkowym splocie. Każdy z nich dodaje stały przyrost, który stanowi dwukrotność podstawy początkowej i może być powtarzany wiele razy. Mamy więc wzór, w którym b = podstawa ir = współczynnik powtarzania przyrostu
Widzieć? Wartość dodana szybko wzrasta, a każdy dodatek nadal ma tylko 2 znaki. Przyrost podstawowy daje za każdym razem 4 dodatkowe znaki.
Biorąc pod uwagę v i naszą formułę v = b + r * 2 * b, musimy znaleźć 2 ints bi r. Nie jestem ekspertem w tego rodzaju równaniach, ale b = int sqrt (v / 2) to dobry początek.
Następnie mamy rib, które razem dają wartość bliską v. Osiągamy v dokładnie z powtarzanym przyrostem (|| -) lub zmniejszeniem (| -).
Stosuj to samo rozumowanie liczb ujemnych, niestety formuła jest podobna, ale nie równa.
źródło
JavaScript, 398710
94 bajty / znaki kodu
Wymyśliłem rozwiązanie! ... a potem przeczytałem odpowiedź Sparra i było dokładnie tak samo.
Pomyślałem, że i tak to opublikuję, ponieważ js pozwala na nieco mniej znaków.
Oto nieuprawniona wersja kodu:
źródło
Python, 398710 (71 bajtów)
Najprostsze możliwe rozwiązanie, tak myślę. Używa 4 * n (+/- 1) znaków stickstack do reprezentowania n.
źródło