Author |
Topic: Two-face: How's this answer? (Read 6596 times) |
|
Chronos
Full Member
 
Gender: 
Posts: 288
|
 |
Two-face: How's this answer?
« on: Sep 28th, 2002, 12:17pm » |
 Quote  Modify
|
So, Two-Face wants to create a random 2000 digit binary password, subject to the constraint that the password has exactly 1000 of each digit. Now, if those were the only constraints, I would put 2000 scraps of paper in a hat, half with each digit, and pull them out one at a time. But the only random-number generator he wants to use is his coin (I presume that he can use pencil and paper or a computer or whatnot for bookkeeping, just not for random number generation).
So, here's how I would proceed: First, he flips his coin 2000 times in a row, and writes down (in order) 1 for each tails, and 2 for each heads. If he's lucky, this will give him a thousand of each, and he's done (this is the best-case answer, which I think the problem was asking for). More likely, though, he has an imbalance of a few dozen or so. Without loss of generality, let's say that he has more 2s than 1s: He has 1000 + n twos, and 1000 - n ones. Now he has to randomly select n of his twos and change them. He does this in n steps: In each step, he goes through a binary tree to choose one of his 1000 + n twos. This will probably take ten flips per step, since he probably doesn't have much more than 1024 twos. If his binary tree gives him a value outside the range of possible twos, then he just throws that step out and redoes it. Assuming that n is 24, he can then get his entire sequence in about 2240 flips: 2000 flips for the original unbalanced sequence, and 24 steps of 10 flips each to balance it. A smaller imbalance would take fewer. There is also the chance that we might have to throw out some trials, so it might take longer, as well, but as long as n is no greater than 24, this shouldn't happen too often.
The only problem is if n is greater than 24. In that case, we're going to be throwing away almost half of our balancing steps, until we get down to 24. This is very inefficient, so I really ought to find a quicker way to handle the first several balancing steps.
|
|
 IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Two-face: How's this answer?
« Reply #1 on: Sep 28th, 2002, 12:45pm » |
Quote Modify
|
In retrospect, my solution is not quite optimal, in terms of expected number of flips. There are a total of (2000 choose 1000) valid passcodes, which is equal to 21994.191180, so it should, in principle, be possible to do this in 1994 or 1995 flips (if we're not unlucky enough to get an out-of-bounds answer from our decision tree: If this happens, then the number of flips is potentially doubled). However, I can think of no simple way to implement this, and if we assume that operations other than flips take time as well and that we're optimizing for time (rather than for number of flips), then even in the best case, my method is probably quicker than this.
|
|
IP Logged |
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Two-face: How's this answer?
« Reply #2 on: Sep 29th, 2002, 11:54am » |
Quote Modify
|
on Sep 28th, 2002, 12:45pm, Chronos wrote:| There are a total of (2000 choose 1000) valid passcodes, which is equal to 21994.191180... |
|
Wait...isn't "choose" used for combinations? This would be a permutation.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Two-face: How's this answer?
« Reply #3 on: Sep 29th, 2002, 12:44pm » |
Quote Modify
|
Actually it's combinations. At first you might think it would be permutations, since a passcode like 2310 isn't the same as 0123. But we have a lot of repeated characters in Two-Face's password. To determine the number of satisfactory passcodes, we want all non-identical permutations of the string:
22222222 .... (1000 times) 111111111 ..... (1000 times)
As an example of two permutations that produce non-identical passcodes, note that if you permute the first two elements of the above string, there's no change in the passcode. So one way of figuring out the total number of passcodes would be to start with 2000! and subtract the overcounts, but that would be messy. An easier way is to note that once you figure out where the 2s are, the remaining slots are automatically filled with 1s, since it's a binary sequence. Thus the number of possible sequences is really the number of ways you can pick 1000 out of 2000 slots to be 2s, which is nchoosek(2000,1000).
Chronos: I'll have to think about your algorithm for a little bit. The one I had in mind is expected to consume 4000 flips.
|
| « Last Edit: Sep 29th, 2002, 12:50pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Two-face: How's this answer?
« Reply #4 on: Sep 30th, 2002, 11:35am » |
Quote Modify
|
Here's another idea on how to randomize the sequence:
1) Construct a starter sequence with 2000 coin flips.
2) Flip the first number, then the second number, then the third number, and keep going until there is an equal number of 2s and 1s in the sequence.
I'm just not sure that this is perfectly random, though.
Ooh! I had a better idea:
1) Enumerate all the permutations of 2s and 1s.
2) Flip the coin 1995 times to pick one of the permutations.
This gives an expectation of about 1995 flips. It also has the upside that it will safely occupy Two-Face's schedule for quite some time...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Two-face: How's this answer?
« Reply #5 on: Sep 30th, 2002, 12:01pm » |
Quote Modify
|
on Sep 28th, 2002, 12:45pm, Chronos wrote:| There are a total of (2000 choose 1000) valid passcodes, which is equal to 21994.191180, so it should, in principle, be possible to do this in 1994 or 1995 flips (if we're not unlucky enough to get an out-of-bounds answer from our decision tree: If this happens, then the number of flips is potentially doubled). |
|
Regarding generating out-of-bounds answers with the 1995 flips, we can protect ourselves from much extra work by short-circuiting the coin flips if we detect that we will be out of bounds. If we short-circuit as soon as we know that our answer will be out-of-bounds, then our expectation is only marginally larger than 1995. I think it's about 2002 coin flips.
|
| « Last Edit: Sep 30th, 2002, 12:03pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Two-face: How's this answer?
« Reply #6 on: Sep 30th, 2002, 8:27pm » |
Quote Modify
|
Quote:
1) Construct a starter sequence with 2000 coin flips.
2) Flip the first number, then the second number, then the third number, and keep going until there is an equal number of 2s and 1s in the sequence.
|
|
Not equally random. At first I thought I could explain this easily by saying that after constructing an initial sequence, your scheme is less likely to invert coins that are further to the right in that initial sequence. However, I'm not sure what that implies. I ended up constructing a table which proves it's not equally random, just by counterexample. Without loss of generality, assume Two-Face wants a four-digit binary passcode sequence that consists of two heads and two tails. The left hand column below shows the possible initial sequences. Some of these initial sequences are already satisfactory sequences, and I have denoted those with a parenthesized number next to them. The right hand column shows the satisfactory sequence each initial sequence maps to after inverting coin polarities from left to right until the number of heads equals the number of tails.
Since there are six satisfactory sequences, the probability of getting any particular satisfactory sequence should be one-sixth. However, the right-hand column shows us that there are more ways to get some sequences than others. Histogrammish table below:
I'm not sure how to explain intuitively why THHT (1) is twice as likely to show up than HTHT (2). I think it has to do with the nonuniformity in the number of polarity alternations in the set of initial sequences. For instance, the relatively low-likelihood satisfactory sequences HTHT (2) and THTH (5) both have three polarity alternations if you read them from left to right. But HHTT (1) only has one alternation. It's all vague to me.
Quote:
1) Enumerate all the permutations of 2s and 1s.
2) Flip the coin 1995 times to pick one of the permutations.
|
|
Enumerating all the possible sequences in a table, and then indexing the table, was an idea I anticipated. I chose the numbers n=2000 and k=1000 so that nchoosek(n,k) would probably be more than the number of atoms in the universe.  Theoretically the table lookup idea would work, and it would minimize the number of necessary flips. But practically, we couldn't store all those sequences on a hard disk.
Chronos: I tried to do a formal calculation of the expected number of flips your solution would take, but I can't figure out how to do it.
|
| « Last Edit: Sep 30th, 2002, 8:36pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Two-face: How's this answer?
« Reply #7 on: Oct 1st, 2002, 6:36am » |
Quote Modify
|
I have it! The optimal strategy!
0) Two-Face flips the coin 1000 times. This gives the last 1000 digits, exactly as flipped.
1) Let's call the number of 2s in the last 1000 digits t. Two-Face flips the coin (1000 - t) times, to give the number of 2s in the first 500 digits.
2) If t is even, then we can proceed directly in the next step, but if t is odd, we must flip a coin to determine where we will break these t flips up.
3) Break the t flips up in the middle (with the preceeding caveat for when t is odd). The number of tails before the break gives the number of 2s in the first 250. By breaking it up recursively like this, you can determine all the first 500 digits using these t flips.
4) Count the number of 2s in the first 500 digits. Call this number s. Now we flip the coin (1000 - t - s) times, to determine the number of 2s between digits 501 and 750. Break these up recursively the same way you did in step 3)
5) I hope you can see the pattern ... The only thing that remains to be worked out is what to do when you can't divide the partitions in half any more ...
All I'm doing is taking 1000 2s and partitioning them successively into smaller and smaller bins. Sort of like a quicksort. Originally, this was an O(n log n) solution, but with the recursive break-up method, you can use more of the information in your coin flips.
On average, we get about 2000 flips, and a completely random string of 2s and 1s!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Two-face: How's this answer?
« Reply #8 on: Oct 1st, 2002, 11:21pm » |
Quote Modify
|
on Sep 30th, 2002, 11:35am, James Fingas wrote:
1) Enumerate all the permutations of 2s and 1s.
2) Flip the coin 1995 times to pick one of the permutations.
This gives an expectation of about 1995 flips. It also has the upside that it will safely occupy Two-Face's schedule for quite some time... |
|
Looks like this method should average less than 2000 flips. Successfully picking the number has an expectation of 1.75 attempts (adding all the probabilities gives the number of attempts as 21995/21994.19118 = 1.75). One of these attempts uses 1995 flips, and a failed attempt (occuring on average 75% of the time) is very likely to require fewer than 6 flips before reaching too large a value.
Quote:| I have it! The optimal strategy! |
|
I am unable to follow the proposed method. A demonstration example of the method with a simple case like 10 flips instead of 2000, would help.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
 |
The Optimal Solution (example)
« Reply #9 on: Oct 2nd, 2002, 5:55am » |
Quote Modify
|
For the enumeration method, you're right, it only takes about 1996.8 flips on average to get a result. I miscalculated slightly...
To show how my partitioning method works, let's consider the 8-bit case. (I haven't figured out how to make it work simply for lengths that aren't powers of 2).
1) Flip a coin 4 times to get the last four bits.
-you flip HTHH
2) Count the number of heads you got, and call this t. You now have to distribute 4-t heads into the first four positions. If t is less than 2, it will be easier to distribute tails (sorry, this part is new!).
-(4-t) is 1 in this case
3) Now flip the coin 4-t times to figure out how many heads are in the first two positions.
-you flip the coin once, and get H.
4) Now you must break up your string of flips from step 3 into two pieces to decide how those 4-t flips are distributed into the first and second positions. Because 4-t is odd, flip a coin to see where the break is.
-you flip the coin, and get T. Therefore, you break after the H--the first position gets H and the second position gets T.
5) We'll skip the recursion because we're already at the leaves, and go on to find the bits for the remaining positions, 3 and 4.
-you flip the coin zero times to learn that there are zero heads in position 3. This also gives you zero heads in position 4.
6) Now we are finished! Let's look at our completed bit string:
HTTT HTHH
<UPDATE --- READ BELOW!>
Uh oh ... I just figured out the problem with partitioning. It isn't completely random either! It turns out that it takes fewer flips on average than the expected value! It does this by returning certain combinations with more likelihood than others 
I guess it isn't the optimal solution after all 
|
| « Last Edit: Oct 2nd, 2002, 6:28am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Two-face: How's this answer?
« Reply #10 on: Oct 2nd, 2002, 7:52am » |
Quote Modify
|
Just saw this problem. My immediate intuition agrees with posts I see from Chronos and SWF: 1995 @ 1.75178. I'm fairly certain this is the optimal soln from past experience, but admittedly only had a few minutes to give to it.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Two-face: How's this answer?
« Reply #11 on: Oct 2nd, 2002, 7:30pm » |
Quote Modify
|
James Fingas, thanks for the example. It seems to work for the case you give, but since you said it isn't optimal, I didn't study the method closer. For the problem of not being a power of two, would it help if the first step was 976 flips such that the number remaining was 1024?
Your approach gives an idea that may result in a very small improvement on the enumeration method. Start with 1000 flips. Then based on the number of heads, in those 1000, make a list of the remaining possibilities and use the enumeration technique to resolve the rest. The advantage is a reduction in number of failed attempts.
For example, if the first 1000 flips had 500 heads, the second 1000 must contain 500 heads. That means 2994.691 possiblities for filling the 2nd stage, which results in an average 1.239 attempts per success, compared to 1.75 with the old method. Seems like it would take more bits to identify a failed attempt this way, but it may be worth it. To make sure, somebody (other than me) would have to figure the probabilties of all the possible number of heads in the first 1000 flips and combine for an overall expectation.
Does anybody have an easy way to calculate out the Nth combination on a sorted list of the possible 2000 bit numbers, so a full list does not have to be made to use the enumeration.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Two-face: How's this answer?
« Reply #12 on: Oct 3rd, 2002, 10:02am » |
Quote Modify
|
SWF, I think your optimization falls victim to the same problems my "optimal" solution did. The problem is that the distribution of the first 1000 bits in the solutions is not equal to the distribution of 1000 bits when you flip them. To illustrate, consider the 8-bit case:
There are 70 possible 8-bit codes with 4 1s and 4 0s. Only one of these starts with "1111". So the probability of getting "1111 0000" with any perfect method must be 1/70. However, if you flip a coin four times, the odds of getting "1111" are 1/16. Therefore, you don't get the right distribution of probabilities.
There are many different methods which are completely random, but don't give an equal probability for all the different possibilities. These include my original method, my not-actually-optimal method, your suggested improvement to the enumeration method, and this one (which has an expectation of only two flips!)
0) Start with 11111 ... 111100000 ... 00000.
1) Flip a coin. If you get heads, use the code you have already generated.
2) If you get tails, then generate the next permutation in the series ( eg. the first time, it's 11111 ... 11101000 ... 00000 )
This one can also generate any permutation, but obviously they don't all have the same probability.
As for generating the nth permutation, here's one way to do it, given the number x which is initially the binary number you generate with 1995 coin flips. Here's my pseudocode:
void generatePermutation( int x, int * permutation ) {
int twosLeft = 1000;
int xTemp = x; /* a 'scratch' variable for x */
int i;
/*We base this on the simple principle that we order the
permutations in decreasing (numerical) order. The array
passed in is expected to be of size 2000 */
for (i:=0; i < 2000; i++)
if (xTemp <= nchoosek(2000-i-1, twosLeft-1)) {
/*this digit is a 2*/
permutation[i] := 2;
twosLeft--;
} else {
/*this digit is a 1*/
permutation[i] := 1;
xTemp -= nchoosek(2000-i-1, twosLeft-1);
}
}
If the value for x is small, then the permutation starts with a '2', and if the value is large, it starts with a '1'. The cutoff is equal to the number of permutations with one less digit, and one less '2'.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Two-face: How's this answer?
« Reply #13 on: Oct 19th, 2002, 8:54pm » |
Quote Modify
|
Nice routine. I'll have to remember that technique. I tried actually finishing it off into a complete program and running it (for much smaller digit lengths, since you get overflow even with 64-bit integers at more than 66 digits in the passcode). I noticed a small blemish: if you want the combinations to be numbered from 0, the "xTemp <=" should be "xTemp <". (The program is OK as is if you want to number them from 1, so I'm not sure whether this was a bug, but I prefer to number them from 0.) Also, there's an unstated assumption that nchoosek(n, -1) = 0, but that's reasonable.
I was thinking about a technique to even out the number of flips. It's the same idea that cropped up in another thread, where the problem was to use one fair coin to decide the outcome of a contest between two players in which the first player is supposed to win with exactly some given probability p != 1/2. Let the sequence of flips a,b,c,... define a binary fraction 0.abc..., and stop as soon as the outcome is definitely different from p, with the first player winning if it's less and the second if it's greater.
We can do the same here, except that instead of one threshold between two outcomes, there are nchoosek(2000,1000)-1 thresholds between nchoosek(2000,1000) outcomes. Assign the number i/nchoosek(2000,1000) to the ith threshold (0<i<nchoosek(2000,1000)). For simplicity, let's also include the extremes 0 and 1 (=0.1111... -- see the 0.999... thread ).
Then Twoface flips his coin until the bitstring he's seen so far is not a prefix of any of the thresholds. At that point its value is definitely between two consecutive thresholds i, i+1, so he chooses the ith combination.
I think this must be optimal in terms both of expected number of flips and standard deviation of the number of flips. I haven't worked out the numbers, though.
|
| « Last Edit: Oct 19th, 2002, 8:58pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Two-face: How's this answer?
« Reply #14 on: Oct 21st, 2002, 10:55pm » |
Quote Modify
|
I think that James' algorithm will work, and if it doesn, it's clearly optimal in terms of number of flips (and probably fast enough that we don't need to worry about other operations). There's still some analysis to be milked out of this problem, though.
For one thing, it should be clear that no algorithm which uses an exact number of flips will give you a uniform distribution of valid passcodes. For that to happen, each valid passcode would have to be generated by the same number of coin sequences, which means that the number of passcodes must be a factor of the number of sequences. But for any given fixed number of flips, the number of possible sequences must be a power of two, so all factors of the number of sequences must also be a power of two. And we know that the number of valid passcodes isn't a power of two.
As an extention of the above, no algorithm which uses a bounded number of flips will give you a uniform distribution, either. Because if it did, then you could devise a corresponding algorithm which used exactly that upper bound number of flips, and just ignored some flips at the end as needed. But that's prohibited by the reasoning above.
And as an aside, Willy, could you show us your 4000 flip solution? Granted that it's obviously not optimal, I'm still curious.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Two-face: How's this answer?
« Reply #15 on: Oct 21st, 2002, 11:30pm » |
Quote Modify
|
Reading it again, I see I wasn't clear about the motivation for my last post. In James's solution (and some of the other ones), there are 21995 possible outcomes of flipping the coin, but there are fewer possible combinations than that. So there's a possibility of getting a sequence of flips that's out of range and having to try again. I wanted to eliminate that.
I suspect (but didn't prove) that my proposed modification doesn't change the expected number of flips, but does reduce the variance by getting rid of those cases. I suppose there are so few of them that even if it does reduce the variance, it doesn't reduce it by much, though.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Two-face: How's this answer?
« Reply #16 on: Oct 22nd, 2002, 12:39am » |
Quote Modify
|
on Oct 21st, 2002, 10:55pm, Chronos wrote:
And as an aside, Willy, could you show us your 4000 flip solution? Granted that it's obviously not optimal, I'm still curious. |
|
OK. I don't have time to read this thread skeptically right now, but here was my algorithm.
The first algorithm that came to mind was to make a table with all C(2000,1000) possibilities and then just flip enough coins to index those possibilities. But C(2000,1000) is a very big number, which makes this method impractical. (However I guess you foxes have gotten around this; I'll read the thread more carefully later.)
Sacrificing optimality for feasibility, I had the following algorithm in mind. Let's say heads maps to "1", and tails maps to "2". First, Two-Face determines the first digit in the passcode by flipping a fair coin. If the coin turns up heads, flip a biased coin in which the probability of turning up heads is 999/1999. What is this fraction? This is the probability that the second coin turns up heads -- conditioned on the fact that the first is heads, and that there are supposed to be 1000 heads in total out of 2000. Two-Face continues flipping coins in this fashion, adjusting the bias along the way such that the probability of heads is conditioned on the results of the tosses so far. The result is a random 2000 digit binary password satisfying the given constraints.
However, note that Two-Face does not have any biased coins, just a fair coin. But we know from the COIN BIASING riddle (medium section) that we can use unbiased coins to make biased coin experiments. If we want a bias of probability p, first rewrite p in binary (e.g. 1/3 = .01010101 ...) Then repeatedly flip the unbiased coin, concatenating 0s and 1s to a running binary decimal value according to the results of the unbiased coin. As soon as this running binary decimal value is larger than p, we output heads, and if it is less than p, we output tails.
All that remains is to calculate the expected number of flips this algorithm consumes. Well, the expected number of flips that are required to simluate any bias p is 2. And Two-Face needs to make 2,000 biased tosses. So the total expected number of flips is 4,000.
Hope this analysis was right 
|
| « Last Edit: Nov 5th, 2002, 11:04pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Two-face: How's this answer?
« Reply #17 on: Oct 22nd, 2002, 5:57am » |
Quote Modify
|
Ye, that's actually a fairly interesting soln Will!
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Two-face: How's this answer?
« Reply #18 on: Nov 5th, 2002, 11:48pm » |
Quote Modify
|
Thanks Eric!
Alright I scanned the thread, and it seems like at some point people became complacent with the 1996 flip enumeration scheme. However, as I mentioned in my Sept 30 2002 post, I would argue that the enumeration scheme is not implementable at all because the number C(2000,1000) is gargantuan. So I don't think my 4000 flip scheme is "obviously not optimal", unless there's some really clever way to store all this information, or if you have an algo to quickly generate the Nth combination. In my Oct 22 2002 post, I thought James had figured out a way to do the latter, but now I see that his code produces permutations, not combinations.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Two-face: How's this answer?
« Reply #19 on: Nov 6th, 2002, 1:34am » |
Quote Modify
|
on Nov 5th, 2002, 11:48pm, william wu wrote:| In my Oct 22 2002 post, I thought James had figured out a way to do the latter, but now I see that his code produces permutations, not combinations. |
|
James's code does the right thing even though he used the word "permutation" instead of "combination" in his writeup.
The problem is that, as you've noted, C(2000,1000) is enormous. The variables in James's code have to be wide enough to hold a number of about that size. Notice that x is passed in as the 1995-bit number that Two-face gets by flipping his coin 1995 times.
As I mentioned in a previous post, I actually translated James's pseudocode into C and ran it. I used a trick to make the nchoosek calls fast -- my nchoosek remembers the last arguments and value that it was called with and uses them to get the next value quickly if the new arguments are within 1 of the old arguments. The program works fine, but I have at most 64-bit integers and 128-bit floats available from my C compiler (gcc), so I couldn't run it on anything like the full problem size. I got it to work up to N=49 (where 2*N is the passcode length).
I didn't work out the time complexity, so I don't know if it would be practical to run the program if you had a bignum package that could handle 1995-bit integers. This doesn't sound like a hard question, but I'm too tired to think about it now.
|
| « Last Edit: Nov 6th, 2002, 2:08am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Two-face: How's this answer?
« Reply #20 on: Nov 6th, 2002, 7:41am » |
Quote Modify
|
on Nov 6th, 2002, 1:34am, TimMann wrote:
James's code does the right thing even though he used the word "permutation" instead of "combination" in his writeup.
|
|
Oh ok. That's where I got confused. Well, I'll have to run it myself and plot a histogram to believe it
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Two-face: How's this answer?
« Reply #21 on: Nov 7th, 2002, 12:56am » |
Quote Modify
|
Plotting a histogram isn't the test you want. The program simply takes the number n generated by flipping the coins as input, and gives the nth combination in canonical order as output. So you just want to test that as n increases, the combinations are generated in order as expected.
Anyway, the answer to the question about what would happen with bignums (arbitrary precision integers) is very favorable. I still didn't bother working out the time complexity, but it's low, so even with the overhead of using bignums the program is fast. There's a quite usable bignum package that comes with the SSL library, so if you're running Linux you probably already have it installed, as I did. It took only a few minutes to convert my version of the program over to using bignums. The resulting program runs lightning fast; even for the full 2000-digit problem size, it runs in about 30 milliseconds on my machine. So Two-face will spend a lot longer flipping his coin by hand than he will running the program to convert the answer to a combination!
|
| « Last Edit: Nov 7th, 2002, 1:15am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
prince
Newbie
Posts: 49
|
|
Re: Two-face: How's this answer?
« Reply #22 on: Dec 6th, 2002, 2:11pm » |
Quote Modify
|
I think the question is flawed (no surprise considering the source). There's no way to guarantee 1000 1's and 1000 2's and be completely random.
In any scheme, the last digit can be predicted, knowing the previous 1999. I don't necessarily mean the last digit in the sequence (as some have proposed selecting the last 500 first), but the last digit determined.
Granted this answer spoils the fun of the puzzle, but it seems this point has been ignored.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Two-face: How's this answer?
« Reply #23 on: Dec 6th, 2002, 2:19pm » |
Quote Modify
|
You're wrong. You don't have to construct the number digit-by-digit. You can always pick from a given set uniformly at random, and that is what the problem asks for.
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
prince
Newbie
Posts: 49
|
|
Re: Two-face: How's this answer?
« Reply #24 on: Dec 6th, 2002, 2:29pm » |
Quote Modify
|
Thanks Eric,
I've spent too long randomizing people. Of course, you're correct.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print