summaryrefslogtreecommitdiff
path: root/06_rect
diff options
context:
space:
mode:
authorHaidong Ji2022-04-15 15:51:30 -0500
committerHaidong Ji2022-04-15 15:51:30 -0500
commit442a49ad5a48d417345959b903ae6a6d32d55759 (patch)
treec7127bb497e5e439018b1915e0136eec2c9cb124 /06_rect
Great C programming funHEADmaster
Excellent fundamentals and displine training, many tools and techniques exercises: gdb, emacs, valgrind, git
Diffstat (limited to '06_rect')
-rw-r--r--06_rect/Makefile2
-rw-r--r--06_rect/README65
-rw-r--r--06_rect/grade.txt13
-rw-r--r--06_rect/rectangle.c201
-rw-r--r--06_rect/rectangle_ans.txt20
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)