The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

HHC 2008
Message #1 Posted by Patrick Rendulic on 30 Sept 2008, 9:57 a.m.

The conference is over, many of us were not there. Is there anyone willing to give the non attendees some news?

Many thanks!

      
Re: HHC 2008
Message #2 Posted by Gene Wright on 30 Sept 2008, 10:11 a.m.,
in response to message #1 by Patrick Rendulic

Well, of course, some things talked about at the conference are covered by the non-disclosure agreement each attendee signed. That's the only way to hear about what may, or may not be coming from HP. :-)

However, a good deal of information was shared by HP and other speakers that is not under the NDA. I'm sure more will be posted soon.

I'm working on a post about the programming contest myself.

The schedule of speakers is found here: Schedule

If anyone wants to hear what an individual spoke about, ask away!

            
Re: HHC 2008
Message #3 Posted by Paul Brogger on 30 Sept 2008, 12:01 p.m.,
in response to message #2 by Gene Wright

Did H-P offer a gift to attendees? If so, what was it?

                  
Re: HHC 2008
Message #4 Posted by Gene Wright on 30 Sept 2008, 12:14 p.m.,
in response to message #3 by Paul Brogger

The free gift this year was an HP 20b calculator. Another free gift was a commemorative HHC 2008 USB flash drive. Attendees were also given an HP Quick Calc calculator. HP provided lunch both days and a very nice dinner Saturday night.

It was very nice being at the Corvallis site with all of its history. We were visited by Sharon Butterfield who took orders for the HP 35 when it was introduced. Mega Shyam and Jim Donnelly shared memories of working with HP over the years, including the story of hunting for a bug that resulted in a warm start of a machine ONLY if a parenthesis was in position 45 of an equation (I think that's what it was). Long timer Charlie Patton gave a presentation on how calculators can continue to be great tools for learning. We were visited by Diana Byrne of HP fame too.

The repurposing of the 20b platform was talked about and examples of flashing the 20b rom were given by attendees. Some of the 20b calculators were flashed and left the conference as simulated HP 45 scientific calculators. :-)

Edited: 30 Sept 2008, 12:20 p.m.

                        
Re: HHC 2008
Message #5 Posted by George Bailey (Bedford Falls) on 30 Sept 2008, 12:48 p.m.,
in response to message #4 by Gene Wright

Quote:
Some of the 20b calculators were flashed and left the conference as simulated HP 45 scientific calculators. :-)

With overlays provided? :-)

                        
Re: HHC 2008
Message #6 Posted by John B. Smitherman on 30 Sept 2008, 3:37 p.m.,
in response to message #4 by Gene Wright

"Mega Shyam and Jim Donnelly shared memories of working with HP over the years, including the story of hunting for a bug that resulted in a warm start of a machine ONLY if a parenthesis was in position 45 of an equation (I think that's what it was)."

That's another good reason to use RPN and avoid parenthesis ;-)

John

            
Re: HHC 2008 Programming Contest
Message #7 Posted by Gene Wright on 30 Sept 2008, 2:15 p.m.,
in response to message #2 by Gene Wright

The programming problem can be found here. It is a PDF document:

[link:http://home.comcast.net/~genela/HHC2008 Programming%20Contest.pdf]HHC 2008 Programming Problem[/link]

There were two classes of machines eligible: RPL (any) and RPN (any). Only four entries were received, two in each category.

Only one machine (a 50g) correctly solved all input problems. That was the winner of course. Allen Thomson. He correctly solved all 7 input cases in about 12 seconds. Timing wasn't as critical, since his program was the only one that worked in all cases.

His approach will be published here soon. It can easily be sped up (he agrees with that!) because given the limited time at the conference, simply getting it to work for the input cases took a lot of thought. Not much time for speeding things up.

One note: The hexagons in the problem are to be regular hexagons - no internal pointing sides.

Download and give it a try.

                  
Re: HHC 2008 Programming Contest
Message #8 Posted by Allen on 30 Sept 2008, 10:25 p.m.,
in response to message #7 by Gene Wright

Gene, well done making such a problem! You are right.. I pulled out my 50g on the plane ride home, and within a few seconds saw some embarrassingly sloppy code ( e.g. << 1 3 PICK SWAP GET >> when I could have just done << OVER HEAD >>. It is sloppy in that regard, but I spend so much time re-typing things from my 48g to the 50g that I had only one occasion to make any speed improvement at all.. that is to replace a small routine with a look-up list to save a length-14 loop call. The remainder of the program is untouched from the original working version.

Does anyone know how to get VISTA to work with the CONN 4X program. I have loaded the USB drivers from the 50g disk, and still making no progress at all hooking either of my 48gx or 50g up to the Windows Box. Shoot!

                        
Re: HHC 2008 Programming Contest
Message #9 Posted by Walter B on 1 Oct 2008, 1:55 a.m.,
in response to message #8 by Allen

Quote:
Does anyone know how to get VISTA to work ...
Allen, that's a good point! Sorry, couldn't let this pass by ;)
                        
Re: HHC 2008 Programming Contest
Message #10 Posted by Gene Wright on 1 Oct 2008, 7:57 a.m.,
in response to message #8 by Allen

Now, now, Allen... I was in no way slamming your code. :-)

First and foremost, code has to work! Given that you said you stayed up until 3am working on this problem and that you were the only one who successfully handled all test cases, your code was exactly what it needed to be!

What I saw that could be improved was simply the use of external subprograms for a start. That makes it much easier to get something to work :-) but is slower (of course) than having everything in one procedure.

So, no slams, just a realization that given more time, it could be sped up.

Egan...good job as usual. I'll post the 7 input cases I used later today.

                  
Re: HHC 2008 Programming Contest
Message #11 Posted by Egan Ford on 1 Oct 2008, 3:42 a.m.,
in response to message #7 by Gene Wright

Gene,

My first crude attempt, if slower than 12 seconds I can speed it up. Please time it for me since I do not have the original problem set. This program should work with any set of points even if they exceed 105 (14 rows).

P.S., great problem, where did it come from?

%%HP: T(3)A(R)F(.);
\<< SORT \-> p
  \<< p SIZE
    CASE DUP 3 ==
      THEN DROP p OBJ\-> \-> a b c r
        \<< 'n' DUP DUP PURGE 1 + * 2 / b - 'n' 0 ROOT CEIL R\->I 'r' STO c b - b a - >
          IF
          THEN r b a - + 2 COMB r 2 COMB - b + c ==
            IF
            THEN "TRIANGLE DOWN"
            ELSE "ERROR"
            END KILL
          ELSE b r 2 COMB r c b - - 2 COMB - - a ==
            IF
            THEN "TRIANGLE UP"
            ELSE "ERROR"
            END KILL
          END
        \>>
      END DUP 4 ==
      THEN DROP p OBJ\-> \-> a b c d r
        \<< 'n' DUP DUP PURGE 1 + * 2 / c - 'n' 0 ROOT CEIL R\->I 'r' STO b r r 1 - * 2 / >
          IF
          THEN r c b - + 2 COMB r 2 COMB - c + d ==
            IF
            THEN b r 2 COMB r c b - - 2 COMB - - a ==
              IF
              THEN "PARALLELOGRAM DIAMOND" KILL
              END
            END
          END
        \>> p OBJ\-> \-> a b c d r
        \<< d c - b a - \=/
          IF
          THEN "ERROR" KILL
          END 'n' DUP DUP PURGE 1 + * 2 / d - 'n' 0 ROOT CEIL R\->I 'r' STO c r r 1 - * 2 / \<=
          IF
          THEN "ERROR" KILL
          END 'n' DUP DUP PURGE 1 + * 2 / b - 'n' 0 ROOT CEIL R\->I 'r' STO a r r 1 - * 2 / \<=
          IF
          THEN "ERROR" KILL
          END r d c - + 2 COMB r 2 COMB - b + d ==
          IF
          THEN "PARALLELOGRAM LEFT" KILL
          END r d c - + 1 + 2 COMB r 1 + 2 COMB - b + d ==
          IF
          THEN "PARALLELOGRAM RIGHT"
          ELSE "ERROR"
          END KILL
        \>>
      END 6 ==
      THEN p OBJ\-> \-> a b c d e f r
        \<< f e - b a - \=/
          IF
          THEN "ERROR" KILL
          END f e - 2 * d c - \=/
          IF
          THEN "ERROR" KILL
          END 'n' DUP DUP PURGE 1 + * 2 / f - 'n' 0 ROOT CEIL R\->I 'r' STO e r r 1 - * 2 / \<=
          IF
          THEN "ERROR" KILL
          END 'n' DUP DUP PURGE 1 + * 2 / b - 'n' 0 ROOT CEIL R\->I 'r' STO a r r 1 - * 2 / \<=
          IF
          THEN "ERROR" KILL
          END r b a - + 2 COMB r 2 COMB - a + c \=/
          IF
          THEN "ERROR" KILL
          END r b a - + 'r' STO r b a - + 2 COMB r 2 COMB - d + f \=/
          IF
          THEN "ERROR" KILL
          END "HEXAGON" KILL
        \>>
      END "ERROR"
    END
  \>>
\>>
                        
Re: HHC 2008 Programming Contest
Message #12 Posted by Egan Ford on 2 Oct 2008, 10:46 a.m.,
in response to message #11 by Egan Ford

The version above is not timer friendly, the version below has the KILL statements removed. Some optimizations.

%%HP: T(3)A(R)F(.);
\<< SORT 'n*(n+1)/2' \-> p t
  \<< "ERROR" p SIZE
    CASE DUP 3 ==
      THEN DROP p OBJ\-> \-> a b c r
        \<< t b - 'n' 0 ROOT CEIL R\->I 'r' STO c b - b a - >
          IF
          THEN a r r 1 - * 2 / >
            IF
            THEN r b a - + 2 COMB r 2 COMB - b + c ==
              IF
              THEN DROP "TRIANGLE DOWN"
              END
            END
          ELSE c r r 1 + * 2 / \<=
            IF
            THEN b r 2 COMB r c b - - 2 COMB - - a ==
              IF
              THEN DROP "TRIANGLE UP"
              END
            END
          END
        \>>
      END DUP 4 ==
      THEN DROP p OBJ\-> \-> a b c d r
        \<< t c - 'n' 0 ROOT CEIL R\->I 'r' STO b r r 1 - * 2 / >
          IF
          THEN r c b - + 2 COMB r 2 COMB - c + d ==
            IF
            THEN b r 2 COMB r c b - - 2 COMB - - a ==
              IF
              THEN DROP "PARALLELOGRAM DIAMOND"
              END
            END
          ELSE d c - b a - ==
            IF
            THEN d r r 1 + * 2 / \<=
              IF
              THEN t b - 'n' 0 ROOT CEIL R\->I 'r' STO a r r 1 - * 2 / >
                IF
                THEN r d c - + 2 COMB r 2 COMB - b + d ==
                  IF
                  THEN DROP "PARALLELOGRAM LEFT"
                  ELSE r d c - + 1 + 2 COMB r 1 + 2 COMB - b + d ==
                    IF
                    THEN DROP "PARALLELOGRAM RIGHT"
                    END
                  END
                END
              END
            END
          END
        \>>
      END 6 ==
      THEN p OBJ\-> \-> a b c d e f r
        \<< f e - b a - ==
          IF
          THEN f e - 2 * d c - ==
            IF
            THEN t f - 'n' 0 ROOT CEIL R\->I 'r' STO e r r 1 - * 2 / >
              IF
              THEN t b - 'n' 0 ROOT CEIL R\->I 'r' STO a r r 1 - * 2 / >
                IF
                THEN r b a - + 2 COMB r 2 COMB - a + c ==
                  IF
                  THEN r b a - + 'r' STO r b a - + 2 COMB r 2 COMB - d + f ==
                    IF
                    THEN DROP "HEXAGON"
                    END
                  END
                END
              END
            END
          END
        \>>
      END
    END
  \>>
\>>

Edited: 2 Oct 2008, 12:11 p.m.

                              
Re: HHC 2008 Programming Contest
Message #13 Posted by Egan Ford on 2 Oct 2008, 6:05 p.m.,
in response to message #12 by Egan Ford

Someone was kind enough to send me the problem set.

I used the following programs to run and time:

Program A (above).

Program PROBS:

%%HP: T(3)A(R)F(.);
\<< {
      { 16 23 31 }
      { 33 26 34 }
      { 18 24 25 32 }
      { 24 25 31 33 }
      { 8 17 32 21 34 10 }
      { 8 17 32 21 33 10 }
      { 56 66 1 }
    } \-> a
  \<< 1 a SIZE
    FOR i a i GET A
    NEXT
  \>>
\>>

Program TIMER:

%%HP: T(3)A(R)F(.);
\<< TICKS \-> t
  \<< EVAL TICKS t - B\->R 8192 /
  \>>
\>>

Output of: << PROBS >> TIMER PRST:

8: "ERROR"
7: "TRIANGLE UP"
6: "PARALLELOGRAM DIAMOND"
5: "ERROR"
4: "HEXAGON"
3: "ERROR"
2: "TRIANGLE UP"
1: 4.80969238281

4.81 seconds. Delightful problem. Thanks.

Edited: 2 Oct 2008, 6:08 p.m.

                                    
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #14 Posted by Gene Wright on 2 Oct 2008, 6:31 p.m.,
in response to message #13 by Egan Ford

Oops. I had meant to post the problem set earlier.

Sorry Egan!

Maybe that will be an encouragement to attend next year's conference...to win the contest! :-)

Now, how about a good, quick working RPN solution?

Gene

                                          
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #15 Posted by Egan Ford on 2 Oct 2008, 7:10 p.m.,
in response to message #14 by Gene Wright

I think someone else has one, if not, and if I have time, I'll give it a go this weekend.

A challenge for any fast RPN version:

What is this shape, if any, following Gene's original rules:

{ 7620789313366866 7620789313207113 7640524666050858 7640524666210611 }
My program will tell you in 1.6 seconds.
                                                
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #16 Posted by Eric Smith on 2 Oct 2008, 7:51 p.m.,
in response to message #15 by Egan Ford

It's an error, since the problem states that points will be numbered in the range [1, 105].

If you remove that constraint, potential solutions can't use a lookup table for the coordinate transformation, though I'm not sure that is faster even in the [1, 105] range.

                                                      
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #17 Posted by Egan Ford on 2 Oct 2008, 8:46 p.m.,
in response to message #16 by Eric Smith

Quote:
It's an error, since the problem states that points will be numbered in the range [1, 105].
Yep, my bad. I'll restate the challenge (taunt):

What is this shape, if any, following Gene's original rules sans the 1-105 range?

Quote:
If you remove that constraint, potential solutions can't use a lookup table for the coordinate transformation, though I'm not sure that is faster even in the [1, 105] range.
Nope, too much to look up, just for the up triangles you have 13 + 2*12 + 3*11 + ..., then you need to add in the down triangles, all 3 different parallelograms, and finally the hexagons.

What it does remove is any type of iterative loop.

Edited: 2 Oct 2008, 9:04 p.m.

                                                            
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #18 Posted by Eric Smith on 3 Oct 2008, 3:15 p.m.,
in response to message #17 by Egan Ford

My (incomplete) solution used a string as a lookup table just for a coordinate transform from triangular to rectangular coordinates, not trying to use a table to enumerate all the possible geometric figures. I thought that would be faster than doing it by a computation, but I could be mistaken, and it certainly doesn't work if there's not a relatively small upper bound on the numbers.

                                                                  
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #19 Posted by Egan Ford on 3 Oct 2008, 4:23 p.m.,
in response to message #18 by Eric Smith

I think that would work quite well if allowed to store a precomputed table. However, if having to compute the table as part of the timed run, well, who knows, with only 7 tests...

                                                                        
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #20 Posted by Eric Smith on 3 Oct 2008, 6:50 p.m.,
in response to message #19 by Egan Ford

As a string, it was just part of the program. I constructed it with another program, then edited it into the solver program.

                                          
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #21 Posted by Jeff O. on 2 Oct 2008, 10:17 p.m.,
in response to message #14 by Gene Wright

Gene, I've been thinking about the problem and think I may have worked out the method I would use. Implementing that method on my 35s may be tricky, and it will probably be less than good and quick, but I'll give it a try. Guess I'd better hurry if Egan is going to work on it!

Edited: 2 Oct 2008, 10:19 p.m.

                                          
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #22 Posted by Egan Ford on 4 Oct 2008, 3:55 a.m.,
in response to message #14 by Gene Wright

Quote:
Now, how about a good, quick working RPN solution?
Here is my 41CX version. I selected the 41CX because I could rapidly develop on my notebook then download to emulators and the real thing for testing. I also wanted a printer, a timer, and alpha support. Where is the 41CXII!?!?!

Performance Expectations

Initially, I did not have time to test on a real 41CX, so I used the i41CXp emulator. The i41CXp emulator can be configured to run at native speed or up to ~5.5 times faster. I used the NQUEENS benchmark to compare performance:

Configuration                Time         Speedup
------------------------     --------     -------
41CX no printer              1076 sec       1.00x
i41CXp default + printer     1071 sec       1.00x
i41CXp default                691 sec       1.56x
i41CXp fast + printer         288 sec       3.74x
i41CXp fast                   197 sec       5.46x
35s                           257 sec       4.19x
i41CXp fast + printer and 35s are the closest in terms of performance with the 35s a bit faster.

NOTE: A thread with some 41CX printer slowdown info/observations: http://www.hpmuseum.org/cgi-sys/cgiwrap/hpmuseum/archv018.cgi?read=138343.

Usage

  1. If using an emulator or the real thing turn off the printer, it will just slow you down.
  2. XEQ SETUP first. This will CLRG, zero the stopwatch, and setup REG 09 as a results counter, this is used after running all tests to print out the results.
  3. XEQ FS. Do this 7 times. Each time you will be prompted for the number of points and the points. FS will then start the stopwatch, find the shape, stop the clock, display the results. Each time FS is run the stopwatch will start from where it left off accumulating the time taken.
  4. Connect printer, then XEQ PRINT to get your results.

Results (printer output from i41CXp)

i41CXp default speed + printer (should be same speed as 41CX):

Update: Physical 41CX Time: 43.57 seconds.

i41CXp fast + printer mode:

The time reported is the total run time.

Challenge: Best my i41CXp/fast+printer results with a 35s. The 35s should have the edge.

Development Environment

I used the vi editor, GNU make, and HP41UC to edit and compile the code. For testing I used V41 and i41CXp. Final verification was done on a module-free stock 41CX halfnut. I wanded in the program in less than a minute. Total development and testing time was about 2-3 hours.

I would have never attempted this on the 35s. I'm just too lazy. I need my "IDE".

Code

NOTE: I was lazy and there is a lot of cut and paste, but its fast.

NOTE: This is a general purpose solution, i.e. there is no 105 point upper limit.

NOTE: I used the following sort routine: http://www.hpmuseum.org/software/41/sortnumb.htm ("Focal Program" version).

Here is a zip file with all the different formats including LIF and RAW for EMU41 and V41: http://www.hpmuseum.org/guest/eganford/hhc2008.zip.

Users with wands may prefer this: http://www.hpmuseum.org/guest/eganford/hhc2008.pdf.

i41CXp users can download "hhc2008" directly into their iPhone/iTouch from http://sense.net/~egan/41cx/.

Or, you can just key it all in. Hopefully there are no bugs.

01 LBL "SETUP"            134 *                     267 1                     400 RCL 02                
02 0                      135 2                     268 +                     401 8                     
03 SETSW                  136 /                     269 SQRT                  402 *                     
04 CLRG                   137 RCL 01                270 1                     403 1                     
05 11                     138 X<=Y?                 271 -                     404 +                     
06 STO 09                 139 GTO 20                272 2                     405 SQRT                  
07 0                      140 RCL 02                273 /                     406 1                     
08 RTN                    141 RCL 01                274 STO 07                407 -                     
09 LBL "FS"               142 -                     275 FRC                   408 2                     
10 FIX 00                 143 ENTER                 276 X=0?                  409 /                     
11 CF 29                  144 ENTER                 277 GTO 09                410 STO 07                
12 CLA                    145 RCL 07                278 RCL 07                411 FRC                   
13 >"NUM PTS?"            146 2                     279 1                     412 X=0?                  
14 PROMPT                 147 *                     280 +                     413 GTO 13                
15 INT                    148 +                     281 INT                   414 RCL 07                
16 STO 00                 149 1                     282 STO 07                415 1                     
17 1000                   150 -                     283 LBL 09                416 +                     
18 /                      151 *                     284 RCL 07                417 INT                   
19 1                      152 2                     285 1                     418 STO 07                
20 +                      153 /                     286 -                     419 LBL 13                
21 STO 10                 154 RCL 02                287 RCL 07                420 RCL 07                
22 LBL 00                 155 +                     288 *                     421 1                     
23 CLA                    156 RCL 03                289 2                     422 -                     
24 >"PT "                 157 X#Y?                  290 /                     423 RCL 07                
25 ARCL 10                158 GTO 20                291 RCL 01                424 *                     
26 >"?"                   159 CLA                   292 X<=Y?                 425 2                     
27 PROMPT                 160 >"TRIANGLE DOWN"      293 GTO 20                426 /                     
28 INT                    161 2                     294 RCL 02                427 RCL 01                
29 STO IND 10             162 STO 08                295 RCL 01                428 X<=Y?                 
30 ISG 10                 163 GTO 20                296 -                     429 GTO 20                
31 GTO 00                 164 LBL 06                297 ENTER                 430 RCL 06                
32 RUNSW                  165 0                     298 ENTER                 431 RCL 05                
33 FIX 04                 166 4                     299 RCL 07                432 -                     
34 RCL 00                 167 X#NN?                 300 2                     433 ENTER                 
35 1000                   168 GTO 11                301 *                     434 ENTER                 
36 /                      169 RCL 03                302 +                     435 RCL 07                
37 1                      170 8                     303 1                     436 2                     
38 +                      171 *                     304 -                     437 *                     
39 SIGN                   172 1                     305 *                     438 +                     
40 LBL 01                 173 +                     306 2                     439 1                     
41 LASTX                  174 SQRT                  307 /                     440 -                     
42 LASTX                  175 1                     308 RCL 02                441 *                     
43 RCL IND L              176 -                     309 +                     442 2                     
44 LBL 02                 177 2                     310 RCL 04                443 /                     
45 X<=NN?                 178 /                     311 X#Y?                  444 RCL 01                
46 GTO 03                 179 STO 07                312 GTO 10                445 +                     
47 X<>Y                   180 FRC                   313 CLA                   446 RCL 03                
48 STO Y                  181 X=0?                  314 >"PARALLELOGRAM"      447 X#Y?                  
49 RCL IND X              182 GTO 07                315 >" LEFT"              448 GTO 20                
50 LBL 03                 183 RCL 07                316 4                     449 RCL 06                
51 ISG Y                  184 1                     317 STO 08                450 RCL 05                
52 GTO 02                 185 +                     318 GTO 20                451 -                     
53 X<> IND L              186 INT                   319 LBL 10                452 ST+ 07                
54 STO IND Z              187 STO 07                320 1                     453 ENTER                 
55 ISG L                  188 LBL 07                321 ST+ 07                454 ENTER                 
56 GTO 01                 189 RCL 07                322 RCL 02                455 RCL 07                
57 CLA                    190 1                     323 RCL 01                456 2                     
58 >"ERROR"               191 -                     324 -                     457 *                     
59 0                      192 RCL 07                325 ENTER                 458 +                     
60 STO 08                 193 *                     326 ENTER                 459 1                     
61 0                      194 2                     327 RCL 07                460 -                     
62 3                      195 /                     328 2                     461 *                     
63 X#NN?                  196 RCL 02                329 *                     462 2                     
64 GTO 06                 197 X<=Y?                 330 +                     463 /                     
65 RCL 02                 198 GTO 08                331 1                     464 RCL 04                
66 8                      199 RCL 03                332 -                     465 +                     
67 *                      200 RCL 02                333 *                     466 RCL 06                
68 1                      201 -                     334 2                     467 X#Y?                  
69 +                      202 ENTER                 335 /                     468 GTO 20                
70 SQRT                   203 ENTER                 336 RCL 02                469 CLA                   
71 1                      204 RCL 07                337 +                     470 >"HEXAGON"            
72 -                      205 2                     338 RCL 04                471 6                     
73 2                      206 *                     339 X#Y?                  472 STO 08                
74 /                      207 +                     340 GTO 20                473 LBL 20                
75 STO 07                 208 1                     341 CLA                   474 STOPSW                
76 FRC                    209 -                     342 >"PARALLELOGRAM"      475 RCL 08                
77 X=0?                   210 *                     343 >" RIGHT"             476 STO IND 09            
78 GTO 04                 211 2                     344 5                     477 1                     
79 RCL 07                 212 /                     345 STO 08                478 ST+ 09                
80 1                      213 RCL 03                346 GTO 20                479 AVIEW                 
81 +                      214 +                     347 LBL 11                480 RTN                   
82 INT                    215 RCL 04                348 0                     481 LBL "PRINT"           
83 STO 07                 216 X#Y?                  349 6                     482 RCL 09                
84 LBL 04                 217 GTO 20                350 X#NN?                 483 1                     
85 RCL 02                 218 RCL 03                351 GTO 20                484 -                     
86 RCL 01                 219 RCL 02                352 RCL 06                485 1000                  
87 -                      220 -                     353 RCL 05                486 /                     
88 RCL 03                 221 ENTER                 354 -                     487 11                    
89 RCL 02                 222 ENTER                 355 RCL 02                488 +                     
90 -                      223 CHS                   356 RCL 01                489 STO 10                
91 X>Y?                   224 RCL 07                357 -                     490 LBL 21                
92 GTO 05                 225 2                     358 X#Y?                  491 CLA                   
93 RCL 07                 226 *                     359 GTO 20                492 RCL IND 10            
94 1                      227 +                     360 RCL 06                493 30                    
95 +                      228 1                     361 RCL 05                494 +                     
96 RCL 07                 229 -                     362 -                     495 INT                   
97 *                      230 *                     363 2                     496 GTO IND X             
98 2                      231 2                     364 *                     497 LBL 30                
99 /                      232 /                     365 RCL 04                498 >"ERROR"              
100 RCL 03                233 RCL 02                366 RCL 03                499 GTO 40                
101 X>Y?                  234 X<>Y                  367 -                     500 LBL 31                
102 GTO 20                235 -                     368 X#Y?                  501 >"TRIANGLE UP"        
103 RCL 03                236 RCL 01                369 GTO 20                502 GTO 40                
104 RCL 02                237 X#Y?                  370 RCL 06                503 LBL 32                
105 -                     238 GTO 20                371 8                     504 >"TRIANGLE DOWN"      
106 ENTER                 239 CLA                   372 *                     505 GTO 40                
107 ENTER                 240 >"PARALLELOGRAM"      373 1                     506 LBL 33                
108 CHS                   241 >" DIAMOND"           374 +                     507 >"PARALLELOGRAM"      
109 RCL 07                242 3                     375 SQRT                  508 >" DIAMOND"           
110 2                     243 STO 08                376 1                     509 GTO 40                
111 *                     244 GTO 20                377 -                     510 LBL 34                
112 +                     245 LBL 08                378 2                     511 >"PARALLELOGRAM"      
113 1                     246 RCL 04                379 /                     512 >" LEFT"              
114 -                     247 RCL 03                380 STO 07                513 GTO 40                
115 *                     248 -                     381 FRC                   514 LBL 35                
116 2                     249 RCL 02                382 X=0?                  515 >"PARALLELOGRAM"      
117 /                     250 RCL 01                383 GTO 12                516 >" RIGHT"             
118 RCL 02                251 -                     384 RCL 07                517 GTO 40                
119 X<>Y                  252 X#Y?                  385 1                     518 LBL 36                
120 -                     253 GTO 20                386 +                     519 >"HEXAGON"            
121 RCL 01                254 RCL 07                387 INT                   520 LBL 40                
122 X#Y?                  255 1                     388 STO 07                521 AVIEW                 
123 GTO 20                256 +                     389 LBL 12                522 ISG 10                
124 CLA                   257 RCL 07                390 RCL 07                523 GTO 21                
125 >"TRIANGLE UP"        258 *                     391 1                     524 FIX 06                
126 1                     259 2                     392 -                     525 RCLSW                 
127 STO 08                260 /                     393 RCL 07                526 CLA                   
128 GTO 20                261 RCL 04                394 *                     527 >"TIME: "             
129 LBL 05                262 X>Y?                  395 2                     528 ATIME24               
130 RCL 07                263 GTO 20                396 /                     529 AVIEW                 
131 1                     264 RCL 02                397 RCL 05                530 RTN                   
132 -                     265 8                     398 X<=Y?                 531 END                   
133 RCL 07                266 *                     399 GTO 20      

Edited: 4 Oct 2008, 11:42 a.m.

                                                
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #23 Posted by Chris Dean on 8 Oct 2008, 2:39 a.m.,
in response to message #22 by Egan Ford

Sorry for the lateness of this posting but I thought I would still submit my 'late entry' for the contest as it may still be of interest to some. The RPN developed is a partial solution and an explanation for this is given below.

I think I have taken a slightly different route to solve the problem which is not constrained by a 105 maximum.

I have developed algorithm in MS Excel VBA so I know that it works and as shown below I have written and typed in the code below on my HP-15C. Unfortunately the code only solves the problem for the triangular case. As Egan will probably agree that this is too laborious. To finish off the code I will need to use row numbers (i.e. -Line numbers in I) as I have run out of labels!

In response to the HHC Programming Contest I have developed the following algorithm based on the specified conditions and the following assumption

• Each point is one unit (row) away from each of its immediate neighbours

With this assumption I have used the fact that the number on the right hand side of the triangle can be generated by the formula

n=row * (row + 1) / 2

This leads to the formula for each corner i to determine which row it resides.

row(i) = INT((-1 + sqr(1+ 8*n(i))) / 2)

If n(i) <> row(i) * (row(i) + 1)/ 2 then row(i) = row(i) + 1

Where n(i) is the value of corner i of the polygon and row(i) is the row number containing the corner.

The points need to be rearranged in some cyclic order. The algorithm to do this will rely on calculating the maximum and minimum values for the defined corners.

Let r(i) represent the rearranged corner data where i = 1, N

For the TRIANGLE (3 points)

Find the minimum point and place in r(1) Find the maximum point and place in r(3) The third point place in r(2)

For the PARALLELOGRAM (4 points)

Find the minimum point and place in r(1) Find the maximum point and place in r(3)

For the remaining two points The find the minimum and place in r(4) The find the maximum and place in r(2)

For the HEXAGON (6 points)

Find the minimum point and place in r(1) Find the maximum point and place in r(4)

For the remaining four points The find the minimum and place in r(2) The find the maximum and place in r(5)

For the remaining two points The find the minimum and place in r(6) The find the maximum and place in r(3)

Therefore given the corner value of the polygon we can calculate its row number and working on the fact that each number is one unit (row) from its immediate neighbours all we need to calculate is the difference between each corner in terms of rows. There is one exception to this which occurs if two numbers are on the same row. This is rectified by just subtracting one corner value from the other.

For the numbers to form a polygon (triangle, parallelogram or hexagon) of equal length sides the difference between each of the points must be the same.

Therefore for each corner i = 1, N which has value r(i) and row value row(i)

if i < N then Diff(i) = ABS(row(i) - row(i + 1)) else Diff(i) = ABS(row(N) - row(1) end if

if Diff(i)= 0 then Diff(i) = ABS(r(i) – r(i + 1)) (or ABS(r(N) – r(1))

If each Diff(i) is the same then the result output is either TRIANGLE (1), PARALLELOGRAM (2) or HEXAGON (3) depending on the number of points entered otherwise ERROR (0) as for the number of points input is not 3, 4 or 6.

F LBL A F CLR REG 1 STO I FLBL B R/S STO (i) G TEST 2 GOTO C 7 RCL I G TEST 5 GOTO C 1 STO+I GOTO B F LBL C RCL I 1 - STO 0 GOSUB 1 G x=0 R/S 10 + STO I GOTO I F LBL 1 RCL 0 3 G TEST 5 GOTO 2 RCL 0 4 G TEST 5 GOTO 2 RCL 0 6 G TEST 5 GOTO 2 0 F LBL 2 2 / G INT G RTN F LBL 3 999 STO 7 CHS STO 8 F LBL 4 RCL 7 RCL (i) G x<=y STO 7 RCL 8 RCL (i) G TEST 9 STO 8 F ISG I GOTO 4 G RTN F LBL 5 STO 7 8 x 1 + SQRT 1 - 2 / G INT STO 8 1 + RCL 8 x 2 / RCL 7 G TEST 5 GOTO 6 RCL 8 1 + G RTN F LBL 6 RCL 8 G RTN F LBL .1 1.003 STO I GSB 3 RCL 7 STO .4 RCL 8 STO .6 1.003 STO I F LBL .4 RCL (i) RCL 7 G TEST 5 GOTO .5 RCL(i) RCL 8 G TEST 5 GOTO .5 RCL (i) STO .5 GOTO .6 F LBL .5 F ISG I GOTO .4 F LBL .6 RCL .4 GOSUB 5 STO .1 RCL .5 GOSUB 5 STO .2 RCL .6 GOSUB 5 STO .3 RCL .1 RCL .2 - G ABS G TEST 1 GOTO .7 RCL .4 RCL .5 - G ABS F LBL .7 STO 1 RCL .2 RCL .3 - G ABS G TEST 1 GOTO .8 RCL .5 RCL .6 - G ABS F LBL .8 STO 2 RCL .1 RCL .3 - G ABS G TEST 1 GOTO .9 RCL .6 RCL .4 - G ABS F LBL .9 STO 3 RCL 1 RCL 2 G TEST 6 GOTO .0 RCL 2 RCL 3 G TEST 6 GOTO .0 GOSUB 1 R/S F LBL .0 0 R/S

                                                      
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #24 Posted by Egan Ford on 8 Oct 2008, 11:52 a.m.,
in response to message #23 by Chris Dean

Quote:
I have developed algorithm in MS Excel VBA so I know that it works and as shown below I have written and typed in the code below on my HP-15C. Unfortunately the code only solves the problem for the triangular case. As Egan will probably agree that this is too laborious. To finish off the code I will need to use row numbers (i.e. -Line numbers in I) as I have run out of labels!
You may find this link helpful: Effective Computer-aided Calculator Programming - Part 1 - Voyager. Now you can rapidly write and test your 15C program on a desktop/laptop, then just take the few minutes to key it into an actual 15C.

Since nothing like this exists for a 35s, you are then stuck with manual entry, debugging, documenting, and rekeying after it crashes (and it does).

                                                            
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #25 Posted by Chris Dean on 8 Oct 2008, 5:17 p.m.,
in response to message #24 by Egan Ford

Egan

Thank you for the link I will try it out.

Chris

                                          
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #26 Posted by Jeff O. on 11 Oct 2008, 11:18 p.m.,
in response to message #14 by Gene Wright

Below is my solution to the HHC 2008 programming contest. It is an RPN program, implemented on the 35S. It correctly solves the seven trial cases (as well as all others I have tried.) Total time to solve the seven trial cases, based on an average of three runs per case, came to 12.6 seconds.

In order to avoid "poisoning" my thought process with better ideas, I have not reviewed any of the other solutions posted here. I'll check them after I post this to see how much better I could have done:-)

It took me a while to figure out how to attack the problem. I kicked around a variety of ideas and finally settled on a method in which I used the row numbers of the values (e.g., 1 is in the 1st row, 12 is in the 5th row, etc.) and the difference in corresponding values in different rows (e.g. the difference between the 1st value in row 7 (22) and the 1st value in row 3 (4) is 18) to check the validity of the set of points. Basically, check the first two points, predict the third based on the the first two and some calculations and see if it matches the entered value, if so and three points were entered it's a triangle, or proceeding to the 4th value for possible parallelograms and the 5th and 6th values for possible hexagons.

The equations I used are as follows:

Row Number of N = RNN = Sqrt(2N + 0.25) - 0.5 (if the formula does not yield an exact integer, then RNN is the next largest integer.)

Corresponding Value Difference between RNx and RNy = CVxy

where RNy is greater than RNx

let D = RNy - RNx

CVxy = D(2RNx+D-1)/2

				   Jump		
Line#	Command		      Start   Target	Comments
A001	LBL A					Label A
A002	RCL F					recall 6th possible value
A003	x>0?					is it greater than 0 (i.e., not equal to 0 or -1)?
A004	GTO A090		1		if yes, assume 6 points entered, branch to hexagon checking routine
A005	RCL E					recall 5th possible value entered
A006	-1					enter -1
A007	x=y?					check if equal to -1
A008	GTO A050		2		if yes, assume 4 points entered, branch to parallelogram checking routine
A009	RCL D					if no, recall 4th possible value entered
A010	x=y?					check if equal to -1
A011	GTO A014		3		if yes, assume 3 points entered, branch to triangle checking routine
A012	CLSTK				8	if not 3, 4, or 6, set of points is invalid, clear stack to display zero.
A013	STOP					stop, display zero for invalid set of points.
A014	RCL B				3	Begin triangle check routine, first sort values.  Recall 2nd entered value
A015	RCL C					recall third value entered
A016	x<y?					third value less than second value?
A017	x<>y					if yes, swap values
A018	STO C					store X reg value in third value register
A019	x<>y					swap
A020	RCL A					recall first value entered
A021	x>y?					first value greater than second value?
A022	x<>y					if yes, swap values
A023	STO A					store smallest value in first value register
A024	x<>y					swap to get second value
A025	RCL C					recall third value
A026	x<y?					third value less than second value?
A027	x<>y					if yes, swap values
A028	STO C					store largest value in third value register
A029	x<>y					swap
A030	STO B					store 2nd largest value in second value register, values now sorted
A031	XEQ V001		4		execute subroutine to determine row number of second value (RN2)
A032	STO M					store row number of 2nd value in M
A033	RCL A					recall smallest value
A034	XEQ V001		4		execute subroutine to determine row number of smallest value (RN1)
A035	STO L					store row number of smallest value in L
A036	-					subtract
A037	x<>0?					is difference not zero?
A038	GTO A044		6		if not 0, values not in same row, possible up-pointing triangle, branch to predict 3rd value
A039	RCL B					if yes, values are in same row, possible down-pointing triangle, recall B…
A040	RCL A					recall A...
A041	-					subtract A from B and…
A042	STO N					store difference in N and…
A043	XEQ W001		7		execute subroutine to determine difference between corresponding values (CV) in RN1 and RN2
A044	RCL+ B				6	for possible up pointing triangle, add row value difference to 2nd value to predict 3rd value.
						 for possible down-pointing triangle add CV difference to 2nd value to predict 3rd value
A045	RCL- C					recall largest value, subtract from predicted
A046	x<>0?					is difference not equal to 0?
A047	GTO A012		8		if entered and predicted 3rd values are not equal, not a triangle, branch to invalid data set stop
A048	1					if entered and predicted 3rd values are equal, is triangle, enter 1 for triangle
A049	STOP					Stop, display 1 for triangle
A050	XEQ S001		9	2	Parallelogram checking routine.  Begin by executing sort subroutine
A051	RCL D					recall 2nd smallest value entered
A052	STO N					Store in register that will hold side length
A053	XEQ V001		4		execute subroutine to determine row number of 2nd value (RN2)
A054	STO M					store row number of 2nd value in M
A055	RCL C					recall smallest value entered
A056	STO- N					subtract from 2nd value to determine side length (if not diamond), store in N 
A057	XEQ V001		4		execute subroutine to determine row number of smallest value (RN1)
A058	STO L					store row number of smallest value in L
A059	-					subtract RN1 from RN2
A060	x=0?					is difference zero?
A061	GTO A071		12		if difference is zero, not diamond parallelogram, branch to check left & right
A062	STO N					if difference not zero, is diamond possibility, store row difference in N
A063	RCL+ D					add to 2nd value to predict 3rd
A064	RCL- E					Subtract entered 3rd value from predicted
A065	x<>0?					is difference not 0?
A066	GTO A012		8		if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A067	RCL M					recall row number of 2nd value
A068	STO L					Store in register holding row number of 1st value
A069	XEQ W001		7		execute subroutine to determine difference between corresponding values (CV) in RN2 and RN4
A070	GTO A084		15		branch to predict 4th value
A071	XEQ W001		7	12	execute subroutine to determine difference between corresponding values (CV) in RN2 and RN3
A072	STO O					Store CV difference for later use
A073	RCL C					Recall 1st value
A074	+					Add CV difference to 1st value to calculate predicted 3rd value for right-pointing case
A075	RCL- E					subtract entered 3rd value from predicted
A076	x=0?					is difference 0?
A077	GTO A083		17		if yes, possible right-pointing parallelogram, branch to predict 4th point
A078	RCL O					if no, may still be left-pointing, recall CV difference
A079	RCL+ D					Add difference to 2nd value to calculate predicted 3rd value for left-pointing case
A080	RCL- E					subtract entered 3rd value from predicted
A081	x<>0?					is difference not 0?
A082	GTO A012		8		if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A083	RCL N				17	recall side length
A084	RCL+ E				15	add to 3rd value to predict 4th point
A085	RCL- F					Subtract entered 4th value from predicted
A086	x<>0?					is difference not 0?
A087	GTO A012		8		if difference is not zero, cannot be a parallelogram, branch to invalid data set stop
A088	2					if difference is 0, is a parallelogram.  Enter 2 for parallelogram
A089	STOP					Stop, display 2 for parallelogram
A090	XEQ S001		9	1	Hexagon checking routine.  Begin by executing sort subroutine
A091	RCL B					recall 2nd smallest value value entered
A092	STO N					Store 2nd smallest value in register that will hold side length
A093	XEQ V001		4		execute subroutine to determine row number of second value
A094	STO M					store row number of 2nd value in M
A095	RCL A					recall smallest value
A096	STO- N					subtract from 2nd value to determine side length, store in N 
A097	XEQ V001		4		execute subroutine to determine row number of smallest value
A098	STO L					store row number of smallest value in L
A099	-					subtract
A100	x<>0?					is difference not zero?
A101	GTO A012 		8		if difference is not zero,cannot be a parallelogram, branch to invalid data set stop
A102	XEQ W001		7		execute subroutine to determine difference between corresponding values in RN2 and RN3
A103	STO O					Store CV difference for later use
A104	RCL A					Recall 1st value
A105	+					Add CV difference to 1st value to calculate predicted 3rd value
A106	RCL- C					subtract entered 3rd value from predicted
A107	x<>0?					is difference not 0?
A108	GTO A012 		8		if difference is not zero, cannot be a hexagon, branch to invalid data set stop
A109	RCL C					Recall 3rd value to predict 4th value
A110	RCL+ N					Add side length
A111	RCL+ N					Add side length again to predict 4th point
A112	RCL- D					Subtract entered 4th value from predicted
A113	x<>0?					is difference not 0?
A114	GTO A012		8		if difference is not zero, cannot be a hexagon, branch to invalid data set stop
A115	RCL N					recall side length
A116	STO+ L					add to RN1, becomes RN3/4
A117	XEQ W001		7		execute subroutine to determine difference between corresponding values in RN3/4 and RN5/6
A118	RCL+C					Add CV difference to 3rd value 
A119	RCL+ N					Add side length to calculate predicted 5rd value
A120	RCL- E					Subtract entered 5th value from predicted
A121	x<>0?					is difference not 0?
A122	GTO A012		8		if difference is not 0 cannot be a hexagon, branch to invalid data set stop
A123	RCL E					recall 5th value
A124	RCL+ N					Add side length to calculate predicted 6th value
A125	RCL- F					Subtract entered 6th value from predicted
A126	x<>0?					is difference not 0?
A127	GTO A012		8		if difference is not 0, cannot be a hexagon, branch to invalid data set stop
A128	3					if difference is 0, is a hexagon, enter 3 for hexagon
A129	STOP					Stop, display 3 for hexagon
S001	LBL S				9	Sort routine
S002	5					input 5 for index (need to loop 5 times to sort 6 values)
S003	STO I					store in index register
S004	RCL A				30	recall 1st value
S005	RCL B					recall 2nd value
S006	x>y?					2nd bigger than 1st?
S007	x<>y					if yes, swap, then…
S008	STO A					store x register in 1st register
S009	x<>y					swap to get current 2nd value
S010	RCL C					recall 3rd value
S011	x>y?					3rd bigger than 2nd?
S012	x<>y					if yes, swap, then…
S013	STO B					store x register in 2nd register
S014	x<>y					swap to get current 3rd value
S015	RCL D					recall 4th value
S016	x>y?					4th bigger than 3rd?
S017	x<>y					if yes, swap, then…
S018	STO C					store x register in 3nd register
S019	x<>y					swap to get current 4th value
S020	RCL E					recall 5th value
S021	x>y?					5th bigger than 4th?
S022	x<>y					if yes, swap, then…
S023	STO D					store x register in 4th register
S024	x<>y					swap to get current 5th value
S025	RCL F					recall 6th value
S026	x>y?					6th bigger than 5th?
S027	x<>y					if yes, swap, then…
S028	STO E					store x register in 5th register
S029	x<>y					swap to get current 6th value
S030	STO F					store in register 6th register
S031	DSE I					decrement index
S032	GTO S004		30		if looped less than 5 times, loop back to repeat
S033	RTN					values sorted
V001	LBL V				4	RPN version of routine to determine row number of given value
V002	2			
V003	x			
V004	0.25			
V005	+			
V006	SQRT			
V007	0.5			
V008	-			
V009	+/-			
V010	INTG			
V011	+/-			
V012	RTN			
W001	LBL W				7	RPN version of routine to determine the absolute difference beteen corresponding 
						 values (1st-1st, 2nd-2nd, etc.) in different rows given the row numbers
W002	2			
W003	RCLx L			
W004	RCL+ N			
W005	1			
W006	-			
W007	RCLx N			
W008	2			
W009	/			
W010	RTN			
...
                                                
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #27 Posted by Egan Ford on 12 Oct 2008, 12:57 p.m.,
in response to message #26 by Jeff O.

Nice. This is the same method I used for both my RPL and RPN versions. The other popular method used was to convert to rectangular coordinates first. That approached optimized the shape search.

                                                      
Re: HHC 2008 Programming Contest -- anyone want to try an RPN solution?
Message #28 Posted by Jeff O. on 12 Oct 2008, 9:52 p.m.,
in response to message #27 by Egan Ford

Egan,
Thanks. I considered converting the values to rectangular coordinates, but when I started figuring out how I might do that I sort of came upon the method used and just went with that.

I am least pleased with the sorting methods I used. For the triangle, it was pretty easy to compare the three values and swap and store as needed, so I just included that in-line in the triangle checker. That seemed impractical for four and six values, so I wrote an inefficient bubble sort subroutine and used the same routine for both four and six values.

I found it interesting that others used the same or very similar "names" for the various figures.

best regards,

Jeff

                                    
Re: HHC 2008 Programming Contest
Message #29 Posted by Gjermund Skailand on 4 Oct 2008, 12:55 p.m.,
in response to message #13 by Egan Ford

Here is my entry. It calculates the 7 test examples in about 1.8 seconds on my hp49g+

The "SQRT" is square root, don't know to write it properly

%%HP: T(3)A(R)F(.);
\<<
\<< 
  -105. SF 
  SORT 
  DUP SIZE  
  CASE 
    DUP 3. == THEN DROP T3 END 
    DUP 4. == THEN DROP T4 2. * END
    DUP 6. == THEN DROP T6 3. * END 
    DROP2 0.  
  END 
  1. + { "ERROR" "TRIANGLE" "PARALELLOGRAM" "HEXAGON" } 
  SWAP GET
\>>
'A' STO

\<< EVAL 1. 6. START 6. ROLL P3 NEXT @ change to grid coordinates 6. PICK 6. PICK - RE @ length \-> A1 A2 A3 A4 A5 A6 L \<< @ walk around A2 A1 - (-1.,0.) L * == A4 A2 - (-1.,-1.) L * == A6 A4 - (0.,-1.) L * == A5 A6 - (1.,0.) L * == A3 A5 - (1.,1.) L * == A1 A3 - (0.,1.) L * == AND AND AND AND AND @ hexagon? \>> \>> 'T6' STO

\<< EVAL \-> A1 A2 A3 A4 \<< A1 A2 A3 3. \->LIST T3 A2 A3 A4 3. \->LIST T3 A1 A2 A4 3. \->LIST T3 A1 A3 A4 3. \->LIST T3 + + + 2. == @ require any two triangles

\>> \>> 'T4' STO

\<< EVAL ROT P3 ROT P3 ROT P3 PICK3 - UNROT SWAP - DUP2 - ABS ROT OVER (1.,1.) * == UNROT @ required for any triangle DUP2 (1.,0.) * == UNROT @ possible 1-2-3 triangle ccw (0.,1.)* == OR @ possible 2-3-5 triangle cw AND \>> 'T3' STO

\<< DUP 8. * "SQRT" 1. - 2. / IP DUPDUP 2. / SWAP OVER * + ROT - NEG 1. - SWAP R\->C \>> 'P3' STO

\<< { { 16. 23. 31. } { 33. 26. 34. } { 18. 24. 25. 32. } { 24. 25. 31. 33. } { 8. 17. 32. 21. 34. 10. } { 8. 17. 32. 21. 33. 10. } { 56. 66. 1. } } 1. 'A' DOLIST \>> 'TIM' STO \>>

TIM -> { "ERROR" "TRIANGLE" "PARALELLOGRAM" "ERROR" "HEXAGON" "ERROR" "TRIANGLE" }

Best regards

                                          
Re: HHC 2008 Programming Contest
Message #30 Posted by Egan Ford on 6 Oct 2008, 8:40 p.m.,
in response to message #29 by Gjermund Skailand

Awesome. BTW, \v/ is the SQRT ASCII symbol.

Below is my final RPL version. A pitiful 3 seconds. I just took my existing code and dumped the SOLVE and COMB functions. My RPL and RPN versions are algorithmically the same.

%%HP: T(3)A(R)F(.);
\<< SORT \-> p
  \<< "ERROR" p SIZE
    CASE DUP 3 ==
      THEN DROP p OBJ\-> \-> a b c r
        \<<
          b 8 * 1 + \v/ 1 - 2 / CEIL 'r' STO
          c b - b a - >
          IF
          THEN
            a r r 1 - * 2 / >
            IF
            THEN
              b a - DUP r 2 * + 1 - * 2 / b + c ==
              IF
              THEN DROP "TRIANGLE DOWN"
              END
            END
          ELSE
            c r r 1 + * 2 / \<=
            IF
            THEN
              b c b - DUP NEG r 2 * + 1 - * 2 / - a ==
              IF
              THEN DROP "TRIANGLE UP"
              END
            END
          END
        \>>
      END DUP 4 ==
      THEN DROP p OBJ\-> \-> a b c d r
        \<<
          c 8 * 1 + \v/ 1 - 2 / CEIL 'r' STO
          b r r 1 - * 2 / >
          IF
          THEN 
            c b - DUP r 2 * + 1 - * 2 / c + d ==
            IF
            THEN b c b - DUP NEG r 2 * + 1 - * 2 / - a ==
              IF
              THEN DROP "PARALLELOGRAM DIAMOND"
              END
            END
          ELSE d c - b a - ==
            IF
            THEN d r r 1 + * 2 / \<=
              IF
              THEN
                b 8 * 1 + \v/ 1 - 2 / CEIL 'r' STO
                a r r 1 - * 2 / >
                IF
                THEN
                  b a - DUP r 2 * + 1 - * 2 / b + d ==
                  IF
                  THEN DROP "PARALLELOGRAM LEFT"
                  ELSE
                    b a - DUP r 1 + 2 * + 1 - * 2 / b + d ==
                    IF
                    THEN DROP "PARALLELOGRAM RIGHT"
                    END
                  END
                END
              END
            END
          END
        \>>
      END 6 ==
      THEN p OBJ\-> \-> a b c d e f r
        \<< f e - b a - ==
          IF
          THEN f e - 2 * d c - ==
            IF
            THEN
              f 8 * 1 + \v/ 1 - 2 / CEIL 'r' STO
              e r r 1 - * 2 / >
              IF
              THEN
                b 8 * 1 + \v/ 1 - 2 / CEIL 'r' STO
                a r r 1 - * 2 / >
                IF
                THEN
                  b a - DUP r 2 * + 1 - * 2 / a + c ==
                  IF
                  THEN
                    r b a - + 'r' STO
                    b a - DUP r 2 * + 1 - * 2 / d + f ==
                    IF
                    THEN DROP "HEXAGON"
                    END
                  END
                END
              END
            END
          END
        \>>
      END
    END
  \>>
\>>
                                                
Re: HHC 2008 Programming Contest
Message #31 Posted by Gjermund Skailand on 7 Oct 2008, 11:13 a.m.,
in response to message #30 by Egan Ford

On the other hand it is fair to mention that my extended version returning type of triangle, paralellogram etc and satisfying your extended challenge has running time about twice of yours (has some additional checks on square root / grid point computation). Further not to mention that my version is more or less spesific to user rpl, whereas yours look like an easy and fast "streamlined" implementation in any language. Best regards

                                                
Re: HHC 2008 Programming Contest
Message #32 Posted by C.Ret on 8 Oct 2008, 5:43 a.m.,
in response to message #30 by Egan Ford

Hi,

This is my first post. Please be indulgent.

I found your codes really interesting showing different approaches and different implementations on various HP calculator. I was really amazing by the differences in execution time depending of algorithm and calculators.

My HP-28S is too slow to use code already post here. In order to get a result in a decent time, I have develop my own program.

Following is my attempt for a solution of this contest for a HP-28S (may work on HP-28C as well) with a brief explanation. I will post it here, so reader of this forum may found here an interesting listings for various HP past and present calculators.

Principes

I use a really different mathematical approach which is base on a projection of each equilateral triangular grid integer position into the complex plan. The coordinates of each point in the complex plan are chosen in a way that all triangle edges have exactly unity length. In the complex plan distance between two point P1 and P2 of respective coordinate z1=x1+i.y1 and z2=x2+i.y2 is easily compute by the norm | z2-z1 | = ABS(z2-z1). Any vertex not following the grid will have a non-integer value greater than unity. For example between point 1 and 5 distance is ABS(z1-z5)=1.7320…

Independently of the size of the list, the analyze of the list of equilateral triangular integer point is made in three step:

  1. - STAGE 1 - conversion of integer list { n1 n2 … nk } into complex coordinate array [ (x1,y1) (x2,y2) … (xk,yk) ].

    In order to save HP28 running time, all complex coordinates are pre-computed and store in the memory of the calculator in complex array ZN. This will spare time for solving (ROOT) 'n' for each point of the polygon. Complex coordinate of point n is simply the n-th element of ZN.

  2. - STAGE 2 - The equilateral triangular integer points entry is re-ordered in order to form a close figure with out crossing. This step is not really needed for triangle, but it is mandatory for larger polygon such as parallelogram of hexagram. Since coordinates are complex number, the easiest way sort the edge in the correct way to form a close topographic figure is simply to reorder by polar angle. This is done using an intermediate list 'I' as an index. To spare computation, the list is not directly sort, indirect addressing is obtained by using the POS function on the list I.

  3. - STAGE 3 - First check distance that edge length is integer. Non integer length is indicating a edge not following the equilateral triangular grid. The last operation consist of scanning the re-ordered polygon to verify that all edge have the same length. The length is first measured between last and first point of the polygon, second integer tested and then the polygon is scan using indirect addressing (I and POS) to check length of each successive edge.

Memory usage, variable and program names:

Global Variables: 
 ZN   : complex row array (105 complex elements)
 IDX  : list use as index for polygon re-ordering
 THO  : array of node polar angle for polygon re-ordering
 TOL  : numeric tolerance to zero (TOL=1E-8)

Programs : A : analyse equilateral trainagular positions list and return text string "ERROR" "TRIANGLE" "PARALELLOGRAM" "HEXAGRAM"… depending of polygon caracteristics. INITA: initialise variables ZN (complex coordinates),TOL and THO TEST : test the seven examples ALST : main sub-program in A


Program A
\<<
   { "ERROR" "DOT" "LINE" "TRIANGLE" "PARALELLOGRAM" "PENTAGRAM" "HEXAGON" } 
   SWAP ALST 1 + GET
\>>
'A' STO

Stack : 1: { n1 n2 … nk } --> 1: "text" Variable used: ZN, THO, IDX.

To initialised variables used by program A, INIT must be run once at time at least before.

Initialisation program : INITA

\<< 
   RAD                                 	@ Set trigonometric mode in radian
   0 13 FOR r                          	@ default value for the 105 first node
      0 r FOR c                        	@ r=row c=colum   0<= c < r
        3 SQRT INV r 2 pi \->NUM
        * 3 / SIN * -                  	@ compute x (real - abscise)
        r 2 / c -                      	@ compute y (imaginary - high)
        R\->C                          	@ convert to complex z=x+i.y
      NEXT
   NEXT
   105 \->ARRY 'ZN' STO                	@ create array and store it in 'ZN4
   1E-9 'TOL' STO                      	@ create TOL for optional cut off rounding
   [ 0 0 0 0 0 0 ] 'THO' STO           	@ create THO storing polar angle during STAGE 2
\>>
'INITA' STO

NZ =[ (0.577,0.000) (-0.289,0.500) (-0.289,0.500) (-1.155,1.000) ...
... (-10.681,-4.500) (-10.681,-5.500) (-10.681,-6.500)]

Sub-Program ALST

\<< DUP SIZE \-> LST k 
  \<<
    { k }                              	@ Polygon size
    DUP 0 CON                          	@ Create index
        ARRY\-> DROP                   	@ convert it to a list
         k \->LIST 'IDX' STO           	@ store it in IDX
    (0,0) CON                          	@ Create complex coordinate array Z
    'ZN' LST 1 GET GET                 	@ get first coordinate
    \-> Z0                             	@ STAGE -1- 
    \<<  
      1 k FOR a                        	@ for each position in list
        a
        'ZN' LST a GET GET             	@ get complex coordinate
        DUP                           	@ preserve complex coordinate
           Z0 - ARG                    	@ Calculate polar angle
           'THO' a 3 PICK PUT          	@ store it in THO
              1 a FOR b                	@ STAGE - 2 -
                'IDX'
                IF OVER THO b GET \>=  	@Compare old with current ARG
                THEN a                 	@ if current is greater count it (a)
                ELSE b                 	@if old is greater count it (b)
                END
                DUP2 GET               	@ get previous IDX value
                1 + PUT                	@ increase and save it in IDX
              NEXT 
           DROP                        	@ drop last ARG value
        PUT                            	@ put complex coordinate in array Z
      NEXT
    \>>                                	@ STAGE -3-
    DUP IDX 1 POS GET                  	@ get first node coordinate. z1
       OVER IDX k POS GET              	@ get last node coordinate zk
       - ABS                           	@ calculate edge length
    \-> Z d
    \<<                                	@ check distance at each edge
      d DUP IP ==                      	@ test if d is integer
      WHILE DUP DUP k < AND            	@ test i>0 AND i<k
      REPEAT                           	@ repeat only if necessary, exit when i=0
        IF                             	@ test each edge only if necessary
           Z IDX 3 PICK POS GET        	@ get i node coordinate
           Z IDX 4 PICK 1 + POS GET    	@ get i+1 node coordinate
           - ABS                       	@ calculate edge length
           d ==                        	@ compare with expected distance d
        THEN 1 +                       	@ jump to next edge
        ELSE 0 *                       	@ "error" clause, stop returning 0
        END
      END
    \>>
  \>>
\>>
'ALST' STO

Note: to avoid rounding error, the following code may be used advantageously:

[...]
       - ABS TOL / CEIL TOL *          	@ calculate edge length
[...]
           d - ABS TOL <               	@ compare with expected distance d

The code is not optimal. For example, time optimization may be obtain by short-cutting STAGE -2- for triangle analysis since the re-order of the node is useless in this case.

Testing program TEST

\<< 
    { 16. 23. 31. } A
    { 33. 26. 34. } A
    { 18. 24. 25. 32. } A
    { 24. 25. 31. 33. } A
    {  8. 17. 32. 21. 34. 10. } A
    {  8. 17. 32. 21. 33. 10. } A
    { 56. 66.  1. } A
\>>
'TEST' STO

The 7 TESTs run in about 25s on an original HP-28S Analyzing a triangle is only 3-4s and an hexagon about 7s. The INITialization up to 105 integer nodes is about 47s-50s depending of memory allocation and system status.

I have no HP48/49/50, but I will bend that my poor code will also run on these systems. Please tell me about how fast!

Any suggestions or comments are welcome.

Best regards. C.Ret

Edited: 9 Oct 2008, 8:18 a.m. after one or more responses were posted

                                                      
Re: HHC 2008 Programming Contest
Message #33 Posted by Gene Wright on 8 Oct 2008, 11:03 a.m.,
in response to message #32 by C.Ret

Great approach.

The timing would be larger than the 20-something seconds, because the initialization time would have to be included. No pre-storing of any information was allowed. :-)

But... this is the entire point of contests like this.

To challenge ourselves with a new problem.

To see how others respond to the same problem.

To learn and have fun.

I hope this contest did that for some of you. Have to think of a good contest for next year!

Gene

                                                            
Re: HHC 2008 Programming Contest
Message #34 Posted by Paul Dale on 8 Oct 2008, 4:44 p.m.,
in response to message #33 by Gene Wright

Then just include the computed list inline in the solution program. No pre-stored data now :-)

- Pauli

                                                                  
Re: HHC 2008 Programming Contest
Message #35 Posted by C.Ret on 9 Oct 2008, 8:02 a.m.,
in response to message #34 by Paul Dale

Yes,

You are right Paul. But I just realize that computing the 105 ZN values each time you run the program is a lot of time lost. Especially when considering that my code will only have to determinate a ZN value for each element in the entry list. This makes computing 105 values and using only 4-7 one time (at a maximum) of it !

There is no benefit in fact !

Edited: 9 Oct 2008, 8:02 a.m.

                                                            
Re: HHC 2008 Programming Contest
Message #36 Posted by Allen on 8 Oct 2008, 6:28 p.m.,
in response to message #33 by Gene Wright

Quote:
No pre-storing of any information was allowed. :-)

Unless I misread it, the contest description did not prohibit look-up tables to be used in place of algorithms to hasten the calculation.

                                                                  
Re: HHC 2008 Programming Contest
Message #37 Posted by Egan Ford on 8 Oct 2008, 6:53 p.m.,
in response to message #36 by Allen

I think the statement "SHIFT CLEAR VARS" implied that. However, if the precomputed table was part of the code, then, I see no problem.

                                                                        
Re: HHC 2008 Programming Contest
Message #38 Posted by Gene Wright on 8 Oct 2008, 9:55 p.m.,
in response to message #37 by Egan Ford

Correct. Lookup tables are fine, but the time to create them / store the information must be included in the run times.

Otherwise, a program could be run that stored a 1, 2, or 3 based on an evaluation of the points.

Then a small program could spit out Triangle, etc. based on that value.

:-)

                                                            
Re: HHC 2008 Programming Contest
Message #39 Posted by C.Ret on 9 Oct 2008, 8:11 a.m.,
in response to message #33 by Gene Wright

Thank you Gene

That is true that this type of contest is a challenge. I have to admit that I have had a lot of troubles elaborating my code. The version I post here is only the third. My first codes were based on row and column in the grid. The distances evaluation based on cartesian coordinates only come late in my development and advantage of the complex ABS and ARG functions any have appear at least.

I use pre-compute ZN values soon in my development since I observe that my slow running HP-28S spend most of it's time determining row/column or position of the nodes. This was due to the fact that I replace the solution used by Egan based on ROOT by a function of my own using iteration, which in fact was not speeding up the process !

Now I have read the solution proposed by Chris Dean, I am able to propose a more elegant approach.

So, you are true when telling that the fun of this contest is to learn how to solve new problem by peeking from others programmers.

I also agree that the time need for computation of the ZN values have to be add to the time need to analyze the entry.

Edited: 9 Oct 2008, 8:20 a.m.

                                                
Re: HHC 2008 Programming Contest (and a tip for future UserRPL optimization)
Message #40 Posted by Egan Ford on 12 Oct 2008, 12:43 p.m.,
in response to message #30 by Egan Ford

With some guidance from Gjermund, I've converted all integers to floats and got the time down to 1.25 seconds for all 7 problems. An incredible 2x+ increase in performance. And that is Gjermund's UserRPL tip: Floats are faster than Ints.

Thanks Gjermund!

The changes:

  1. Added a . (dot) after each integer.
  2. Converted the input list to floats (I->R after SORT).

%%HP: T(3)A(R)F(.);
\<< SORT I\->R \-> p
  \<< "ERROR" p SIZE
    CASE DUP 3. ==
      THEN DROP p OBJ\-> \-> a b c r
        \<<
          b 8. * 1. + \v/ 1. - 2. / CEIL 'r' STO
          c b - b a - >
          IF
          THEN
            a r r 1. - * 2. / >
            IF
            THEN
              b a - DUP r 2. * + 1. - * 2. / b + c ==
              IF
              THEN DROP "TRIANGLE DOWN"
              END
            END
          ELSE
            c r r 1. + * 2. / \<=
            IF
            THEN
              b c b - DUP NEG r 2. * + 1. - * 2. / - a ==
              IF
              THEN DROP "TRIANGLE UP"
              END
            END
          END
        \>>
      END DUP 4 ==
      THEN DROP p OBJ\-> \-> a b c d r
        \<<
          c 8. * 1. + \v/ 1. - 2. / CEIL 'r' STO
          b r r 1. - * 2. / >
          IF
          THEN 
            c b - DUP r 2. * + 1. - * 2. / c + d ==
            IF
            THEN b c b - DUP NEG r 2. * + 1. - * 2. / - a ==
              IF
              THEN DROP "PARALLELOGRAM DIAMOND"
              END
            END
          ELSE d c - b a - ==
            IF
            THEN d r r 1. + * 2. / \<=
              IF
              THEN
                b 8. * 1. + \v/ 1. - 2. / CEIL 'r' STO
                a r r 1. - * 2. / >
                IF
                THEN
                  b a - DUP r 2. * + 1. - * 2. / b + d ==
                  IF
                  THEN DROP "PARALLELOGRAM LEFT"
                  ELSE
                    b a - DUP r 1. + 2. * + 1. - * 2. / b + d ==
                    IF
                    THEN DROP "PARALLELOGRAM RIGHT"
                    END
                  END
                END
              END
            END
          END
        \>>
      END 6 ==
      THEN p OBJ\-> \-> a b c d e f r
        \<< f e - b a - ==
          IF
          THEN f e - 2. * d c - ==
            IF
            THEN
              f 8. * 1. + \v/ 1. - 2. / CEIL 'r' STO
              e r r 1. - * 2. / >
              IF
              THEN
                b 8. * 1. + \v/ 1. - 2. / CEIL 'r' STO
                a r r 1. - * 2. / >
                IF
                THEN
                  b a - DUP r 2. * + 1. - * 2. / a + c ==
                  IF
                  THEN
                    r b a - + 'r' STO
                    b a - DUP r 2. * + 1. - * 2. / d + f ==
                    IF
                    THEN DROP "HEXAGON"
                    END
                  END
                END
              END
            END
          END
        \>>
      END
    END
  \>>
\>>

Edited: 12 Oct 2008, 1:23 p.m.

                              
Re: HHC 2008 Programming Contest
Message #41 Posted by Allen on 2 Oct 2008, 10:19 p.m.,
in response to message #12 by Egan Ford

This is a beautiful solution.. question: one of the requirements is to make sure that all inputs were ON the grid. I don't see in the program above how this is accomplished?

                                    
Re: HHC 2008 Programming Contest
Message #42 Posted by Egan Ford on 3 Oct 2008, 2:27 a.m.,
in response to message #41 by Allen

The same basic steps are used for all 3 shapes. I'll just describe triangle.

  1. Assume ERROR.
  2. Sort points and assign to ABC
  3. If B-A < C-B, then AB closer, triangle down, else triangle up.
  4. Find the row that B is on. I use B since B is always on the horizontal base. To find B's row solve the equation r*(r+1)/2 - B = 0 using the 50g solver (ROOT), then round up (CEIL). r is now the row number. BTW, r*(r+1)/2 is the value of the last point on each row r.
  5. Verify that AB (or BC) is on the same row. Depending on A or C, I check that A > r*(r-1)/2 (the end of the above row), or that C <= r*(r+1)/2 (end of B's row). If on the same row continue.
  6. Lastly determine if the 3rd point makes a triangle. If base BC, then look up B->A, else down B->C. The distance to look is equal to the length of the base. The diagonal difference between points going left is C(r+x,2) - C(r,2), going right, same but r=r+1. Where r is the row number and x is the distance. If what you expect matches the remaining point, then you have a triangle on the grid.
The other shapes work the same way. If you look at the code you will see a lot of cut and paste (I was lazy). There is also room for optimizations, e.g. C(r+x,2) - C(r,2) may be sped up with x(2r+x-1)/2.

I hope this helps.

Edited: 3 Oct 2008, 2:34 a.m.

      
Re: HHC 2008
Message #43 Posted by Geoff Quickfall on 30 Sept 2008, 1:03 p.m.,
in response to message #1 by Patrick Rendulic

Boy Gene, don't you sleep!

The conference was my first and it was fantastic! Full of informative talks packed into the two days. Programming, calculator design, future outlook for calculators in general, some fancinating regression techniques.

Once I get my sleep and my notes there will be more to say.

Cheers, Geoff

Edited: 30 Sept 2008, 1:03 p.m.

            
Re: HHC 2008
Message #44 Posted by Namir on 30 Sept 2008, 6:15 p.m.,
in response to message #43 by Geoff Quickfall

Hi Geoff,

I really enjoyed meeting you and seeing your fantastic collection of vintage HP calculators and HP-01 watches (many of the calculator and watches you have so meticulously restored). I had a great pleasure listening to your stories as a pilot and as an HP collector.

I sure hope you will come back in HHC2009.

Namir

                  
Re: HHC 2008
Message #45 Posted by Geoff Quickfall on 30 Sept 2008, 6:42 p.m.,
in response to message #44 by Namir

Thanks Namir, I am glad you enjoyed it as I enjoyed seeing the power that your algorithms brought to the HP calculator. I have sent you a private email also

I will be at the 2009 HCC and plan to be more organized. I will combine it with a presentation on restoration techniques once I get all the research in one place and with the permission of the individuals that pioneered some of procedures.

To all that attended, thanks for making me welcome as a newbie!

Geoff

                        
Re: HHC 2008
Message #46 Posted by Namir on 30 Sept 2008, 11:32 p.m.,
in response to message #45 by Geoff Quickfall

Geoff,

my email is nshammas<at>aol<dot>com.

Namir

                              
Thanks Namir!
Message #47 Posted by Geoff Quickfall on 1 Oct 2008, 2:00 p.m.,
in response to message #46 by Namir

Thanks Namir!

            
Re: HHC 2008
Message #48 Posted by Olivier (Wa) on 1 Oct 2008, 10:59 p.m.,
in response to message #43 by Geoff Quickfall

I second that! It was my first conference as well and I thoroughly enjoyed meeting all of you over there, particularly finally be able to put a face behind the names :-) Count me in for next year as well, wherever that might be.

      
Re: HHC 2008
Message #49 Posted by Johnny Bjoern Rasmussen on 9 Oct 2008, 5:02 p.m.,
in response to message #1 by Patrick Rendulic

Did anyone take pictures on HHC 2008? I would like to read some kind of review as well.

Cheers

Johnny

            
Re: HHC 2008 conference report soon
Message #50 Posted by Gene Wright on 9 Oct 2008, 5:38 p.m.,
in response to message #49 by Johnny Bjoern Rasmussen

The final conference report should be published soon by Richard Nelson, as it is every year.

A quick google search of "hhc2007 conference report" brings up as its third result a post to the museum here by Jake Schwartz with a link to the conference site with the final report from last year.

I expect the 2008 report to be out soon.

So, I would keep an eye out here, on comp.sys.hp48, or at the HHC website found here: HHC 2008 webpage


[ Return to Index | Top of Index ]

Go back to the main exhibit hall