Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Regex-based solution to xkcd #287 5 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Actually, backtracking is not required.

    By using dynamic programming, one can find all solutions in pseudo-polynomial time.

    Let me know if you want example code for this.

    • Oh, I know that this particular problem can be done with no backtracking.

      I mean, do you think I am seriously proposing regexes as the best approach to this problem? :-)

      • No - I was replying to your "Obviously, backtracking is needed" comment, that is all.

        Using regular expressions for this is a nifty hack that I enjoyed reading about.

        • Ah, oh. Yeah, the general case. Are you referring to things like Branch&Bound?

          • I'm referring to general dynamic programming.

            Building a table can help solve this problem in O(M+N), where M is linear with the price goal (the higher the price, the longer this algorithm takes) and N is linear with the number of items you have to choose from.

            If one builds a table where the rows represent a price (0 cents, 5 cents, 10 cents, etc, up to the goal price) and the columns represent the items, then moving from the top-left to the bottom-right, one can fill in the table based only on information a
Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.