Asp Forum - Solution needed..urgent!!

Ankur Arora

10/23/2008 7:42:00 AM

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.

20 Answers

Hendrik Schober

10/23/2008 8:03:00 AM

Ankur Arora wrote:
> 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.

Sounds like a nice homework question.
How far did you get by now? Where are you stuck? Any specific questions
we might help you with finding an answer for?

Schobi
(who just found another exercise idea for torturing his students with)

P.S.: http://www.parashift.com/c++-faq-lite/how-to-post.ht...

blargg.h4g

10/23/2008 9:23:00 AM

In article
<73194abd-bb72-4a04-b2c3-3ed69ded30bb@64g2000hsu.googlegroups.com>, Ankur
Arora <ankurarora81@gmail.com> wrote:

> Hi all,
>
> The following post is probably not appropriate for this group but I

let me guess, you are above all that?

> 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.

This page has some great advice, specifically the part about choosing a
forum: http://www.catb.org/~esr/faqs/smart-ques...

Juha Nieminen

10/23/2008 12:10:00 PM

Ankur Arora wrote:
> Do not use STL.

Any rational reason for this?

Richard Herring

10/23/2008 12:52:00 PM

In message <CQZLk.87$yl1.45@read4.inet.fi>, Juha Nieminen
<nospam@thanks.invalid> 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

red floyd

10/23/2008 1:23:00 PM

Ankur Arora wrote:
> Hi all,
> ["do my homework" redacted]

You can find a good solution here:

http://www.parashift.com/c++-faq-lite/how-to-post.ht...

osmium

10/23/2008 1:39:00 PM

"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.

acehreli

10/23/2008 1:48:00 PM

On Oct 23, 12:42 am, Ankur Arora <ankuraror...@gmail.com> wrote:

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

How about that? Any rationale for that?

Ali

Stuart Golodetz

10/23/2008 1:51:00 PM

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. In other words, you'll learn a whole lot more by
working around the stupid wording of the question than you ever would
have done by merely solving the question itself...

Cheers,
Stu

P.S. It's also worth noting that the question said "STL" and not
"Standard Library". Should we take this to mean that any portions of the
Standard Library which were not inherited from the STL are usable...?

Ankur Arora

10/23/2008 1:51:00 PM

On Oct 23, 2:51 pm, Richard Herring <junk@[127.0.0.1]> wrote:
> In message <CQZLk.87$yl1...@read4.inet.fi>, Juha Nieminen
> <nos...@thanks.invalid> 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 ?

Kai-Uwe Bux

10/23/2008 2:39:00 PM

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

comp.lang.c++

Solution needed..urgent!!

Ankur Arora

Hendrik Schober

blargg.h4g

Juha Nieminen

Richard Herring

red floyd

osmium

acehreli

Stuart Golodetz

Ankur Arora

Kai-Uwe Bux

x Login to ForumsZone