Worek , zwany także multiset, to nieuporządkowana kolekcja. Możesz nazwać to zestawem, który pozwala na duplikaty, lub listą (lub tablicą), która nie jest uporządkowana / indeksowana. W tym wyzwaniu zostaniesz poproszony o wdrożenie operacji worka: test dodawania, różnicy, mnożenia, dzielenia, liczenia i równości.
Operacje
Określone operacje mogą nie być konwencjonalne.
- dodatek łączy dwie torby w jedną, zachowując całkowitą liczbę każdej wartości
[1,2,2,3] + [1,2,4] = [1,1,2,2,2,3,4]
- różnica usuwa z torby każdy element innej torby lub nic nie robi, jeśli nie ma takiego elementu
[1,2,2,4] - [1,2] = [2,4]
[1,2,3] - [2,4] = [1,3]
- mnożenie zwielokrotnia każdy element w torbie.
[1,2,3,3,4] * 3 = [1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]
2 * [1,3] = [1,1,3,3]
- podział jest rzadki: każdy n równych elementów umieszcza się w n równych nowych torbach, elementy, które nie mogą utworzyć grupy n, pozostają w torbie. Zwróć jedną z n nowych toreb.
[1,1,2,2,2] / 2 = [1,2]
[1,2,2,3,3,3] / 3 = [3]
- liczenie liczy, ile worków dzielnika można wyprodukować z worka dywidendy
[1,1,2,2,2,2,3,3,3] c [1,2,3] = 2
- test równości sprawdza, czy dwie torby mają taką samą liczbę każdego elementu
[1,2,2,3] == [3,2,1,2] = truthy
[1,2,3] == [1,2,2,3] = falsy
(można=
do tego również użyć )
Jeśli używasz własnych symboli dla operatorów, proszę podać.
Formaty
Torby będą wyświetlane jako listy formularza [1,1,2,3,4]
. Możesz użyć dowolnego nawiasu kwadratowego, a nawet cudzysłowów lub nic. int
Dla celów tego pytania elementy będą liczbami całkowitymi (matematycznie, niekoniecznie ). Torby nie muszą być sortowane.
Format wejściowy będzie dwie torby lub worka, a oznacza liczbę całkowitą, z operatorem. Możesz określić własny format, o ile zawiera on te trzy.
Format powinien być pojedynczy torba z tym samym formacie.
Zasady
- nie możesz używać wbudowanych funkcji, operacji lub bibliotek (w tym biblioteki standardowej), które już je implementują; można jednak stosować łączenie i mnożenie listy, ponieważ są one z definicji operacjami na liście, a nie operacjami workowania (które w zasadzie robią to samo)
- obowiązują standardowe luki
- najkrótsza odpowiedź wygrywa
Przypadki testowe
[1,2,2,3] + [1,2,4]
[1,1,2,2,2,3,4]
[1,2,2,4] - [1,2]
[2,4]
[1,2,3] - [2,4]
[1,3]
[1,2,3,3,4] * 3
[1,1,1,2,2,2,3,3,3,3,3,3,4,4,4]
2 * [1,3]
[1,1,3,3]
[1,1,2,2,2] / 2
[1,2]
[1,2,2,3,3,3] / 3
[3]
[1,1,2,2,2,2,3,3,3] c [1,2,3]
2
[3,2,1,2] == [1,2,2,3]
truthy
[1,2,3] == [1,2,2,3]
falsy
źródło
Odpowiedzi:
05AB1E,
9287838277 bajtówPodziel według operacji
Wyjaśnienie
Dodanie
Umieść jedną torebkę w drugiej i spłaszcz je do jednej torebki.
Mnożenie
Upewnij się, że liczba znajduje się na górze stosu. Nazwij to X.
Duplikuj torbę X razy i dołącz do jednej torby.
Liczyć
Dla każdego elementu w worku z dzielnikiem policz liczbę wystąpień w worku z dywidendą.
Minimalna liczba to liczba worków, które możemy wykonać.
Równość
Posortuj obie torby i sprawdź, czy są równe.
Podział
Policz, ile razy każdy unikalny element występuje w torbie.
Jeśli występuje co najmniej tyle razy, co dzielnik. Zachowaj kopie (nr_of_copies_total // divisor) w torbie.
Różnica
Dla każdego elementu w subtrahend, posortuj go na przód minuend.
Jeśli bieżący poddźwięk jest równy pierwszemu elementowi w menu, usuń go z menu.
źródło
APL (155)
To definiuje
∆
„torbę” operatora , która definiuje operacje worka dla danych funkcji. To znaczy+∆
Byłby dodatkiem. Następnie odczytuje wiersz z klawiatury i ocenia go jako wyrażenie APL.Funkcje to:
+∆
, dodatek-∆
, odejmowanie×∆
, mnożenie÷∆
, podział⊂∆
, licząc≡∆
, równoważność (choć ze względu na grę w golfa dowolna nierozpoznana funkcja wykona równoważność)Wyjaśnienie:
∆←{
...}
: zdefiniuj operatora∆
:O←⍺⍺
: zapisz daną funkcję wO
(⎕CR
nie będzie działać⍺⍺
bezpośrednio)O←⎕CR'O'
: pobierz ciąg reprezentujący tę funkcję'+'=O
...:
: do dodania,⍺,⍵
: połącz obie listy razemR[⍋R←
...]
: i posortuj wynik'-'=O:
: do odejmowania,⍺{
...}⍵
: uruchom następującą funkcję rekurencyjną:⍵≡⍬:⍺
: jeśli subtrahend jest pusty, zwróć minuend⍺/⍨(⍳⍴⍺)≢⍺⍳⊃⍵∇1↓⍵
: w przeciwnym razie usuń pierwszy element subtrahend z subtrahend i minuend i spróbuj ponownie(⍬=⍴⍵)∧K←'×'=O:
do mnożenia i jeśli właściwy argument nie jest torbą:⍵/⍺
: skopiuj każdy element w lewym argumencie przez prawy argumentK:
: ... a jeśli właściwym argumentem jest torba:⍺/⍵
: replikuj każdy element w prawym argumencie przez lewy argument (jest to tak, że mnożenie jest przemienne)'÷'=O:
: dla podziału,⍵≤⍺∘.+⍺
: zobacz, które elementy w ⍺ występują co najmniej ⍵ razy,⍺/⍨
: wybierz te z ⍺,∪
: i usuń wszystkie duplikaty z tej listy'⊂'=O:
: do liczenia,⍵{
...}⍺
: uruchom następującą funkcję rekurencyjną:(∪⍺)≢∪⍵:0
: jeśli jedna lista zawiera elementy, a druga nie, wynik to 01+⍺∇⍵-∆⍺
: w przeciwnym razie odejmij dywidendę od dzielnika, spróbuj ponownie i zwiększ wynik.⋄
: jeśli żaden z powyższych, nie wykonaj testu równoważności:⍺[⍋⍺]≡⍵[⍋⍵]
: posortuj obie listy i sprawdź, czy są równe⎕
: przeczytaj wyrażenie z klawiatury, oceń je i wyślij wynik.Przypadki testowe:
źródło
[2,2,2,2,2,2]/3
powinien dać[2,2]
, ale twój wydaje się dawać[2]
.∆
, użytkownik zostanie zrzucony do natywnej REPL APL, gdzie∆
jest teraz poprawny. Myślę, że możesz zaoszczędzić kilka bajtów, przesuwając odejmowanie do końca, ponieważ jest to jedyny, który wymaga dwóch linii. Zamiast⎕CR
, użyj,*
aby symbolizować liczenie, i wykonajO←⍺⍺2
, a następnie2=O:
dla plus,1=O
dla mult,0=O:
dla equiv,7<O:
dla count i0<O:
dla div (z implikacją0>O:
dla subtr).JavaScript (ES6), 260 bajtów
Zajmuje 3 parametry. Pierwszy parametr to tablica, drugi to operator, trzeci zależy od operatora. Torby są potrzebne do przechowywania liczb całkowitych nieujemnych.
Nie golfowany:
źródło
Oktawa,
253244226 bajtówTa funkcja musi znajdować się w pliku. Aby zapisać funkcję w oknie poleceń, musisz użyć
endfunction
lubend
.Podziękowania dla Luisa Mendo za zaoszczędzenie 18 bajtów.
Operacje to:
Przykład użycia:
Nie golfowany:
źródło
Matematyka,
387347300284 bajtyNieznacznie zdezelowany (czyli stara wersja), nie miał pełnego wsparcia dla testów równości (zwrócił prawdziwe wartości, ale pozostawił nieocenione dla niepasujących toreb).
Implementuje wymagany typ danych za pomocą head
b
.Pierwsza
b
jest zdefiniowana jakoOrderless
. Każdy obiekt przekazany do jądra z headb
automatycznie posortuje swoje argumenty. Więc nawet jeślib[3,2,1]
zostanie wpisany, oceniający nigdy nie zobaczy niczego innegob[1,2,3]
.Dodawanie jest trywialnie zdefiniowane jako łączenie elementów.
Określono specjalną zasadę dotyczącą różnicy między dwoma workami (wyjaśniono poniżej). Poprzednia wersja miała symbol pomocniczy dla wyrażeń formy
-bag
.Następnie mnożenie (tak długo, jak długo
n
jest liczbą całkowitą dodatnią) jest rekurencyjnie definiowane jako,n*b[...] = b[...] + (n-1)*b[...]
które ostatecznie zredukuje się do prostej sumy.Specjalna reguła dla
b[...] - b[...]
zlicza liczbę odrębnych elementów w sumie worków i odejmuje torbę, która ma zostać odjęta dwukrotnie od tego wyniku. Łatwiej wyjaśniono:Powyżej znajduje się lista
Keys->Values
.KeyValueMap
zTable
tworzy listy za każdymKey
Value
razem. (istnieje równieżMax[...,0]
możliwość nie tworzenia tabel o ujemnej długości). Wydaje się to jako:który jest spłaszczony, a głowa
List
zastąpiona przezb
.Podział według liczb całkowitych jest nieco podobny w użytych funkcjach, jest to po prostu dzielony podział elementu zliczony przez liczbę całkowitą.
Dzielenie według zbiorów lub liczenie Zmieniłem od czasu oryginalnej implementacji. Odbywa się to teraz rekurencyjnie w następujący sposób. Powiedzmy, dzielimy torbę
b1
przezb2
(które w kodzie golfowym sąc
ia
odpowiednio. W przypadku(b1-b2) + b2 == b1
, a następnie dodanie 1 i dodać do tego w wyniku podziału(b1-b2)/b2
. Jeżeli nie, to zwraca 0 i wyjście rekursji.Jeśli torby pasują, wbudowany
==
dajeTrue
. Ostatnia linia wymusza „a”,False
jeśli nie.Przypadki testowe:
źródło
Q - 219 znaków
a
do dodania,s
dla różnicy (odejmowania),m
do mnożenia,d
do dzielenia,c
dla liczenia,e
dla równości.Algorytm dodawania jest oczywisty, wystarczy połączyć torby.
Funkcja odejmowania indeksuje w torbie wejściowej (reprezentowanej jako tablica) z całym zakresem indeksów, z wyjątkiem pierwszych
n
indeksów każdej klasy równoważności utworzonych przez równość z każdym elementem wy
, gdzien
jest liczba kopii tego reprezentanta wy
. Obsługa możliwych duplikatówy
sprawia, że jest to prawdziwy potwór funkcji.Funkcja mnożenia pobiera
x
wartości z każdego z nichy
, w przypadku, gdyy
jest to pojedyncza wartość, zamiast tablicy, po prostu je replikuje.Funkcja podziału generuje wartości, których liczba w tablicy jest większa niż
y
, a następnie usuwa duplikaty.Funkcja zliczania oblicza liczbę każdego elementu
y
, a następnie zwraca minimum.Dwie torby są równe, jeśli ich reprezentacje w sortowanej tablicy są równe.
źródło
Ruby, odpowiedź na definicję klasy,
323291 bajtówPrzede wszystkim chciałem stworzyć
Bag
prawdziwą klasę ze względu na elastyczność Ruby w stosunku do klas. W tym przypadku dziedziczy po,Array
ponieważ jest krótszy niż konieczność inicjowania wewnętrznej tablicy i radzenia sobie z innymi rzeczami.Prawdopodobnie zrobię poważniejszą odpowiedź na golfa, która wykorzystuje funkcję do radzenia sobie z operacjami jutro. Jestem bardzo zmęczony i bawiłem się z tym zbyt dobrze,
mimo że musiałem wdawać się w definicję klasynumerycznej,Number * Bag
abydziałać poprawnieWYRAŻAJ FUNKCJĘ WYSOKOŚCI, ABY ZROBIĆ TO, ABY NIE POTRZEBOWAŁO POMYŚLENIA DEFINICJI KLASY NUMERYCZNEJWypróbuj online! (Białe znaki nie mają znaczenia w Ruby, więc kod jest tam nieco nieoznaczony.)
źródło
Ruby, 201 bajtów
Jak obiecałem w mojej drugiej odpowiedzi, oto jedna, która używa funkcji zamiast budowania nowej klasy. Jestem tak blisko przekroczenia znaku 200 bajtów ... Wypróbuj online
Wykorzystuje to te same kody jak @Neil w odpowiedzi na JavaScript i tę samą kolejność argumentów (lhs, opcode, rhs)
Kod:
źródło
C ++,
555551 bajtów(dodano podział wierszy dla czytelności - wymagany i liczony jest tylko pierwszy znak nowej linii)
Wyjaśnienie
Wdrażamy naszą torbę jako mapę (wartości, liczby). Podstawowe operacje można wdrożyć, manipulując licznikami; odejmowanie i dzielenie liczb całkowitych również muszą usuwać wszystkie elementy, których liczba osiąga zero, aby
std::map::operator==
działało to jako test równości.Poniższy rozszerzony kod jest ogólną wersją powyższego, o wiele mniej golfa: używamy osobnego
s()
do wyciskania wartości zerowych i implementujemyconst
operacje w zakresie operatorów przypisania w idiomatyczny sposób C ++. Używamy równieżs()
do pomnożenia przez0
zwrócenie naprawdę pustej torby (testowane przez dodanie(B{1}*0 != B{})
domain()
); oryginał nie przejdzie tego testu i nie jest jasne, czy jest to wymóg.Testy
źródło
Python 2.7 - 447B (rozmiar pliku)
To moja pierwsza próba w Codegolf, mam nadzieję, że się spełni. Potrzebowałem 2h. (Ale wciąż jestem początkującym w Pythonie)
Edycja: Podziękowania dla „Kevina Lau - nie Kenny'ego” za wskazanie:
Edycja: Dodatkowo zaoszczędziłem miejsce, zastępując funkcje lambdami, nowe linie i wcięcia większą liczbą średników.
Kod:
czeki:
Wynik:
Mógłbym kiedyś spróbować z ustawioną podstawą. Edycja: Może nawet spróbuję tylko z funkcjami.
źródło
self
- coś podobnego teżS
by działało . Inną sztuczką jest to, że wbudowanasorted
funkcja robi dokładnie to, co chcesz z nowej funkcjis
, więc możesz zrezygnować z definicji funkcji (ponieważ używasz jej tylko raz). Nigdy nie potrzebujesz,__radd__
ponieważ nigdy nie dodajesz torebek innych niż torby, chociaż nadal potrzebujesz__rmul__
. Na koniec potrzebujesz tylko jednego miejsca wcięcia zamiast czterech, co znacznie zmniejsza liczbę bajtów