HHC 2015 RPN programming Contest is now open

[Gerson W. Barbosa]

(10-01-2015 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 E-3 takes up 5.

There is one exception: when the previous line contains a number, too, an invisible 'null' is inserted between the two, to separate the numbers. That takes up an extra byte.
On the 42S, this invisible null is present in all number entry lines, whether they are preceded by another number or not. And so the byte count for programs with number entry lines is different between the 41 and 42.

Cheers, Werner

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.

[Gerson W. Barbosa]

(10-01-2015 07:23 AM)Csaba Tizedes Wrote:  

(09-30-2015 03:42 PM)Gerson W. Barbosa Wrote:  Your program is 45-step long and takes up 84 bytes on the HP-42S

Hi, Gerson, thank you for your checking - I'll try to find an emulator to check your (and others) solutions - or I'll "translate" these solutions to 15C for better understanding.

Csaba

Csaba, you're much welcome! BTW, on the HP-41 your byte count should be 75. Sorry for the misleading 42S byte count!

Gerson.

P.S.: Just checked CAT 1 on the HP-41C 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.

[Egan Ford]

(10-01-2015 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.

[David Hayden]

(10-01-2015 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.

[Werner]

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

[Gerson W. Barbosa]

(10-01-2015 12:44 PM)Egan Ford Wrote:  

(10-01-2015 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.

Thanks for the tip. It works on my HP-41C 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

[Peter Murphy]

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

[Dieter]

(09-30-2015 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"                  
 02 5           ; loop over 5 dice
 03 1           ; alternatively use ENTER SIGN
 04 LBL 00
 05 RCL IND Y   ; map to prime number
 06 X^2         ; x^2 - x + 11, x = 0-10 prime
 07 LASTx
 08 -
 09 11
 10 +
 11 *           ; multiply primes
 12 DSE Y
 13 GTO 00
 14 ENTER
 15 ENTER
 16 ENTER
 17 55913       ; check for 1,2,3,4
 18 MOD
 19 X<>Y
 20 157573      ; check for 2,3,4,5
 21 MOD
 22 *
 23 X<>Y
 24 496961      ; check for 3,4,5,6
 25 MOD
 26 *
 27 END

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

[David Hayden]

(10-01-2015 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⁴ + 10³ + 10⁵ + 10¹ = 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
for each die
    x := 1 SL die_value //  "SL" means binary shift left
    total = total OR x   // binary OR


// A small straight occurs if total has 1111 in it.
while (total != 0)
    if (total AND 1111b) == 1111b   // binary AND to mask off bits
        return 0
    else
        total = total SR 1   // binary shift right

// If you get here then you found no small straight.
return 1

See if you can put this into RPL:
input: stack levels 1-5 contain the values of the 5 die in the roll
output: level 1 is 0 if there is a small straight, a non-zero number otherwise.

[Gerson W. Barbosa]

(10-01-2015 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.

(10-01-2015 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.

[C.Ret]

(10-02-2015 01:01 PM)David Hayden Wrote:  See if you can put this into RPL:
input: stack levels 1-5 contain the values of the 5 die in the roll
output: level 1 is 0 if there is a small straight, a non-zero number otherwise.

On HP-49/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:


« 2. SWAP ^ R→B « OR » STREAM BIN →STR "1111" POS NOT »

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.

[Peter Murphy]

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 one-line 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 = 0-10 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.)

[Dieter]

(10-02-2015 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 = 0-10 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

[Dieter]

(10-02-2015 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

[Peter Murphy]

Hi Dieter,

All I can say is that "bingo" is right. Another wonderful lesson. Thanks for the clarification!

Peter

[Gerson W. Barbosa]

(10-02-2015 10:40 PM)Dieter Wrote:  

(10-02-2015 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

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:


01>LBL 'RR        4
02 XEQ 'SORT      6
03 CLX            1
04 STO 06         1
05 STO 07         1
06 4              1
07 STO 00         1
08 SIGN           1
09>LBL 00         1
10 RCL IND 00     2?  
11 CHS            1
12 RCL 00         1
13 RCL Z          2?        
14 +              1
15 RCL IND X      2?
16 X<>Y           1
17 RDN            1
18 +              1
19 X=Y?           1
20 ST+ 06         2?        
21 X<>Y           1
22 X>Y?           1
23 ST+ 07         2?
24 DSE 00         2
25 GTO 00         2
26 RCL 07         1
27 RCL 06         1
28 X<=Y?          1
29 GTO 01         2
30 3              1
31 X>Y?           1
32 GTO 01         2
33 RCL 04         1
34 RCL 02         1
35 -              1
36 X<>Y           1
37 X<=Y?          1
38 GTO 01         1
39 FRC            1
40 RTN            1
41>LBL 01         2
42 SIGN           1
43 END          ---
                 60?

[Dieter]

(10-02-2015 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
...
43 END          ----   <= an END requires 3 bytes
                 60?

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 HP-41 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

[Allen]

(10-02-2015 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 = 0-10 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^3-x+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^2-17x+83\): 67,53,41,31,23,17,prod: 1764708511
\(x^2-17x+89\): 73,59,47,37,29,23,prod: 4995745291
\(x^2-15x+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^3-5x^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.

[Allen]

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 co-prime 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).

[David Hayden]

(10-01-2015 02:39 PM)Werner Wrote:  1 E4 = 3 bytes

Yes, but on the 41 you don't have to enter 1, you can just enter EEX 4 which is 2 bytes (the same as 4 10^X as you pointed out).