July 2018 little math problem

[DavidM]

Thanks to all who are sharing their various analyses of this deceivingly simple-looking puzzle! It's a great example of how the application of deductive reasoning can greatly reduce the work needed to solve a problem.

(07-26-2018 03:43 PM)Thomas Klemm Wrote:  We can start with \(e\in\{1\ldots9\}\). And then let \(c\) and \(g\) be different digits with \(c<g\). This gives us \(9\times\binom{8}{2}=252\) possibilities.

...

So far I've made it up to Thomas' optimizations, which I've translated into an RPL/ListExt implementation.

As expected, this brought the run time down considerably from the previous versions.
Real 50g: 63.9s
Emu48+ on laptop: 1.68s

I'm still trying to wrap my ahead around Albert's and Valentin's approach, especially in terms of how they might translate to a more familiar language.

This has proven to be an intriguing problem!

Code:

Spoiler...











\<<
  9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s
  \<<
    dig
    1.
    \<<
      { e } STO
      CRMNT
      2.
      \<<
        IF
          DUP EVAL <
        THEN
          { c g } STO
          c e g 45. + + + DUP 's' STO
          IF
            4. MOD NOT
          THEN
            s 4. / DUPDUP 's' STO
            c e + - DUP 'd' STO
            SWAP e g + - DUP 'f' STO
            IF
              DUP2 MIN 0. >
              UNROT MAX 10. <
              AND
            THEN
              IF
                { c d e f g } LRCL LDDUP SIZE 5. SAME
              THEN
                dig { c d e f g } LRCL LRMOV
                4.
                \<<
                  { a b h i } STO
                  IF
                    a b c + + s SAME
                    g h i + + s SAME
                    AND
                  THEN
                    { a b c d e f g h i } LRCL R\->I
                    DUP REV
                  END
                \>>
                DOPERM EVAL
              END
            END
          END
        ELSE
          DROP
        END
      \>>
      DOPERM EVAL
    \>>
    DOPERM
  \>>
\>>


The same code, with comments added:

\<<
  @ create digits list and declare locals
  9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s

  \<<
    @ permute all single digits
    @ I'm using DOPERM here instead of a FOR loop
    @ so that I can take advantage of CRMNT to easily obtain remaining digits
    dig
    1.

    \<<
      @ save e
      { e } STO

      @ permute all remaining digits, in combinations of 2
      CRMNT
      2.
      \<<
        IF
          @ only proceed if c < g
          DUP EVAL <

        THEN
          @ save c,g
          { c g } STO

          @ determine whether s would be valid with this c,e,g
          c e g 45. + + + DUP 's' STO

          IF
            @ only proceed if trial s is evenly divisible by 4
            4. MOD NOT

          THEN
            @ convert trial s (4s) to final s
            s 4. / DUPDUP 's' STO

            @ compute d and f
            c e + - DUP 'd' STO
            SWAP e g + - DUP 'f' STO

            IF
              @ only proceed if d and f are valid digits
              DUP2 MIN 0. >
              UNROT MAX 10. <
              AND

            THEN
              IF
                @ only proceed if c,d,e,f,g are all unique
                { c d e f g } DUP SIZE SWAP LRCL LDDUP SIZE SAME

              THEN
                @ select remaining digits for a b h i, then
                @ check all permutations
                dig { c d e f g } LRCL LRMOV
                4.

                \<<
                  @ store a,b,h,i
                  { a b h i } STO

                  IF
                    @ only proceed if sum(a,b,c) and sum(g,h,i) = s
                    a b c + + s SAME
                    g h i + + s SAME
                    AND

                  THEN
                    @ all checks passed, add digits and their
                    @ mirrored form to result
                    @ (R->I simply added to remove fraction marks)
                    { a b c d e f g h i } LRCL R\->I
                    DUP REV

                  END
                \>>
                DOPERM EVAL
              END
            END
          END
        ELSE
          DROP
        END
      \>>
      DOPERM EVAL
    \>>
    DOPERM
  \>>
\>>