HHC 2008



#35

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

Many thanks!


#36

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!


#37

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


#38

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.


#39

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

With overlays provided? :-)

#40

"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

#41

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.


#42

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!


#43

Quote:
Does anyone know how to get VISTA to work ...

Allen, that's a good point! Sorry, couldn't let this pass by ;)
#44

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.

#45

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
\>>
\>>

#46

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.


#47

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.


#48

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


#49

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.

#50

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.


#51

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.


#52

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.


#53

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


#54

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

#55

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.

#56

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.


#57

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


#58

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


#59

Egan

Thank you for the link I will try it out.

Chris

#60

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

#61

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.


#62

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

#63

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


#64

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
\>>
\>>

#65

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

#66

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


#67

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


#68

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

- Pauli


#69

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.

#70

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.


#71

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


#72

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.

:-)

#73

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.

#74

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.

#75

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?


#76

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.

#77

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.


#78

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


#79

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


#80

Geoff,

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

Namir


#81

Thanks Namir!

#82

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.

#83

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

Cheers

Johnny


#84

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


Possibly Related Threads…
Thread Author Replies Views Last Post
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 2,483 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC 2013 programming contest winners Brian Walsh 52 13,088 09-26-2013, 11:39 PM
Last Post: David Hayden
  Box left at HHC Tim Wessman 1 1,648 09-26-2013, 11:05 PM
Last Post: Wlodek Mier-Jedrzejowicz
  HHC 2013 speakers' files Joe Horn 2 1,673 09-26-2013, 02:51 AM
Last Post: Geoff Quickfall
  HHC 2013 Day 2 Highlights Eddie W. Shore 6 2,663 09-23-2013, 04:03 PM
Last Post: Kimberly Thompson
  HHC 2013: Day 1 Highlights Eddie W. Shore 28 8,160 09-23-2013, 03:22 PM
Last Post: Brad Barton
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 5,796 09-22-2013, 09:39 AM
Last Post: Miguel Toro
  HHC 2013 room numbers David Hayden 2 1,343 09-20-2013, 05:34 PM
Last Post: sjthomas
  FYI: HHC 2013 Programming contests are coming Gene Wright 0 933 09-17-2013, 03:12 PM
Last Post: gene wright
  HHC 2013: One Week To Go Eddie W. Shore 2 1,544 09-13-2013, 05:32 PM
Last Post: Craig Ruff

Forum Jump: