+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Little problem(s) July 2022 (/thread-18533.html)
Pages: 1 2
Little problem(s) July 2022 - pier4r - 07-04-2022 06:04 PM
#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 }
RE: Little problem(s) July 2022 - Thomas Klemm - 07-04-2022 08:20 PM
Klick at your own risk: Spoiler
RE: Little problem(s) July 2022 - Albert Chan - 07-04-2022 11:11 PM
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
endFor 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
RE: Little problem(s) July 2022 - pauln - 07-05-2022 01:01 AM
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.
RE: Little problem(s) July 2022 - Thomas Klemm - 07-05-2022 03:31 AM
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?
RE: Little problem(s) July 2022 - Thomas Klemm - 07-05-2022 04:06 AM
(07-05-2022 01:01 AM)pauln Wrote: a very standard question in technical interviews these days.
Cf. Technical Interviews
RE: Little problem(s) July 2022 - pier4r - 07-05-2022 10:00 AM
(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.
RE: Little problem(s) July 2022 - pier4r - 07-05-2022 01:56 PM
(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?)
RE: Little problem(s) July 2022 - John Keith - 07-05-2022 02:03 PM
(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.
RE: Little problem(s) July 2022 - Thomas Klemm - 07-05-2022 03:41 PM
(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.
RE: Little problem(s) July 2022 - Thomas Klemm - 07-05-2022 04:28 PM
(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.
RE: Little problem(s) July 2022 - Albert Chan - 07-05-2022 09:41 PM
(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
endlua> f2({2,7,11,15}, 17)
1 4
lua> f2({2,5,7,8,10,11,15}, 15)
2 5
3 4
RE: Little problem(s) July 2022 - Thomas Klemm - 07-06-2022 06:16 AM
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 ENDBut 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
RE: Little problem(s) July 2022 - Thomas Klemm - 07-06-2022 06:35 AM
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 ENDI 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.
RE: Little problem(s) July 2022 - Werner - 07-06-2022 07:48 AM
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
RE: Little problem(s) July 2022 - Thomas Klemm - 07-06-2022 08:29 AM
(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 ENDExample
17
[ 4x1 Matrix ]
XEQ "FIND"
Y: 4
X: 1
RE: Little problem(s) July 2022 - John Keith - 07-06-2022 01:29 PM
(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.
RE: Little problem(s) July 2022 - Thomas Klemm - 07-07-2022 05:56 AM
(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
\>>
\>>RE: Little problem(s) July 2022 - pier4r - 07-07-2022 10:51 AM
(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.
RE: Little problem(s) July 2022 - Thomas Klemm - 07-07-2022 11:15 AM
(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