Programming puzzles: processing lists!

[DavidM]

(06-25-2017 11:50 AM)pier4r Wrote:  Going through the algorithm for #34 . The idea is to feed one value at time (without arranging optimally the list in input beforehand, also, shuffle it a bit to be sure it is messy) and perform insertions in a balanced search binary tree (that has to keep the balancing).

Pier, you are an artist as well as a calculator enthusiast! You're also way ahead of me in the challenges as I have fallen behind while, uhm, working on other things.

Here's a couple submissions for #14 and #15, which I opted to do with only the built-in commands. I assumed (perhaps wrongly) that the list wouldn't begin or end with the sentinel (0). They're almost identical, but I suppose that's to be expected:

Code:

Ch14
\<<
  0 DUP
  \-> list base num
  \<<
    @ determine the maximum digit in the list
    list \<< MAX \>> STREAM

    @ add 1 for the selected base
    1 + 'base' STO

    @ convert the list digits to integers in base 10
    list
    1
    \<<
      IF DUP THEN       @ if the current digit isn't 0, then...
        num base * +    @ multiply current num by base and add new digit
      ELSE              @ else the digit is the separator (0)
        num SWAP        @ place current num on stack and reset running total to 0
      END
      'num' STO         @ save the updated num
    \>>
    DOSUBS              @ process the list

    @ subtract the second number from the first
    EVAL num -

    @ obtain the sign and ABS of the difference
    DUP SIGN SWAP ABS

    @ digit counter, for later grouping into final list
    0

    @ put the difference in SL1
    SWAP

    @ convert number to digits
    WHILE             @ do while the running result > 0
      DUP
    REPEAT
      10 IDIV2        @ determine quotient (SL2) and remainder (SL1)
      ROT 1 + ROT     @ update digit counter and move current digit into place
    END

    DROP              @ drop the remaining quotient (0)
    \->LIST REVLIST   @ put resulting digits into a list and reverse them
    *                 @ apply sign
  \>>
\>>

Ch15
\<<
  0 DUP
  \-> list base num
  \<<
    @ determine the maximum digit in the list
    list \<< MAX \>> STREAM

    @ add 1 for the selected base
    1 + 'base' STO

    @ convert the digits to integers in base 10
    list
    1
    \<<
      IF DUP THEN       @ if the current digit isn't 0, then...
        num base * +    @ multiply current num by base and add new digit
      ELSE              @ else the digit is the separator (0)
        num SWAP        @ place current num on stack and reset running total to 0
      END
      'num' STO         @ save the updated num
    \>>
    DOSUBS              @ process the list

    @ add the second number to the first
    EVAL num +

    @ obtain the sign and ABS of the difference
    DUP SIGN SWAP ABS

    @ digit counter, for later grouping into final list
    0

    @ put the difference in SL1
    SWAP

    @ convert number to digits
    WHILE             @ do while the running result > 0
      DUP
    REPEAT
      base IDIV2      @ determine quotient (SL2) and remainder (SL1)
      ROT 1 + ROT     @ update digit counter and move current digit into place
    END

    DROP              @ drop the remaining quotient (0)
    \->LIST REVLIST   @ put resulting digits into a list and reverse them
    *                 @ apply sign
  \>>
\>>

You may already be aware of this, and I couldn't remember if this has already been mentioned: the first example for #15 appears to have an incorrect result. Shouldn't it be 201 (base 4) instead of 111?

#16 has three parts, and I wasn't about to skip using my newfangled DOPERM command for these:

Code:

C1601
\<<
  @ given list defined in problem description
  { 0 8 8 2 }

  @ convert to list of characters
  48 ADD CHR

  @ size of list (needed by DOPERM)
  DUP SIZE

  @ execute for each permutation
  \<<
    @ convert character list to string, then convert string to number
    SL\->S STR\->

    @ determine if it is a multiple of 117
    DUP 117 MOD

    @ drop the result if it is not a multiple of 117
    NOT NOT DROPN
  \>>
  DOPERM

  @ remove duplicates
  LDDUP
\>>

C1602
\<<
  @ given list defined in problem description
  { 1 3 4 }

  @ convert to list of characters
  48 ADD CHR

  @ size of list (needed by DOPERM)
  DUP SIZE

  @ execute for each permutation
  \<<
    @ convert character list to string, then convert string to number
    SL\->S STR\->

    @ is the current number a prime?
    DUP ISPRIME?

    @ if not, drop it
    NOT DROPN
  \>>
  DOPERM

  @ remove duplicates (not strictly needed for the given argument, but good to have)
  LDDUP

\>>

C1603
\<<
  @ given list defined in problem description
  { 6 4 0 9 }

  @ convert to list of characters
  48 ADD CHR

  @ size of list (needed by DOPERM)
  DUP SIZE

  @ execute for each permutation
  \<<
    @ convert character list to string, then convert string to number
    SL\->S STR\->

    @ find cube root of the current number
    DUP 3 XROOT \->NUM

    @ if the cube root is an integer, then...
    IF DUP FP 0 == THEN
      @ convert it to an exact number and place in a list with the permutation
      R\->I 2 \->LIST
    ELSE
      @ not an integer, drop both the permutation and the cube root
      DROP DROP
    END
  \>>
  DOPERM
\>>

#17 is very straightforward with DOPERM. It appears that my 50g is OK with up to 7 digits for this particular exercise. 8 digits gives a result of (8!-1) entries (40319), which well exceeds the memory available for the stack. Here's the submission:

Code:

Ch17
\<<
  @ convert to list of characters
  48 ADD CHR

  @ size of list (needed by DOPERM)
  DUP SIZE

  @ execute for each permutation
  \<<
    @ output the permutation as a number
    SL\->S STR\->
  \>>
  DOPERM

  @ explode final list and drop the first permutation
  LIST\-> ROLL DROP
\>>