diff options
Diffstat (limited to '06_rect')
| -rw-r--r-- | 06_rect/Makefile | 2 | ||||
| -rw-r--r-- | 06_rect/README | 65 | ||||
| -rw-r--r-- | 06_rect/grade.txt | 13 | ||||
| -rw-r--r-- | 06_rect/rectangle.c | 201 | ||||
| -rw-r--r-- | 06_rect/rectangle_ans.txt | 20 |
5 files changed, 301 insertions, 0 deletions
diff --git a/06_rect/Makefile b/06_rect/Makefile new file mode 100644 index 0000000..b083f98 --- /dev/null +++ b/06_rect/Makefile @@ -0,0 +1,2 @@ +rectangle: rectangle.c + gcc -o rectangle -pedantic -std=gnu99 -Wall -Werror rectangle.c diff --git a/06_rect/README b/06_rect/README new file mode 100644 index 0000000..7309f2c --- /dev/null +++ b/06_rect/README @@ -0,0 +1,65 @@ +For this problem, we will be writing a function which takes +two rectangles, determines the region in which they overlap +(which is also a rectangle), and returns that region. + +Before proceeding, think about what the corner case(s) [no pun intended!] +in this problem might be. + + 1. Open the provided file called "rectangle.c" + + 2. In the "rectangle.c" file, define a struct for rectangles + which has 4 fields: x, y, width, and height. Each of these + fields should be an int. Use typedef so that the typename + "rectangle" refers to your struct. + + 3. One corner we might have to deal with is if the rectangle's + representation is non-standard: if the width or height are + negative. One way to deal with inputs that come in non-standard + formats is to "canonicalize" them---convert them to the standard + (or "canonical") representation. First, write the function + + rectangle canonicalize(rectangle r); + + which takes a rectangle, and "fixes" its representation + by ensuring that the width and height are non-negative (and + appropriately adjusting the x and/or y co-ordinate). That is, + if your canonicalize function were passed a rectangle with + x=3, y=2, width=-2, height=4 + then it should return a rectangle with + x=1, y=2, width=2, height=4 + as these both describe the same rectangle, but the later is + in a canonical representation. + + It may be a good idea to stop and test this function + before proceeding. Compile and run your code. + The main function we have provided should be useful, + as it canonicalizes the rectangles it prints. + + 4. Now, write the function + rectangle intersection(rectangle r1, rectangle r2) + which takes two rectangles (r1, and r2), and returns + the rectangle representing the intersection of the two. + + Note that there is a corner case where the correct answer + is "no intersection". We have not learned how to represent + "no such thing" yet, but we will consider a rectangle with + both width and height equal to 0 to mean "no such rectangle". + + We will consider a rectangle to have one (but not the other) + of width or height equal to 0 to be an appropriate answer + when rectangles share an edge but do not overlap. For example, + x=0,y=0,width=1, height=1 + and + x=-1,y=1,width=3,height=2 + Should result in the "rectangle" + x=0,y=1,width=1,height=0 + 5. We have provided a main function which tests your code, + as well as correct output (rectangle_ans.txt) to diff against. + + 6. Submit your code + +Hint: + Do Step 1 (work an example yourself) four or five times. + Draw a variety of different ways that rectangles can overlap. + Use these to help you think abou the general algorithm for how + to determine their overlapping region. diff --git a/06_rect/grade.txt b/06_rect/grade.txt new file mode 100644 index 0000000..c82efe8 --- /dev/null +++ b/06_rect/grade.txt @@ -0,0 +1,13 @@ +Grading at Sun 28 Nov 2021 08:50:44 PM UTC +Attempting to compile rectangle.c +Tring to run rectangle +Your file matched the expected output +removing your main() and replacing it with out own to run more tests... +################################################# +testcase1: +testcase1 passed +################################################# +testcase2: +testcase2 passed + +Overall Grade: A diff --git a/06_rect/rectangle.c b/06_rect/rectangle.c new file mode 100644 index 0000000..9d3708e --- /dev/null +++ b/06_rect/rectangle.c @@ -0,0 +1,201 @@ +#include <stdio.h> +#include <stdlib.h> +//I've provided "min" and "max" functions in +//case they are useful to you +int min (int a, int b) { + if (a < b) { + return a; + } + return b; +} +int max (int a, int b) { + if (a > b) { + return a; + } + return b; +} + +//Declare your rectangle structure here! +typedef struct rectangle_t { + int x; + int y; + int width; + int height; +} rectangle; + +rectangle canonicalize(rectangle r) { + //WRITE THIS FUNCTION + if (r.width < 0) { + r.x = r.x + r.width; + r.width = r.width * (-1); + } + if (r.height < 0) { + r.y = r.y + r.height; + r.height = r.height * (-1); + } + return r; +} +rectangle left_rect(rectangle r1, rectangle r2) { + if (r1.x < r2.x){ + return r1; + } else { + return r2; + } +} + +rectangle lower_rect(rectangle r1, rectangle r2) { + if (r1.y < r2.y){ + return r1; + } else { + return r2; + } +} + +rectangle intersection(rectangle r1, rectangle r2) { + //WRITE THIS FUNCTION + r1 = canonicalize(r1); + r2 = canonicalize(r2); + rectangle ans; + ans.x = max(r1.x, r2.x); + ans.y = max(r1.y, r2.y); + + // Find the width + // find the rectangle with the smallest x + rectangle left = left_rect(r1, r2); + if (ans.x <= left.x + left.width){ + ans.width = min(r1.x + r1.width, r2.x + r2.width) - ans.x; + } else { + ans.width = 0; + ans.height = 0; + return ans; + } + + rectangle lower = lower_rect(r1, r2); + if (ans.y <= lower.y + lower.height){ + ans.height = min(r1.y + r1.height, r2.y + r2.height) - ans.y; + } else { + ans.height = 0; + ans.width = 0; + return ans; + } + return ans; +} + +//You should not need to modify any code below this line +void printRectangle(rectangle r) { + r = canonicalize(r); + if (r.width == 0 && r.height == 0) { + printf("<empty>\n"); + } + else { + printf("(%d,%d) to (%d,%d)\n", r.x, r.y, + r.x + r.width, r.y + r.height); + } +} + +int main (void) { + rectangle r1; + rectangle r2; + rectangle r3; + rectangle r4; + + r1.x = 2; + r1.y = 3; + r1.width = 5; + r1.height = 6; + printf("r1 is "); + printRectangle(r1); + + r2.x = 4; + r2.y = 5; + r2.width = -5; + r2.height = -7; + printf("r2 is "); + printRectangle(r2); + + r3.x = -2; + r3.y = 7; + r3.width = 7; + r3.height = -10; + printf("r3 is "); + printRectangle(r3); + + r4.x = 0; + r4.y = 7; + r4.width = -4; + r4.height = 2; + printf("r4 is "); + printRectangle(r4); + + //test everything with r1 + rectangle i = intersection(r1,r1); + printf("intersection(r1,r1): "); + printRectangle(i); + + i = intersection(r1,r2); + printf("intersection(r1,r2): "); + printRectangle(i); + + i = intersection(r1,r3); + printf("intersection(r1,r3): "); + printRectangle(i); + + i = intersection(r1,r4); + printf("intersection(r1,r4): "); + printRectangle(i); + + //test everything with r2 + i = intersection(r2,r1); + printf("intersection(r2,r1): "); + printRectangle(i); + + i = intersection(r2,r2); + printf("intersection(r2,r2): "); + printRectangle(i); + + i = intersection(r2,r3); + printf("intersection(r2,r3): "); + printRectangle(i); + + i = intersection(r2,r4); + printf("intersection(r2,r4): "); + printRectangle(i); + + //test everything with r3 + i = intersection(r3,r1); + printf("intersection(r3,r1): "); + printRectangle(i); + + i = intersection(r3,r2); + printf("intersection(r3,r2): "); + printRectangle(i); + + i = intersection(r3,r3); + printf("intersection(r3,r3): "); + printRectangle(i); + + i = intersection(r3,r4); + printf("intersection(r3,r4): "); + printRectangle(i); + + //test everything with r4 + i = intersection(r4,r1); + printf("intersection(r4,r1): "); + printRectangle(i); + + i = intersection(r4,r2); + printf("intersection(r4,r2): "); + printRectangle(i); + + i = intersection(r4,r3); + printf("intersection(r4,r3): "); + printRectangle(i); + + i = intersection(r4,r4); + printf("intersection(r4,r4): "); + printRectangle(i); + + + return EXIT_SUCCESS; + +} diff --git a/06_rect/rectangle_ans.txt b/06_rect/rectangle_ans.txt new file mode 100644 index 0000000..0b1b88f --- /dev/null +++ b/06_rect/rectangle_ans.txt @@ -0,0 +1,20 @@ +r1 is (2,3) to (7,9) +r2 is (-1,-2) to (4,5) +r3 is (-2,-3) to (5,7) +r4 is (-4,7) to (0,9) +intersection(r1,r1): (2,3) to (7,9) +intersection(r1,r2): (2,3) to (4,5) +intersection(r1,r3): (2,3) to (5,7) +intersection(r1,r4): <empty> +intersection(r2,r1): (2,3) to (4,5) +intersection(r2,r2): (-1,-2) to (4,5) +intersection(r2,r3): (-1,-2) to (4,5) +intersection(r2,r4): <empty> +intersection(r3,r1): (2,3) to (5,7) +intersection(r3,r2): (-1,-2) to (4,5) +intersection(r3,r3): (-2,-3) to (5,7) +intersection(r3,r4): (-2,7) to (0,7) +intersection(r4,r1): <empty> +intersection(r4,r2): <empty> +intersection(r4,r3): (-2,7) to (0,7) +intersection(r4,r4): (-4,7) to (0,9) |