Jak poprosić kasjera o pieniądze w banku?

35

Muszę iść do banku i wypłacić trochę pieniędzy. Muszę wypłacić 30 USD, 22 USD, aby zapłacić współlokatorowi za Internet i 8 USD za pranie. Ponieważ żadna z nich nie może zmienić, potrzebuję 30 USD na podzielenie na dwie partie dwóch rozmiarów. Oznacza to, że kiedy kasjer zapyta mnie, jak chcę moje 30 USD, będę musiał złożyć wniosek. Mogę im powiedzieć, że chcę za dwadzieścia, piątkę i pięć. Ale chcę, aby moja prośba była jak najprostsza, aby uniknąć konieczności powtarzania się. Aby uprościć moją prośbę, mógłbym poprosić o to, aby moja gotówka zawierała dwadzieścia i co najmniej 2, ponieważ 8 wynika z sumy, ale jeszcze lepiej mogę po prostu poprosić, aby jeden z rachunków, który otrzymam, był rachunkiem za jeden dolar (jeśli nie są do tego przekonani, po prostu spróbuj zarobić 29 dolarów bez zarabiania 8).

Więc to wszystko w porządku i elegancko, ale muszę przeprowadzać te obliczenia za każdym razem, gdy idę do banku, więc pomyślałem, że napiszę program, który to zrobi (czy napiszesz program, który to dla mnie zrobi).

Twój program lub funkcja powinna wziąć listę liczb całkowitych reprezentujących wszystkie płatności, które muszę dokonać, oraz zestaw liczb całkowitych reprezentujących nominały rachunków dostępnych w banku, i musisz podać najmniejszą listę nominałów, tak aby każdy sposób na sumę obejmuje to, że listę nominałów można jednoznacznie podzielić na listę płatności.

Dodatkowe zasady

  • Możesz założyć, że lista nominałów zawsze będzie zawierać a 1lub możesz dodać ją do każdej listy samodzielnie.

  • Niektóre dane wejściowe będą miały wiele minimalnych rozwiązań. W takich przypadkach możesz wypisać jedno z nich.

To jest więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

Payments, denominations    -> requests
{22,8}    {1,2,5,10,20,50} -> {1} or {2}
{2,1,2}   {1,5}            -> {1}
{20,10}   {1,2,5,10,20,50} -> {}
{1,1,1,1} {1,2}            -> {1,1,1}
{20,6}    {1,4,5}          -> {1}
{2,6}     {1,2,7}          -> {2}
{22, 11}  {1, 3, 30, 50}   -> {1, 3}
{44, 22}  {1, 3, 30, 50}   -> {1, 3, 3, 30}
Kreator pszenicy
źródło
22
Na początku myślałem, że to spam, nie na temat lub coś w tym stylu ...
Erik the Outgolfer
1
@EriktheOutgolfer akapity tak bardzo bolą wyzwania> _ <
Magic Octopus Urn
2
Myślę, że powinieneś dołączyć co najmniej jeden przypadek testowy, w którym żądanie musi dotyczyć czegoś innego niż banknoty za jednego dolara {2,6} {1,2,7} -> {2}.
Arnauld
@Arnauld Dodałem twoją skrzynkę
Wheat Wizard
1
(If you are not convinced of this just try to make 29 dollars without making 9)Masz na myśli bez robienia 8? I nie rozumieją lub nie
undergroundmonorail

Odpowiedzi:

5

JavaScript (ES6), 485 476 bajtów

W porządku ... to potwór. :-(
Ale to dość szybki potwór, który prawie natychmiast rozwiązuje wszystkie przypadki testowe.

Mogę później spróbować bardziej zaawansowanego golfa, ale spędziłem już o wiele za dużo czasu.

f=(b,a,L=[...a])=>L.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).sort((a,b)=>a[b.length]||-1).find(L=>(Y=G(U(b)-U(L),L.sort((a,b)=>a-b)),Y[0]&&!Y.some(a=>P(b.map(a=>G(a,[]))).every(b=>b+''!=a))),U=a=>~~eval(a.join`+`),P=(e,C=[],R=[])=>e[0].map(v=>R=(c=v.map((x,i)=>x+(C[i]|0)),e[1])?[...P(e.slice(1),c),...R]:[c,...R])&&R,G=(n,l)=>(S=[],g=(n,l)=>n?a.map(x=>x<l[0]|x>n||g(n-x,[x,...l])):S=[l.map(v=>s[a.indexOf(v)]++,s=[...a].fill(0))&&s,...S])(n,l)&&S)||f(b,a,[...a,...L])

Przypadki testowe

W jaki sposób?

Uwaga: To nie jest już zgodne z bieżącą wersją, ale jest o wiele łatwiejsze do odczytania w ten sposób.

// b = list of payments, a = list of bills,
// L = list from which the requested bills are chosen
f = (b, a, L = [...a]) => (
  // U = helper function that computes the sum of an array
  U = a => ~~eval(a.join`+`),

  // P = function that computes the summed Cartesian products of arrays of integers
  // e.g. P([[[1,2],[3,4]], [[10,20],[30,40]]]) --> [[33,44], [13,24], [31,42], [11,22]]
  P = (e, C = [], R = []) => e[0].map(v => R =
    (c = v.map((x, i) => x + (C[i] | 0)), e[1]) ? [...P(e.slice(1), c), ...R] : [c, ...R]
  ) && R,

  // G = function that takes a target amount and a list of requested bills and returns
  // all combinations that contain the requested bills and add up to this amount;
  // each combination is translated into a list of number of bills such as [2,0,0,1,0]
  G = (n, l) => (
    S = [],
    g = (n, l) => n ?
      a.map(x => x < l[0] | x > n || g(n - x, [x, ...l])) :
      S = [l.map(v => s[a.indexOf(v)]++, s = [...a].fill(0)) && s, ...S]
  )(n, l) && S,

  // compute X = list of possible bill combinations to process all payments
  X = P(b.map(a => G(a, []))),

  // compute the powerset of L and sort it from shortest to longest list
  L.reduce((a, x) => [...a, ...a.map(y => [x, ...y])], [[]])
  .sort((a, b) => a[b.length] || -1)

  .find(L => (
    // compute Y = list of possible combinations to reach the total amount,
    // using the requested bills
    Y = G(U(b) - U(L), L.sort((a, b) => a - b)),

    // exit if Y is not empty and all combinations in Y allow to generate all payments
    Y[0] && !Y.some(a => X.every(b => b + '' != a)))
  )

  // if no solution was found, enlarge the set of requested bills and try again
  || f(b, a, [...a, ...L])
)
Arnauld
źródło
Nie znam się zbyt dobrze na javascript, ale czy można zredukować &&do &i ||do |?
Taylor Scott,
@TaylorScott Jest to możliwe tylko pod pewnymi warunkami. Na przykład, a || boceni btylko jeśli ajest fałszem, podczas gdy a | bbezwarunkowo wykona bitową operację OR pomiędzy ai b.
Arnauld,
4

Python 2 , 456 455 bajtów

Niezwykle, bardzo, bardzo wolno !!!! Powinien działać poprawnie na wszystkich przykładowych danych wejściowych, mając wystarczająco dużo czasu

Edycja: Zapisano 1 bajt dzięki @Jonathan Frech

def F(p,d):v=sum(p);E=enumerate;l=lambda x,y:y[1:]and(x>=y[-1]and[k+[y[-1]]for k in l(x-y[-1],y)]+l(x,y[:-1])or l(x,y[:-1]))or[[1]*x];Q=l(v,d);m=lambda x,y=[0]*len(p):x and max(m(x[1:],[a+x[0]*(i==j)for i,a in E(y)])for j,_ in E(y))or y==p;f=lambda x,h=[]:x and min([S for i,s in E(x)for S in h+[s],f(x[:i]+x[i+1:],h+[s])if all(map(m,filter(lambda k:all(k.count(j)>=S.count(j)for j in S),Q)))],key=len)or[1]*v;print-(all(map(m,Q))-1)*min(map(f,Q),key=len)

Wypróbuj online!

Wyjaśnienie

p,d=input() # Read input
v=sum(p) # Save a byte by keeping track of the total money withdrawn
E=enumerate # We use enumerate a lot
# Generates the possible combinations of denominators that add up to the withdrawn amount 
l=lambda x,y:y[1:]and(x>=y[-1]and[k+[y[-1]]for k in l(x-y[-1],y)]+l(x,y[:-1])or l(x,y[:-1]))or[[1]*x]
# We use the list generated by l quite a few times
Q=l(v,d)
# Checks if we can divide a list of denominators x in such a way that we get the wished division of the money
m=lambda x,y=[0]*len(p):x and max(m(x[1:],[a+x[0]*(i==j)for i,a in E(y)])for j,_ in E(y))or y==p
# For a list of denominators, it tries all possible combinations of the denominators as input to the teller, selecting the one with minimum length
f=lambda x,h=[]:x and min([S for i,s in E(x)for S in h+[s],f(x[:i]+x[i+1:],h+[s])if all(map(m,filter(lambda k:all(k.count(j)>=S.count(j)for j in S),Q)))],key=len)or[1]*v
# Call f with all possible lists of denominators, and check if saying nothing to the teller will work
print-(all(map(m,Q))-1)*min(map(f,Q),key=len)
Halvard Hummel
źródło
1
Korzystanie z funkcji aniżeli input()jest jeden bajt krótszy .
Jonathan Frech