Little problem(s) July 2022

[pier4r]

#1 Sum of two integers in a list

Input:
L2: a list (or an array) of positive integers values
L1: an integer Int1

Output:
L1: the positions of the two different (!) elements in the list in input whose sum is equal to Int1

Constraints:
- Assume the input list to have only one couple of values that equals to Int1 or none. No duplicates.

#2 Sum of two integers in a list bonus No1

Like the problem in #1 but try to get less than O(n^2)

#3 Sum of integers in a list bonus No2
Input:
L2: a list (or an array) of positive integers values
L1: an integer Int1

Output:
L1: the positions of the different (!) elements in the list in input whose sum is equal to Int1, so that the number of elements that produce the sum is maximum (if it is possible to equal Int1). If multiple options are possible, one is to be picked.

Example inputs:
{ 1 2 3 2 2 1 }
6
output:
{ 1 2 4 6 } @1 2 2 1
@alternative { 1 2 5 6 }

[Thomas Klemm]

Klick at your own risk: Spoiler

[Albert Chan]

I am not sure if this match the requirements.
Here is Lua's solution, which should be trivial to convert to Python
Note: Lua index is 1-based; Python 0-based.

Code:

function f(lst, x)
    local idx = {}
    for i=1,#lst do idx[i] = i end
    return recurse(lst, x, idx, 0, 0)
end    
    
function recurse(lst, x, idx, n, prev)
    if x==0 then print(unpack(idx,1,n)); return end    
    n = n+1 -- setup for next item
    for i = n, #lst do
        local y = idx[i]
        if prev > y then continue end   -- idx combinations
        y = x - lst[y]
        if y < 0 then continue end
        idx[n], idx[i] = idx[i], idx[n] -- swap
        recurse(lst, y, idx, n, idx[n])   
        idx[n], idx[i] = idx[i], idx[n] -- restore
    end
end

For index permutations instead of combinations, remove if prev > y then ... line

lua> L1, L2 = {1,2,3,2,2,1}, 6
lua> f(L1, L2) -- L1 index combinations that sum to L2
1      2      3
1      2      4      6
1      2      5      6
1      3      4
1      3      5
1      4      5      6
2      3      6
2      4      5
3      4      6
3      5      6

[pauln]

Actually, question #2 happens to be a very standard question in technical interviews these days.

Candidates are supposed to solve a couple of questions of that kind in the typical 45' interview. The difficulty is to do this in "real time" without significant bugs, in the language of your choice.

[Thomas Klemm]

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
  \>>
\>>

Example

{ 2 7 11 15 }
17

(4,1)
(1,4)

Add a final DROP if you are only interested in one solution.

---

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?

[Thomas Klemm]

(07-05-2022 01:01 AM)pauln Wrote:  a very standard question in technical interviews these days.

Cf. Technical Interviews

[pier4r]

(07-05-2022 01:01 AM)pauln Wrote:  Actually, question #2 happens to be a very standard question in technical interviews these days.

yes I saw the problem in a post online that mentioned careercup. I found it nonetheless a nice challenge for list processing ( see here ) and thus I wanted to share plus adding some variants (#3, that may likely be an already posed question but I was simply trying to expand on #1).

Further I am pretty sure that is unlikely that such problems were solved (with shared solution) within the realm of calculators capabilities (especially older ones), unless they were already discussed here on on other calculator forums.

[pier4r]

(07-05-2022 03:31 AM)Thomas Klemm Wrote:  Addendum:
Under the hood the implementation of POS is probably \(\mathcal{O}(n)\).

Why is POS \(\mathcal{O}(n)\) in userRPL? Is there no direct access to the position in a list, does the system have to iterate through the elements every time? (is DOSUBS the only way to avoid it?)

[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.

[Thomas Klemm]

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL?

I must admit that I don't know the details, but I assume that POS has to check every entry to find the position.
The worst case is if we search for an entry that is absent.

This program measures the time of POS for an increasing list:

Code:

\<< 1 SWAP
  FOR i
    DUP + DUP
    TICKS
    SWAP 0 POS DROP
    TICKS SWAP -
    SWAP
  NEXT
  DROP
\>>

Example

{ 1 1 1 1 1 1 1 1 }
10

This produced the following values:

8 14 29 74 93 181 245 343 430 580

It looks like an exponential curve to me:



Since the length of the list is doubled in each iteration this gives a linear relationship.
At least it is not logarithmic and definitely not constant.

[Thomas Klemm]

(07-05-2022 02:03 PM)John Keith Wrote:  Very nice program, as usual.

Thank you!

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

You should know by now that I prefer functional programming.
It's really a very nice solution.

Quote: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.

This reminds me of Clojure’s persistent vectors, which gives practically O(1) runtime for appends, updates, lookups and subvec.
Because each node has 32 leaves, the tree becomes very flat.
Thus, access is constant for most practical use cases.

[Albert Chan]

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL? Is there no direct access to the position in a list, does the system have to iterate through the elements every time? (is DOSUBS the only way to avoid it?)

POS first need to match the object, then return its position.
With unsorted list, linear search is O(n)
Sorted list can use binary search, time complexity O(log(n))

BTW, if the list were sorted, there is no need for POS at all.
We just repeatedly shorten the 2 tails ...

Code:

function f2(lst, x) -- lst sorted, no duplicates
    local i, j = 1, #lst
    while i < j do
        local y = lst[i] + lst[j] - x
        if     y > 0 then j=j-1
        elseif y < 0 then i=i+1
        else print(i, j); i=i+1; j=j-1
        end
    end
end

lua> f2({2,7,11,15}, 17)
1      4
lua> f2({2,5,7,8,10,11,15}, 15)
2      5
3      4

[Thomas Klemm]

This is a solution for #1 for the HP-42S:

Code:

00 { 38-Byte Prgm }
01▸LBL "FIND"
02 GTO 01
03▸LBL 00
04 RCL IND ST Y
05 RCL+ IND ST Y
06 RCL- 00
07 X=0?
08 GTO 02
09 R↓
10 DSE ST X
11 GTO 00
12 R↓
13 DSE ST X
14▸LBL 01
15 ENTER
16 DSE ST X
17 GTO 00
18▸LBL 02
19 R↓
20 END

But it should work with the HP-41C as well after minor adjustments.
The \(\text{target}\) and the values of the list \(\{a_1, a_2, \cdots, a_n\}\) are expected in the registers:

R00: \(\text{target}\)
R01: \(a_1\)
R02: \(a_2\)
…
Rnn: \(a_n\)

Example

17 STO 00

2 STO 01
7 STO 02
11 STO 03
15 STO 04

4
XEQ "FIND"

4
1

[Thomas Klemm]

This is my attempt of a solution for #2 for the HP-42S:

Code:

00 { 41-Byte Prgm }
01▸LBL "FIND"
02 RCL- ST Y
03 STO "N"
04 INDEX "N"
05 R↓
06 EDIT
07▸LBL 00
08 [FIND]
09 XEQ 01
10 →
11 FC? 77
12 GTO 00
13 EXITALL
14 R↓
15 RTN
16▸LBL 01
17 RCLIJ
18 R↓
19 X<>Y
20 END

I tried to use the undocumented function [FIND] with John's idea.

Example

[ 4x1 Matrix ]
17
XEQ "FIND"

But alas it fails when using the Free42 simulator.
It appears that [FIND] is not using the indexed matrix N but the matrix that is currently edited.
Therefore all elements are found.

I've tried to index the matrix N within the loop but that gives me an error: Restricted Operation
Interestingly I can do that manually while editing the matrix.
But that exits the edit mode.

I can't check this with my HP-42S right now.
But maybe someone else can confirm that this is the same behaviour.

[Werner]

It is the same in the real 42S.
You cannot EDIT a matrix and INDEX another one at the same time - EDITing implies INDEXing, and there can be only one matrix indexed at any one time.
The only way to access two matrices at the same time is to store one in REGS and EDIT/INDEX the other.

Cheers, Werner

[Thomas Klemm]

(07-06-2022 07:48 AM)Werner Wrote:  store one in REGS and EDIT/INDEX the other

Thanks a lot for the hint.
This appears to work:

Code:

00 { 49-Byte Prgm }
01▸LBL "FIND"
02 STO "REGS"
03 -
04 STO "N"
05 INDEX "N"
06 DIM?
07 -
08 1ᴇ3
09 ÷
10 SIGN
11▸LBL 00
12 RCL IND ST L
13 [FIND]
14 XEQ 01
15 R↓
16 ISG ST L
17 GTO 00
18 RTN
19▸LBL 01
20 RCLIJ
21 R↓
22 X<>Y
23 END

Example

17
[ 4x1 Matrix ]
XEQ "FIND"

Y: 4
X: 1

[John Keith]

(07-05-2022 09:41 PM)Albert Chan Wrote:  BTW, if the list were sorted, there is no need for POS at all.
We just repeatedly shorten the 2 tails ...

Code:

function f2(lst, x) -- lst sorted, no duplicates
    local i, j = 1, #lst
    while i < j do
        local y = lst[i] + lst[j] - x
        if     y > 0 then j=j-1
        elseif y < 0 then i=i+1
        else print(i, j); i=i+1; j=j-1
        end
    end
end

lua> f2({2,7,11,15}, 17)
1      4
lua> f2({2,5,7,8,10,11,15}, 15)
2      5
3      4

This is a very good solution, especially for languages that have sets or binary trees as data types. On the HP48, unfortunately, a UserRPL implementation would be slower than one using POS.

[Thomas Klemm]

(07-05-2022 02:03 PM)John Keith Wrote:  

Code:

  \<< ms SWAP POS DUP 0 SAME DROPN
  \>> DOLIST

This reminded me of the FORTH word 0= which is NOT.
Or was it SysRPL?
So we can replace 0 SAME by this:

Code:

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

[pier4r]

(07-05-2022 03:41 PM)Thomas Klemm Wrote:  

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL?

I must admit that I don't know the details, but I assume that POS has to check every entry to find the position.
The worst case is if we search for an entry that is absent.

Yes somehow I managed to mix POS with GET in my mind (I hope GET is O(1) with lists in userRPL, now I start to have doubts).
(thank you to Albert Chan as well!)

But then we cannot really lie to the interviewer can we? That is also the interesting part of those problems solved with the calculator capabilities, one doesn't exactly have all the tools (data structures or methods) needed.

[Thomas Klemm]

(07-07-2022 10:51 AM)pier4r Wrote:  one doesn't exactly have all the tools (data structures or methods) needed

That's why we should use MIX (or nowadays rather MMIX) in job interviews.
Cf. MMIX Home Page