17
\$\begingroup\$

Background

The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not possible to pay certain amounts, like 4 foos, using these coins. Nevertheless, all large enough amounts can be formed. Your job is to find the largest amount that can't be formed with the coins (5 foos in this case), which is known as the coin problem.

Input

Your input is a list L = [n1, n2, ..., nk] of positive integers, representing the values of coins in circulation. Two things are guaranteed about it:

  • The GCD of the elements of L is 1.
  • L does not contain the number 1.

It may be unsorted and/or contain duplicates (think special edition coins).

Output

Since the GCD of L is 1, every large enough integer m can be expressed as a non-negative linear combination of its elements; in other words, we have

 m = a1*n1 + a2*n2 + ... + ak*nk 

for some integers ai ≥ 0. Your output is the largest integer that cannot be expressed in this form. As a hint, it is known that the output is always less than (n1 - 1)*(nk - 1), if n1 and nk are the maximal and minimal elements of L (reference).

Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. If your language has a built-in operation for this, you may not use it. There are no requirements for time or memory efficiency, except that you should be able to evaluate the test cases before posting your answer.

After I posted this challenge, user @vihan pointed out that Stack Overflow has an exact duplicate. Based on this Meta discussion, this challenge will not be deleted as a duplicate; however, I ask that all answers based on those of the SO version should cite the originals, be given the Community Wiki status, and be deleted if the original author wishes to post their answer here.

Test Cases

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49
\$\endgroup\$
  • 4
    \$\begingroup\$ FrobeniusNumber in Mathematica. \$\endgroup\$ – alephalpha Sep 6 '15 at 16:30
  • \$\begingroup\$ @alephalpha Good catch, I had forgotten to disallow built-ins. \$\endgroup\$ – Zgarb Sep 6 '15 at 16:32
  • 2
    \$\begingroup\$ There is a way better upper bound, found in this paper that establishes (p - 1)(q - 1) as the upper bound, where p and q are the smallest and biggest element of the set. \$\endgroup\$ – orlp Sep 6 '15 at 16:58
  • 2
    \$\begingroup\$ Are there any limits of run time or memory usage? \$\endgroup\$ – Dennis Sep 6 '15 at 17:01
  • \$\begingroup\$ On Stack Overflow there was a code golf question like this a while back \$\endgroup\$ – Downgoat Sep 6 '15 at 17:39
2
\$\begingroup\$

Pyth, 23 bytes

ef!fqTs.b*NYQY^UTlQS*FQ

It's very slow, as it checks all values up to the product of all the coins. Here's a version that is almost identical, but 1) reduces the set of coins to those not divisible by each other and 2) only checks values up to (max(coins) - 1) * (min(coins) - 1) (47 bytes):

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

Explanation

                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element
\$\endgroup\$
6
\$\begingroup\$

Perl, 60 54 51 bytes

50 bytes code + 1 bytes command line

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Will carry on golfing and post an explanation later. The basic approach is to let the regex engine do the hard work with string matching. For example, it will construct a regex similar to ^(.{3})*(.{7})*(.{8})*$ and match against a string of length n where n descends from the product of the inputs until it fails to match.

Note that this will become exponentially slow as the number of arguments increases.

Usage: Arguments are read in from STDIN (new line separated), for example:

printf "101\n10" | perl -p entry.pl
\$\endgroup\$
1
\$\begingroup\$

Python2, 188 187 bytes

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

The second indentation is rendered as 4 spaces on SO, those should be tabs.

Actually a 'fast' solution, not bruteforce, uses 'Wilf's Method' as described here.

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

Javascript ES6, 120 130 126 128 127 125 chars

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

Alternative 126 chars version:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

Test:

"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})
\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace the forEach( with map( \$\endgroup\$ – Ypnypn Sep 7 '15 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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