Little problem(s) July 2022
07-04-2022, 06:04 PM (This post was last modified: 07-07-2022 05:31 PM by pier4r.)
Post: #1
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
Little problem(s) July 2022
#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 }

Wikis are great, Contribute :)
07-04-2022, 08:20 PM
Post: #2
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
Klick at your own risk: Spoiler
07-04-2022, 11:11 PM
Post: #3
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: Little problem(s) July 2022
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
07-05-2022, 01:01 AM
Post: #4
 pauln Member Posts: 84 Joined: May 2022
RE: Little problem(s) July 2022
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.
07-05-2022, 03:31 AM (This post was last modified: 07-05-2022 03:54 AM by Thomas Klemm.)
Post: #5
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
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.

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?
07-05-2022, 04:06 AM
Post: #6
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(07-05-2022 01:01 AM)pauln Wrote:  a very standard question in technical interviews these days.

Cf. Technical Interviews
07-05-2022, 10:00 AM (This post was last modified: 07-05-2022 10:08 AM by pier4r.)
Post: #7
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
RE: Little problem(s) July 2022
(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.

Wikis are great, Contribute :)
07-05-2022, 01:56 PM (This post was last modified: 07-05-2022 01:57 PM by pier4r.)
Post: #8
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
RE: Little problem(s) July 2022
(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?)

Wikis are great, Contribute :)
07-05-2022, 02:03 PM (This post was last modified: 07-05-2022 02:11 PM by John Keith.)
Post: #9
 John Keith Senior Member Posts: 1,021 Joined: Dec 2013
RE: Little problem(s) July 2022
(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   \>> \>>

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.
07-05-2022, 03:41 PM
Post: #10
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(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.

Attached File(s) Thumbnail(s)

07-05-2022, 04:28 PM
Post: #11
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(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.
07-05-2022, 09:41 PM
Post: #12
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: Little problem(s) July 2022
(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
07-06-2022, 06:16 AM
Post: #13
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
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
07-06-2022, 06:35 AM
Post: #14
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
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.
07-06-2022, 07:48 AM
Post: #15
 Werner Senior Member Posts: 863 Joined: Dec 2013
RE: Little problem(s) July 2022
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
07-06-2022, 08:29 AM
Post: #16
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(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
07-06-2022, 01:29 PM
Post: #17
 John Keith Senior Member Posts: 1,021 Joined: Dec 2013
RE: Little problem(s) July 2022
(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.
07-07-2022, 05:56 AM
Post: #18
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(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  \>> \>>
07-07-2022, 10:51 AM
Post: #19
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
RE: Little problem(s) July 2022
(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.

Wikis are great, Contribute :)
07-07-2022, 11:15 AM
Post: #20
 Thomas Klemm Senior Member Posts: 2,006 Joined: Dec 2013
RE: Little problem(s) July 2022
(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.