Two recursive calls inside of a recursive function

Discussion in 'C++' started by n00m, Mar 10, 2008.

  1. n00m

    n00m Guest

    typedef int grid[10][10];

    void foo(grid oc, grid a) {
    ...
    foo(oc,a); // call #1
    ...
    foo(oc,a); // call #2
    ...
    }

    Maybe it's a too_newbie question nonetheless:
    after returning from call #1 arrays "oc" and "a" get "spoiled".
    I need to pass to call #2 exactly the same arrays as were passed to
    call #1.
    Can't understand "how?" (in Pascal no any trouble in this case)

    Need your help. Thanks.
     
    n00m, Mar 10, 2008
    #1
    1. Advertising

  2. On 2008-03-10 10:03, n00m wrote:
    > typedef int grid[10][10];
    >
    > void foo(grid oc, grid a) {
    > ...
    > foo(oc,a); // call #1
    > ...
    > foo(oc,a); // call #2
    > ...
    > }
    >
    > Maybe it's a too_newbie question nonetheless:
    > after returning from call #1 arrays "oc" and "a" get "spoiled".
    > I need to pass to call #2 exactly the same arrays as were passed to
    > call #1.
    > Can't understand "how?" (in Pascal no any trouble in this case)


    There should be no problem in this case either since both arguments to
    foo() are passed as copies. This combined with the lack of return-value
    makes me wonder what the function is supposed to accomplish.

    --
    Erik Wikström
     
    Erik Wikström, Mar 10, 2008
    #2
    1. Advertising

  3. Erik Wikström schrieb:
    > On 2008-03-10 10:03, n00m wrote:
    >> typedef int grid[10][10];
    >>
    >> void foo(grid oc, grid a) {
    >> ...
    >> foo(oc,a); // call #1
    >> ...
    >> foo(oc,a); // call #2
    >> ...
    >> }
    >>
    >> Maybe it's a too_newbie question nonetheless:
    >> after returning from call #1 arrays "oc" and "a" get "spoiled".
    >> I need to pass to call #2 exactly the same arrays as were passed to
    >> call #1.
    >> Can't understand "how?" (in Pascal no any trouble in this case)

    >
    > There should be no problem in this case either since both arguments to
    > foo() are passed as copies. This combined with the lack of return-value
    > makes me wonder what the function is supposed to accomplish.


    The pointers are passend as copy, but they point to the same array in
    memory. If the first call modifies the array, the second call will get the
    modified values.

    To the OP:
    Try a vector of vectors instead:

    typedef std::vector< std::vector<int> > grid;

    int main()
    {
    grid oc(10, std::vector<int>(10));
    grid a(10, std::vector<int>(10));

    // fill the arrays as before...

    foo(oc, a);
    }

    --
    Thomas
    http://www.netmeister.org/news/learn2quote.html
    The pedants here will shout "int main(void)" but I'll just whisper it.
    --Bob Wightman in comp.lang.c
     
    Thomas J. Gritzan, Mar 10, 2008
    #3
  4. n00m

    n00m Guest

    >This combined with the lack of return-value
    >makes me wonder what the function is supposed to accomplish.



    It's for counting the number of ways to fill a given grid (7x8) with
    ciphers 0..6
    with all 28 dominos bones. E.g., the answers for these 2 grids:

    2
    0 3 0 2 2 0 2 3
    1 5 6 5 5 1 2 2
    3 4 1 4 5 4 4 4
    6 6 1 0 5 2 3 0
    4 0 3 2 4 1 6 0
    1 4 1 5 6 6 3 0
    1 2 6 5 5 6 3 3

    5 3 1 0 0 1 6 3
    0 2 0 4 1 2 5 2
    1 5 3 5 6 4 6 4
    0 5 0 2 0 4 6 2
    4 5 3 6 0 6 1 1
    2 3 5 3 4 4 5 3
    2 1 1 6 6 2 4 3


    are 18 and 1.

    Initially I wrote it in Pascal (in that the code works absolutely as
    expected, so to speak).
    Then I rewrote it to C.. The whole text (still vectors don't want to
    work in my hands):



    #include <cstdio>
    #include <cstdlib>


    typedef short grid[10][10];


    int ans; // it's global!


    void foo(short sch, grid oc, grid a, short p, short q, short fl) {

    if (sch==28) {ans++; return;}

    if (fl==1) {
    oc[a[p][q]][a[p][q+1]]=1;
    oc[a[p][q+1]][a[p][q]]=1;
    a[p][q]=7;
    a[p][q+1]=7;
    }
    else {
    oc[a[p][q]][a[p+1][q]]=1;
    oc[a[p+1][q]][a[p][q]]=1;
    a[p][q]=7;
    a[p+1][q]=7;
    }
    for (int i=1; i<=7; i++)
    for (int j=1; j<=8; j++)
    if ((a[j]!=7)&&(a[i-1][j]==7)&&(a[j-1]==7)) {
    if (oc[a[j]][a[j+1]]==0)
    foo(sch+1,oc,a,i+0,j+0,1);
    if (oc[a[j]][a[i+1][j]]==0)
    foo(sch+1,oc,a,i+0,j+0,2);
    return;
    }
    } // end of foo()



    int main() {

    grid oc,a;

    for (int i=0; i<=9; i++)
    for (int j=0; j<=9; j++)
    a[j]=7;

    for (int i=0; i<=7; i++) {
    oc[7]=1; oc[7]=1;
    }

    FILE* fp=fopen("E:\\dominos.txt","r");

    int tcs;

    fscanf(fp,"%d",&tcs);

    while (tcs--) {

    for (int i=0; i<=6; i++)
    for (int j=0; j<=6; j++)
    oc[j]=0;

    for (int i=1; i<=7; i++)
    for (int j=1; j<=8; j++)
    fscanf(fp,"%d",&a[j]);

    ans=0;
    foo(1,oc,a,1,1,1);
    foo(1,oc,a,1,1,2);
    printf("%d\n",ans);

    }

    fclose(fp);

    system("pause");
    return 0;
    }
     
    n00m, Mar 10, 2008
    #4
  5. On 2008-03-10 11:03, Thomas J. Gritzan wrote:
    > Erik Wikström schrieb:
    >> On 2008-03-10 10:03, n00m wrote:
    >>> typedef int grid[10][10];
    >>>
    >>> void foo(grid oc, grid a) {
    >>> ...
    >>> foo(oc,a); // call #1
    >>> ...
    >>> foo(oc,a); // call #2
    >>> ...
    >>> }
    >>>
    >>> Maybe it's a too_newbie question nonetheless:
    >>> after returning from call #1 arrays "oc" and "a" get "spoiled".
    >>> I need to pass to call #2 exactly the same arrays as were passed to
    >>> call #1.
    >>> Can't understand "how?" (in Pascal no any trouble in this case)

    >>
    >> There should be no problem in this case either since both arguments to
    >> foo() are passed as copies. This combined with the lack of return-value
    >> makes me wonder what the function is supposed to accomplish.

    >
    > The pointers are passend as copy, but they point to the same array in
    > memory. If the first call modifies the array, the second call will get the
    > modified values.


    Sorry about that, I missed the typedef and assumed that grid was some
    kind of class. Personally I find that arrays can be useful, but you
    should never pass them around without a wrapper-class.

    --
    Erik Wikström
     
    Erik Wikström, Mar 10, 2008
    #5
  6. n00m

    Jim Langston Guest

    n00m wrote:
    >> This combined with the lack of return-value
    >> makes me wonder what the function is supposed to accomplish.

    >
    >
    > It's for counting the number of ways to fill a given grid (7x8) with
    > ciphers 0..6
    > with all 28 dominos bones. E.g., the answers for these 2 grids:
    >
    > 2
    > 0 3 0 2 2 0 2 3
    > 1 5 6 5 5 1 2 2
    > 3 4 1 4 5 4 4 4
    > 6 6 1 0 5 2 3 0
    > 4 0 3 2 4 1 6 0
    > 1 4 1 5 6 6 3 0
    > 1 2 6 5 5 6 3 3
    >
    > 5 3 1 0 0 1 6 3
    > 0 2 0 4 1 2 5 2
    > 1 5 3 5 6 4 6 4
    > 0 5 0 2 0 4 6 2
    > 4 5 3 6 0 6 1 1
    > 2 3 5 3 4 4 5 3
    > 2 1 1 6 6 2 4 3
    >
    >
    > are 18 and 1.
    >
    > Initially I wrote it in Pascal (in that the code works absolutely as
    > expected, so to speak).


    Pascal would pass the entire array to the function, in C and C++ there is no
    way to pass a native array as a parameter, only some pointer type ( int[],
    int*, etc..). If you want to emulate the way Pascal is doing it, you need
    to make a copy of the array and pass that, which is where vector should work
    for you.

    Consider:
    #include <vector>
    #include <iostream>

    typedef std::vector<std::vector<int> > DataType;

    void foo(short sch, DataType oc, DataType a, short p, short q, short fl)
    {
    // Etc...
    }

    int main()
    {
    DataType a;

    // Size our Data to 10 by 10
    for ( size_t i = 0; i < 10; ++i )
    a.push_back( std::vector<int>(10) );

    for ( size_t i = 0; i < 10; ++i)
    for (size_t j = 0; j < 10; ++j)
    a[j] = 7;

    // This makes a copy
    DataType oc = a;

    for ( size_t i = 0; i < 8; ++i) {
    oc[7]=1; oc[7]=1;
    }

    // Etc...

    // Now, we want to pass a copy to foo, not the original.
    // So make a copy.

    DataType OCCopy = oc;
    DataType ACopy = a;
    foo(1,OCCopy,ACopy,1,1,1);

    // Reset our copies
    OCCopy = oc;
    ACopy = a;
    foo(1,OCCopy,ACopy,1,1,1);


    }
     
    Jim Langston, Mar 10, 2008
    #6
  7. n00m

    Jim Langston Guest

    Jim Langston wrote:
    > n00m wrote:
    >>> This combined with the lack of return-value
    >>> makes me wonder what the function is supposed to accomplish.

    >>
    >>
    >> It's for counting the number of ways to fill a given grid (7x8) with
    >> ciphers 0..6
    >> with all 28 dominos bones. E.g., the answers for these 2 grids:
    >>
    >> 2
    >> 0 3 0 2 2 0 2 3
    >> 1 5 6 5 5 1 2 2
    >> 3 4 1 4 5 4 4 4
    >> 6 6 1 0 5 2 3 0
    >> 4 0 3 2 4 1 6 0
    >> 1 4 1 5 6 6 3 0
    >> 1 2 6 5 5 6 3 3
    >>
    >> 5 3 1 0 0 1 6 3
    >> 0 2 0 4 1 2 5 2
    >> 1 5 3 5 6 4 6 4
    >> 0 5 0 2 0 4 6 2
    >> 4 5 3 6 0 6 1 1
    >> 2 3 5 3 4 4 5 3
    >> 2 1 1 6 6 2 4 3
    >>
    >>
    >> are 18 and 1.
    >>
    >> Initially I wrote it in Pascal (in that the code works absolutely as
    >> expected, so to speak).

    >
    > Pascal would pass the entire array to the function, in C and C++
    > there is no way to pass a native array as a parameter, only some
    > pointer type ( int[], int*, etc..). If you want to emulate the way
    > Pascal is doing it, you need to make a copy of the array and pass
    > that, which is where vector should work for you.
    >
    > Consider:
    > #include <vector>
    > #include <iostream>
    >
    > typedef std::vector<std::vector<int> > DataType;
    >
    > void foo(short sch, DataType oc, DataType a, short p, short q, short
    > fl) {
    > // Etc...
    > }
    >
    > int main()
    > {
    > DataType a;
    >
    > // Size our Data to 10 by 10
    > for ( size_t i = 0; i < 10; ++i )
    > a.push_back( std::vector<int>(10) );
    >
    > for ( size_t i = 0; i < 10; ++i)
    > for (size_t j = 0; j < 10; ++j)
    > a[j] = 7;
    >
    > // This makes a copy
    > DataType oc = a;
    >
    > for ( size_t i = 0; i < 8; ++i) {
    > oc[7]=1; oc[7]=1;
    > }
    >
    > // Etc...
    >
    > // Now, we want to pass a copy to foo, not the original.
    > // So make a copy.
    >
    > DataType OCCopy = oc;
    > DataType ACopy = a;
    > foo(1,OCCopy,ACopy,1,1,1);
    >
    > // Reset our copies
    > OCCopy = oc;
    > ACopy = a;
    > foo(1,OCCopy,ACopy,1,1,1);
    >
    >
    > }


    Also, it may be better just to make a copy inside of Foo.

    void foo(short sch, const DataType oc, const DataType a, short p, short q,
    short fl)
    {
    DataType OCWorking = oc;
    DataType AWorking = a;
    // Etc...
    }

    Then change OCWorking and AWorking inside foo to your heart's content, and
    the passed in vectors won't be changed, then you don't have to copy them
    inside of main. Makes more sense actually.


    --
    Jim Langston
     
    Jim Langston, Mar 10, 2008
    #7
  8. n00m

    John Bode Guest

    On Mar 10, 4:03 am, n00m <> wrote:
    > typedef int grid[10][10];
    >
    > void foo(grid oc, grid a) {
    > ...
    > foo(oc,a); // call #1
    > ...
    > foo(oc,a); // call #2
    > ...
    >
    > }
    >
    > Maybe it's a too_newbie question nonetheless:
    > after returning from call #1 arrays "oc" and "a" get "spoiled".
    > I need to pass to call #2 exactly the same arrays as were passed to
    > call #1.
    > Can't understand "how?" (in Pascal no any trouble in this case)
    >
    > Need your help. Thanks.


    C++ inherited C's semantics when it comes to arrays, and that's what's
    biting you here.

    When an array identifier appears in most contexts, it's type is
    implicitly converted from "N-element array of T" (T a[N]) to "pointer
    to T" (T *a), and its value is set to point to the base of the array.
    Given the code:

    int main(void)
    {
    grid g1, g2;
    ...
    foo (g1, g2);
    return 0;
    }

    In the call to foo, both g1 and g2 are converted from types "10-
    element array of 10-element array of int" to "pointer to 10-element
    array of int", or int (*)[10]. Instead of passing copies of g1 and g2
    to foo, you're passing their addresses. So, any changes to the formal
    parameters oc and a in foo() are reflected in the actual parameters g1
    and g2. That's why your arrays are getting "spoiled."

    This is one reason I avoid typedefing array and pointer types. Their
    handling is different enough from other types that you don't want to
    hide that information.

    There are a couple of ways around this. One is to wrap your array in
    a struct type:

    struct grid {
    int data[10][10];
    };

    Another way is to use STL containers like vectors or maps, but I've
    never done it in a way to mimic 2-d arrays; I don't know how easy it
    would be. The wrapping-in-a-struct trick works pretty well.
     
    John Bode, Mar 10, 2008
    #8
  9. n00m

    n00m Guest

    As it was suggested I did it via typedef vector< vector<short> >
    grid;
    It works "great" but alas it's too sloooow: http://www.spoj.pl/status/VONNY,zzz/
    Just in case: my question is not about a better algo for the prob on
    the link.
     
    n00m, Mar 12, 2008
    #9
  10. n00m

    n00m Guest

    Jim Langston wrote:
    > // Now, we want to pass a copy to foo, not the original.
    > // So make a copy.
    >
    > DataType OCCopy = oc;
    > DataType ACopy = a;
    > foo(1,OCCopy,ACopy,1,1,1);
    >
    > // Reset our copies
    > OCCopy = oc;
    > ACopy = a;
    > foo(1,OCCopy,ACopy,1,1,1);



    Seems some steps in your code are unnecessary. It's my code:


    #include <cstdio>
    #include <cstdlib>
    #include <vector>

    using namespace std;

    typedef vector< vector<short> > grid;

    int ans;


    void foo(short sch, grid oc, grid a, short p, short q, short fl) {

    if (sch==28) {ans++; return;}

    if (fl==1) {
    oc[a[p][q]][a[p][q+1]]=1;
    oc[a[p][q+1]][a[p][q]]=1;
    a[p][q]=7;
    a[p][q+1]=7;
    }
    else {
    oc[a[p][q]][a[p+1][q]]=1;
    oc[a[p+1][q]][a[p][q]]=1;
    a[p][q]=7;
    a[p+1][q]=7;
    }
    for (int i=1; i<=7; i++)
    for (int j=1; j<=8; j++)
    if ((a[j]!=7)&&(a[i-1][j]==7)&&(a[j-1]==7)) {
    if (oc[a[j]][a[j+1]]==0)
    foo(sch+1,oc,a,i+0,j+0,1);
    if (oc[a[j]][a[i+1][j]]==0)
    foo(sch+1,oc,a,i+0,j+0,2);
    return;
    }
    }


    int main() {

    grid oc(10,10),a(10,10);

    for (int i=0; i<=9; i++)
    for (int j=0; j<=9; j++)
    a[j]=7;

    for (int i=0; i<=7; i++) {
    oc[7]=1; oc[7]=1;
    }

    FILE* fp=fopen("E:\\e.txt","r");

    int tcs;

    fscanf(fp,"%d",&tcs);

    while (tcs--) {

    for (int i=0; i<=6; i++)
    for (int j=0; j<=6; j++)
    oc[j]=0;

    for (int i=1; i<=7; i++)
    for (int j=1; j<=8; j++)
    fscanf(fp,"%d",&a[j]);

    ans=0;
    foo(1,oc,a,1,1,1);
    foo(1,oc,a,1,1,2);
    printf("%d\n",ans);

    }

    fclose(fp);

    system("pause");
    return 0;
    }
     
    n00m, Mar 12, 2008
    #10
  11. n00m

    n00m Guest

    Jim Langston wrote:

    > Also, it may be better just to make a copy inside of Foo.
    >
    > void foo(short sch, const DataType oc, const DataType a, short p, short q,
    > short fl)
    > {
    > DataType OCWorking = oc;
    > DataType AWorking = a;
    > // Etc...
    > }
    >
    > Then change OCWorking and AWorking inside foo to your heart's content, and
    > the passed in vectors won't be changed, then you don't have to copy them
    > inside of main. Makes more sense actually.



    It timelimits too (I'd given a try of memcpy(), as my 1st workaround).
     
    n00m, Mar 12, 2008
    #11
  12. n00m schrieb:
    > As it was suggested I did it via typedef vector< vector<short> >
    > grid;
    > It works "great" but alas it's too sloooow: http://www.spoj.pl/status/VONNY,zzz/
    > Just in case: my question is not about a better algo for the prob on
    > the link.


    For a more efficient solution, instead making a copy per function call, you
    could remember the old values and undo the modification to the array at the
    end of the function.

    --
    Thomas
    http://www.netmeister.org/news/learn2quote.html
    NOTICE: alloc: /dev/null: filesystem full
     
    Thomas J. Gritzan, Mar 12, 2008
    #12
  13. n00m

    n00m Guest

    Thomas J. Gritzan wrote:
    > n00m schrieb:
    > ... ... ...


    Yes. I'm agree.

    What do you think about this (a funny thing; I can imagine only /**/
    instead of spaces):

    This problem tests your knowledge of the C programming language. Your
    task is to submit a snippet of C code that consists of two
    declarations defining a type called "zan", which should be a struct
    containing two members: first an unsigned int called "aku", then a
    constant pointer to char called "soku".

    To make things more interesting, you can't use any whitespace in
    either declaration, and the two declarations must be sufficiently
    dissimilar (basically, you have to use two different tricks to get
    around the lack of whitespace).

    Input
    There is no input.

    Output
    Your submission should consist of exactly two declarations as
    described above, separated by whitespace.

    Update: "Exactly two" means exactly two. Your code isn't allowed to
    define any other types; anything containing struct foo or typedef
    unsigned int is rejected.

    "Whitespace" includes newlines. NUL ('\0') is not whitespace, but it
    isn't a valid token separator either.

    Example
    Output:
    typedef:struct{unsigned*aku;char*soku;}zan;
    typedef:struct{unsigned*aku;char*soku;}zan;

    This example is invalid for the following reasons:

    typedef: is a syntax error
    aku and soku have the wrong type
     
    n00m, Mar 13, 2008
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Darrel
    Replies:
    2
    Views:
    314
    darrel
    Nov 4, 2004
  2. Replies:
    2
    Views:
    936
    Bengt Richter
    Aug 1, 2005
  3. streamkid
    Replies:
    6
    Views:
    358
    streamkid
    Feb 24, 2007
  4. Steven Burn
    Replies:
    2
    Views:
    154
    Steven Burn
    Oct 21, 2005
  5. Bob
    Replies:
    5
    Views:
    262
Loading...

Share This Page