First of all, you have to give the sequence of moves. You can't just say how many of each and then give a total - that would be far too easy. Secondly, it is not nearly as simple a problem as it appears. Take, for instance, the following:

4 10 3 1

The 4 is largest, so you take it, right? But wait! This leaves the enemy with the ability to take 10. We can't have that. So we instead take 1, thus forcing the enemy to take 4 or 3 (they pick 4), leaving us with the 10 and them with the 3. Our total score is now 4, vs the -4 we would have had if we'd picked the 4 at the beginning.

My point is that making any choice involves knowing what the best scores are for the two branches, each of which needs to know what the best scores are for the two branches further down, etc. etc. You can do this with recursion (2^n), but it's inefficient since you end up doing a lot of the calculations multiple times, so the best approach is bottom up, starting with all the pairs, then moving to triples, quadruples, etc. until you have only one set. This is (n^2)/2, which is much better.

For instance:

4 10 3 1
R6 L7 L2
L3 L-8 (enemy subtracts and picks smallest)
R4

So the best choices are pop (1), shift (4), shift (10), ? (3).

In reply to Re: Puzzle: Given an array of integers, find the best sequence of pop / shift... by TedPride
in thread Puzzle: Given an array of integers, find the best sequence of pop / shift... by TedPride

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.