Little problem(s) July 2022

[John Keith]

(07-05-2022 03:31 AM)Thomas Klemm Wrote:  Here's my solution of #2 for the HP-48:

Code:

\<< OVER - \-> ns ms
  \<< 1 ns SIZE
    FOR i
      ms ns i GET POS
      IF DUP
      THEN i R\->C
      ELSE DROP
      END
    NEXT
  \>>
\>>

---

Addendum:
Under the hood the implementation of POS is probably \(\mathcal{O}(n)\).
This makes my solution \(\mathcal{O}(n^2)\) and thus rather a solution for #1.
But we don't have to tell that the interviewer, do we?

Very nice program, as usual.

This is not really an improvement, but I couldn't resist a functional version of your program for the 48G:

Code:


\<< OVER - \-> ms
 \<< 1
  \<< ms SWAP POS DUP 0 SAME DROPN
  \>> DOLIST
 \>>
\>>

Unfortunately it is not a well-behaved function because, due to what I consider to be a bug in DOLIST, it returns nothing if no pair of numbers in the list sums to the level 1 argument. The ListExt function LMAP does not have this problem (it returns an empty list) but that is limited to the 49g and 50g.

As an addendum to your addendum, your program is technically O(n^2) but since built-in functions like POS are many times faster than any UserRPL equivalent, it comes out much closer to O(n) in practice.