Code Golf: Frobenius Number

Question

Write the shortest program that calculates the Frobenius number for a given set of positive numbers. The Frobenius number is the largest number that cannot be written as a sum of positive multiples of the numbers in the set.

Example: For the set of the Chicken McNugget^TM sizes [6,9,20] the Frobenius number is 43, as there is no solution for the equation a*6 + b*9 + c*20 = 43 (with a,b,c >= 0), and 43 is the largest value with this property.

It can be assumed that a Frobenius number exists for the given set. If this is not the case (e.g. for [2,4]) no particular behaviour is expected.

References:

• http://en.wikipedia.org/wiki/Coin_problem
• http://mathworld.wolfram.com/FrobeniusNumber.html

[Edit] I decided to accept the GolfScript version. While the MATHEMATICA version might be considered "technically correct", it would clearly take the fun out of the competition. That said, I'm also impressed by the other solutions, especially Ruby (which was very short for a general purpose language).

Answer 1

Haskell 155 chars
The function f does the work and expects the list to be sorted. For example f [6,9,20] = 43

b x n=sequence$replicate n[0..x]
f a=last$filter(not.(flip elem)(map(sum.zipWith(*)a)(b u(length a))))[1..u] where
    h=head a
    l=last a
    u=h*l-h-l

P.S. since that's my first code golf submission I'm not sure how to handle input, what are the rules?

Answer 2

Haskell 153 chars

A different take on a Haskell solution. I'm a rank novice at Haskell, so I'd be surprised if this couldn't be shortened.

m(x:a)(y:b)
 |x==y=x:m a b
 |x<y=x:m(y:b)a
 |True=y:m(x:a)b
f d=l!!s-1where
 l=0:foldl1 m[map(n+)l|n<-d]
 g=minimum d
 s=until(\n->l!!(n+g)-l!!n==g)(+1)0

Call it with, e.g., f [9,6,20].

Answer 3

GolfScript 47/42 chars

Faster solution (47).

~:+{0+{.1<{$}{1=}if|}/.!1):1\{:X}*+0=-X<}do];X(

Slow solution (42). Checks all values up to the product of every number in the set...

~:+{*}*{0+{.1<{$}{1=}if|}/1):1;}*]-1%.0?>,

Sample I/O:

$ echo "[6 9 20]"|golfscript frobenius.gs
43
$ echo "[60 90 2011]"|golfscript frobenius.gs
58349

Answer 4

Mathematica 0 chars (or 19 chars counting the invoke command)

Invoke wtih

FrobeniusNumber[{a,b,c,...}]

Example

In[3]:= FrobeniusNumber[{6, 9, 20}]
Out[3]= 43

Is it a record? :)

Answer 5

Perl 105 107 110 119 122 127 152 158 characters

Latest edit: Compound assignment is good for you!

$h{0}=$t=1;$t*=$_ for@ARGV;for$x(1..$t){$h{$x}=grep$h{$x-$_},@ARGV}@b=grep!$h{$_},1..$t;print pop@b,"\n"

Explanation:

$t = 1;
$t *= $_ foreach(@ARGV);

Set $t to the product of all of the input numbers. This is our upper limit.

foreach $x (1..$t)
{
  $h{$x} = grep {$_ == $x || $h{$x-$_} } @ARGV;
}

For each number from 1 to $t: If it's one of the input numbers, mark it using the %h hash; otherwise, if there is a marked entry from further back (difference being anything in the input), mark this entry. All marked entries are non-candidates for Frobenius numbers.

@b=grep{!$h{$_}}(1..$t);

Extract all UNMARKED entries. These are Frobenius candidates...

print pop @b, "\n"

...and the last of these, the highest, is our Frobenius number.

Answer 6

Ruby 100 86 80 chars

(newline not needed) Invoke with frob.rb 6 9 20

a=$*.map &:to_i;
p ((1..eval(a*"*")).map{|i|a<<i if(a&a.map{|v|i-v})[0];i}-a)[-1]

Works just like the Perl solution (except better:). $* is an array of command line strings; a is the same array as ints, which is then used to collect all the numbers which can be made; eval(a*"*") is the product, the max number to check.

In Ruby 1.9, you can save one additional character in by replacing "*" with ?*.

Edit: Shortened to 86 using Symbol#to_proc in $*.map, inlining m and shortening its calculation by folding the array.
Edit 2: Replaced .times with .map, traded .to_a for ;i.

Answer 7

Mathematica PROGRAM - 28 chars

Well, this is a REAL (unnecessary) program. As the other Mathematica entry shows clearly, you can compute the answer without writing a program ... but here it is

f[x__]:=FrobeniusNumber[{x}]

Invoke with

f[6, 9, 20]

43

Answer 8

FrobeniusScript 5 characters

solve

Sadly there does not yet exist any compiler/interpreter for this language.

No params, the interpreter will handle that:

$ echo solve > myProgram  
$ frobeniusScript myProgram
6
9
20
^D
Your answer is: 43
$ exit

Answer 9

C#, 360 characters

using System;using System.Linq;class a{static void Main(string[]b)
{var c=(b.Select(d=>int.Parse(d))).ToArray();int e=c[0]*c[1];a:--e;
var f=c.Length;var g=new int[f];g[f-1]=1;int h=1;for(;;){int i=0;for
(int j=0;j<f;j++)i+=c[j]*g[j];if(i==e){goto a;}if(i<e){g[f-1]++;h=1;}
else{if(h>=f){Console.Write(e);return;}for(int k=f-1;k>=f-h;k--)
g[k]=0;g[f-h-1]++;h++;}}}}

I'm sure there's a shorter C# solution than this, but this is what I came up with.

This is a complete program that takes the values as command-line parameters and outputs the result to the screen.