Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...

by ayrnieu (Beadle)
on Mar 20, 2006 at 05:35 UTC ( #537881=note: print w/replies, xml ) Need Help??


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

but it's inefficient since you end up doing a lot of the calculations multiple times,

use Memoize;
  • Comment on Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...
  • Download Code

Replies are listed 'Best First'.
Re^3: Puzzle: Given an array of integers, find the best sequence of pop / shift...
by tilly (Archbishop) on Mar 21, 2006 at 00:08 UTC
    Memoize will work, but it's not magic. The simplest way to write the function is as follows:
    sub get_move_score { my @numbers = @_ or return("end", "", 0); return "shift", $numbers[0], $numbers[0] if 1 == @numbers; my $shift = shift @numbers; my $pop = pop @numbers; my $score_shift = $shift - (get_move_score(@numbers, $pop))[2]; my $score_pop = $pop - (get_move_score($shift, @numbers))[2]; if ($score_pop > $score_shift) { return "pop", $pop, $score_pop; } else { return "shift", $shift, $score_shift; } }
    Now if you memoize that and try to run it for a list of n numbers, the memory requirements are O(n**3). (You wind up calling it for O(n) starting points, with O(n) ending points, with an argument list of length O(n) passed in.) For a list of 1000 numbers, that means that you'll need to store order of a billion or so numbers. (Less a factor of 6 or so, I could work it out.) Given how Perl hogs memory, and what most PCs are capable of, your implementation will probably fail on account of running out of memory.

    You can fix that by having @numbers be in a global array, and then only pass in the start and end points of the list. But now if you want to play more than one game, you're hosed. (Unless you read the documentation for Memoize, and correctly call memoize/unmemoize in pairs.)

    Which means that in this case it is better to understand what the program is supposed to do, and explicitly build up your own data structure.

Re^3: Puzzle: Given an array of integers, find the best sequence of pop / shift...
by QM (Parson) on Mar 20, 2006 at 19:04 UTC
    Memoize only reduces the work, it doesn't eliminate checking to see if it's already done.

    For N=1000, 2^n ~~ 1e301, while n^2/2 ~~ 1e5. The first will never finish in the lifetime of the universe, the second in a blink of an eye.

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://537881]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2022-01-20 11:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (56 votes). Check out past polls.

    Notices?