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

    OVER HEAD

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

---

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

---

Thanks Gene,
Dave

Quote:

---

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

---

Quote:

---

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

---

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.

---

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

  OVER HEAD

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

  OVER HEAD

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

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)

---

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.

---

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.

---

Thanks again for the improvements.

Dave

Quote:

---

That's the great thing about this forum.

---

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