Wprowadzenie
Jesteś przyjacielem kustosza muzeum sztuki, który ostatnio czerpał przyjemność z otrzymywania sztuki nowoczesnej od czterech artystów ( z których niektórzy mogą dać kustoszowi zero dzieł sztuki, młodych łotrów ). Ponieważ jest to sztuka współczesna, wszystkie dzieła danego artysty wyglądają dokładnie tak samo. Twój przyjaciel chce użyć komputera, aby zdecydować, w której kolejności umieścić te elementy.
Wymagania programowe
Twój program musi przyjąć pięć liczb całkowitych (przekazanych do funkcji lub wprowadzonych przez stdin (lub w jakiś inny sposób)). Pierwsze cztery to liczba obrazów dostarczonych przez każdego z czterech artystów. Ostatnia wartość to indeks permutacji i
(liczony od 1, a nie 0). Kurator chce zobaczyć i
permutację według porządku leksykograficznego obrazów.
Twój program musi wyprowadzić tę permutację w dowolnym rozsądnym formacie: np . abbccd
Lub [0 1 1 2 2 3]
. Środowisko wykonawcze dla danych wejściowych wynoszące mniej niż dziesięć obrazów musi zająć mniej niż godzinę (mam nadzieję, że nie powinno to stanowić problemu).
Nie wolno używać żadnych wbudowanych funkcji do obliczania permutacji
Przykłady
Wejście: 0 1 2 0 2
Biorąc pod uwagę, że mamy jeden obraz artysty B i dwa artysty C (i wszystkie wyglądają tak samo), permutacje w porządku leksykograficznym to:
[„bcc”, „ cbc ”, „ccb”]
Podświetlona permutacja byłaby prawidłowym wyjściem, ponieważ jest to druga w kolejności leksykograficznej.
Wejście: 1 2 0 1 5
[„abbd”, „abdb”, „adbb”, „babd”, „ badb ”, „bbad”, „bbda”, „bdab”, „bdba”, „dabb”, „dbab”, „dbba”]
Testowanie
Oto kilka testów, które powinny być poprawne.
1 2 4 1 5 - ABBDCCCC
2 2 3 1 86 - ABBCACDC
4 1 2 0 24 - AACACBA
1 4 3 2 65 - ABBCBBDCDC
Krótki fragment kodu w Python3, który powinien losowo generować dane wejściowe i wyjściowe, jest dostępny tutaj (niepoprawny dla wpisu, używa importu permutacji w Pythonie):
from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))
Tablica wyników
Optimizer - CJam - 39 - Confirmed - Bruteforce
EDC65 - JavaScript - 120 - Confirmed - Bruteforce
Jakube - Python2 - 175 - Confirmed - Algorithmic
źródło
{:A.a.{~97+[:I.}:
jest poprawny J i działa, ale używaA.
przez większość pracy, więc nie jest prawidłowy. Gdybyś mógł napisać funkcję, która zastąpi jąA.
i zastąpi w tej funkcji, uzyskałbyś poprawną odpowiedź.{:A.[:I.}:
... Chodzi o to, ale nadal nie sądzę,A.
aby była poprawna: jsoftware.com/help/dictionary/dacapdot.htmOdpowiedzi:
Python 2:
175163 znakówTo nie jest poważna odpowiedź na golfa. Z innym algorytmem osiągnąłem 138 bajtów. Chciałem to tutaj opublikować, ponieważ nie używa brutalnej siły. Złożoność to Theta (# zdjęcia).
Stosowanie:
edytować:
Ten sam algorytm, tylko niektóre gry w golfa: nie importuj metody czynnikowej i drobnych zmian w kolejności obliczeń.
Tłumaczenie Pyth: 61 znaków
Nic specjalnego tutaj, dokładne tłumaczenie mojego kodu python. Jednak zdecydowanie za długo. Użyłem też kilku brzydkich (długich) rzeczy. Pierwsze 9 liter jest definicją silni.
Także rzeczy takie
Q[j]-=1
są o wiele za długie:XQNt@QN
(1 znak więcej niż Python !!!)Stosowanie:
Wypróbuj tutaj: Pyth Compiler / Executor . Wyłącz tryb debugowania i użyj
[2, 2, 3, 1, 86]
jako danych wejściowych.źródło
from math import*
poza tę funkcję. Dodając cię do tabeli liderów!CJam,
50 4339 bajtówMożna w to dużo grać w golfa.
Pobiera dane wejściowe ze STDIN w następującym formacie:
Wysyła obraz. Na przykład dla powyższego wejścia:
Wypróbuj online tutaj
Pamiętaj, że internetowy kompilator rezygnuje z większych rozmiarów obrazów. Będziesz musiał wypróbować większe dane wejściowe w wersji Java
źródło
JavaScript (ES6) 120
138 147Jako funkcja z wymaganymi pięcioma parametrami, wyjście przez konsolę.
Używanie symboli 0,1,2,3. Obliczam sumę symboli, a następnie buduję i sprawdzam każdą podstawową liczbę 4 mającą wymaganą liczbę cyfr. Liczby z niewłaściwą liczbą dowolnej cyfry są odrzucane.
Uwaga: w przypadku 32-bitowej liczby całkowitej JavaScript działa to maksymalnie dla 15 obrazów.
Edytuj Krótszy (unikaj .toString) i znacznie szybszy (zmodyfikowany warunek wyjścia). Czas na każdy test poniżej 1 sek.
Edycja2 bez zmiany algorytmu, więcej golfa (dodano wcięcie dla czytelności)
Niegolfowany I nie wymaga FireFox
Testuj w konsoli FireBug / FireFox
Wynik
źródło
Pyth , 20 lat
Wypróbuj tutaj.
Dane wejściowe są w formie listy Python, np
[1, 2, 4, 1, 5]
Dane wyjściowe mają również postać listy w języku Python, np.
[0, 1, 1, 3, 2, 2, 2, 2]
Dla powyższych danych wejściowych.Rozwiązaniem jest brutalna siła, co w najgorszym przypadku zajmuje około 10 sekund na moim komputerze.
Jak to działa:
źródło