HHC 2015 RPN programming Contest is now open

[Csaba Tizedes]

(10-02-2015 01:01 PM)David Hayden Wrote:  

(10-01-2015 04:30 PM)Peter Murphy Wrote:  Would anyone be willing to discuss the scheme or schemes they used to solve this?

My solution sets the flags that correspond to the dice. So mine sets flags 1, 3, 4, and 5 in the example ... he has a bunch of code to detect duplicate dice ... 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.

Same as my method but I used lots of steps for totally same task:

My method is works on that we store the numbers of dices in R1~R5.
We need one additional register R6 to mark if we have 6 on any dice.
This is that point where my solution grows too high: with indirect addressing I marked each register (steps: 011~023):

Code:


9
STO 6
...
LBL 0
RCL I
RCL (i)
STO I
RCL (i)
ABS
CHS
STO (i)
ROLL DN
ROLL DN
STO I
ISG I
GTO 0

This is totally same but very very long code... If I use flags these steps can shortened.

After marking registers from R1~R6 the original content is remain in each registers only the sign is changed:

If we have 1,1,2,6,6,9 in registers R1~R6, after running above code we have -1,-1,2,6,6,-9 in registers (because on dices we have 1, 2 and 6).

The other part (counting) is also straighforward.

Csaba

[Massimo Gnerucci]

(10-03-2015 03:12 AM)David Hayden Wrote:  

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

Yes, that's a valid shortcut but it will be registered as 1 E4 nonetheless.

[Egan Ford]

(10-01-2015 05:44 AM)Werner Wrote:  Gene: I would be honoured!

Werner, congrats!

[Egan Ford]

(10-01-2015 05:45 PM)Dieter Wrote:  A clever idea. But it can be done in 53 bytes – simply multiply the MODs:

Doh! Thanks.

[Egan Ford]

(10-02-2015 01:01 PM)David Hayden Wrote:  

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

Others took this approach as well including Werner's 42-byter. However Werner looked for >= 1111 so that nothing was required to remove dups. I was working on a similar solution, but decided to pursue different approaches, including your flag approach, but I never finished it.

[Egan Ford]

(10-03-2015 01:19 AM)Allen Wrote:  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).

After I posted my prime-based solution I tried to create other prime and co-prime series, but it didn't get me close to 42 bytes. Dieter's optimization + your series still puts it 7 bytes short:

49 bytes (was 53 with x^2-x+11):

Code:


  1 LBL RR
  2 5           ; loop over 5 dice
  3 1
  4 LBL 00
  5 RCL IND Y   ; map to 6x+1
  6 6
  7 *
  8 1
  9 +
 10 *           ; multiply co-primes
 11 DSE Y
 12 GTO 00
 13 ENTER
 14 ENTER
 15 ENTER
 16 8645        ; check for 1,2,3,4
 17 MOD
 18 X<>Y
 19 38285       ; check for 2,3,4,5
 20 MOD
 21 *
 22 X<>Y
 23 108965      ; check for 3,4,5,6
 24 MOD
 25 *
 26 END

We can shave off a byte by only checking for 1,2,5,6 pairs, then checking 3,4:

48 bytes:

Code:


  1 LBL RR
  2 5           ; loop over 5 dice
  3 1
  4 LBL 00
  5 RCL IND Y   ; map to 6x+1
  6 6
  7 *
  8 1
  9 +
 10 *           ; multiply co-primes
 11 DSE Y
 12 GTO 00
 13 ENTER
 14 ENTER
 15 ENTER
 16 91          ; check for 1,2
 17 MOD
 18 X<>Y
 19 403         ; check for 2,5
 20 MOD
 21 *
 22 X<>Y
 23 1147        ; check for 5,6
 24 MOD
 25 *           ; if 0, then possible small straight
 26 X<>Y        
 27 95          ; check for 3,4
 28 MOD
 29 +           ; + not *
 30 END

Next possible optimization would be to pre compute series, store checks in registers, loop the checks. That's 3 loops and possibly a GSB.

[Gene]

(10-03-2015 11:01 AM)Massimo Gnerucci Wrote:  

(10-03-2015 03:12 AM)David Hayden Wrote:  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).

Yes, that's a valid shortcut but it will be registered as 1 E4 nonetheless.

Gene: And EEX 4 would violate the no synthetic programming rule.

The contest was wide open. Very few constraints so that a lot of ideas could be tried.

In reality, to fit the small straight routine into the larger yahtzee program, other considerations have to be accounted for.

The YZ program uses flags already, so modifying flags would force a re-write of many areas.
The YZ program uses memories 1-13 to store the scorecard for the game. Dice are actually in 14-18. :-)

That's what made Werner's code so attractive. Short, no flags, no extra memories. Seems like a good fit.

Perhaps, given the improvement found here :-) I should post the code for the game in total. Who knows how short it might become!

[Egan Ford]

Optimized brute-force search.

40 bytes:

Code:


  1 LBL RR                  ; 11 SigmaREG required?
  2 CL Sigma                ; count numbers in sequence
  3 6                       ; search for 6, 5, 4, 3, 2, 1 loop
  4 STO 07
  5 LBL 07
  6     5                   ; search each dice
  7     STO 06
  8     LBL 06
  9         RCL 07          ; outer loop
 10         RCL IND 06      ; inner loop
 11         x=y?            ; is there a match?
 12         GTO 09          ; if so, break out of here
 13     DSE 06
 14     GTO 06
 15     CL Sigma            ; no match, reset sequence counter
 16     LBL 09
 17     x=y?                ; got match
 18     Sigma+              ; inc sequence counter
 19     RCL 16              ; recall n
 20     4
 21     -
 22     x=0?                ; got 4 in a row?
 23     STO 07              ; then store that in 07 to exit main loop
 24 DSE 07
 25 GTO 07
 26 END                     ; X = non-zero

[Allen]

(10-03-2015 04:48 PM)Gene Wrote:  Perhaps, given the improvement found here :-) I should post the code for the game in total. Who knows how short it might become!

I would find that very interesting, indeed. Thank you again for such a fun challenge. I learned some things from the other programmers!

[David Hayden]

(10-03-2015 04:48 PM)Gene Wrote:  Gene: And EEX 4 would violate the no synthetic programming rule.

EEX is not synthetic. It's on the keyboard after all. It sounds like there is a synthetic E command, but EEX is fair game.

However, someone else pointed out that entering EEX 4 in program mode results in the 3 byte number 1 E4.

[Dieter]

(10-04-2015 01:52 PM)David Hayden Wrote:  

(10-03-2015 04:48 PM)Gene Wrote:  Gene: And EEX 4 would violate the no synthetic programming rule.

EEX is not synthetic. It's on the keyboard after all. It sounds like there is a synthetic E command, but EEX is fair game.

However, someone else pointed out that entering EEX 4 in program mode results in the 3 byte number 1 E4.

I think Gene wanted to say that a two byte "E4" command was not allowed as it can only be generated by synthetic programming.
As you said, simply typing [EEX] [4] yields a standard "1 E4" line with three bytes.

Dieter

[Gene]

(10-04-2015 01:52 PM)David Hayden Wrote:  

(10-03-2015 04:48 PM)Gene Wrote:  Gene: And EEX 4 would violate the no synthetic programming rule.

EEX is not synthetic. It's on the keyboard after all. It sounds like there is a synthetic E command, but EEX is fair game.

However, someone else pointed out that entering EEX 4 in program mode results in the 3 byte number 1 E4.

Correct. 1 E4 is valid per the conditinos. E4 is not. :-)

Missed you (and Egan) at the conference this year!

[David Hayden]

Here's another solution. It's 25 steps, 40 bytes and uses 2 registers.

The idea is to sort the numbers and then count the number of times that the difference between adjacent numbers is 1. If the difference is ever greater than 1, then reset the counter.

In pseudo-code:

Code:

SORT
last_die = 9  // pretent last die was a large number
For i = 5 to 1
    current_die = RCL IND i
    diff := last_die - current_die
    if diff > 1 then
        sum := 0;
    diff := 0;
    else
    sum := sum + diff;
    if sum = 3 then
        CLX
    RTN
RTN some non-zero value

Notice that because last_die is initialized to zero, the first time through teh loop diff is always greater than 1 so sum gets reset to 0.

Here is the code with byte counts and comments.

R06 is the index register
R07 is the value of the last die

Code:

01 LBL 'RR'   6 bytes
02 XEQ 'SORT' 6 bytes
03 5          1 byte        // Store index
04 STO 06     1 byte
05 9          1 byte        // and fake last die value
06 STO 07     1 byte

07 LBL 01     1 byte        // Running sum of diffs is in X
08 X<>Y       1 byte        // put sum back in X
09 RCL 07     1 byte        // last die
10 RCL IND 06 2 bytes       // current die
11 STO 07     1 byte        // update last die
12 -          1 byte        // get difference between last and current die
13 1          1 byte
14 X<Y?       1 byte        // difference > 1?
15 CLST       1 byte        // sum := 0, diff := 0
16 ROLL DOWN  1 byte
17 +          1 byte        // Update sum of differences
18 3          1 byte
19 X=Y?       1 byte        // If you found a run then
20 CLX        1 byte        // clear it
21 X=0?       1 byte        // and
22 RTN        1 byte        // return

23 DSE 06     2 bytes       // Loop
24 GTO 01     2 bytes
25 END        3 bytes

[Jeff O.]

As is my usual practice, I worked on the challenge for a while before checking the discussion here.

I initially resisted methods that required the sort routine. I worked through a few methods, best I could do was 32 steps/56 bytes using flags. I kept having nagging misgivings about using flags, when to clear them, etc. So I worked on a scheme where I stored ones in a sequence of registers, and “optimized” that down to 42 steps/66 bytes. With this concept, I kept having nagging misgivings about using registers and when to clear them. So I finally PMed Gene and asked about the propriety of using flags and/or registers. He said the rules did not prevent it, but that “in reality the routine is in the middle of a program that uses the first 15 user flags and has most registers spoken for.”

So I decided to abandon my reticence to using the sort routine and see if that would help me develop shorter/better programs. After a few iterations, I arrived at 25 step/45 byte version that re-uses register 5, but no other registers or flags, and a 26 step/46 byte version that uses no flags or registers and preserves all of the die values, in case they are needed later in the Yahtzee program. These two programs are presented below for those who might be interested.

I thought about the problem for a couple of days, trying to come up with alternate approaches that might lead to shorter programs, but had no flashes of inspiration, so I finally read this thread. As I suspected, there were some approaches that made sense and I might have arrived at independently had I kept devoting time to the problem, and others I would never have thought of in million years (e.g., using prime numbers.) Thanks Gene for another fun project.

Code:


Version 1, 25 steps/45 bytes, walks on the sorted die value stored in Register 5.
001    LBL RR        
002    XEQ SORT      execute external sort routine
003    4             enter 4 for loop index 
004    x<>05         exchange with value in R5, R5 will be loop index 
005    3             enter 3 for initial "sum of differences"
006    x<>y          exchange for correct order
007    LBL 01        
008    RCL IND 05    recall value in register pointed to by index
009    -             find difference between adjacent regiser values
010    1             enter 1
011    x<y?          difference 2 or more?
012    GTO 02        if so, these two values cannot be part of a straight, go to 
                     routine to reset sum of differences
013    RDN           if less than 2 (1 or 0) roll down to get difference and 
                     sum to x and y
014    -             subtract difference from previous "sum of differences"
015    x=0?          does running sum of differences equal 0
016    GTO 05        if so, there is a small straight, branch to end routine
017    GTO 03        if not, branch to loop check
018    LBL 02        branch point for difference greater than 1
019    3             enter 3 to reset sum of differences to three
020    LBL 03        loop check label
021    RCL IND 05    recall value in register pointed to by index for next difference
022    DSE 05        decrement index
023    GTO 01        loop back to compare two more values
024    LBL 05        end routine, will be zero for straight, value in R1 for no straight
025    END           end

Version 2, 26 steps/46 bytes, preserves all die values.
001    LBL RR        
002    XEQ SORT      execute external sort routine
003    4             enter 4 for loop index
004    ENTER         separate 4 from the following 3
005    3             enter 3 for initial "sum of differences"
006    RCL 05        recall value in register 5 for first difference comparison
007    LBL 01        
008    RCL IND Z     recall value in register pointed to by index
009    -             subtract Rn from Rn+1
010    1             enter 1
011    x<y?          difference 2 or more?
012    GTO 02        if so, these two values cannot be part of a straight, go to 
                     routine to reset sum of differences
013    RDN           if less than 2 (1 or 0) roll down to get difference and 
                     sum to x and y
014    -             subtract difference from previous "sum of differences"
015    x=0?          does running sum of differences equal 0
016    GTO 05        if so, there is a small straight, branch to end routine
017    GTO 03        if not branch to loop check
018    LBL 02        branch point for difference greater than 1
019    RCL ST T      recall index
020    3             enter 3 to reset sum of differences to three
021    LBL 03        loop check label
022    RCL IND Y     recall value in register pointed to by index for next difference
023    DSE Z         decrement index
024    GTO 01        loop back to compare two more values
025    LBL 05        end routine, will be zero for straight, value in R1 for no straight
026    END           end

- edited for the sake of brevity, improve program comments, and to correct typos

[Sylvain Cote]

It took me 6 versions (between 40 and 45 bytes) before being able to come up with a version under 40 bytes.

Code:

CAT"1
LBL`RR
END         38 BYTES

Code:

BB LL Code          Comment
-- -- ------------- ------------------------
05 01 LBL "RR"      Entry point
02 02 5             Loop #1 start index
01 03 LBL 01        Loop #1 top
02 04 RCL IND X     Get register value specified in X
02 05 SF IND X      Set flag specified in X
01 06 RDN           Get back loop index
02 07 DSE X         Decrement index and skip if zero
01 08 GTO 01        Go back loop #1 top
02 09 FS? 05        If flag 5 is set (see comment 3)
02 10 SF 01         set flag 1
02 11 4             Loop #2 start index
01 12 LBL 02        Loop #2 top
02 13 FC? IND X     If flag cleared
01 14 GTO 03        we leave, it's not a sequence
02 15 DSE X         Decrement index and skip if zero
01 16 GTO 02        Go back loop #2 top
02 17 1             We have a sequence of 4  :-)
01 18 STOP          Stop the program
01 19 LBL 03        Error!
02 20 0             We do not have a proper sequence
03 21 END           End of the program

Resources ...
Regs.: 1 to 5 with values sets before running this program
Flags: 1 to 5 and need to be cleared before running this program
Prog.: 38 Bytes

Comments:
1) there is only two valid values 1234 and 2345
2) the flags 1 to 5 are set based on the values (1 to 5) found. I used flags to remove duplicates and the needed for sorting
3) because a sequence of four is a winner, if flag 5 is set, then I set the flag 1 and only the first four flags (1 to 4) is validated


Edit: Arrrg, I forgot the value 6, I will correct it and come back

[David Hayden]

(10-07-2015 12:41 AM)Sylvain Cote Wrote:  Edit: Arrrg, I forgot the value 6, I will correct it and come back

Note that the contest also required that you be able to run the program again by loading R01-R05 with new values and pressing R/S, so you need to clear the flags and deal with the STOP somehow.

[Jeff O.]

In analyzing Werner’s code (which is quite brilliant, in my opinion), I decided that I needed a list of every possible combination of die values that could fall out of the Yahtzee cup. With five dice, each having six possible values, there are 6^5 or 7776 possible sets. But the order does not matter (e.g., 1-2-3-4-5 is the same as 5-4-3-2-1 is the same as 3-1-5-4-2, etc.), so there are a lot fewer unique combinations that we need to worry about. Through a laborious and most likely inefficient process (listing and counting them in excel), I determined that there seem to be just 252 unique combinations, as follows:

1. All five dice the same single value – 6 possible groups (five ones, five twos, etc.)
2. Four dice of one value, one of another value – 30 groups
3. Three dice of one value, two of another value – 30 groups
4. Three dice of one value, one of another value, and one of a third value – 60 groups
5. Two dice of one value, two of another value, and one of a third value – 60 groups
6. Two dice of one value, one of another value, one of a third value, and one of a fourth value– 60 groups
7. All five dice have different values – 6 groups (1-2-3-4-5, 1-2-3-4-6, 1-2-3-5-6, 1-2-4-5-6, 1-3-4-5-6 and 2-3-4-5-6)
   

6 + 30 + 30 + 60 + 60 + 60 + 6 = 252

Can anyone confirm the above? (Or deny, I may be wrong and won’t mind being corrected.) Figuring items 1 and 7 is trivial, even for me. I think items 2 and 3 are figured simply as 6 ways to pick the first number times 5 ways to pick the second equals 30. I am a little murkier on how to figure items 4, 5 and 6. For items 4 and 5, my inclination would be to start with 6 ways to pick the first number times 5 ways to pick the second times 4 ways to pick the third equals 120. But that would include some duplications, I think, as for example, 3 sixes, 1 five and 1 four is the same as 3 sixes, 1 four and 1 five. Seems like each such combination would appear twice, so I would divide the 120 by 2 to get 60. For item 6, I’d start 6 x 5 x 4 x 3 equals 360, then divide by 3! to account for the repeats among the three single values, yielding 360/6 which equals 60. But I’m not completely sure about those methods. Assuming I have the figures correct, is there a simple method to calculate that there are 252 unique combinations among the 7776 non-unique ones? (My exposure to calculations involving probabilities and statistics is pretty limited, so please be gentle.)

[Thomas Klemm]

(10-14-2015 05:29 PM)Jeff O. Wrote:  I determined that there seem to be just 252 unique combinations

You are correct: Number of combinations with repetition
\[
\binom{n+k−1}{k}=\binom{6+5−1}{5}=\binom{10}{5}=252
\]
Cheers
Thomas

[Jeff O.]

(10-14-2015 07:01 PM)Thomas Klemm Wrote:  You are correct: Number of combinations with repetition
\[
\binom{n+k−1}{k}=\binom{6+5−1}{5}=\binom{10}{5}=252
\]
Cheers
Thomas

Thanks for the information, and for not telling me to "RTFI" (Read the Fine Internet). :-)

I guess I forgot that it is 2015 and all I had to do was type "combination" into a search engine. It is too easy to rely on the expertise that I know resides in the members of this Forum.

[Jeff O.]

(09-29-2015 09:25 AM)Werner Wrote:  Managed to squeeze off a byte:
42 bytes

Cheers, Werner

As I stated elsewhere, in my opinion your program is quite brilliant. It took me a little while to figure out what you were doing, what the heck the LOG, FRC and SIGN instructions could possibly have to do with this problem. But after walking through it a time or two (or three), I was able to see the method you used, which is quite clever. Then I thought I saw a simple improvement, put the RCL 5 in the loop to build the sum, like this:

Code:


001    LBL"RR"
002    5
003    0
004    LBL 01
005    RCL IND Y
006    10^X
007    +
008    DSE Y
009    GTO 01
010    X<>Y
011    LBL 02
012    SIGN
013    10^x
014    /
015    RCL X
016    1111
017    X>Y?
018    GTO 00
019    -
020    LOG
021    FRC
022    X#0?
023    GTO 02
024    LBL 00
025    END

That is indeed one step shorter, but due to the need to enter the 0 ahead of the summing loop, the byte count is the same. More elegant to start the sum with one of the values to be summed (10^register 5) and then sum the rest than to start at zero. For the same byte count, I’ll take elegance over step count. Other similar rearrangements yielded 25 steps, but higher byte counts, so I think your code is optimal. Again, very nice work!