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. +
-
RC
» » 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
»
»