Thursday, February 3, 2011

Solving the postage stamp problem using regex

See: Postage stamp problem on Wikipedia
int n = 0;

while (
   (new String(new char[++n]))
      .matches("(.{1}|.{4}|.{9}|.{31}|.{51}){0,5}")
);

System.out.println(n); // 127
(see also on ideone.com)

That is, when the only available stamp denominations are {1, 4, 9, 31, 51}, and when envelopes can only accommodate up to 5 stamps, the smallest unrepresentable total stamp value is 127.

It's easy to confirm correctness, because (not so) coincidentally, this set of stamp denominations is the unique solution to the (5, 5) global PSP. See Al Zimmermann's Programming Contest - Son of Darts.

No comments:

Post a Comment