Programming Puzzle

[Dissipate]

Here is an interesting programming puzzle you might want to try:

You want to program a card game that uses a standard deck of 52 playing cards. In order to program such a game you have to simulate a deck of cards being dealt one by one off the top of a virtual deck. Hence, you must write a function that shuffles the deck of cards before the cards are dealt.

So an array of integers from 1 - 52 is passed into your function Shuffle(). Shuffle() then randomizes the location of all the numbers in the array to simulate the deck of cards being thoroughly shuffled. The only things you have to work with are the array itself and a random number generator, plus some integer variables to use as placeholders and of course standard loops.

Explain the algorithm of the Shuffle() function.

 

[Cattlegod]

do your own homework 🙂

 

[Goosemaster]

Originally posted by: Cattlegod
do your own homework 🙂

:laugh:

 

[wfbberzerker]

are you serious?

 

[Kyteland]

Edit: nevermind, that was what you wanted.

Removed. Do your own homework.

well, Notfred posted his so I'll put it back.

#include "rand.h"
#include <algorithm>

template<typename Type>
void Shuffle(uint count, Type & entries)
{
while (count > 1)
{
uint selectedIndex = CRand::Get_Rand(count--);
std::swap(entries[selectedIndex], entries[count]);
}
}

 

[notfred]

Some random pseudo language:

Shuffle(CardArray deck){
int i = deck.length;
while (--i) {
int j = rand (i + 1);
Card temp = deck[ j ];
deck[ j ] = deck[ i ];
deck[ i ] = temp;
}
}

This iterates over the deck 52 times, each time replacing the element at 52 - i with a different randomly selected element in the array.

Note: I didn't invent this, it's called a Fisher-Yates shuffle.

 

[Dissipate]

Originally posted by: Cattlegod
do your own homework 🙂

Not homework. I'm not taking any programming classes this quarter. 🙂

I just thought this was an interesting/elegant solution to a problem I used to wrestle with as a kid trying to program card games.

 

[notfred]

So is this thread done then?

 

[Dissipate]

Originally posted by: notfred
So is this thread done then?

Did you peek at the solution?

 

[notfred]

Originally posted by: Dissipate

Originally posted by: notfred
So is this thread done then?

Did you peek at the solution?

I posted a solution. It was one I already knew. Does that count as peeking?

 

[Dissipate]

Originally posted by: notfred

Originally posted by: Dissipate

Originally posted by: notfred
So is this thread done then?

Did you peek at the solution?

I posted a solution. It was one I already knew. Does that count as peeking?

Yep. If you didn't derive the algorithm yourself you cheated.

Answer this question though:

How does the number of seeds of the PRNG used to determine the swap values affect the algorithm?

 

[notfred]

Originally posted by: Dissipate

Originally posted by: notfred

Originally posted by: Dissipate

Originally posted by: notfred
So is this thread done then?

Did you peek at the solution?

I posted a solution. It was one I already knew. Does that count as peeking?

Yep. If you didn't derive the algorithm yourself you cheated.

Answer this question though:

How does the number of seeds of the PRNG used to determine the swap values affect the algorithm?

I don't see how it's cheating to have seen the answer before. 😛
I'm not an expert on pseudorandom number generators, but don't they generally just have 1 seed?

 

[Rayden]

Let me propose another interesting programming problem.

You are given an array of 100 elements with numbers 0-100 so of course one is missing. How do you find out which number is missing in O(n) time? (ie as fast as possible)

 

[notfred]

Originally posted by: Rayden
Let me propose another interesting programming problem.

You are given an array of 100 elements with numbers 0-100 so of course one is missing. How do you find out which number is missing in O(n) time? (ie as fast as possible)

Are they in sorted order? And anyway, just iterating across them would be O(n) time. If they're in sorted order you could do a binary search and get the answer in O(log n) time.

 

[mugs]

Originally posted by: Rayden
Let me propose another interesting programming problem.

You are given an array of 100 elements with numbers 0-100 so of course one is missing. How do you find out which number is missing in O(n) time? (ie as fast as possible)

Add them up and subtract the total from whatever the total should be

 

[Kyteland]

Originally posted by: notfred
I'm not an expert on pseudorandom number generators, but don't they generally just have 1 seed?

Quite a few use multiple seeds. The one we use at work uses 3.

 

[z0mb13]

Originally posted by: mugs

Originally posted by: Rayden
Let me propose another interesting programming problem.

You are given an array of 100 elements with numbers 0-100 so of course one is missing. How do you find out which number is missing in O(n) time? (ie as fast as possible)

Add them up and subtract the total from whatever the total should be

winnarrrr!!

 

[Rayden]

Originally posted by: z0mb13

Originally posted by: mugs

Originally posted by: Rayden
Let me propose another interesting programming problem.

You are given an array of 100 elements with numbers 0-100 so of course one is missing. How do you find out which number is missing in O(n) time? (ie as fast as possible)

Add them up and subtract the total from whatever the total should be

winnarrrr!!

I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

 

[Kyteland]

Originally posted by: Rayden
I guess I was wrong when I specified O(n) time as it is actually O(1). I should have said O(n) or better.

And the sum should be:
0 + 1 + 2 + ... + n = (n)*(n+1)/2

Subtracting n numbers from (n)*(n+1)/2 is O(1)? 😕

 

[chuckywang]

Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

 

[QED]

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

Uhhh... that won't work.

Odd are quite likely that you will pick the same card several times.

Unless you meant to do a check after you pick a card to verify you haven't picked it already.

 

[chuckywang]

Originally posted by: MathMan

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

Uhhh... that won't work.

Odd are quite likely that you will pick the same card several times.

Unless you meant to do a check after you pick a card to verify you haven't picked it already.

You remove any card you already picked from the deck. Hence why you generate a random number between 1-51 on your second go around.

 

[HBalzer]

Originally posted by: Dissipate
Here is an interesting programming puzzle you might want to try:

You want to program a card game that uses a standard deck of 52 playing cards. In order to program such a game you have to simulate a deck of cards being dealt one by one off the top of a virtual deck. Hence, you must write a function that shuffles the deck of cards before the cards are dealt.

So an array of integers from 1 - 52 is passed into your function Shuffle(). Shuffle() then randomizes the location of all the numbers in the array to simulate the deck of cards being thoroughly shuffled. The only things you have to work with are the array itself and a random number generator, plus some integer variables to use as placeholders and of course standard loops.

Explain the algorithm of the Shuffle() function.

What school are you attending?

 

[QED]

Originally posted by: chuckywang

Originally posted by: MathMan

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

Uhhh... that won't work.

Odd are quite likely that you will pick the same card several times.

Unless you meant to do a check after you pick a card to verify you haven't picked it already.

You remove any card you already picked from the deck. Hence why you generate a random number between 1-51 on your second go around.

Ok... I see now-- but you left out that part in your original explanation though.

It also makes the shuffle operation an O(n^2) operation....

 

[chuckywang]

Originally posted by: MathMan

Originally posted by: chuckywang

Originally posted by: MathMan

Originally posted by: chuckywang
Randomly generate a number from 1-52. Put that card as the first card in your shuffled deck. Randomly generate a number from 1-51. Put that card as the second card in your shuffled deck. Etc...

Uhhh... that won't work.

Odd are quite likely that you will pick the same card several times.

Unless you meant to do a check after you pick a card to verify you haven't picked it already.

You remove any card you already picked from the deck. Hence why you generate a random number between 1-51 on your second go around.

Ok... I see now-- but you left out that part in your original explanation though.

It also makes the shuffle operation an O(n^2) operation....

Depends on the complexity of the random number generator. If it's O(1), then the shuffle operation is O(n). If it's O(n), then the shuffle operation is O(n^2).

I'm all ears for an algorithm that can do this with only one use of the random number generator.