Dylemat kuratora

9

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ć ipermutację według porządku leksykograficznego obrazów.

Twój program musi wyprowadzić tę permutację w dowolnym rozsądnym formacie: np . abbccdLub [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
Alexander Craggs
źródło
1
Mówisz: „wszystkie elementy wyglądają dokładnie tak samo”. Czy masz na myśli „wszystkie utwory danego artysty wyglądają dokładnie tak samo, ale utwory różnych artystów wyglądają inaczej”?
DavidC
To nie byłby prawidłowy wpis, ale myślę, że nadal może być przydatny dla kogoś: {:A.a.{~97+[:I.}:jest poprawny J i działa, ale używa A.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ź.
4ıʇǝɥʇuʎs,
@ ɐɔıʇǝɥʇuʎs - Nie musisz używać „ABCD”, możesz w ogóle użyć dowolnego systemu znakowego / numerycznego / symbolicznego. Obawiam się, że nie znam J, więc nie mogę powiedzieć dokładnego problemu, ale mam nadzieję, że to pomoże =)
Alexander Craggs
@PopeyGilbert Cóż, wersja, która po prostu wyrzuca liczby, byłaby {:A.[:I.}:... Chodzi o to, ale nadal nie sądzę, A.aby była poprawna: jsoftware.com/help/dictionary/dacapdot.htm
4ıʇǝɥʇuʎs
Co jeśli wymagana permutacja nie istnieje? 1 0 0 0 100?
edc65

Odpowiedzi:

5

Python 2: 175 163 znaków

To 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).

f=lambda x:0**x or x*f(x-1)
def g(Q,n):
 while sum(Q):
  for j in 0,1,2,3:
   p=f(sum(Q)-1)*Q[j]
   for k in Q:p/=f(k)
   if p<n:n-=p
   else:print j;Q[j]-=1;break

Stosowanie:

g([1, 4, 3, 2], 65)

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

Lu*GhHUb1WsPQV4J*@QNytsPQFZPQ=J/JyZ)I<JeQ XQ4-eQJ)EN XQNt@QNB

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.

Lu*GhHUb1    def y(b): G=1; for H in range(b): G*= H+1; return G

Także rzeczy takie Q[j]-=1są 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.

Jakube
źródło
To działa! Gratulujemy wprowadzenia pierwszego rozwiązania Python! Odkryłem jednak, że w moim środowisku muszę wyjść from math import*poza tę funkcję. Dodając cię do tabeli liderów!
Alexander Craggs,
Wow ... Twoje rozwiązanie jest niesamowicie wydajne - w przypadku 32 obrazów zajmuje to tylko 0,034 sekundy o.0.
Alexander Craggs,
3

CJam, 50 43 39 bajtów

q~(])\{W):Wa*}%s:X{Xm*:s_&}X,(*{$X=},$=

Można w to dużo grać w golfa.

Pobiera dane wejściowe ze STDIN w następującym formacie:

4 1 2 0 24

Wysyła obraz. Na przykład dla powyższego wejścia:

0020210

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

Optymalizator
źródło
Gratulacje z okazji pierwszego rozwiązania! 50 bajtów to z pewnością trudna do pokonania wartość. Dodam cię jako szczyt tabeli liderów!
Alexander Craggs
@PopeyGilbert powinieneś przynajmniej poczekać około tygodnia przed zaakceptowaniem odpowiedzi
Optimizer
Ach, okej, bardzo przepraszam! W poprzednim wyzwaniu zmieniłem tylko zaakceptowaną odpowiedź, gdy ktoś został pokonany. Mój błąd.
Alexander Craggs
1
@PopeyGilbert To bardzo szlachetne z twojej strony (i żałuję, że wszyscy autorzy pretendentów zrobili to), i zasadniczo nie ma nic złego w wcześniejszym przyjęciu, jeśli tak, ale niektórzy ludzie wydają się obrażeni, jeśli wyzwanie tutaj przyjmie odpowiedź wcześnie (ponieważ, ja chyba nikt nie oczekuje, że autor zmieni przyjętą odpowiedź).
Martin Ender
Osobiście uważam, że przed zaakceptowaniem powinny być co najmniej 2 odpowiedzi, nawet jeśli zrobiono to wcześniej. Oczywiście, jeśli jest tylko jedna odpowiedź do około tygodnia, zaakceptuj ją.
Optymalizator
3

JavaScript (ES6) 120 138 147

Jako 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)

F=(w,x,y,z,n)=>{
  for(a=0;n;n-=l=='0,0,0,0')
    for(l=[w,x,y,z],t=w+x+y+z,v='',b=a++;t--;b/=4)--l[d=b&3],v=d+v;
  console.log(v)
}

Niegolfowany I nie wymaga FireFox

F=function(w,x,y,z,n) {
  for(a=0; n; a++) // exit when solution found (if wrong parameters, run forever)
  {
    l=[w,x,y,z]; // required number of each symbol
    t=w+x+y+z; // total of digits
    v=''; // init output string
    for(b=a;
      t--; // digit count down
      b >>= 2) // shift for next digit
    {
        d = b & 3; //get digit
        --l[d]; // decrement for the current digit
        v = d + v; // add to output string         
    }
    l[0]|l[1]|l[2]|l[3] // if digits ok
    ||--n // decrement counter
  }
  console.log(v) // when found, exit for and print the answer
}

Testuj w konsoli FireBug / FireFox

F(1, 2, 4, 1, 5) 
F(2, 2, 3, 1, 86)
F(4, 1, 2, 0, 24)
F(1, 4, 3, 2, 65)

Wynik

01132222
01120232
0020210
0112113232
edc65
źródło
Dzień dobry! Mam trochę problemów z uruchomieniem go. Pobieram FireFox, aby zobaczyć, czy to pomoże. Dodam cię do tabeli liderów!
Alexander Craggs
Znalazłem dość przyjemny stolik tutaj - będę zakładać Firefox jest konieczne. Przetestowane i działa! Zmieniono tabelę wyników na potwierdzoną.
Alexander Craggs
Tabela liderów, ale bez entuzjazmu ... naprawdę to nie lubisz! :(
edc65
Agh! Tak mi przykro = (Teraz głosowano =)
Alexander Craggs
Zastanawiam się, jak długo ten algorytm będzie w CJam. Ale na razie nie mam pojęcia, jak to działa: P
Optimizer
2

Pyth , 20 lat

@fqPQm/TdU4^U4sPQteQ

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:

@fqPQm/TdU4^U4sPQteQ
           ^U4sPQ         All permutations of [0, 1, 2, 3] with length equal to the number
                          of paintings.
     m/TdU4               Find the count (/) of paintings by painter in the input list.
 fqPQ                     Filter the permutations on the counts being the desired counts
                          in the input.
                          This gives all possible orderings of the paintings.
@                teQ      Index into this list at the given location - 1. (0-indexing)
isaacg
źródło