Napisz program, który przyjmuje ciąg nieparzystej długości zawierający tylko znaki .
i :
. Za pomocą początkowo pustego stosu wygeneruj liczbę z tego ciągu w następujący sposób:
Dla każdego znaku c w ciągu (od lewej do prawej) ...
- Jeśli c jest,
.
a stos zawiera mniej niż 2 elementy, wciśnij 1 na stosie. - Jeśli c jest,
.
a stos zawiera 2 lub więcej elementów, usuń dwie górne wartości ze stosu i wypchnij ich sumę na stos. - Jeśli c jest,
:
a stos zawiera mniej niż 2 elementy, wciśnij 2 na stosie. - Jeśli c jest,
:
a stos zawiera 2 lub więcej elementów, usuń dwie najwyższe wartości ze stosu i wepchnij ich produkt na stos.
Wynikowa liczba to wartość na górze stosu. Twój program powinien wydrukować ten numer na standardowe wyjście (z opcjonalnym końcowym znakiem nowej linii).
(Mała analiza pokazuje, że pozostała tylko jedna liczba, chyba że łańcuch ma równą długość, dlatego je ignorujemy. W rzeczywistości stos nigdy nie ma więcej niż 2 elementy.)
Na przykład liczba ::...:.:.
to 9:
2 1 2 2 /______ stack just after the character below is handled
2 2 4 4 5 5 7 7 9 \
: : . . . : . : . <-- string, one character at a time
Jako kontrolę poczytalności, oto liczby dla wszystkich ciągów długości 1, 3 i 5:
. 1
: 2
... 2
..: 1
.:. 3
.:: 2
:.. 3
:.: 2
::. 4
::: 4
..... 3
....: 2
...:. 4
...:: 4
..:.. 2
..:.: 1
..::. 3
..::: 2
.:... 4
.:..: 3
.:.:. 5
.:.:: 6
.::.. 3
.::.: 2
.:::. 4
.:::: 4
:.... 4
:...: 3
:..:. 5
:..:: 6
:.:.. 3
:.:.: 2
:.::. 4
:.::: 4
::... 5
::..: 4
::.:. 6
::.:: 8
:::.. 5
:::.: 4
::::. 6
::::: 8
Najkrótszy program w bajtach wygrywa. Tiebreaker jest wcześniejszym postem.
- Możesz założyć, że dane wejściowe są zawsze prawidłowe, tzn. Ciąg zawierający tylko
.
i:
którego długość jest nieparzysta. - Zamiast pisać program, możesz napisać funkcję, która pobiera prawidłowy ciąg i wypisuje lub zwraca wygenerowaną liczbę.
Odpowiedzi:
CJam,
27 24 2322 bajtówCałkiem prosto. Używam stosu CJam jako stosu wspomnianego w pytaniu;)
Algorytm
Najpierw spójrzmy na kod ASCII dla
.
i:
.Ponieważ w CJam indeks się zawija, zobaczmy, czy możemy użyć tych wartości bezpośrednio, aby uzyskać żądaną operację.
Nie mogę więc po prostu użyć kodów ASCII w ciągu operacji o długości 4. Spróbujmy innych wartości
który na sznurku o długości 4 sprowadza się do
Mogę użyć tej operacji mod 10, ale będzie to kosztować 2 bajty. Spróbujmy czegoś innego
Fajnie !, teraz odejmujemy 1 dla warunku rozmiaru stosu, aby uzyskać indeksy
0, 1, 2 and 3
i użyć5
tablicy length ("1+2* "
) jako przypadku przełącznika. Ostatnia spacja to tylko wypełniacz, aby uzyskać długość 5. To tylko 1 dodatkowy bajt w porównaniu z operacją modowania.Wypróbuj online tutaj
1 bajt zapisany dzięki cosechy
źródło
> <> (Ryba) , 33 bajty
Dość proste z małymi sztuczkami / optymalizacjami.
Wyjaśnienie:
i
= punkt kodowy następnego znaku wejściowego,-1
jeśli osiągnięto koniec wejścia;a
= 10;b
= 11;)
=>
i
punkt kodowy pierwszego wejścia char,b%1-
top_of_stack mod 11 - 1
maski48 ('.') , 56 (':')
do1 , 2
i:1+?\~n;
jeśli osiągnięty został koniec danych wejściowych, wydrukuj ostatni wynik i zakończb%1-
wejście maski do1 , 2
0@
wciśnij0
pod dwoma numeramii5a*)
przeczytaj następny wpis i zamaskuj go do0 , 1
porównania50
1
(':'
) pomnóż dwa górne elementy, tworząc stos [0 produkt][0 sum]
albo[0+product=product]
40.
przeskocz (pętla) z powrotem do pozycji(4,0)
, nasz punkt4
,i:1+?\~n;
źródło
Haskell,
7365 bajtówProste rozwiązanie, wykorzystujące fakt, że stos nigdy nie ma więcej niż 2 elementy.
źródło
C, 104 bajty
To jest za długie.
źródło
Pyth,
2524 bajtówWpadłem na pomysł studiując rozwiązanie @ isaacg. Ale używam stosu.
Demonstracja online lub pakiet testowy
Wyjaśnienie
Pierwszą rzeczą, którą robię, jest konwersja ciągu wejściowego na 0 i 1. A
"."
przekształca się w0
, a":"
w1
.Następnie zmniejszam tę listę liczb:
źródło
JavaScript (ES6), 65
Używamy tylko 2 komórek naszego stosu.
Zacznij wpisywać wartość ws [0].
Następnie na każdej nieparzystej pozycji (licząc od 0) w ciągu wejściowym wprowadź wartość w s [1].
Na każdej parzystej pozycji wykonaj oblicz (dodaj lub pomnóż) i zapisz wynik w s [0].
Więc zapomnij o stosie i użyj tylko 2 zmiennych, a i b.
Szybki test
Wydajność
źródło
f=s=>[(c=s[i]>'.',i&1?b=1+c:+i?c?a*=b:a+=b:a=1+c)for(i in s)]|a
Pyth, 27 bajtów
Stos? Kto potrzebuje stosu.
Demonstracja.
źródło
Siatkówka ,
1057573 bajtówMój pierwszy program Retina! (Podziękowania dla Martina Büttnera za zapisanie 2 bajtów, nie mówiąc już o wymyśleniu języka.)
Każda linia powinna znajdować się w osobnym pliku; lub możesz umieścić je wszystkie w jednym pliku i użyć
-s
flagi. The<empty>
Notacja reprezentuje pusty plik / linię.Zainspirowany odpowiedzią mbomb007 , ale podchodzę nieco inaczej. Jedną z głównych różnic jest to, że buduję stos przed kropkowanym łańcuchem (górą stosu jest skierowana w prawo). Ułatwia to konwersję symboli na odpowiednie liczby w miejscu. Używam również
a
zamiast1
zamiany tylko na końcu, aby uniknąć parsowania dwuznaczności w podobnych sekwencjach$1a
. Jeśli odpowiedź typu „tak”aaaaaa
jest akceptowalna jako liczba jednoargumentowa, ostatnie dwa wiersze / pliki można wyeliminować, aby zaoszczędzić 4 bajty.Wyjaśnienie:
Dopasowuje, jeśli na stosie (0
(a+;)?
) znajduje się 0 lub 1 elementów, po których następuje kropka (\.
); jeśli tak, to zastępuje kropkęa;
(tj. wypycha 1).Dopasowuje, jeśli na stosie znajduje się 0 lub 1 przedmiotów, a następnie dwukropek. Jeśli tak, zastępuje dwukropek
aa;
(tj. Wypycha 2).Dopasowuje, jeśli na stosie znajdują się dwa przedmioty, po których następuje kropka. Usuwa kropkę i średnik między elementami, tym samym dodając je.
Pasuje, jeśli na stosie znajdują się dwa przedmioty, których szczyt to 2, a następnie dwukropek. Usuwa dwukropek i 2 i powtarza drugą liczbę dwa razy, mnożąc ją przez 2.
Wyrażenie regularne pasuje, jeśli na stosie znajdują się dwa przedmioty, których górna część to 1, a następnie dwukropek. Usuwa dwukropek i 1, pozostawiając drugą liczbę bez zmian (tj. Pomnożoną przez 1).
)`
wskazuje koniec pętli. Jeśli w łańcuchu zostaną wprowadzone jakiekolwiek zmiany, formant powróci na początek programu i ponownie uruchomi podstawienia. Jeśli ciąg przestał się zmieniać, zastąpiliśmy wszystkie kropki i dwukropki, a wszystko, co pozostało, to czyszczenie ...Usuwa resztkowy średnik.
Przekształca wszystkie a w 1. Ponownie, jeśli jednostkowym liczbom wolno używać dowolnego symbolu, ten krok jest niepotrzebny.
źródło
Rdza, 170 znaków
Kolejny dowód, że Rust jest absolutnie okropny w golfie. Pełny nieoznaczony kod:
Oto interesująca sztuczka, której użyłem w tym. Możesz ogolić znak w instrukcji if / else, zwracając mu wartość, która jest natychmiast odrzucana, co oznacza, że potrzebujesz tylko jednego średnika zamiast dwóch.
Na przykład,
można zmienić na
który ocala postać, goląc średnik.
źródło
Haskell,
888179 bajtówWygląda na to, że ktoś pobił mnie do kresu na rozwiązaniu Haskell, nie tylko to, że jego rozwiązanie jest krótsze niż moje. To źle, ale nie widzę powodu, aby nie publikować tego, co wymyśliłem.
źródło
APL (50)
Jestem tutaj w bardzo niekorzystnej sytuacji, ponieważ APL nie jest językiem stosowym. W końcu jednak musiałem ograniczyć nadużycia, aby skrócić program.
Funkcja wewnętrzna pobiera „polecenie” po lewej stronie i stos po prawej stronie i stosuje je, zwracając stos. Funkcja zewnętrzna zmniejsza ją w ciągu, zaczynając od pustego stosu.
Wyjaśnienie:
(⌽⍵),⊂⍬
: początkowa lista do zmniejszenia.⊂⍬
pusta lista w ramkach, która reprezentuje stos,(⌽⍵)
jest odwrotnością danych wejściowych. (Redukcję stosuje się od prawej do lewej nad listą, więc ciąg będzie przetwarzany od prawej do lewej. Wcześniejsze odwrócenie danych wejściowych powoduje, że znaki zostaną zastosowane we właściwej kolejności.){
...}
: funkcja wewnętrzna. Bierze stos po prawej stronie, postać po lewej i zwraca zmodyfikowany stos.F←'.:'⍳⍺
: indeks znaku w ciągu.:
, będzie wynosił 1 lub 2 w zależności od wartości.2>⍴⍵:F,⍵
: Jeśli 2 jest większy niż bieżący rozmiar stosu, wystarczy dołączyć bieżącą wartość do stosu.⋄
: Inaczej,2↓⍵
: usuń dwa górne elementy ze stosu(
...)/2↑⍵
: zredukuj nad nimi daną funkcję i dodaj ją do stosu.⍎F⌷'+×'
: funkcją jest+
(dodawanie) lub×
(mnożenie), wybrane przezF
.⊃
: w końcu zwróć najwyższy przedmiot ze stosuźródło
Rubin - 96 znaków
Ten interesujący kawałek jest tutaj
eval
.Poza tym zakładam, że po pierwszym znaku stos będzie zawsze wynosił 2, matematyka, 2, matematyka ... To pozwala mi używać mniej kodu, chwytając dwa znaki jednocześnie - nigdy nie muszę myśleć czy postać jest matematyką czy liczbą. To jest pozycyjne.
Nie golfowany:
źródło
TI-BASIC,
7873706966 bajtówTI-BASIC jest dobry w liniach jednowarstwowych, ponieważ nawiasy zamykające są opcjonalne; i odwrotnie, jest to słaby język, w którym wymagane jest przechowywanie wielu wartości, ponieważ przechowywanie w zmiennej zajmuje dwa do czterech bajtów miejsca. Dlatego celem jest napisanie jak największej liczby wierszy. TI-BASIC jest także okropny (jak na język tokenizowany) przy manipulowaniu ciągami dowolnego rodzaju; nawet czytanie podciągów jest długotrwałe.
Sztuczki obejmują:
int(e^([boolean]
zamiast1+(boolean
; oszczędza jeden bajtźródło
".:.":prgmDOTTY
oszczędzając 4 bajty.1+(":"=sub(Ans,1,1
Udać się,
129115112 bajtów(nieco) niespokojny:
Wypróbuj online tutaj: http://play.golang.org/p/B3GZonaG-y
źródło
Python 3, 74
Najpierw przekształca listę wejściową w ciąg 1 i 2, przyjmując pierwszą wartość jako wartość początkową
x
. Następnie usuwa dwa elementy narazs
, biorąc pierwszy numer i albo dodając, albo mnożąc bieżący numer, w zależności od tego, czy drugi to 1, czy 2.źródło
to jest tak łatwa obsługa, wyrafinowana przez op (celowo)
to jest po prostu ...
Kod: C (80 bajtów)
wkład
długość = 2n + 1 wektor V typu char '. ” lub „:”
Wydajność
liczba całkowita k
Funkcjonować
Symulacja:
spróbuj tutaj
źródło
*(V-1)
) ma wartość zero?Retina,
181135129 bajtówKażda linia powinna znajdować się w osobnym pliku.
<empty>
reprezentuje pusty plik. Dane wyjściowe są w Unary.Gdy${0}1
jest używany, nawiasy klamrowe oddzielają się$0
od1
, w przeciwnym razie byłaby to$01
pierwsza pasująca grupa. Próbowałem użyć$001
, ale wydaje się, że nie działa w smaku regex .NET.Edycja: Znaleziono
$&
to samo co$0
.W pseudokodzie jest to w zasadzie pętla „do-while”, jak pokazano poniżej. Naciskam pierwszy numer, a następnie zapętlam: wciskam drugi numer, usuwam operację (instrukcję), wykonuję matematykę, usuwam op. Kontynuuj zapętlanie. Zauważ, że kiedy operacja zostanie wyświetlona, spowoduje to również usunięcie spacji po wykonaniu wszystkich instrukcji.
Skomentowano:
źródło
(:)(.*)
->$1$2
jestem pewien, że może to być po prostu(:.*)
->$1
(ponieważ utrzymujesz obie grupy w tej samej kolejności i nie robisz z nimi nic innego ).Python 3, 122 bajty
Nie golfowany:
W Pythonie odwołujesz się do indeksu takiej listy:
Możesz w to wstawić wartość boolowską,
True
jest1
iFalse
jest0
.Wypróbuj online tutaj
źródło
Perl, 77 bajtów
rozszerzony:
@o
Tablica odwzorowuje cyfry operatorów. Następnie zastępujemy pary cyfr odpowiednim operatorem, zamienionym na infix. Wyrażenie regularne zaczyna się od,\B
więc nie dopasowujemy pierwszej postaci. Wyniks///g
mówi nam, ile otwartych parenów potrzebujemy na początku. Następnie, po skompletowaniu wyrażenia pełnej poprawki, możemy go ocenić. (Usuń,eval
jeśli chcesz zobaczyć wyrażenie).Oto uprząż testowa, której użyłem do weryfikacji wyników:
Dane wejściowe to lista wyrażeń kropkowych i ich wartości (podanych w pytaniu), a dane wyjściowe to pary {faktyczne, oczekiwane}.
źródło