15
\$\begingroup\$

There's a payment machine for laundry in my building which does a few frustrating things. The ones relevant to this challenge are:

  • It doesn't make change. So if you pay over the amount then you are not getting that over-payment back.
  • It doesn't accept coins smaller than 20c. Meaning the only coins it accepts are 20c, 50c, 1€ and 2€ (1€=100c).
  • The price of running one machine is 2.30€

The third item doesn't seem immediately frustrating, however if we take a look at all the ways to make 2.30€ we can see an issue:

2€ 1€ 50c 20c
0 1 1 4
0 0 3 4
0 0 1 9

You may notice that in order to pay 2.30€ you must have at least a 50c coin and four 20c coins. There's no way to substitute other coins in, if you show up and you don't have that combination of coins (plus extra coins to cover the remainder) you are going to have to overpay.

I'm very suspicious that the designers of the machine set the price this way just to make it look reasonable but force over-payment. I think most people end up paying 2.50€ because it's simpler or because their pocket change doesn't meet the stringent requirements to pay exactly 2.30€

To illustrate this hypothesis I have created a strictness index. To measure it you take all the ways you can make a particular price using the available coin set and for each coin type find the option that uses the least of that coin, record the number of that coin used and sum them all up.

If we use the example above, the strictness index is 0 + 0 + 1 + 4 = 5. In fact there is no possible price with a worse strictness index for this set of coins. 5 is the limit.

Not all prices have a strictness index, for example 1.97€ can't be made with the coins above so this procedure doesn't make sense. We just ignore these values, we only care about prices that are possible to make with the given coins.

Task

In this challenge you will take a set of positive integers representing coin values and calculate the maximum strictness index a price can have in this coin system.

The input set will always contain at least 2 values, there will never be duplicates and you may assume it is in strictly ascending or descending order.

This is so the goal is to minimize the size of your source code as measured in bytes.

Test cases

2 5 10 20 -> 5
2 3 -> 3
2 3 5 -> 2
1 8 -> 7
2 4 -> 2
\$\endgroup\$
2
  • \$\begingroup\$ Should [2,4] be handled? Jelly and Javascript answer timeout, though I don't know it's slow or infinite loop \$\endgroup\$
    – l4m2
    Dec 22, 2022 at 6:57
  • \$\begingroup\$ @l4m2 [2,4] should be handled. and if I'm correct the output should be 2 with strictness index 1. \$\endgroup\$
    – Wheat Wizard
    Dec 22, 2022 at 11:53

3 Answers 3

4
\$\begingroup\$

Jelly, 19 bytes

Œṗf³$ƑƇœ&/¹¡L
P!Ç€Ṁ

Try it online!

-1 thanks to Jonathan Allan.

Unlike Vyxal, Jelly's multiset intersection appears to work properly.

This is roughly \$O\left(2^{\left(\prod{s}\right)!}\right)\$. I'm pretty sure using caird's fork would save a few bytes but I can't be bothered for now.

P!Ç€Ṁ  Main link (takes a list of numbers)
P!     Factorial of product
   €   Map over 1...n
  Ç    Helper (see below)
    Ṁ  Take maximum

Œṗf³$ƑƇœ&/¹¡L  Helper link (takes argument n)
Œṗ             Integer partitions
      Ƈ        Filtered by...
    $Ƒ         Same under
  f³           Remove all but input
         /     Reduce by
       œ&      Multiset union
          ¹¡   N times
            L  Get final length
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The order notation given is also \$O\left(2^{\left(2^n\right)}\right)\$ where \$n\$ is the number of bits in the input. \$\endgroup\$
    – Wheat Wizard
    Jun 28, 2022 at 9:50
  • 1
    \$\begingroup\$ How about œ&/¹¡ in place of oؽœ&/? \$\endgroup\$ Jun 28, 2022 at 17:51
1
\$\begingroup\$

Python3, 551 bytes:

from itertools import*
def f(v):
 j,m=[],{}
 for I,n in enumerate(v):
  c=0
  while(c:=c+1):
   F,O=0,[]
   for j in permutations(Y:=[*(set(v)-{n})],len(Y)):
    s=c*n
    for i in j:s-=i*(s//i)
    if s>0:O+=[c];F=1
    else:O+=[0];F=0;break
   m[n]=max(O)if 0 not in O else(m[n]if n in m else 0)
   if F==0:break
 U,V=[],[i for i in m if m[i]]
 for i in range(1,len(V)+1):
  for j in combinations(V,i):
   n=sum(k*m[k]for k in j)
   if 0==any(any(0==(n-(t*(n//t)))%l and t*(n//t)for l in j)for t in {*v}-{*V}):U+=[sum(m[l]for l in j)]
 return max(U)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 143 bytes

with(Math)f=(a,i=0,t)=>!t&&(g=n=>n>0?min(...a.map(m=>(m==t)+g(n-m))):n&&1/0,g(i,s=0)||a.map(v=>s+=g(i,t=v)),max(s,f(a,i+1,a.map(v=>i/=v*v)|i)))

Try it online!

I hope the answer is correct although I cannot verify it by any larger testcases due to its terrible time complexity.

\$\endgroup\$
5
  • \$\begingroup\$ n&&1/0 => -n/!n \$\endgroup\$
    – l4m2
    Dec 22, 2022 at 6:46
  • \$\begingroup\$ Also how to prove the \$\prod a_i^2\$ upperbound? \$\endgroup\$
    – l4m2
    Dec 22, 2022 at 6:52
  • 1
    \$\begingroup\$ @l4m2 I had forgot the question. Maybe because for any price \$P=P_0+\text{lcm}(\vec{a})\$. You can first calculate the value for \$P_0\$. And you can use whatever coin to fit the following \$\text{lcm}(\vec{a})\$, the result is not greater than the \$P_0\$ \$\endgroup\$
    – tsh
    Dec 22, 2022 at 7:13
  • \$\begingroup\$ then why the square? \$\endgroup\$
    – l4m2
    Dec 22, 2022 at 7:25
  • \$\begingroup\$ @I4m2 I have no idea... (Maybe I had.) \$\endgroup\$
    – tsh
    Dec 22, 2022 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.