HHC 2012 RPL Programming Contest

[Gene Wright]

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.

[C.Ret]

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.

[Werner]

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

[C.Ret]

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

[Paul Dale]

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

- Pauli

[Gene Wright]

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

[Gilles Carpentier]

I've my solution...

What is noon Sunday in GMT times ?

[Jim Horn]

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.

[Gilles Carpentier]

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 ?

[Paul Dale]

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

- Pauli

[C.Ret]

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.

[Gilles Carpentier]

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.

[Gilles Carpentier]

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.

[Paul Dale]

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(n²) 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(n²) obvious algorithm especially when N_max 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

[Gilles Carpentier]

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.

[C.Ret]

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

      »

   »

»

[Gilles Carpentier]

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.

[C.Ret]

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) !

[David Hayden]

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

Dave

[C.Ret]

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.

[C.Ret]

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.

[Edwin]

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

[Edwin]

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

[Paul Dale]

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.

[Werner]

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

[C.Ret]

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.

[Gilles Carpentier]

"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

[David Hayden]

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

[Werner]

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

Cheers, Werner

[Gilles Carpentier]

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.

[C.Ret]

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 ! :-)

[Gilles Carpentier]

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.

[Gilles Carpentier]

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

[Werner]

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