# HP Forums

Full Version: HHC 2008 Programming Contest revisited
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

While surfing around the other day, I came across the [link:http://home.comcast.net/~genela/HHC2008 Programming%20Contest.pdf]HHC 2008 Programming Contest[/link] and This thread discussing solutions.

I wrote my own solution before checking how others had done it. Mine turned out to be similar to Gjermund Skailand's: convert the points to (row,position) format, expressed as a complex number, and then see if the points match one of the required shapes. There's no point in showing that implementation since I think Gjermund's is better :).

This morning I thought of a slight modification which is shown below. After converting to row,column format, I normalize the shape so that the length of P2-P1 is 1.0 and P1 is at (0,0). Once the shape is thus normalized, I can compare it to the 6 normalized solutions. The main program is thus quite small. A trivial optimization would be to remove the first before comparing to the solution set since normalizing guarantees that the first point is (0,0)

This solves the test set as given in Egan's "PROBS" program and timed using TEVAL on my 50g in 2.75 seconds. It is still slower than Egan's final solution.

```«
@ Convert to row,column format
«  n «
n DUP
1. -
2. *
0.25 +
ƒ 0.5 -
IP  @ That's the row number.
@ Save it and get the starting value for the row
SWAP
OVER
DUP 1. +
*
2. /
1. +
-
RC
» »
 RC «
@ MAIN PROGRAM STARTS HERE
SORT          @ Sort points by position
RC DOLIST     @ convert to (row,col) format
DUP 2. GET
-             @ P2-P1
ABS /         @ Normalize length
DUP HEAD -    @ Normalize position
@ List of the normalized shapes
{ { (0. 0.) (1. 0.) (1. 1.) }
{ (0. 0.) (0. 1.) (1. 1.) }
{ (0. 0.) (1. 0.) (1. 1.) (2. 1.) }
{ (0. 0.) (0. 1.) (1. 0.) (1. 1.) }
{ (0. 0.) (0. 1.) (1. 1.) (1. 2.) }
{ (0. 0.) (0. 1.) (1. 0.) (1. 2.) (2. 1.) (2. 2.) }
}
SWAP POS      @ Position of shape in the list
IF DUP 0. ==
THEN
DROP
"ERROR"
ELSE
{"TRIANGLE" "TRIANGLE"
"PARALLELOGRAM" "PARALLELOGRAM"
"PARALLELOGRAM"
"HEXAGON"
}
SWAP GET
END
»
»
```

Wonderful solution!

I have been very happy with the reception the contest received here at the forum.

My only real regret is that I fear this contest was way too involved to be done AT the conference.

Perhaps this year I'll have two contests... one for actual conference attendees and the other for our virtual attendees here.

Of course, that would mean I would have to have a "door prize" of some sort for the fastest / best solution within a period of time.

I think I can work that out. :-)

Quote:
Wonderful solution!

Thanks. It's a wonderful little problem!
Quote:
I have been very happy with the reception the contest received here at the forum.

My only real regret is that I fear this contest was way too involved to be done AT the conference.

Perhaps this year I'll have two contests... one for actual conference attendees and the other for our virtual attendees here.

I think it's a double edged sword. The problem received a lot of attention here because it's fairly interesting and difficult and can be attacked in several different ways. But those same qualities may have made it too hard to tackle during the limited time available at the conference.

I wasn't at the conference but as I recall from reading the schedule, attendees basically had Saturday night to write their code. So I'd think that the contest should aim to be solvable in about 3 hours (gotta let people get some sleep ya know!) :)

Here's something to consider: ask a few trusted people who wont' attend the conference to preview the problem and attempt to solve it in, say 3 to 6 hours. They could send you their solution, the time it took to solve and any comments on the problem. That might help you gauge the difficulty of the problem.

Quote:
Of course, that would mean I would have to have a "door prize" of some sort for the fastest / best solution within a period of time.

I think I can work that out. :-)

Heck, I'd chip in \$10 to help sweeten the pot. Anyone else?

Thanks Gene,
Dave

Quote:
My only real regret is that I fear this contest was way too involved to be done AT the conference.

I see no reason why you could not have announced the contest 7 days before the conference and then have collected the results during the conference. That would allow more time for more people to work on more interesting puzzles. I would recommend not posting publicly however to avoid spoilers. I would announce, then privately send out a PDF to interested individuals. This will also work for a contest that may involve a free-bee given to conference attendees. At least the problem is in their minds. And, I believe that you'll get more participants.
Quote:
Perhaps this year I'll have two contests... one for actual conference attendees and the other for our virtual attendees here.

That sounds like a lot of work for you. I'd stick to one.
Quote:
Of course, that would mean I would have to have a "door prize" of some sort for the fastest / best solution within a period of time.

Wasn't that the case? Fastest solution in 24 hours? Personally I like days to think about a problem. It allows me to explore many avenues and make multiple discoveries without the stress of having to produce my best in a short amount of time.

Your solution is really beautiful! It made me have a closer look at the contest. Unfortunately I didn't have the time when it was posted. May I suggest some improvements?

1. To get the row number the quadratic equation doesn't have to be solved exactly since only the integer part is used. Therefore it's enough to use this formula:

```r = ip(sqrt(2n) - 0.5)
```

2. The absolute value of the column isn't important since only the difference to the head counts. Thus adding 1 can be eliminated.

3. Using n in the procedure RC saves a DUP and a SWAP. I assume this is faster but I might be wrong.

4. Since RC is used only once the procedure can be inlined. Here again it's just my assumption that this is faster than using a local variable. I wanted to remove the other local variable n as well since it wasn't really used. But DOLIST needs that.

5. Skip (0 0) as you suggested.

6. I've added "ERROR" to the list of messages. Don't know whether this makes it any faster. At least it's shorter.

Here's what I got:

```%%HP: T(3)A(D)F(.);
\<<
SORT          @ Sort points by position
\<<  \-> n    @ Convert n to (row,col) format
\<<
n
2 *
\v/ 0.5 -
IP  @ That's the row number.
@ Save it and get the starting value for the row
n
OVER
DUP 1 +
*
2 /
-
R\->C
\>>
\>> DOLIST    @ Convert points to (row,col) format
DUP 2 GET
-             @ P2-P1
ABS /         @ Normalize length
DUP HEAD -    @ Normalize position
TAIL          @ Skip (0 0)
@ List of messages
{
"ERROR"
"TRIANGLE"
"TRIANGLE"
"PARALLELOGRAM"
"PARALLELOGRAM"
"PARALLELOGRAM"
"HEXAGON"
}
@ List of the normalized shapes
{
{ (1 0) (1 1) }
{ (0 1) (1 1) }
{ (1 0) (1 1) (2 1) }
{ (0 1) (1 0) (1 1) }
{ (0 1) (1 1) (1 2) }
{ (0 1) (1 0) (1 2) (2 1) (2 2) }
}
ROT POS      @ Position of shape in the list
1 + GET      @ Return message
\>>
```

And then I was thinking whether we could also get rid of the division by 2 when calculating the column.
This changes the list of normalized shapes but my tests suggest that it makes it indeed a little faster:

```%%HP: T(3)A(D)F(.);
\<<
SORT          @ Sort points by position
\<<  \-> n    @ Convert n to (row,col) format
\<<
n
2 *
DUP
\v/ .5 -
IP  @ That's the row number.
@ Save it and get the starting value for the row
SWAP
OVER
DUP 1 +
*
-
R\->C
\>>
\>> DOLIST    @ Convert points to (row,col) format
DUP 2 GET
-             @ P2-P1
ABS /         @ Normalize length
DUP HEAD -    @ Normalize position
TAIL          @ Skip (0 0)
@ List of messages
{
"ERROR"
"TRIANGLE"
"TRIANGLE"
"PARALLELOGRAM"
"PARALLELOGRAM"
"PARALLELOGRAM"
"HEXAGON"
}
@ List of the normalized shapes
{
{ (1 0) (1  2) }
{ (0 1) (.5 1) }
{ (1 0) (1  2) (2  2) }
{ (0 1) (.5 0) (.5 1) }
{ (0 1) (.5 1) (.5 2) }
{ (0 1) (.5 0) (.5 2) (1 1) (1 2) }
}
ROT POS      @ Position of shape in the list
1 + GET      @ Return message
\>>
```

I used a 48gx for timing (Egan's method):

```Your original program:   4.45s - 4.77s
My first solution:       4.15s - 4.47s
My second solution:      4.09s - 4.38s
```
Though the intervalls are overlapping they suggest that the last solution is the fastest.

Edited: 29 Mar 2009, 8:45 a.m.

Quote:
Your solution is really beautiful! It made me have a closer look at the contest. Unfortunately I didn't have the time when it was posted. May I suggest some improvements?

Quote:
To get the row number the quadratic equation doesn't have to be solved exactly since only the integer part is used. Therefore it's enough to use this formula:

```r = ip(sqrt(2n) - 0.5)
```

Good point. Thanks. In a later version, I used the fractional part of the result to quickly get the column number. I'll have to experiment with this to see which way is faster overall.

Quote:
• The absolute value of the column isn't important since only the difference to the head counts. Thus adding 1 can be eliminated.

• Using n in the procedure RC saves a DUP and a SWAP. I assume this is faster but I might be wrong.

• Since RC is used only once the procedure can be inlined. Here again it's just my assumption that this is faster than using a local variable. I wanted to remove the other local variable n as well since it wasn't really used. But DOLIST needs that.

• Whoops! Thank you for pointing out these inefficiencies. It always amazes me how another set of eyeballs looking at some code can improve it.

Creating RC has a local variable came from my original solution which I didn't post here. I used it in a couple of places in that version and when I came up with the one that I posted, it never even occurred to me to check whether I was calling it multiple times.

On the other hand, I suspect that in-lining the function will make only a small difference in performance since accessing a local variable is very fast. Hmmm... Thinking about this more, it might be fastest to have the file put RC in a global. That way the time requires to skip over the function gets pushed to "file load time" instead of run time, and the goal is to reduce run time.

Quote:
• Skip (0 0) as you suggested.

• I've added "ERROR" to the list of messages. Don't know whether this makes it any faster. At least it's shorter.

• That last change is downright embarrassing :) I should have thought of that one myself. It's much cleaner.

Thanks again for the improvements.

Dave

Quote:

I fully agree!

Quote:
In a later version, I used the fractional part of the result to quickly get the column number. I'll have to experiment with this to see which way is faster overall.

Sounds interesting. Let us know your results.

Quote:
it might be fastest to have the file put RC in a global.

Without knowing the details I still assume in-lining is faster since you don't need the time for the look-up of the variable.

However I agree that you won't gain much since it's done only once. Whatever is done in the DOLIST-loop weights much more.

Quote:
I should have thought of that one myself.

I was only inspired by your ideas.

Kind regards

Thomas