HHC 2015 RPN programming Contest is now open

10012015, 10:57 AM
Post: #61




RE: HHC 2015 RPN programming Contest is now open
(10012015 05:51 AM)Werner Wrote: Gerson: on the 41, numeric values take up as many bytes as the digits and/or extra chars. So 123456 takes up 6 bytes and 1 E3 takes up 5. Werner, thank you very much! This means my program is "only" 62 bytes long, not 64 :) (assuming there is no other difference between the 41C and 42S regarding byte counts). Gerson. 

10012015, 11:13 AM
(This post was last modified: 10022015 01:25 PM by Gerson W. Barbosa.)
Post: #62




RE: HHC 2015 RPN programming Contest is now open
(10012015 07:23 AM)Csaba Tizedes Wrote:(09302015 03:42 PM)Gerson W. Barbosa Wrote: Your program is 45step long and takes up 84 bytes on the HP42S Csaba, you're much welcome! BTW, on the HP41 your byte count should be 75. Sorry for the misleading 42S byte count! Gerson. P.S.: Just checked CAT 1 on the HP41C with infrared module in TRACE mode, your program is actually 89 bytes long (final instruction END, instead of RTN). Mine is 78 bytes long, but takes 12 seconds for 11234 whilst yours takes 9.5 seconds. P.P.S.: I had forgotten to PACK, sorry. After doing it, CAT 1 says 81 and 71, respectively. But the byte tables appear to give lesser numbers, so this may not be definitive yet. 

10012015, 12:44 PM
Post: #63




RE: HHC 2015 RPN programming Contest is now open
(10012015 10:57 AM)Gerson W. Barbosa Wrote: Werner, thank you very much! This means my program is "only" 62 bytes long, not 64 :) (assuming there is no other difference between the 41C and 42S regarding byte counts). Thank you both. To check byte counts I've been running PACK, then CAT 1 with output to printer. A printout with bytes per line would help for optimizing. 

10012015, 01:35 PM
Post: #64




RE: HHC 2015 RPN programming Contest is now open
(10012015 12:44 PM)Egan Ford Wrote: To check byte counts I've been running PACK, then CAT 1 with output to printer. A printout with bytes per line would help for optimizing.The bytes for instruction are in Appendix D of the 41C manual which is available on the Museum DVDs. That's what I was using. Egan, in your solution you can replace 10000 with EEX 4 for a savings of 3 bytes. 

10012015, 02:39 PM
Post: #65




RE: HHC 2015 RPN programming Contest is now open
.. Only if you have the CCD module installed. Or the ZENROM.
10000 = 5 bytes 1 E4 = 3 bytes 4 10^X = 2 bytes (CCD) E4 = 2 bytes, but is a synthetic instruction and Not Allowed. Cheers, Werner 

10012015, 03:56 PM
(This post was last modified: 10012015 03:58 PM by Gerson W. Barbosa.)
Post: #66




RE: HHC 2015 RPN programming Contest is now open
(10012015 12:44 PM)Egan Ford Wrote:(10012015 10:57 AM)Gerson W. Barbosa Wrote: Werner, thank you very much! This means my program is "only" 62 bytes long, not 64 :) (assuming there is no other difference between the 41C and 42S regarding byte counts). Thanks for the tip. It works on my HP41C with infrared module in TRACE mode. BTW, I discovered my program is 78 bytes long, not the 62 I get on the 42S. Too good I don't have to rely on this for a living 

10012015, 04:30 PM
Post: #67




RE: HHC 2015 RPN programming Contest is now open
Would anyone be willing to discuss the scheme or schemes they used to solve this? I'm coming at it from the point of view of a not very sophisticated 50g user, and I can see how SORT and ΔLIST and some tests could be made to solve it. (I'd be very interested in smarter ways to solve it on the 50g, of course.)
But the contest solutions look pretty opaque to me, and the commented solutions only give me hints as to the schemes involved. I'd be happy to know how working in binary can lead to a solution, and (from Egan Ford, perhaps) how prime numbers can be invoked in solving the problem. This is a long way from concern about byte count, but I think that others might be interested in seeing through the coding to the underlying process. Thanks! Peter Murphy 

10012015, 05:45 PM
(This post was last modified: 10012015 05:56 PM by Dieter.)
Post: #68




RE: HHC 2015 RPN programming Contest is now open
(09302015 10:13 AM)Egan Ford Wrote: All stack, 58 bytes (yeah, not even close to my last attempt (42 bytes), but just a different way to solve that none have posted, unless I missed it) A clever idea. But it can be done in 53 bytes – simply multiply the MODs: Code: 01 LBL "RR" On a standard 41C/CV/CX this runs in about 3 seconds for any input. Add a final X≠0? SIGN if you prefer an output of 0 or 1. Dieter 

10022015, 01:01 PM
Post: #69




RE: HHC 2015 RPN programming Contest is now open
(10012015 04:30 PM)Peter Murphy Wrote: Would anyone be willing to discuss the scheme or schemes they used to solve this?Egan's first solution works by taking each unique die value X and summing up 10^{X}. For example, if the roll is 4 3 5 3 1, it will add up 10^{4} + 10^{3} + 10^{5} + 10^{1} = 111,010. It then looks for 1111 in the sequence. In this example, 1111 doesn't appear so there is no small straight. My solution sets the flags that correspond to the dice. So mine sets flags 1, 3, 4, and 5 in the example. It then checks the flags to decide if there is a small straight. To do this, notice that ALL small straights must contain 3 and 4. If those dice are present then there must be two more die with adjacent values and that happens when the other two are to the left (1 and 2), or to the right (5 and 6) or on the sides (2 and 5). In Egan's method, checking for a small straight is pretty easy (just look for 1111) but he has a bunch of code to detect duplicate dice. In my soultion, there is no need to detect duplicate dice (setting a flag works if the flag is initially set), but the code to detect a small straight is complicated. With binary numbers, one can get the best of both worlds with an algorithm like this: Code: // Compute a binary number "total" that has bit X set for each die value X in the roll input: stack levels 15 contain the values of the 5 die in the roll output: level 1 is 0 if there is a small straight, a nonzero number otherwise. 

10022015, 01:17 PM
Post: #70




RE: HHC 2015 RPN programming Contest is now open
(10012015 12:44 PM)Egan Ford Wrote: To check byte counts I've been running PACK, then CAT 1 with output to printer. A printout with bytes per line would help for optimizing. (10012015 01:35 PM)David Hayden Wrote: The bytes for instruction are in Appendix D of the 41C manual which is available on the Museum DVDs. That's what I was using. Before leaving the byte counting subject, please allow me one more question: how does this actually work? The first time I took a printout of CAT 1 I obtained 78 bytes for my program and 89 for Csaba Tizedes's. Now, after PACKING, which I'd forgotten to do previously, I get 71 and 81, respectively. Using the table in Appendix D of the 41C manual I get 58 for mine (assuming RCL Z and RCL IND X take up two bytes each). Which is correct? Thank you very much! Gerson. 

10022015, 05:22 PM
(This post was last modified: 10022015 06:05 PM by C.Ret.)
Post: #71




RE: HHC 2015 RPN programming Contest is now open
(10022015 01:01 PM)David Hayden Wrote: See if you can put this into RPL: On HP49/50g, I would have preferred a list of the 5 dices as an input on level 1: only. The output remains the same; level 1: contains values 1. or 0. respectively when no or one small straight is present in the list. Code:
Note that this code is not limited to only 5 dices. List of any size are acceptable. As well as dice values not limited from 1 to 6. Any values from 0 up to 63 are possible. A small straight is found as soon as (at least a set of) 4 integers are contiguous. 

10022015, 09:19 PM
Post: #72




RE: HHC 2015 RPN programming Contest is now open
Many thanks to David Hayden for explaining (in #69, above) the 10^X scheme for reducing the numbers on the dice to ones and zeros. I learned something nice there.
And thanks to C.Ret for taking up David's challenge, producing (in #71) a marvelous oneline RPL solution, which indeed appears to work for any number of dice. The ability expert programmers of the 50g to produce concise programs is amazing. I still wonder about Egan's commented code (in #47, on page 3 of this thread) in which he refers to "map to prime numbers," ""x^2  x + 11, x = 010 prime." what algorithm is he applying here? David? Egan? Editorial note, especially for foreign speakers of English: the plural is "dice," the singular is "die." (OT: "sheep" is both singular and plural.) 

10022015, 10:22 PM
(This post was last modified: 10022015 10:47 PM by Dieter.)
Post: #73




RE: HHC 2015 RPN programming Contest is now open
(10022015 09:19 PM)Peter Murphy Wrote: I still wonder about Egan's commented code (in #47, on page 3 of this thread) in which he refers to "map to prime numbers," ""x^2  x + 11, x = 010 prime." what algorithm is he applying here? David? Egan? It's just me, but I think I can explain how it works. ;) For integer x=0...10, the expression x²–x+11 yields a prime number. In our case x is an integer between 1 and 6, and so the expression returns 11, 13, 17, 23, 31 and 41. So if the roll is 1 3 2 4 6 this sequence is transformed to 11 17 13 23 41. Multiplying these values yields a characteristic product, in this case 1281137. Now a small straight has to contain 1 2 3 4 or 2 3 4 5 or 3 4 5 6, which corresponds to the products 11*13*17*31=55913, resp. 13*17*23*31=157573, resp. 17*23*31*41=496961. The remaining fifth die just changes this result by a (prime) factor. So all that's left to do is check whether the product is divisible by 55913, 157573 or 496961. If it is, a small straight has been detected. In our case 1281137 mod 55913 = 0 => Bingo. Dieter 

10022015, 10:40 PM
Post: #74




RE: HHC 2015 RPN programming Contest is now open
(10022015 01:17 PM)Gerson W. Barbosa Wrote: Before leaving the byte counting subject, please allow me one more question: how does this actually work? The first time I took a printout of CAT 1 I obtained 78 bytes for my program and 89 for Csaba Tizedes's. Now, after PACKING, which I'd forgotten to do previously, I get 71 and 81, respectively. Using the table in Appendix D of the 41C manual I get 58 for mine (assuming RCL Z and RCL IND X take up two bytes each). Which is correct? Since I am not sure which program exactly you refer to: What about a listing that includes the byte count for each step? This way any potential errors can be detected easily. Dieter 

10022015, 10:43 PM
Post: #75




RE: HHC 2015 RPN programming Contest is now open
Hi Dieter,
All I can say is that "bingo" is right. Another wonderful lesson. Thanks for the clarification! Peter 

10022015, 11:01 PM
Post: #76




RE: HHC 2015 RPN programming Contest is now open
(10022015 10:40 PM)Dieter Wrote:(10022015 01:17 PM)Gerson W. Barbosa Wrote: Before leaving the byte counting subject, please allow me one more question: how does this actually work? The first time I took a printout of CAT 1 I obtained 78 bytes for my program and 89 for Csaba Tizedes's. Now, after PACKING, which I'd forgotten to do previously, I get 71 and 81, respectively. Using the table in Appendix D of the 41C manual I get 58 for mine (assuming RCL Z and RCL IND X take up two bytes each). Which is correct? Well, I am loathe to submit my listing again, especially after seeing such wonderful codes above, but I'll accept your help. Thanks again! Gerson. Code:


10022015, 11:36 PM
(This post was last modified: 10022015 11:54 PM by Dieter.)
Post: #77




RE: HHC 2015 RPN programming Contest is now open
(10022015 11:01 PM)Gerson W. Barbosa Wrote: Well, I am loathe to submit my listing again, especially after seeing such wonderful codes above, but I'll accept your help. Your result is almost exact. Except the first and last step: Code: 01>LBL 'RR 4 <= Alpha labels require 4 bytes + #characters = here 6 bytes So your program uses 2 + 3 more bytes, i.e. 65 bytes in total. And that's exactly what my hardware 41CV reports after SAVEP and RCLPT. BTW, in an earlier post you said... Quote:...the lack of some comparison tests on the HP41 is always a problem, at least for me. The '41 features 10 out of 12 possible comparison tests, i.e. all except X≥Y? and X≥0?. These two can be replaced by a simple combination of X≠Y? and X>Y? resp. X≠0? and X>0?. Dieter 

10032015, 12:02 AM
(This post was last modified: 10032015 12:51 AM by Allen.)
Post: #78




RE: HHC 2015 RPN programming Contest is now open
(10022015 09:19 PM)Peter Murphy Wrote: I still wonder about Egan's commented code (in #47, on page 3 of this thread) in which he refers to "map to prime numbers," ""x^2  x + 11, x = 010 prime." what algorithm is he applying here? David? Egan? Egan's beautiful and clever solution (my favorite) is just the right balance for the approach he took. Using a trivial python program, one will find that \(x^3x+11\) is not the only diophantine polynomial that maps {1..6} on to the set of primes. There are countably infinite polynomials that will map to primes, including: \(x^2+17x+37\): 53,67,79,89,97,103,prod: 249446106271 \(x^2+17x+97\): 113,127,139,149,157,163,prod: 7606248149551 \(x^217x+83\): 67,53,41,31,23,17,prod: 1764708511 \(x^217x+89\): 73,59,47,37,29,23,prod: 4995745291 \(x^215x+67\): 53,41,31,23,17,13,prod: 342406129 The trick is to minimize the byte count for BOTH the generating function, and the modulus tests. To that end, the polynomial Egan chose is probably the smallest byte count to calculate using just x^2 and x. Interestingly, there is one other trivial polynomial that can shorten the program by at least two more bytes: \(x^35x^2+23\): 19,11,5,7,23,59, prod=9926455 It takes an extra step or two to calculate the primes (19,11,5,7,23,59) but since all the MOD tests have to test for dice 3 and 4, the total length of the program is reduced since the smallest primes (5 and 7) are used in every product for testing (in this case 7315, 8855, and 47495). The smaller products actually make the total byte count smaller, even if the polynomial is not as clean. Kudos to Egan for such a clever solution. 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

10032015, 01:19 AM
(This post was last modified: 10032015 01:38 AM by Allen.)
Post: #79




RE: HHC 2015 RPN programming Contest is now open
Just to clarify, the numbers that {1,2,3,4,5,6} map to do not have to be prime numbers for Egan's solution to work, they only have to all be coprime with each other (you get both if you look for only prime numbers).
To that end \(6x+1\) makes for an even shorter program. ( by checking 8645, 38285, and 108965). (maps to 7,13,19,5^2,31,37). 17bii  32s  32sii  41c  41cv  41cx  42s  48g  48g+  48gx  50g  30b 

10032015, 03:12 AM
Post: #80




RE: HHC 2015 RPN programming Contest is now open  
« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)