MC: Ping-Pong Cubes

[DavidM]

An interesting challenge, Joe. This has a similar feel to some of your past challenges (Pan-prime Cube and All-odd digits come to mind). I suspect that some of the optimizations from the Pan-prime cube challenge could be helpful for this one; in particular, knowing in advance that certain root digit suffixes will create invalid results might speed things up. I didn't take it that far, though.

Here's my "plain UserRPL" approach:

Code:

\<<
  {
    DUP 2. MOD SWAP 10. / IP 1.
    WHILE
      OVER
    REPEAT
      ROT PICK3 2. MOD
      SWAP OVER XOR
      ROT AND
      ROT 10. / IP SWAP
    END
    NIP NIP
  }
  0.
  10.
  WHILE
    OVER 10. <
  REPEAT
    IF
      PICK3 OVER
      SWAP EVAL
    THEN
      IF
        PICK3 OVER
        DUPDUP * *
        SWAP EVAL
      THEN
        SWAP 1. + SWAP
        DUP 4. ROLLD
      END
    END
     1. +
  END
  DROP2 DROP
\>>

The code within the list brackets above is a subroutine that takes a real number as input and returns a 1 if the input was valid, otherwise a 0. It simply checks the parity of each digit after the first to make sure it isn't the same as the previous one.

The basic approach was to execute a loop on sequential integers starting with 10, stopping only after the 10th solution is found. In each loop iteration, the root is checked for validity before proceeding to check the cube. I opted to skip some obvious code shortcuts due to their performance impact. That said, I'm sure there are much faster UserRPL implementations possible -- I hope others will post their own. The above program completes in 24.6 seconds on my 50g.

For those who might like to compare a SysRPL approach, I submit the following translation of the above program. It uses the exact same approach as the UserRPL one above, and completes in less than half the time of the above at 9.6 seconds. Note: I use Debug4x, which doesn't require the code within a WHILE clause to be encapsulated in a ":: ... ;" block. You would have to add the :: and ; symbols to the WHILE clauses if you don't use Debug4x as your compiler:

Code:

::
   CK0NOLASTWD

   ( Valid Ping Pong Check )
   ' ::
      DUP %2 %MOD %0<> SWAP %10 %/ %IP TRUE
      BEGIN
         OVER %0<>
      WHILE
         ROT 3PICK %2 %MOD %0<>
         SWAPOVER XOR
         ROTAND
         ROT %10 %/ %IP SWAP
      REPEAT
      ROTROT2DROP
   ;

   ( count of solutions )
   BINT0

   ( bind local vars )
   FLASHPTR 2LAMBIND

   ( seed initial test )
   %10

   ( do until 10 solutions found )
   BEGIN
      1GETLAM BINT10 #<
   WHILE
      DUP 2GETEVAL IT ::
         DUPDUP DUP %* %* 2GETEVAL IT ::
            1GETLAM #1+ 1PUTLAM
            DUP
         ;
      ;
      %1+
   REPEAT

   ( drop the count )
   DROP

   ( abandon local vars )
   ABND
;

...and finally, to show how much time is spent in that laborious ping-pong validation, I replaced the validation subroutine from the previous SysRPL example with this Saturn code object to see how much improvement I could get. Using this brought the total time down to 1.26 seconds:

Code:

   CODEM
      SAVE
      A=DAT1 A
      AD1EX
      D1+5
      A=DAT1 W
      ST=1 0
      B=0 S
      B+1 S
      C=A M
      CSL W
      A-1 X
      C&B S
      D=C S
      {
         CSL W
         C&B S
         ?C=D S ->{ ST=0 0 }
         D=C S
         A-1 X
         UPNC
      }
      LOAD
      LA 03AC0
      ?ST=1 0 ->{ LA 03A81 }
      DAT1=A A
      RPL
   ENDCODE