HHC 2012 RPL Programming Contest



#2

Here you go!

RPL Contest

Please do not post any solutions here until after Noon CDT Sunday September 22, 2012.
Questions here and I will be checking periodically. Enjoy!

Edited: 22 Sept 2012, 10:03 a.m.


#3

Hi,

Thanks, it looks to be a great challenge...

If, I correctly interpret the problem,

diameter of { 0 3 0 0 4 0 3 4 4 3 } is 5
and
diameter of { 3 6 5 2 3 1 8 2 6 5 4 4 7 4 } is 6.4031

Edited: 22 Sept 2012, 12:58 p.m.


#4

Isn't the drawing somewhat misleading? Finding the smallest enclosing circle of a set of points is a different problem.


#5

Hi,

Yes, that's right, finding the smallest enclosing circle is another problem.

To make the drawing less confusing, I may have illustrate another list of points:

{ 1 0 0 0 1 1 2 3 3 4 4 0 } returns 5

#6

There doesn't appear to be a winning criteria here....


- Pauli


#7

"The winning program will be the one for which size*speed (bytes*sec) is least, where the speed of execution will be determined for one or more test cases chosen by the judge."


#8

I've my solution...

What is noon Sunday in GMT times ?

#9

With the completely new programming language of the 39gII, perhaps we'll see similar challenges for it in the future. Meanwhile, thank you, Gene and company for the nifty challenges and terrific Conferences! And thank you, Forum goers, for your insight, skills, and delightful exchanges.

#10

Hi Gene,

I have a doubt :

It is write for the input list : "The list will contain at least one pair of numbers..."

Does that mean that { 2 3 } is a correct input which seems a non sense ? Does the output must be zero if this input is allowed ?


#11

My assumption is that yes, a single point is legal and that the distance in this case is zero.


- Pauli

#12

Hi, Gilles.

Yes, that correct the rule clearly indicate that { 2 3 } is a correct entry;
And yes, in this case, the diameter of the circle have to be zero, since that is the only size for a circle passing the two farest distant instance of the only point !

In the same idea,{ 2 3 2 3 } or { 2 3 2 3 } or { 2 3 2 3 ... 2 3 }are also instances returnng zero sized circle diameter.

At least, all this is my interpretation and assumption for the excercice.

#13

Hi all !

I'm back to home and saw the RPN contribution, so I suppose it's time to publish ;)

«
DUP SIZE 2. / 1. +  -> s
«
EVAL DUP2
1. s FOR n R->C s 2. * n - ROLLD NEXT
0.
s 2. + 4. FOR n
4. n FOR m OVER m PICK - ABS MAX NEXT
NIP
-1. STEP
NIP
»
»

145 Bytes
Run time = 0.2772 s with the example of the contest on my real HP50G

I suppose there could be a trick with the "up to 10 pairs of numbers" limit, but i dont see ... The limitation of this program is the just memory....

Edited: 23 Sept 2012, 3:33 p.m.


#14

Improve version (140 Bytes) and some comments :

«
LIST-> 2. / 1. +  -> s @ 'explode' the list on the stack and size/2+1 in 's'
«
DUP2 @ Trick for one point only input
1. s FOR n R->C s 2. * n - ROLLD NEXT @ Transform all datas in complex numbers (points) on the stack
0. @ Init the max distance
s 2. + 4. FOR n
4. n FOR m OVER m PICK - ABS MAX NEXT @ get the max distance all on the stack
NIP
-1. STEP
NIP
»
»


Edited: 23 Sept 2012, 6:12 p.m.

#15

Another interesting problem. Looks to be the diameter of a graph unless I'm mistaken. I'm not aware of any algorithm better than the O(n2) brute force approach. Pull out my only working RPL device, a veteran HP 28S with replacement battery cover and code it:

<<
DUP SIZE 2 / 0 DUP -> L N D A # List, N, diameter, first point
<<
IF N 1 > # Special case single point list
THEN
1 N 1 -
FOR I
L I 2 * GET
L I 2 * 1 - GET # Get Ith point
R->C 'A' STO # as a complex number
I 1 + N
FOR J
L J 2 * GET
L J 2 * 1 - GET # Get Jth point
R->C A - ABS # distance apart
D MAX 'D' STO # keep the maximum distance
NEXT
NEXT
END
>>
D
>>

Don't bother typing this in and running it. It isn't optimised for speed or size. The later RPL machines add lots of nice list processing features that the 28S doesn't have so a 28S program is unlikely to be competitive.

There is a pseudo diameter algorithm for a graph which is faster but not guaranteed to get the maximal result. This is essentially pick a point and find the farthest from it. Repeat to get the diameter. Perhaps repeat a couple of times but we're getting back towards the O(n2) obvious algorithm especially when Nmax is 10.

Can we determine the minimum and maximum coordinates and use that instead? No, it is possible to construct a set where the maximal distance doesn't include the points with minimum or maximum coordinates. (0, 1-eps), (0, eps-1), (1-eps, 0), (eps-1, 0) define a circle about the origin with diameter 2-2*eps < 2. The two points (2*eps-1, 2*eps-1) and (1-2*eps, 1-2*eps) line strictly inside these bounds but are almost 2*sqrt(2) > 2.8 apart.

There are plenty of optimisations possible. The code to extract the values from the list isn't ideal and should be in a subroutine. An array of complex values would be better again and the code to convert should pay for itself given the number of times it is executed. Unfortunately, the 28S can't have a local variable with an array in it and it requires a list based index. This means the overhead for using an array of complex numbers is more than the benefits:

<<
LIST-> 2 / DUP 1 ->LIST (0,0) CON 0 DUP -> N A D E
<<
1 N FOR I
R->C A I 1 ->LIST ROT PUT 'A' STO
NEXT
IF N 1 >
THEN
1 N OVER - FOR I
A I 1 ->LIST GET 'E' STO
I 1 + N FOR J
A J 1 ->LIST GET E - ABS D MAX 'D' STO
NEXT
NEXT
END
D
>>
>>

This version is slower than the list based approach for small lists and about the same for the maximum sized list.

One further optimisation is possible here. Instead of two loops, one to pack the complex values and one to find the diameter, they could be combined.

<<
LIST-> 2 / DUP 1 ->LIST (0,0) CON 0 DUP -> N A D E
<<
1 N FOR I
R->C DUP 'E' STO A I 1 ->LIST ROT PUT 'A'
IF I 1 >
THEN
1 I OVER - FOR J
A J 1 ->LIST GET E - ABS D MAX 'D' STO
NEXT
END
NEXT D
>>
>>

Performance has improved and the size is reduced but this isn't as fast as the original list only approach.


Sorry no sizes or execution times. I don't remember how to find the size of a program on a 28S and I suspect its timings won't be good enough.


- Pauli


#16

Here is another way to do with the 50G.
It uses lot list processing. It is a little shorter that my full stack version below (140 Bytes vs 145), but 2 or more times slower :

«
2. « NSUB 2. MOD {R->C} {DROP2} IFTE » DOSUBS @ Transform the list in complex number (point) list
{} SWAP 2. OVER SIZE START
DUP HEAD SWAP TAIL DUP ROT - ABS ROT + SWAP
NEXT
DROP 0. + « MAX » STREAM
»

My 2 versions use the same algorithm to compare each point with each others and avoid to compare twice the sames points.
Both use a trick to work with 1 point only to return zero.

EDIT : I think my "full stack" version could work on a 28 with just changing NIP with SWAP DROP... I m fairly sure that the full stack approach is the best for time execution in this case but ... who kwnows ;)
The problem with my list processing version is that I augment the size of the list in each loop and this is very slow in RPL

Note that << MAX >> STREAM is a very easy way to find the max of a list on the 50. Perhaps a way on the 50 is to use the STREAM command to calculate the distance and get the MAX in the same time ... could be an interesting approach


Edited: 23 Sept 2012, 6:33 p.m.


#17

Hi, Gilles


As you, I use the MAX function to stream maximal diameter out of the computation.
As you, I also convert the initial list to a row array format containing complex number since with complex, distance is easely compute through the ABS function.

But, in my code, the ABS distance computation is hide into the RNRM instruction that operate norm operation (ABS equivalent) for each element in a row and only returns the maximal.

This is my code for HP-28S which use the same algorithm, but look much shorter :

« LIST-> 2 / -> n                            //  desmount original list and get number of points
« { n 2 } ->ARRY [1,(0,1)] * -> D // convert into complex row vector
« 0 // Initiate max diameter value
1 n FOR i // for each point in the row vector
D DUP DUP i GET CON - RNRM MAX // compute distance with other points and keep maximum
NEXT
»
»
»

#18

Hi C.ret...

Beautifull ! shorter but slower ....

1.2 sec vs 0.27 with 'full stack' and ~ 0.6s with list processing on the 50G. It goes faster on the real HP50G than with the "authentic calculator speed" of EMU48 wich is not very accurate


Edited: 24 Sept 2012, 7:13 a.m.


#19

Hi, Gilles

I only realise now that my code is not speed optimize !
The FOR i loop compare each point two times !
The distance is symetric, ABS((2,3)-(1,1)) is equivalent to ABS((1,1)-(2,3))

A speed improuve algorithm may be :

« LIST-> 2 / -> n                            //  desmount original list and get number of points
« { n 2 } ->ARRY [1,(0,1)] * -> D // convert into complex row vector
« 0 // Initiate max diameter value
1 n 2 / FOR i // for half of the points in the row vector
D DUP DUP i GET CON - RNRM MAX // compute distance with other points and keep maximum
NEXT
»
»
»

This will reduce the running time by a factor 2 (nearly) !


#20

It's a very minor point, but you can save 2.5 bytes by replacing DUP DUP with DUPDUP.

Dave


#21

Yes, that right. Unfortunetely, DUPDUP don't exist on my HP-28S.

For an HP-48/50g vrsion, perhaps have instruction LIST-> to be exchange with OBJ-> as well.

#22

Hi Pauli,


I made the same analysis as you. Consequently I also use exactly the same algorithm.
I just have spare much more operation by converting the original list into a row vector of complex (array of points 's coordinate).

This result in a shorter code (see post below)

From this row vector of complex coordinate, a substration and ABS norm make easy to compute distance. And MAX is used to keep the largest distance into the stack.

#23

This is my version with the 50G:

\<< 0 1 PICK3 SIZE 1 -
FOR I OVER I DUP 1 + SUB 1 I 2 -
FOR J PICK3 J DUP 1 + SUB OVER - DUP * EVAL + ROT MAX SWAP 2
STEP DROP 2
STEP NIP \v/
\>>

Bytes: 125

-Edwin


#24

the same code enhanced (50G)

« 0. 1. PICK3 SIZE 1. -
FOR I OVER I DUP 1. + SUB 1. I 2. -
FOR J PICK3 J DUP 1. + SUB OVER - AXL ABS ROT MAX SWAP 2.
STEP DROP 2.
STEP NIP
»
Bytes: 120.5

-Edwin

#25

I figured I'd try this problem on the 34S. Since there are no lists, I've changed things so that the values are in registers 00 .. n and n+1 is on the stack. So the problem example is set up:

    00:  1        05:  3
01: 1 06: 3
02: 0 07: 4
03: 0 08: 1
04: 2 09: 0

And 10 is on the stack.

My not heavily optimised program for this is:

    01: LBL A
02: # 002
03: -
04: x[<=]0?
05: CLx
06: x=0?
07: RTN
08: # 002
09: SDR 005
10: +
11: STO J
12: # 000
13: LBL 00
14: RCL J
15: STO K
16: DROP
17: LBL 01
18: [cmplx]RCL[->]J
19: [cmplx]RCL-[->]K
20: [cmplx]ABS
21: [<->] XZTT
22: MAX
23: DSL K
24: GTO 01
25: DSE J
26: GTO 00
27: END

Of these, the END and the three LBLs can be removed for a total of 23 steps. This is 46 bytes. The five point example executes instantly, ten points in well under a second.

- Pauli

Edited: 24 Sept 2012, 5:20 p.m.

#26

If the entry list was a list of complex points, it would be easy:

\<<
0
SWAP
2
\<< - ABS MAX \>>
DOCOMB
\>>

That is, if only we had the command DOCOMB ;-)
DOCOMB would work much like DOLIST and DOSUBS.
Its arguments are:

3: list
2: n = number of list elements to be taken in every iteration
1: object

DOCOMB will evaluate <object> for every combination of n elements taken from list L.

eg.

3: { 1 2 3 4 }
2: 3
1: \<< 3 \->LIST \>>
DOCOMB

will result in

{ 1 2 3 }
{ 1 2 4 }
{ 1 3 4 }
{ 2 3 4 }

versions of DOCOMB for n=2 or n=3 are easy:

@ DOCOMB for n=2
\<<
3 PICK SIZE
\-> L n ob s
\<<
1 s 1 -
FOR i
i 1 + s
FOR j
L i GET L j GET ob EVAL
NEXT
NEXT
\>>
\>>

@ DOCOMB for n=3
\<<
3 PICK SIZE
\-> L n ob s
\<<
1 s 2 -
FOR i
i 1 + s 1 -
FOR j
j 1 + s
FOR k
L i GET L j GET L k GET ob EVAL
NEXT
NEXT
NEXT
\>>
\>>

Your mission, if you choose to accept it, is to write DOCOMB so
that it will accept any n, n=1..size of list. Any single
combination must have the objects in the same order as they appear
in the list. Successive combinations may be generated in any order.

Success, Werner

Edited: 27 Sept 2012, 1:56 a.m. after one or more responses were posted


#27

Quote:
If the entry list was a list of complex points, it would be easy:

I agree with that !

But, we have to recognised that we are not far from it, a couple of instructions will do it!

Please consider the following trace :

PROGRAM STEPS        STACK AND DISPLAY
-------------------- ---------------------------------------
« 1: { 1 1 0 0 2 3 3 4 1 0 }

LIST-> 11: 1
10: 1
9: 0
8: 0
7: 2
6: 3
5: 3
4: 4
3: 1
2: 0
1: 10.
2. / 11: 1
10: 1
9: 0
8: 0
7: 2
6: 3
5: 3
4: 4
3: 1
2: 0
1: 5.

-> n « 10: 1
9: 1
8: 0
7: 0
6: 2
5: 3
4: 3
3: 4
2: 1
1: 0

{ n 2 } ->ARRY 1: [[ 1 1 ]
[ 0 0 ]
[ 2 3 ]
[ 3 4 ]
[ 1 0 ]]

[ (1,0) (0,1) ] 2: [[ 1 1 ][ 0 0 ][ 2 3 ][ 3 4 ][ 1 0]]
1: [ (1,0) (0,1) ]

* 1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

-> D « 0 1: 0

1 n FOR i 1: 0

D 2: 0
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

DUP DUP 4: 0
3: [(1,1) (0,0) (2,3) (3,4) (1,0)]
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

i GET CON 3: 0
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (1,1) (1,1) (1,1) (1,1)]

- 2: 0
1: [(0,0) (-1,-1) (1,2) (2,3) (0,-1)]

RNRM 2: 0
1: 3.60555127546

MAX 1: 3.60555127546

NEXT 1: 3.60555127546

D 2: 3.60555127546
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

DUP DUP 4: 3.60555127546
3: [(1,1) (0,0) (2,3) (3,4) (1,0)]
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

i GET CON 3: 3.60555127546
2: [(1,1) (0,0) (2,3) (3,4) (1,0)]
1: [(0,0) (0,0) (0,0) (0,0) (0,0)]

- 2: 3.60555127546
1: [(1,1) (0,0) (2,3) (3,4) (1,0)]

RNRM 2: 3.60555127546
1: 5.

MAX 1: 5.

NEXT 1: 5.

.........

RNRM 2: 5.
1: 4.472135955

MAX 1: 5.

NEXT 1: 5.

» » » 1: 5.
-------------------- ---------------------------------------

« LIST-> 2 / -> n 
« { n 2 } ->ARRY [ 1 (0,1) ] * -> D
« 0
1 n FOR i
D DUP DUP i GET CON - RNRM MAX NEXT
»
»
»

The initial list is easely converted into a row array contening the coordinate of the points as complex coordinates by the two first line of the code.


Edited: 26 Sept 2012, 9:39 a.m.

#28

"If the entry list was a list of complex points, it would be easy: "

Here is another easy way to do :

 2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS 

{ 3 6 5 2 3 1 8 2 6 5 4 4 7 4 }

->

{ (3.,6.) (5.,2.) (3.,1.) (8.,2.) (6.,5.) (4.,4.) (7.,4.) }


118 Bytes solution

«
2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS
DUP SIZE NDUPN ->LIST DUP TRAN
\GSLIST SWAP \GSLIST - ABS
0 + «MAX» STREAM
»

Edited: 26 Sept 2012, 5:10 p.m. after one or more responses were posted


#29

Quote:
 2. « IF NSUB 2. MOD THEN R->C ELSE DROP2 END » DOSUBS 

{ 3 6 5 2 3 1 8 2 6 5 4 4 7 4 }
->
{ (3.,6.) (5.,2.) (3.,1.) (8.,2.) (6.,5.) (4.,4.) (7.,4.) }


Here's a slight size improvement. If there's a way to put a built-in command directly on the stack, that would save another 5 bytes:

  1. « NSUB 2. MOD NOT { R->C } IFT  » DOSUBS

#30

2. \<< R\->C -1. NSUB ^ DROPN \>> DOSUBS
Cheers, Werner

#31

Now we have a 108 Bytes program ;)


This one in 99 Bytes:

«
2. « R->C -1. NSUB ^ DROPN » DOSUBS
DUP SIZE NDUPN ->LIST DUP TRAN
\GSLIST SWAP \GSLIST - ABS
SORT REVLIST HEAD
»

But both have problem with single point entry list (SigmaList 'bug')


Edited: 27 Sept 2012, 6:09 a.m.


#32

Yes, where

 LIST-> -> n « {n 2} ->ARRY [1 (0,1)] * »
or shortly
LIST-> 2 / { 2 } + ->ARRY [1 (0,1)] *
have no problem with inital single point list ! :-)


#33

Hi C.ret

This works fine but takes a lot of bytes !
I would try to be less than 100 Bytes whatever speed (I think it is imposssible to be quicker than a full stack approach ) ;)

<< LIST-> 2 / { 2 } + ->ARRY [1 (0,1)] * >>

takes 58.5 Bytes

<< LIST-> 2 / { 2 } + ->ARRY [1 'i'] * >>

only 47.5 but in this case, we must be in complex mode, so we have to set and restore flags...

« 2. « R->C -1. NSUB ^ DROPN » DOSUBS »

is 46 Bytes


Edited: 27 Sept 2012, 12:15 p.m.

#34

A 98 bytes version. Handle one point case.

  «
1. « IFERR R->C THEN END » DOSUBS
DUP HEAD + DUP SIZE NDUPN ->LIST
DUP TRAN \GSLIST SWAP \GSLIST -
AXL RNRM
»

AXL convert list<->matrix

#35

C'mon. That Mission Impossible quote was a joke, you know ;-)


Possibly Related Threads...
Thread Author Replies Views Last Post
  Writing RPL programs on OS X Sean Freeman 18 772 11-30-2013, 03:59 PM
Last Post: Sean Freeman
  48G vs 49G+ User RPL Speed Comparison John Colvin 7 290 11-16-2013, 10:07 PM
Last Post: Han
  RPL 32 David Hayden 4 250 11-11-2013, 11:34 AM
Last Post: David Hayden
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 356 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC 2013 programming contest winners Brian Walsh 52 1,876 09-26-2013, 11:39 PM
Last Post: David Hayden
  Box left at HHC Tim Wessman 1 193 09-26-2013, 11:05 PM
Last Post: Wlodek Mier-Jedrzejowicz
  HHC 2013 speakers' files Joe Horn 2 202 09-26-2013, 02:51 AM
Last Post: Geoff Quickfall
  HHC 2013 Day 2 Highlights Eddie W. Shore 6 411 09-23-2013, 04:03 PM
Last Post: Kimberly Thompson
  HHC 2013: Day 1 Highlights Eddie W. Shore 28 1,047 09-23-2013, 03:22 PM
Last Post: Brad Barton
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 740 09-22-2013, 09:39 AM
Last Post: Miguel Toro

Forum Jump: