# Texas Programming Contest Problem : Upper Division

Divya Madugula

Greenhorn

Posts: 5

posted 3 years ago

The first step is always to forget about java.

If I handed YOU a piece of paper with "4N, 5E, 2N, 3E, 6S, 8W", how would YOU find the area?

Tell us in English, step by step.

If I handed YOU a piece of paper with "4N, 5E, 2N, 3E, 6S, 8W", how would YOU find the area?

Tell us in English, step by step.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Divya Madugula

Greenhorn

Posts: 5

posted 3 years ago

I really don't know how to proceed ... but if given a pen and a paper i would proceed this way :

//dividing the total area into smaller rectangles and summing up

4N,5E : (N and E would become the height and the width of the rectangle ) area : 4 * 5 = 20

2N,3E : (N and E would become the height and the width of the rectangle ) area : 2 * 3 = 6

6S,8W : subtracting the previously counted 2N,5E dimension (height becomes 6-2 and width becomes 8-5 ) area : 4 * 3 =12

summing up all that we get the area as : 20+6+12 = 38

But the problem here is with subtraction... The dimensions can be irregular ... while putting the things on paper ,

we come to know about the operation we are supposed to do while looking at the figure we assume ..,

but the question is identify merely using dimensions ... that's really twisted and is not easy to deal with !!!

well i was even thinking that i can approach the problem while counting total area of the bigger rectangle and taking away the unwanted regions area ...

its like .. go for the total dimension sum :

N : 4+2 , S: 6, E:5+3, W:8

if (N == S && E==W) then we can proceed // Calculating the total area and removing the unwanted part ... identification of the unwanted region is the main part ... but how do we identify that ???

6 * 8 = 48 // gives total area

5 * 2 = 10 // part to be removed in the above case

actual area accounts to : 48 - 10 = 38

else invalid dimensions : not a proper rectangle

fred rosenberger wrote:The first step is always to forget about java.

If I handed YOU a piece of paper with "4N, 5E, 2N, 3E, 6S, 8W", how would YOU find the area?

Tell us in English, step by step.

I really don't know how to proceed ... but if given a pen and a paper i would proceed this way :

//dividing the total area into smaller rectangles and summing up

4N,5E : (N and E would become the height and the width of the rectangle ) area : 4 * 5 = 20

2N,3E : (N and E would become the height and the width of the rectangle ) area : 2 * 3 = 6

6S,8W : subtracting the previously counted 2N,5E dimension (height becomes 6-2 and width becomes 8-5 ) area : 4 * 3 =12

summing up all that we get the area as : 20+6+12 = 38

But the problem here is with subtraction... The dimensions can be irregular ... while putting the things on paper ,

we come to know about the operation we are supposed to do while looking at the figure we assume ..,

but the question is identify merely using dimensions ... that's really twisted and is not easy to deal with !!!

well i was even thinking that i can approach the problem while counting total area of the bigger rectangle and taking away the unwanted regions area ...

its like .. go for the total dimension sum :

N : 4+2 , S: 6, E:5+3, W:8

if (N == S && E==W) then we can proceed // Calculating the total area and removing the unwanted part ... identification of the unwanted region is the main part ... but how do we identify that ???

6 * 8 = 48 // gives total area

5 * 2 = 10 // part to be removed in the above case

actual area accounts to : 48 - 10 = 38

else invalid dimensions : not a proper rectangle

posted 3 years ago

Hello this problem is interestingly enough there are lots of ways to tackle it. By finding the N==S and W==E approach good I think. But then you need a way to figure out what part to remove.

Given the problem can have a max of 12 pairs or parameters, you should able to figure out which of these parameters are needed to find your removed portion.

Divya Madugula wrote:well i was even thinking that i can approach the problem while counting total area of the bigger rectangle and taking away the unwanted regions area ...

its like .. go for the total dimension sum :

N : 4+2 , S: 6, E:5+3, W:8

if (N == S && E==W) then we can proceed // Calculating the total area and removing the unwanted part ... identification of the unwanted region is the main part ... but how do we identify that ???

6 * 8 = 48 // gives total area

5 * 2 = 10 // part to be removed in the above case

actual area accounts to : 48 - 10 = 38

else invalid dimensions : not a proper rectangle

Hello this problem is interestingly enough there are lots of ways to tackle it. By finding the N==S and W==E approach good I think. But then you need a way to figure out what part to remove.

Given the problem can have a max of 12 pairs or parameters, you should able to figure out which of these parameters are needed to find your removed portion.

posted 3 years ago

Fun problem. I think I might have a go at it myself.

A couple of pointers (and certainly the way I'm going to try):

1. I think you may have more success by first calculating the area of the rectangle that the floor fits in, and then

2. Since the path is circular, you can also simplify the problem by starting from a

I have to admit that I'm not absolutely sure about #1, but it

Winston

Divya Madugula wrote:I really don't know how to proceed ... but if given a pen and a paper i would proceed this way :

//dividing the total area into smaller rectangles and summing up

Fun problem. I think I might have a go at it myself.

A couple of pointers (and certainly the way I'm going to try):

1. I think you may have more success by first calculating the area of the rectangle that the floor fits in, and then

*subtracting*rectangles created by the path.

2. Since the path is circular, you can also simplify the problem by starting from a

*specific*corner (say top-left, or the first Easterly move).

I have to admit that I'm not absolutely sure about #1, but it

*feels*right.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

posted 3 years ago

There is a very very easy way to do this. Given a closed polygon described by the ordered sequence of 'n' points p(0),p(1),p(2).... p(n-1) the area of the polygon is half the sum of the determinant of all the pairs of neighbouring points. The determinant of two point p(r) and p(s) is given by

Note that the point after p(n-1) is p(0).

Note - this works for arbitrary shapes even if convex. If the result is negative just take the absolute value.

Takes about 5 lines of code.

Note that the point after p(n-1) is p(0).

Note - this works for arbitrary shapes even if convex. If the result is negative just take the absolute value.

Takes about 5 lines of code.

posted 3 years ago

:-) I have been censured for posting the detail of the algorithm and not allowing the OP to be misdirected by the earlier posts.

Winston Gutkowski wrote:Richard Tookey wrote:Takes about 5 lines of code.

After you've worked out the coordinates.

Didn't know that formula; but found it now that you've mentioned it. Cheers.

Winston

:-) I have been censured for posting the detail of the algorithm and not allowing the OP to be misdirected by the earlier posts.

posted 3 years ago

Mine, for example...

I suspect all my colleagues were suggesting is that next time you point the poster in the right direction, rather than handing them the answer; for example:

"It looks to me like this is a calculation of the area of a polygon. Why don't you look it up?"

Winston

Richard Tookey wrote:I have been censured for posting the detail of the algorithm and not allowing the OP to be misdirected by the earlier posts.

Mine, for example...

I suspect all my colleagues were suggesting is that next time you point the poster in the right direction, rather than handing them the answer; for example:

"It looks to me like this is a calculation of the area of a polygon. Why don't you look it up?"

Winston

posted 3 years ago

I've been around the same forums as you Winston for a long time and know that that was unusual for you.

Which is what I would have done if it had a chance of standing out from the earlier not so good advice.

I spent an hour today creating a complete solution as detailed in the problem specification. After optimization I reduced it to 18 lines of code. This included a check on the validity of the input string, the parsing of the input string and the computation of the area and the execution of the prime test case.

An interesting point to me is that everyone concentrated on the algorithm to compute the area but parsing the input takes much more code. My advice for that would be to use regular expressions but I will pretty much guarantee that this advice would be ignored since regex are for nerds.

Winston Gutkowski wrote:Richard Tookey wrote:I have been censured for posting the detail of the algorithm and not allowing the OP to be misdirected by the earlier posts.

Mine, for example...

I've been around the same forums as you Winston for a long time and know that that was unusual for you.

I suspect all my colleagues were suggesting is that next time you point the poster in the right direction, rather than handing them the answer; for example:

"It looks to me like this is a calculation of the area of a polygon. Why don't you look it up?"

Winston

Which is what I would have done if it had a chance of standing out from the earlier not so good advice.

I spent an hour today creating a complete solution as detailed in the problem specification. After optimization I reduced it to 18 lines of code. This included a check on the validity of the input string, the parsing of the input string and the computation of the area and the execution of the prime test case.

An interesting point to me is that everyone concentrated on the algorithm to compute the area but parsing the input takes much more code. My advice for that would be to use regular expressions but I will pretty much guarantee that this advice would be ignored since regex are for nerds.