List Commands Library for 50g

[DavidM]

I went ahead and implemented the I→NL command. It seemed silly not to, especially since it could be made to be a good performer via the use of a custom Saturn routine to populate the result list.

DOCOMB and DOPERM now have a local variable available for obtaining the "discards" from the source list after a combination has been selected. I'm not sure if there's a formal name for those elements, but I've been thinking of them as the "combination remnant", so the local is currently named CRMNT. Better naming suggestions are welcome! The user program can simply include CRMNT in its code at any point where those elements are needed. They are returned as a list.

In searching for a good example problem to show the use of CRMNT with DOPERM, I decided that the "Vietnamese Snake Puzzle" from Gerald's post was a good match. It may also be easier to understand for the folks that already participated in that thread. If you're not familiar with it, I'd advise taking a look at the original source first to get an idea what it's about.

Like many permutation problems, there is great benefit in recognizing the constraints that are built into the problem itself that may keep you from having to use a "brute-force" approach that simply checks every possible permutation. For this example, I'm focusing on one of those constraints: ((13BI)+(CGH))/CI must be an integer in all of the final solutions.

With that in mind, I've constructed the following program using commands from the library where appropriate. It essentially permutes the list of 9 digits, choosing 5 at a time for the initial test. For each of those permutations, it checks the above expression to see if it is an integer, and if so, continues to check the remaining digits as a potential solution to the final expression:

Code:

\<<
  { 1 2 3 4 5 6 7 8 9 }   @ available digits

  DUP EVAL \-> A B C D E F G H I \<<  @ create locals for vars A-I
    5   @ permute 5 of the digits each iteration
    \<<

      @ the following assumes var order in list is { B G H C I }
      DUP EVAL    @ keep a copy of the current permutation, then explode
      DUP2 * 6 ROLLD 13 * 5 ROLL * 4 ROLLD * * + SWAP /   @ evaluate (13BI+CGH)/CI

      @ if the result is an integer...
      IF DUPDUP IP == THEN
        \-> num \<<   @ save the value of the above expression for later use

          @ store B G H C I vars
          { B G H C I } STO

          @ process the following for all permutations of { A D E F}
          CRMNT   @ remnant of current combination of { B G H C I }
          4       @ permute all 4 digits
          \<<
            @ evaluate the full expression with this permutation
            DUP EVAL              @ keep a copy of the list, then explode
            NEG SWAP 12 * + + +   @ evaluate A + D + 12E - F
            num +                 @ add in (13BI+CGH)/CI

            @ if the total is the sought-after solution...
            IF 87 == THEN

              @ store permutation into A D E F vars
              { A D E F } STO

              @ create an integer representing each variable in order
              { A B C D E F G H I } LV\->I

            ELSE      @ else this permutation is not a solution
              DROP    @ { A D E F }
            END
          \>>
          DOPERM
          EVAL  @ explodes list of solutions or drops empty list if no solution
        \>>

      ELSE      @ else (13BI+CGH)/CI is not an integer
        DROP2   @ { B G H C I }, num
      END
    \>>
    DOPERM
  \>>
\>>

I've commented this code copiously in an effort to make it clear what it does. On my 50g, it finds all 136 solutions in about 23.5 minutes. Further constraint checking would likely speed this up a bit, but I wanted to keep this as simple as possible while still showing a meaningful use of the CRMNT local.

These latest changes (and a couple others) will be in the next update, which will hopefully be one of the last ones before finalizing the command set. I'll give it a couple more days as I continue to hammer out some more tests with it.