Alex Rivera | Logout

Code Golf: Frobenius Number

Asked 2010-08-12T07:02:19.500
12

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 McNuggetTM 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:

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

language-agnostic code-golf rosetta-stone
Edit
Report

2 Answers

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.

answered 2010-08-12T22:26:09.027
5

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
answered 2010-08-13T00:20:29.650

Your Answer