Mini challenge - coin toss « Next Oldest | Next Newest »

 ▼ MikeO Member Posts: 121 Threads: 21 Joined: Jun 2008 03-21-2009, 07:54 PM You want to play a game that requires a coin toss, but you have no coins to toss. Fortunately, you have your trusty HP-67 or (fill in your favorite classic HP programmable calculator.) Create the shortest program you can that will provide a randomized coin toss result. -Mike Edited: 21 Mar 2009, 8:07 p.m. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-22-2009, 09:35 AM Here is a starting point for the HP-67: ```LBL A PI + 3 Y^X FRAC STO A 2 * INT R/S RCL A GTO A ``` To operate: ```Set the display mode to DSP 0 and then perform the following steps: 1. Enter a seed value and press [A]. 2. The program displays 1 for head and 0 for tail. 3. Press R/S to see the next head or tail value. ``` The program uses register A to maintain the current pseudo-random number. I think you can shorten the program if you use a less-than-obvious steps to generate the random numbers. Namir Edited: 22 Mar 2009, 9:48 a.m. Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-22-2009, 09:52 AM Here is a shorter version for the HP-67: ```LBL A 1/X FRAC STO A 2 * INT R/S RCL A GTO A ``` Using 1/X to generate a random number for a coin toss "might" be an acceptable trick. Initial seed should be 0.1 < seed < 0.9 AND 1/seed <> integer. Avoid "nice" fractions that lead to reciprocals that are integers. Here is an HP-41C version (which is 1 step shorter than the HP-67 version shown above) that does not use any memory registers, except the stack: ```LBL COIN 1/X FRC STO Y ST+ X INT STOP X<>Y GTO COIN ``` To start the program, set FIX 0, enter a seed value (0.1 < seed < 0.9 AND 1/seed <> integer), and execute the command XEQ COIN. You get the first coin toss. Press the [R/S] key to view subsequent coin tosses. Namir Edited: 22 Mar 2009, 11:04 a.m. ▼ Chris Dean Member Posts: 120 Threads: 9 Joined: Aug 2005 03-22-2009, 02:58 PM Here is my solution for the 15c ```g RAN# . 5 + g INT 0 represents Heads or Tails 1 the other. This of course assumes the coin does not land on its side, it is evenly balanced and therefore a toss of the coin may be represented by the Uniform distribution. There is no need for a label just press R/S. ``` Edited: 22 Mar 2009, 3:01 p.m. ▼ Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 03-22-2009, 05:13 PM And a step shorter is: ``` g RAN# 2 * INT ``` And on a 41 with games module: ``` XEQ RNDM ST+ X INT ``` or even: ``` 2 XEQ RNDMW ``` - Pauli Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-22-2009, 08:49 PM What would your code look like for an HP-67? Gordon Strickland Junior Member Posts: 18 Threads: 0 Joined: Sep 2007 03-23-2009, 07:16 PM Message #4 notes that one must exclude from the analysis the possibility that the coin lands and stays balanced on its edge. It is perhaps equally important to exclude the possibility of a passing magpie snatching the coin in mid-air and making off with it. ▼ Palmer O. Hanson, Jr. Posting Freak Posts: 901 Threads: 113 Joined: Jun 2007 03-23-2009, 09:03 PM Quote: Message #4 notes that one must exclude from the analysis the possibility that the coin lands and stays balanced on its edge. Here's an old coin flip story from my college days. An engineer and his date were trying to decide whether to go dancing or to a movie. His date said "Heads we go to a movie; tails we go dancing." The engineer asked "What if the coin stands on its edge?" His date replied "Then, we'll take a hotel room for the night." The engineer flipped the coin, it rolled into a crack in the sidewalk and came to rest standing on its edge. His date suggested "Shouldn't we make it two out of three?" Palmer ▼ Jeff Kearns Member Posts: 222 Threads: 21 Joined: Oct 2006 03-23-2009, 09:18 PM Palmer: Didn't you study engineering in university? Jeff Kearns ▼ Palmer O. Hanson, Jr. Posting Freak Posts: 901 Threads: 113 Joined: Jun 2007 03-23-2009, 10:17 PM Quote: Palmer: Didn't you study engineering in university? Yes. University of Minnesota graduating in 1950. Chuck Sommer Junior Member Posts: 27 Threads: 1 Joined: Aug 2007 03-22-2009, 03:05 PM My solution uses a TI-84 Plus silver edition. Take the calculator and toss it in the air to land on the floor with a randomizing rotational motion about it's long axis. Face up is heads, face down is tails. I would never suggest using one of our precious HPs for this task. Chuck ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 03-22-2009, 04:07 PM A voyager will allow a longer series of tosses than any TI. Edited: 24 Mar 2009, 3:40 a.m. Andrés C. Rodríguez (Argentina) Posting Freak Posts: 1,193 Threads: 43 Joined: Jul 2005 03-22-2009, 05:31 PM While it is possible to use the linear congruential method to create pseudorandom sequences of the form x(i) = FRAC ((x(i-1) * a + b) as some of the answers to this challenge suggested, not every value for "a" and "b" gives acceptable random behavior. The matter is throughly discussed in Knuth's "Art of Computer Programming", Vol 2. There, you can find a nice example of a complex and apparently good random generator which, after a few cycles, begins to oscillate within a few answers that repeat themselves in an obviously non-random manner. Knuth dixit: "Never use a random method to generate random numbers" One of the better tests for randomness is the "Spectral test", also discussed in the same book. HP took care, when creating pseudorandom generators, in the HP 25 Applications Manual, and in the HP 41 Standard Pac, to publish programs that pass the Spectral test. I have long memorized them, and used them from time to time. While they are not the shortest, they are short (and fast) enough for usual purposes. For the HP 41: ```RCL 00 9821 * .211327 + FRAC STO oo ``` For the coin toss, simply add: ```2 * INT ``` (An answer of 0 is "heads", an answer of 1 is "tails") Of course, the pseudorandom "seed" can be any number between 0 and 1, stored in Register 00 ▼ Mike T. Senior Member Posts: 282 Threads: 46 Joined: Jul 2005 03-26-2009, 07:44 PM I long ago memorised the following short(ish) pseudo random number generator routine for use on my HP33C. I think this uses a seed value (.5284163) copied from a similar routine somewhere in the HP97 manual - I can't check that anymore and it might not even be the first number in the sequence generated by the HP97 pseudo random number routine, as I used it at the time because I found it the easiest to remember. ```01 - 73 . 02 - 5 5 03 - 2 2 04 - 8 8 05 - 4 4 06 - 1 1 07 - 6 6 08 - 3 3 09 - 14 74 PAUSE 10 - 9 9 11 - 9 9 12 - 7 7 13 - 61 x 14 - 15 33 g FRAC 15 - 13 09 GTO 09 ``` On re-reading the HP33C manual a couple of years ago I found a similar routine on page 66 with the same multiplier, but using a different seed value (.2315478). Obviously by the time I stopped borrowing my father's HP97 and actually owned my first HP calculator I'd already given up reading the manuals or I might have decided to memorise a different seed value! I do remember that the seed value was an important factor in determining the number of random numbers that the routine above would generate before beginning to repeat itself. (I guess that one day I'll have to try to find out if the seed given in the HP33C manual is actually any 'better' than the one I used). Interestingly the more complicated routine given above for the later HP41C that allows the user to use any number between zero and one as a seed, also appears on page 67 of the HP34C Applications Guide. Mike T. Michael de Estrada Posting Freak Posts: 1,665 Threads: 142 Joined: Jan 2009 03-22-2009, 07:07 PM Did this on my HP-50g using the built-in clock to generate the random number instead of the RAND function. It also works on my HP-48SX. << TIME 10000 * FP 2 * IP >> where TIME yields the current clock time, FP and IP take the fractional and integer parts of the number. Michael Edited: 22 Mar 2009, 7:43 p.m. ▼ Khanh-Dang Nguyen Thu-Lam Junior Member Posts: 24 Threads: 4 Joined: Oct 2007 03-23-2009, 04:16 AM << TICKS 1 R->B AND >> This one is shorter but gives an integer. Append B->R if you really need a real. I guess it also provides more randomness than your version, at least on Saturn-based models because the clock tick is 1/8192. I don't know how the TICKS and TIME commands are emulated on ARM-based calcs. The program above assume nothing about the wordsize (see the STWS and RCWS commands). If you assume the wordsize is 1 bit (e.g. run the << 1 STWS >> before), you can hardly write something shorter than: << TICKS >> Again, append B->R if you really need a real. ▼ Michael de Estrada Posting Freak Posts: 1,665 Threads: 142 Joined: Jan 2009 03-23-2009, 02:51 PM I agree that your version is shorter, and it is also more elegant IMO. However, I don't think there is any difference in the "randomness" of the results from the two different approaches. If you are thinking that randomness somehow relates to precision, then there will be no difference between your method and mine. Your method requires the calculator to have slightly less than 4 significant digits for decimal fractions of a second. The internal precision is 12 decimal digits of which 6 are consumed for whole hours, minutes and seconds, leaving 6 digits for fractional seconds. Therefore, when a clock tick is converted to HMS format, there is no loss of accuracy. As to what constitutes "randomness", perhaps one of the statistical mathematicians among us can propose a test. Michael Edited: 23 Mar 2009, 2:51 p.m. ▼ Khanh-Dang Nguyen Thu-Lam Junior Member Posts: 24 Threads: 4 Joined: Oct 2007 03-23-2009, 05:29 PM I just meant if you run your program in a loop, for example: << 1 100 START YOURPROGRAM NEXT >> then, the sequence will be even more predictable than with my method. Edited: 23 Mar 2009, 5:36 p.m. Andrés C. Rodríguez (Argentina) Posting Freak Posts: 1,193 Threads: 43 Joined: Jul 2005 03-22-2009, 08:04 PM Youi can throw your calculator into the air, and see if it hits the floor with the keyboard facing up or down... :-) Eventually, if this is too hard to consider, just throw the batteries into the air... MikeO Member Posts: 121 Threads: 21 Joined: Jun 2008 03-23-2009, 12:39 AM Some creative answers so far. Namir provides both HP67 and HP41 versions. Andrés provides both an algorithm and a practical alterative when batteries are low, or missing - simply toss the calculator. Hilarious. Michael de Estrada provides a quick RPL version. Here's my contribution (RPN) for HP97 - 2 lines: ```001 X<->Y -41 002 GTO(i) 22 45 ``` To run: store -1 in register I, then 0 Enter 1. Then press R/S to flip and R/S to view it. Repeat as often as needed. Edited: 23 Mar 2009, 1:05 a.m. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-23-2009, 02:59 AM Does the hp97 code simulate random coin tosses? ▼ Howard Owen Posting Freak Posts: 1,830 Threads: 113 Joined: Aug 2005 03-23-2009, 04:29 AM The randomness derives from the precise time you press R/S the second time. The coin toss will be as random as the choice of time interval between presses of r/s is. If you make that choice based on some physically random event like radioactive decay, this program will pass the spectral test with flying colors :) Regards, Howard ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-23-2009, 06:30 AM Ok, I see. The R/S simply interrupts the program execution showing either 0 or 1. Interesting solution, making the user as part of the program! Edited: 23 Mar 2009, 8:02 a.m. ▼ Howard Owen Posting Freak Posts: 1,830 Threads: 113 Joined: Aug 2005 03-23-2009, 12:32 PM I'd be tempted to say that this approach is cheating, except the author is the one that posed the challenge in the first place!Regards,Howard ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-23-2009, 12:51 PM I agree. Mike should have been a bit more specific about how to write the solution. Using machines with random number generators saves many steps. Also I coded my solution to run as a proper program. Namir ▼ Howard Owen Posting Freak Posts: 1,830 Threads: 113 Joined: Aug 2005 03-23-2009, 01:48 PM I dunno, Namir. Quote: Create the shortest program you can that will provide a randomized coin toss result. The 2 line program does fit the given criteria. Of course, like I implied, that's what you would expect from the poser of the challenge. :) It appears to me that a solution of this kind is not possible on the 41C in two steps. The best you could do would be three lines: ```LBL 01 X<>Y GTO 01 ``` Where we use a short form GTO for speed. But this program needs one less setup step - the preloading of the i register. On the 35S, a similar program is: ```R001 LBL R R002 X<>Y R003 GTO R002 ``` Still 3 lines, but you could say the initial label isn't actually used, and that this is really a 2 line program. Except you probably couldn't since the label is mandatory. Let's say this is a 2.5 line program. :) Regards,Howard MikeO Member Posts: 121 Threads: 21 Joined: Jun 2008 03-23-2009, 08:20 PM Quote: I'd be tempted to say that this approach is cheating, except the author is the one that posed the challenge in the first place!Regards,Howard Hey, hey! I resemble that remark! ;) ▼ Howard Owen Posting Freak Posts: 1,830 Threads: 113 Joined: Aug 2005 03-24-2009, 03:44 AM Quote: Hey, hey! I resemble that remark! ;) Hee hee. But I stopped short of actually calling it cheating :)Regards,Howard ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-24-2009, 09:58 AM I think in future challenges, the author of the challenge should specify how the solution works (whether to write a program or a set of keystrokes)--what to input and what and HOW you get the output. Namir Edited: 24 Mar 2009, 10:00 a.m. ▼ Walter B Posting Freak Posts: 4,587 Threads: 105 Joined: Jul 2005 03-24-2009, 02:12 PM Come on, isn't it part of the fun to see the different approaches -- or using another word: to see the Ansatz ;) I won't regulate too much. But that's strictly my personal opinion. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 03-24-2009, 03:20 PM Had Mike described how the solution he is looking for works, we'd be more unified in our answers. ▼ Howard Owen Posting Freak Posts: 1,830 Threads: 113 Joined: Aug 2005 03-24-2009, 03:59 PM What's the point of being unified? A lot of the fun is seeing lots of different approaches and interpretations. I'm normally an observer on these challenges, but I love to read them because I usually learn something about the math and the calculators. Mike's solution made me think about the difference between random and pseudo random processes. Obviously, we rely on pseudo random processes in computation because a reliable source of dynamic disorder isn't usually available. You can't have a geiger counter and radioactive source built in to every mobile and stationary computing device. And we also may need randomness at a rate far greater than nature can conveniently provide, such as in Physics simulations on a supercomputing cluster. So Mike's solution won't work in those cases. But it could be useful in the case where all you need is a literal toss of a coin. It could even produce a better random series than any pseudo random algorithm, again depending on the method you use to choose the interval between key presses. On the other hand, I found that I kept getting the same answer with my key presses because I had an unconscious rhythm going. On my HP41, the numbers were oscillating slowly enough that this rhythm would result in a long series of 1s or 0s before it drifted out of phase far enough to flip over to the other state. If I tried to consciously vary the frequency of my key presses, I got better results. But that made me think about how I was choosing my intervals. Was it truly random? Since it was based on a cognitive process, I'll bet not. So that's an awful lot of thought generated by all the solutions presented here and especially by the attendant discussions. And that means all the solutions and all the discussion. None of the attempts to solve the more conventional (and useful) case of pseudo random number generation are invalidated by a clever solution addressing a different level of the problem. Regards,Howard Edit: Another benefit to a pseudo random process is that it is repeatable. Physically random process by definition do not repeat indefinitely. (You could record and play back such a sequence, however.) Edited: 24 Mar 2009, 4:04 p.m. MikeO Member Posts: 121 Threads: 21 Joined: Jun 2008 03-23-2009, 08:33 PM Quote: Interesting solution, making the user as part of the program! The solution occurred to me as a direct analogue of flipping a coin - with the program simulating the spinning coin, and hitting R/S simulating the toss and catching of the coin. Although a bit tongue-in-cheek, I think the technique might be a good way to randomize a seed value in some way on machines that don't have built-in random number routines. I noticed you had a couple different formulas for pseudo random number generators. These are interesting. Thanks Namir! Edited: 23 Mar 2009, 9:18 p.m. htom trites jr Member Posts: 66 Threads: 2 Joined: Aug 2007 03-23-2009, 03:54 PM Random from a computer is beyond hard. You can get beyond some of the simple woes using a version of the Von Neumann Coin procedure. ```Begin Repeat R1 <-- random(head,tail); R2 <-- random(head,tail); Until R1 <> R2; Return R1 End ``` This strips out simple constant biases towards head or tail (actual coins are usually slightly biased to head.) The procedure is not perfect, however.

 Possibly Related Threads... Thread Author Replies Views Last Post HPCC Mini Conference 2013 hugh steers 6 1,691 09-13-2013, 04:27 PM Last Post: BruceH Picture from the Mini-HHC (LA) Geir Isene 11 2,413 07-07-2013, 01:06 PM Last Post: Jim Horn My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 6,040 03-07-2013, 03:44 AM Last Post: Walter B WP 34S mini-challenge (B) Gerson W. Barbosa 17 3,407 12-27-2012, 04:39 PM Last Post: Marcus von Cube, Germany Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 2,809 10-05-2012, 10:36 PM Last Post: David Hayden HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 2,713 07-08-2012, 06:23 PM Last Post: Diego Diaz HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 5,089 11-14-2011, 08:12 AM Last Post: Valentin Albillo Mini challenge. CEIL / FLOOR in RPN M. Joury 47 8,547 10-31-2011, 10:11 AM Last Post: M. Joury A simple wp34s mini-challenge Gerson W. Barbosa 29 5,143 06-29-2011, 06:02 PM Last Post: Guenter Schink HP-15C mini-challenge (Project Euler - problem #1) Gerson W. Barbosa 14 2,970 05-08-2011, 11:08 AM Last Post: Marcus von Cube, Germany

Forum Jump: