Solution needed..urgent!!

Discussion in 'C++' started by Ankur Arora, Oct 23, 2008.

  1. Ankur Arora

    Ankur Arora Guest

    Hi all,

    The following post is probably not appropriate for this group but I
    know there are brilliant minds active at this place (trust me, this
    puzzle will involve some time and lots of grey matter), so would
    appreciate if you guys can jump in with any solutions/suggestions.
    Thanks!

    You are given a deck containing n cards. While holding the deck:

    1. Take the top card off the deck and set it on the table
    2. Take the next card off the top and put it on the bottom of the deck
    in your hand.
    3. Continue steps 1 and 2 until all cards are on the table. This is a
    round.
    4. Pick up the deck from the table and repeat steps 1-3 until the deck
    is in the original order.

    Write a program to determine how many rounds it will take to put a
    deck back into the original order. This will involve creating a data
    structure to represent the
    order of the cards. This program should be written in C or C++. Do
    not use STL. It should
    take a number of cards in the deck as a command line argument and
    write the result to stdout.
     
    Ankur Arora, Oct 23, 2008
    #1
    1. Advertising

  2. Ankur Arora wrote:
    > Do not use STL.


    Any rational reason for this?
     
    Juha Nieminen, Oct 23, 2008
    #2
    1. Advertising

  3. In message <CQZLk.87$>, Juha Nieminen
    <> writes
    >Ankur Arora wrote:
    >> Do not use STL.

    >
    > Any rational reason for this?


    It motivates homework question 2:

    "Why didn't your first design work?
    (a) dangling pointers;
    (b) uninitialised pointers;
    (b) double deletion;
    (c) incorrect container insertion/deletion algorithm;
    (d) all of the above"

    :-/
    --
    Richard Herring
     
    Richard Herring, Oct 23, 2008
    #3
  4. Ankur Arora

    red floyd Guest

    red floyd, Oct 23, 2008
    #4
  5. Ankur Arora

    osmium Guest

    "Ankur Arora" wrote:

    > The following post is probably not appropriate for this group but I
    > know there are brilliant minds active at this place (trust me, this
    > puzzle will involve some time and lots of grey matter), so would
    > appreciate if you guys can jump in with any solutions/suggestions.
    > Thanks!
    >
    > You are given a deck containing n cards. While holding the deck:
    >
    > 1. Take the top card off the deck and set it on the table
    > 2. Take the next card off the top and put it on the bottom of the deck
    > in your hand.
    > 3. Continue steps 1 and 2 until all cards are on the table. This is a
    > round.
    > 4. Pick up the deck from the table and repeat steps 1-3 until the deck
    > is in the original order.
    >
    > Write a program to determine how many rounds it will take to put a
    > deck back into the original order. This will involve creating a data
    > structure to represent the
    > order of the cards. This program should be written in C or C++. Do
    > not use STL. It should
    > take a number of cards in the deck as a command line argument and
    > write the result to stdout.


    The question is phrased in a way to start you on a wild goose chase.
    Identify that bit and go on from there. I think that is the only part that
    requires gray (or grey) matter.
     
    osmium, Oct 23, 2008
    #5
  6. Ankur Arora

    Guest

    On Oct 23, 12:42 am, Ankur Arora <> wrote:

    > This program should be written in C or C++.


    How about that? Any rationale for that?

    Ali
     
    , Oct 23, 2008
    #6
  7. Ankur Arora

    Ankur Arora Guest

    On Oct 23, 2:51 pm, Richard Herring <junk@[127.0.0.1]> wrote:
    > In message <CQZLk.87$>, Juha Nieminen
    > <> writes
    >
    > >Ankur Arora wrote:
    > >> Do not use STL.

    >
    > >  Any rational reason for this?

    >
    > It motivates homework question 2:
    >
    > "Why didn't your first design work?
    > (a) dangling pointers;
    > (b) uninitialised pointers;
    > (b) double deletion;
    > (c) incorrect container insertion/deletion algorithm;
    > (d) all of the above"
    >
    > :-/
    > --
    > Richard Herring


    Wow!!sorry about that, I can see its very offending.'will make it a
    point to follow the guidelines.Thanks.

    Here's what I have come up with so far (very basic, algorithmic
    steps):-
    - use of pointers to manipulate the deck since we will be doing a lot
    of shuffling. A link list would be a good choice with each node
    representing a card and the link list chain representing a particular
    ordering.
    - At least two loops, outer representing the condition till the deck
    is in the original order and the inner representing a complete round.
    - The inner loop will have its auxiliary list i.e. a particular
    ordering after the completion of a complete round.
    - At the end of each inner loop iteration we will check the auxiliary
    list with the original list to see whether its the same as the
    original list (this would be done in the conditional statement of the
    outer loop).

    Need to find out the implementation details for the inner loop (guess
    that would easy) and a way to check whether the auxiliary list is same
    as the original list at the end of each inner loop iteration.

    Any other design/ideas ?
     
    Ankur Arora, Oct 23, 2008
    #7
  8. Ankur Arora

    Kai-Uwe Bux Guest

    Ankur Arora wrote:

    [snip]
    > Here's what I have come up with so far (very basic, algorithmic
    > steps):-
    > - use of pointers to manipulate the deck since we will be doing a lot
    > of shuffling. A link list would be a good choice with each node
    > representing a card and the link list chain representing a particular
    > ordering.
    > - At least two loops, outer representing the condition till the deck
    > is in the original order and the inner representing a complete round.
    > - The inner loop will have its auxiliary list i.e. a particular
    > ordering after the completion of a complete round.
    > - At the end of each inner loop iteration we will check the auxiliary
    > list with the original list to see whether its the same as the
    > original list (this would be done in the conditional statement of the
    > outer loop).
    >
    > Need to find out the implementation details for the inner loop (guess
    > that would easy) and a way to check whether the auxiliary list is same
    > as the original list at the end of each inner loop iteration.
    >
    > Any other design/ideas ?


    Yes: The shuffle rule describes a fixed permutation of [1...n]. All you need
    to do is find the order of that permutation. That can be accomplished by
    finding the cycle representation and computing the LCM of the lengths of
    all cycles. This approach has the advantage of being much faster in those
    cases where the counting would take forever (and there are such n).


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Oct 23, 2008
    #8
  9. On 2008-10-23 15:51, Ankur Arora wrote:
    > On Oct 23, 2:51 pm, Richard Herring <junk@[127.0.0.1]> wrote:
    >> In message <CQZLk.87$>, Juha Nieminen
    >> <> writes
    >>
    >> >Ankur Arora wrote:
    >> >> Do not use STL.

    >>
    >> > Any rational reason for this?

    >>
    >> It motivates homework question 2:
    >>
    >> "Why didn't your first design work?
    >> (a) dangling pointers;
    >> (b) uninitialised pointers;
    >> (b) double deletion;
    >> (c) incorrect container insertion/deletion algorithm;
    >> (d) all of the above"
    >>
    >> :-/
    >> --
    >> Richard Herring

    >
    > Wow!!sorry about that, I can see its very offending.'will make it a
    > point to follow the guidelines.Thanks.
    >
    > Here's what I have come up with so far (very basic, algorithmic
    > steps):-
    > - use of pointers to manipulate the deck since we will be doing a lot
    > of shuffling. A link list would be a good choice with each node
    > representing a card and the link list chain representing a particular
    > ordering.
    > - At least two loops, outer representing the condition till the deck
    > is in the original order and the inner representing a complete round.
    > - The inner loop will have its auxiliary list i.e. a particular
    > ordering after the completion of a complete round.
    > - At the end of each inner loop iteration we will check the auxiliary
    > list with the original list to see whether its the same as the
    > original list (this would be done in the conditional statement of the
    > outer loop).
    >
    > Need to find out the implementation details for the inner loop (guess
    > that would easy) and a way to check whether the auxiliary list is same
    > as the original list at the end of each inner loop iteration.


    A tip: represent each card with a number and let the original deck be
    sorted (so a deck of 4 cards would start as 1, 2, 3, 4). Then checking
    if the deck is back to the original state is easy.

    --
    Erik Wikström
     
    Erik Wikström, Oct 23, 2008
    #9
  10. Ankur Arora

    James Kanze Guest

    On Oct 23, 3:50 pm, Stuart Golodetz
    <> wrote:
    > Juha Nieminen wrote:
    > > Ankur Arora wrote:
    > >> Do not use STL.


    > >   Any rational reason for this?


    > By not allowing you to use STL, they encourage you to write
    > your own classes to do the same thing - the process of
    > reinventing the wheel will convey to you (a) a fair amount
    > about the STL, (b) an understanding of why reinventing the
    > wheel is generally to be avoided and (c) a healthy
    > appreciation of the hard work put in by the people who have
    > worked on the STL over the years.


    I'm not so sure about that. Writing a simple array class which
    is usable in one particular context is actually very simple.
    Designing the interface so that it can be generally usable in
    the widest number of different contexts is another matter, not
    to mention implementing it in a manner so that it will have
    adequate performance for all possible uses.

    It's worth implementing some simple containers and algorithms
    yourself, to understand the issues better, but doing so will not
    help you better understand the STL.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Oct 23, 2008
    #10
  11. Ankur Arora

    Guest

    On 23 Oct, 14:51, Ankur Arora <> wrote:
    > Here's what I have come up with so far (very basic, algorithmic
    > steps):-
    > - use of pointers to manipulate the deck since we will be doing a lot
    > of shuffling. A link list would be a good choice with each node
    > representing a card and the link list chain representing a particular
    > ordering.


    This sounds good. I'd recommend the type of linked list where you keep
    track of both the first and the last element in the list. This makes
    adding to the end much quicker.

    Hope that helps.
    Paul.
     
    , Oct 23, 2008
    #11
  12. Ankur Arora

    Ankur Arora Guest

    On Oct 23, 11:04 pm, Pete Becker <> wrote:
    > On 2008-10-23 16:22:52 -0400, said:
    >
    > > On 23 Oct, 14:51, Ankur Arora <> wrote:
    > >> Here's what I have come up with so far (very basic, algorithmic
    > >> steps):-
    > >> - use of pointers to manipulate the deck since we will be doing a lot
    > >> of shuffling. A link list would be a good choice with each node
    > >> representing a card and the link list chain representing a particular
    > >> ordering.

    >
    > > This sounds good. I'd recommend the type of linked list where you keep
    > > track of both the first and the last element in the list. This makes
    > > adding to the end much quicker.

    >
    > When you're manipulating a deck of 52 cards, making append fast is not
    > important. An array is a much more natural data structure for this
    > purpose, and it's much easier to use.
    >
    > --
    >   Pete
    > Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
    > Standard C++ Library Extensions: a Tutorial and Reference
    > (www.petebecker.com/tr1book)


    Guys..Thanks for the tips!
    A circular link list could also be considered..i think.
     
    Ankur Arora, Oct 24, 2008
    #12
  13. Ankur Arora

    Guest

    I will really appreciate if anybody could please post the solution ?
    Thanks
     
    , Nov 7, 2008
    #13
  14. Ankur Arora

    Kai-Uwe Bux Guest

    to restore context:
    > You are given a deck containing n cards. While holding the deck:
    >
    > 1. Take the top card off the deck and set it on the table
    > 2. Take the next card off the top and put it on the bottom of the deck
    > in your hand.
    > 3. Continue steps 1 and 2 until all cards are on the table. This is a
    > round.
    > 4. Pick up the deck from the table and repeat steps 1-3 until the deck
    > is in the original order.
    >
    > Write a program to determine how many rounds it will take to put a
    > deck back into the original order.


    wrote:

    > I will really appreciate if anybody could please post the solution ?


    I shall ignore the requirement that STL not be used. I hope that my solution
    therefore will not qualify for the homework (also, some time has passed).
    Also, I shall not use the algorithm outlined in the description of the
    problem but use an entirely different idea that will give the same output.

    Also: I will assume that the compiler supports long long (you really want
    some arbitrary length integral type). The program will silently wrap around
    and not report the overflow. I attach some values that I found, which
    illustrate that point. At n=280, 2^32 will not suffice and at n=1004, the
    result is beyond 2^64. (These numbers also illustrate why I will not
    determine the order of the permutation by counting: it would take forever.)


    #include <cassert>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <iterator>
    #include <iostream>

    // #include <kubux/integer>

    // typedef kubux::integer arithmetic_type;
    typedef unsigned long long arithmetic_type;

    typedef std::vector< unsigned long > permutation;

    permutation id ( unsigned long n ) {
    permutation result;
    result.reserve( n );
    for ( unsigned long i = 0; i < n; ++i ) {
    result.push_back( i );
    }
    return ( result );
    }

    void shuffle ( permutation & perm ) {
    permutation result;
    result.reserve( perm.size() );
    while ( ! perm.empty() ) {
    result.push_back( perm.front() );
    perm.erase( perm.begin() );
    std::rotate( perm.begin(), perm.begin() + 1, perm.end() );
    }
    std::swap( result, perm );
    }

    arithmetic_type gcd ( arithmetic_type a, arithmetic_type b ) {
    if ( b < a ) {
    std::swap( a, b );
    }
    while ( a != 0 ) {
    arithmetic_type dummy( b % a );
    b = a;
    a = dummy;
    }
    return( b );
    }

    arithmetic_type lcm ( arithmetic_type a, arithmetic_type b ) {
    arithmetic_type quot = b / gcd(a,b);
    return ( a * ( b / gcd(a,b) ) );
    }

    arithmetic_type order ( permutation const & p ) {
    arithmetic_type l ( 1 );
    std::set< unsigned long > still_free;
    std::copy( p.begin(), p.end(),
    std::inserter( still_free, still_free.end() ) );
    while ( ! still_free.empty() ) {
    unsigned long index = *(still_free.begin());
    unsigned long where = index;
    arithmetic_type length = arithmetic_type();
    do {
    ++ length;
    where = p[where];
    still_free.erase( where );
    } while ( where != index );
    l = lcm( l, length );
    }
    return ( l );
    }

    arithmetic_type number ( unsigned long n ) {
    permutation p ( id( n ) );
    shuffle( p );
    return ( order( p ) );
    }

    int main ( void ) {
    for ( unsigned long n = 1; ; ++n ) {
    std::cout << n << " --> " << number(n) << '\n';
    }
    }


    /*
    Some values:
    1 --> 1
    3 --> 2
    5 --> 3
    6 --> 5
    7 --> 6
    10 --> 9
    12 --> 28
    18 --> 70
    23 --> 210
    35 --> 308
    38 --> 990
    44 --> 2618
    58 --> 13300
    67 --> 27720
    68 --> 203490
    83 --> 360360
    111 --> 1021020
    112 --> 1511640
    113 --> 6230070
    162 --> 59254020
    185 --> 1376845470
    230 --> 2153331180
    280 --> 56270739378
    315 --> 591118103520
    338 --> 2328245689770
    441 --> 7600186994400
    554 --> 247651817843430
    689 --> 3993173946822060
    839 --> 16415300091350160
    907 --> 24858416865744000
    944 --> 27303154083485280
    947 --> 150103870204688400
    949 --> 4073014663549605312
    1004 --> 889351355342914944480
    1307 --> 1423178772983737169400
    1649 --> 709044136174739580415200
    1705 --> 1384460057373814306578000
    1799 --> 17843737077119301787398960
    1934 --> 26473022063487459901268520
    1948 --> 412108799554731513698624160
    2591 --> 10132942664275877164628800800
    2606 --> 492252055940052814523176659600
    3011 --> 4061133619046911989389682594720
    3368 --> 28987127583211271154658957499520
    3472 --> 28786869259134681128048175521961000
    4037 --> 13968231274398330387225456621929156160
    4451 --> 44613968405036781772417636768076148600
    4743 --> 47127723619287268204539720673201387200
    4924 --> 1015809212163473864903934664023523839570
    6387 --> 91321559704961673892472654357633041307427900
    7772 --> 9027755125844404863192942627813586968870041001600
    8921 --> 46137862364188321895572339367552812592575522848000
    9749 --> 1514900913329751772087279522915115470030101944229120
    */


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Nov 7, 2008
    #14
    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. Andrew Francis
    Replies:
    0
    Views:
    426
    Andrew Francis
    Jun 28, 2006
  2. =?Utf-8?B?Y2FzaGRlc2ttYWM=?=

    Solution file not in the solution folder

    =?Utf-8?B?Y2FzaGRlc2ttYWM=?=, Sep 12, 2006, in forum: ASP .Net
    Replies:
    2
    Views:
    1,114
    Laurent Bugnion
    Sep 12, 2006
  3. , India
    Replies:
    17
    Views:
    1,066
    James Kanze
    Oct 1, 2007
  4. Replies:
    8
    Views:
    513
  5. email55555 email55555

    [SOLUTION] Ruby Quiz #14 LCD Numbers ( solution #2 )

    email55555 email55555, Jan 9, 2005, in forum: Ruby
    Replies:
    16
    Views:
    284
    David Tran
    Jan 10, 2005
Loading...

Share This Page