Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

problem while solving basic dynamic programming question

by yujong_lee (Novice)
on Mar 15, 2020 at 06:53 UTC ( #11114280=perlquestion: print w/replies, xml ) Need Help??

yujong_lee has asked for the wisdom of the Perl Monks concerning the following question:

I'm solving basic dynamic programming question. It's simple. input is single integer. if input is 3, all possible cases is 3,1+2,2+1,1+1+1 so out put is 4. if input is 4, output is 7 because 4 = 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1. code above is my code to solve this.

use strict; use warnings; our @cache; sub find { my $num = shift; if(defined $cache[$num]) {return $cache[$num];} if($num == 0) {return 1;} if($num < 0) {return 0;} $cache[$num] = &find($num -1) + &find($num - 2) + &find($num - 3); return $cache[$num]; } my $test_case = <>+0; for(1..$test_case) { my $num = <>+0; print &find($num),"\n"; }

but the output is wrong. and I found that output of 2 is 3, instead of 2. also output of 3 is 5 instead of 4. to fix this, I write @cache1..3 = (1,2,4); and of course, It is fixed. But, I want to remove @cache1..3 = (1,2,4); and want to know why my original code is not working properly. when call solution(2), isn't it obvious that the output is solution(1) + solution(0) + solution(-1)? and when I call solution(0), solution(1), solution(-1) individually, the output is 1,1,0 so sum is 2. not 3. Thank you for your help.

Replies are listed 'Best First'.
Re: problem while solving basic dynamic programming question
by haukex (Chancellor) on Mar 15, 2020 at 08:42 UTC
    if(defined $cache[$num]) {return $cache[$num];} if($num < 0) {return 0;}

    In Perl, -1 is a valid array index, meaning the last element of the array (-2 is the second-to-last, and so on). Move the if($num < 0) check before the if(defined $cache[$num]) check and your code produces the expected output. Another option would be to use a hash instead of an array as the cache.

    A couple more tips:

    • Instead of a global, you could define your cache as what is known as a "static" variable in other languages, using state.
    • Update: While implementing the cache yourself like that is fine, note that Perl has a module for that, Memoize.
    • The &find() style of calling subs is outdated, call your subs without the &.
    • The if($num == 0) check isn't necessary if you pre-populate your array with that index.
    • You can use Test::More instead of inputting your test cases manually:
    use warnings; use strict; use feature 'state'; sub find { state @cache = (1); my $num = shift; return 0 if $num < 0; if ( defined $cache[$num] ) { return $cache[$num] } $cache[$num] = find($num-1) + find($num-2) + find($num-3); return $cache[$num]; } use Test::More tests=>3; is find(2), 2; is find(3), 4; is find(4), 7;
      It was helpful. Thank you
Re: problem while solving basic dynamic programming question
by vr (Curate) on Mar 15, 2020 at 11:11 UTC

    Ehm... If you accept 3 in list of answers for input "3", then there should be 4 in list for "4", then total count for the latter would be 8, not 7. In fact, said count is equal 2**(N-1), rather than Tribonacci sequence with whatever initial triplet as your code implies.

    Visualize it this way: there are N ones 1,1,1,.... You insert any number of pluses in between and perform these additions to get partial answer. So, emit all subsets of all positions, it should be clear enough. I'd NOT recommend to submit code below if this is HW assignment. Result is correct, algo is kind of joke.

    use strict; use warnings; use Algorithm::Combinatorics 'subsets'; $" = ' + '; use constant N => 5; my $i = subsets [ 1 .. N - 1 ]; while () { my $s = '1,' x N; substr $s, 2 * $_ - 1, 1, '+' for @{ $i-> next or last }; print eval( $s = "@{[ eval $s ]}" ), " = $s\n"; } __END__ 5 = 5 5 = 1 + 4 5 = 2 + 3 5 = 1 + 1 + 3 5 = 3 + 2 5 = 1 + 2 + 2 5 = 2 + 1 + 2 5 = 1 + 1 + 1 + 2 5 = 4 + 1 5 = 1 + 3 + 1 5 = 2 + 2 + 1 5 = 1 + 1 + 2 + 1 5 = 3 + 1 + 1 5 = 1 + 2 + 1 + 1 5 = 2 + 1 + 1 + 1 5 = 1 + 1 + 1 + 1 + 1
Re: problem while solving basic dynamic programming question
by tybalt89 (Parson) on Mar 15, 2020 at 15:11 UTC
    #!/usr/bin/perl use strict; # https://perlmonks.org/?node_id=11114280 use warnings; use List::Util qw( uniq ); my @cache = []; for my $n ( 3 .. 4 ) { print "$_\n" for sort @{ find($n) }; print "\n"; } sub find { my $n = shift; $cache[$n] //= [ uniq $n, map { my $nn = $_; map { my $t = $_; map "$t+$_", @{ find($nn) } } @{ find($n - $nn +) } } 1 .. $n - 1 ]; }

    Outputs:

    1+1+1 1+2 2+1 3 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 4
Re: problem while solving basic dynamic programming question
by jo37 (Monk) on Mar 15, 2020 at 08:17 UTC

    You describe the output for a single number as input, but your program reads two numbers from <>. The intention is not clear to me.

    Don't know if this is related to your problem.

    Greetings,
    -jo

    $gryYup$d0ylprbpriprrYpkJl2xyl~rzg??P~5lp2hyl0p$
      your program reads two numbers from <>. The intention is not clear to me.

      It's pretty common on sites like HackerRank etc. to have the solutions first read in the number of test cases, and then read in each test case.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://11114280]
Approved by marto
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2020-06-06 09:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you really want to know if there is extraterrestrial life?



    Results (41 votes). Check out past polls.

    Notices?