mukesh tiwari | 11 Dec 19:43 2012
Picon

C++

Hello All
I am trying to transform this C++ code in Haskell. In case any one interested this is solution of SPOJ problem.

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int memo[1100][1100] ;

int recurse( int h , int a , int cnt , bool flag )
    {
      if ( h <= 0 || a <= 0 ) return cnt ;
      if ( memo[h][a] ) return memo[h][a] ;
      if ( flag ) memo[h][a] =  recurse ( h + 3 , a + 2 , cnt + 1 , !flag )  ;                  
      else
         memo[h][a] = max ( memo[h][a] ,  max ( recurse ( h - 5 , a - 10 , cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ;

     return memo[h][a];
   }

int main()
  {
    int n , a , b ;
    scanf( "%d", &n );
    for(int i = 0 ; i < n ; i++)
    {
     memset ( memo , 0 , sizeof memo ) ;
     scanf("%d%d", &a , &b );
     printf("%d\n" , recurse( a , b , -1 ,  1 ));
     if( i != ( n - 1 ) ) printf("\n");
    }

  }

I am stuck with that memo[1100][1100] is global variable so I tried to solve this problem using state monad ( Don't know if its correct approach or not ) but it certainly does not seem correct to me. Till now I came up with code. Could some one please tell me how to solve this kind of problem ( Generally we have a global variable either multi dimensional array or map  and we store the best values found so far in the table ).

import qualified Data.Map.Strict as SM
import Control.Monad.State

{--
funsolve_WF :: Int -> Int -> Int -> Int
funsolve_WF h a cnt
     | h <= 0 || a <= 0 = cnt
     | otherwise = funsolve_Air h a ( cnt + 1 )

funsolve_Air :: Int -> Int -> Int -> Int
funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' ) ( funsolve_WF ( h + 3  - 20 )  ( a + 2  + 5 )  cnt' ) where
                      cnt' = cnt + 1
--}
 
 
 
funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int )  Int ) Int
funSolve hl am cnt f
    | hl <= 0 && am <= 0 = return cnt
    | otherwise = do
            mp <- get
            case () of
               _| SM.member ( hl , am ) mp -> return  mp SM.! ( hl , am )
                | f -> do
                      --here I have to insert the value return by function funSolve ( hl + 3 ) ( am + 2 ) (  cnt + 1 )  ( not f ) to map whose key is ( hl , am )
                        let k = evalState ( funSolve ( hl + 3 ) ( am + 2 )  ( cnt + 1 ) ( not f ) ) mp
                        modify ( SM.insert ( hl , am ) k )

                       
                | otherwise ->  do
                       do
                        let k_1 = evalState ( funSolve ( hl - 5 )  ( am - 10 )  ( cnt + 1 ) ( not f  ) ) mp
                            k_2 = evalState ( funSolve ( hl - 20 ) ( am + 5  )  ( cnt + 1 ) ( not f  ) ) mp
                            k_3 =  mp SM.! ( hl , am )
                        modify ( SM.insert ( hl , am )  ( maximum [ k_1 , k_2 , k_3 ] )  )

Regards
Mukesh Tiwari

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Serguey Zefirov | 11 Dec 20:59 2012
Picon

Re: C++

This array is for dynamic programming.

You can diagonalize it into a list and use technique similar to the
Fibonacci numbers.

The resulting solution should be purely declarative.

2012/12/11 mukesh tiwari <mukeshtiwari.iiitm <at> gmail.com>:
> Hello All
> I am trying to transform this C++ code in Haskell. In case any one
> interested this is solution of SPOJ problem.
>
> #include<cstdio>
> #include<iostream>
> #include<cstring>
> using namespace std;
>
> int memo[1100][1100] ;
>
> int recurse( int h , int a , int cnt , bool flag )
>     {
>       if ( h <= 0 || a <= 0 ) return cnt ;
>       if ( memo[h][a] ) return memo[h][a] ;
>       if ( flag ) memo[h][a] =  recurse ( h + 3 , a + 2 , cnt + 1 , !flag )
> ;
>       else
>          memo[h][a] = max ( memo[h][a] ,  max ( recurse ( h - 5 , a - 10 ,
> cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ;
>
>      return memo[h][a];
>    }
>
> int main()
>   {
>     int n , a , b ;
>     scanf( "%d", &n );
>     for(int i = 0 ; i < n ; i++)
>     {
>      memset ( memo , 0 , sizeof memo ) ;
>      scanf("%d%d", &a , &b );
>      printf("%d\n" , recurse( a , b , -1 ,  1 ));
>      if( i != ( n - 1 ) ) printf("\n");
>     }
>
>   }
>
> I am stuck with that memo[1100][1100] is global variable so I tried to solve
> this problem using state monad ( Don't know if its correct approach or not )
> but it certainly does not seem correct to me. Till now I came up with code.
> Could some one please tell me how to solve this kind of problem ( Generally
> we have a global variable either multi dimensional array or map  and we
> store the best values found so far in the table ).
>
> import qualified Data.Map.Strict as SM
> import Control.Monad.State
>
> {--
> funsolve_WF :: Int -> Int -> Int -> Int
> funsolve_WF h a cnt
>      | h <= 0 || a <= 0 = cnt
>      | otherwise = funsolve_Air h a ( cnt + 1 )
>
> funsolve_Air :: Int -> Int -> Int -> Int
> funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' )
> ( funsolve_WF ( h + 3  - 20 )  ( a + 2  + 5 )  cnt' ) where
>                       cnt' = cnt + 1
> --}
>
>
>
> funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int )  Int )
> Int
> funSolve hl am cnt f
>     | hl <= 0 && am <= 0 = return cnt
>     | otherwise = do
>             mp <- get
>             case () of
>                _| SM.member ( hl , am ) mp -> return  mp SM.! ( hl , am )
>                 | f -> do
>                       --here I have to insert the value return by function
> funSolve ( hl + 3 ) ( am + 2 ) (  cnt + 1 )  ( not f ) to map whose key is (
> hl , am )
>                         let k = evalState ( funSolve ( hl + 3 ) ( am + 2 )
> ( cnt + 1 ) ( not f ) ) mp
>                         modify ( SM.insert ( hl , am ) k )
>
>
>                 | otherwise ->  do
>                        do
>                         let k_1 = evalState ( funSolve ( hl - 5 )  ( am - 10
> )  ( cnt + 1 ) ( not f  ) ) mp
>                             k_2 = evalState ( funSolve ( hl - 20 ) ( am + 5
> )  ( cnt + 1 ) ( not f  ) ) mp
>                             k_3 =  mp SM.! ( hl , am )
>                         modify ( SM.insert ( hl , am )  ( maximum [ k_1 ,
> k_2 , k_3 ] )  )
>
> Regards
> Mukesh Tiwari
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Clark Gaebel | 11 Dec 21:47 2012
Picon
Picon

Re: C++

If you're trying to memoize a recursive algorithm with a global array of previous states, you could use the marvellous MemoTrie package [1]. It lets you write your algorithm recursively, while getting all the benefits of memoization! Here's an example with the fibonacci function:

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = memofib (n - 2) + memofib (n - 1)

memofib :: Int -> Integer
memofib = memo fib

> memofib 113 -- runs in O(n), with (permanent!) memory usage also at O(n).

  - Clark

[1] http://hackage.haskell.org/package/MemoTrie


On Tue, Dec 11, 2012 at 2:59 PM, Serguey Zefirov <sergueyz <at> gmail.com> wrote:
This array is for dynamic programming.

You can diagonalize it into a list and use technique similar to the
Fibonacci numbers.

The resulting solution should be purely declarative.

2012/12/11 mukesh tiwari <mukeshtiwari.iiitm <at> gmail.com>:
> Hello All
> I am trying to transform this C++ code in Haskell. In case any one
> interested this is solution of SPOJ problem.
>
> #include<cstdio>
> #include<iostream>
> #include<cstring>
> using namespace std;
>
> int memo[1100][1100] ;
>
> int recurse( int h , int a , int cnt , bool flag )
>     {
>       if ( h <= 0 || a <= 0 ) return cnt ;
>       if ( memo[h][a] ) return memo[h][a] ;
>       if ( flag ) memo[h][a] =  recurse ( h + 3 , a + 2 , cnt + 1 , !flag )
> ;
>       else
>          memo[h][a] = max ( memo[h][a] ,  max ( recurse ( h - 5 , a - 10 ,
> cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ;
>
>      return memo[h][a];
>    }
>
> int main()
>   {
>     int n , a , b ;
>     scanf( "%d", &n );
>     for(int i = 0 ; i < n ; i++)
>     {
>      memset ( memo , 0 , sizeof memo ) ;
>      scanf("%d%d", &a , &b );
>      printf("%d\n" , recurse( a , b , -1 ,  1 ));
>      if( i != ( n - 1 ) ) printf("\n");
>     }
>
>   }
>
> I am stuck with that memo[1100][1100] is global variable so I tried to solve
> this problem using state monad ( Don't know if its correct approach or not )
> but it certainly does not seem correct to me. Till now I came up with code.
> Could some one please tell me how to solve this kind of problem ( Generally
> we have a global variable either multi dimensional array or map  and we
> store the best values found so far in the table ).
>
> import qualified Data.Map.Strict as SM
> import Control.Monad.State
>
> {--
> funsolve_WF :: Int -> Int -> Int -> Int
> funsolve_WF h a cnt
>      | h <= 0 || a <= 0 = cnt
>      | otherwise = funsolve_Air h a ( cnt + 1 )
>
> funsolve_Air :: Int -> Int -> Int -> Int
> funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' )
> ( funsolve_WF ( h + 3  - 20 )  ( a + 2  + 5 )  cnt' ) where
>                       cnt' = cnt + 1
> --}
>
>
>
> funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int )  Int )
> Int
> funSolve hl am cnt f
>     | hl <= 0 && am <= 0 = return cnt
>     | otherwise = do
>             mp <- get
>             case () of
>                _| SM.member ( hl , am ) mp -> return  mp SM.! ( hl , am )
>                 | f -> do
>                       --here I have to insert the value return by function
> funSolve ( hl + 3 ) ( am + 2 ) (  cnt + 1 )  ( not f ) to map whose key is (
> hl , am )
>                         let k = evalState ( funSolve ( hl + 3 ) ( am + 2 )
> ( cnt + 1 ) ( not f ) ) mp
>                         modify ( SM.insert ( hl , am ) k )
>
>
>                 | otherwise ->  do
>                        do
>                         let k_1 = evalState ( funSolve ( hl - 5 )  ( am - 10
> )  ( cnt + 1 ) ( not f  ) ) mp
>                             k_2 = evalState ( funSolve ( hl - 20 ) ( am + 5
> )  ( cnt + 1 ) ( not f  ) ) mp
>                             k_3 =  mp SM.! ( hl , am )
>                         modify ( SM.insert ( hl , am )  ( maximum [ k_1 ,
> k_2 , k_3 ] )  )
>
> Regards
> Mukesh Tiwari
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane