summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPeter Wu <peter@lekensteyn.nl>2016-12-12 13:25:13 +0100
committerPeter Wu <peter@lekensteyn.nl>2016-12-12 13:25:13 +0100
commit011c56b0267a51f4c67e93c2fedbaa95782c484b (patch)
tree175d587f8e3a09c23367ddc72f497627d2a16698
parent405549ccd17c5d2709eccef65b1faa228dfad682 (diff)
download2IMF25-AR-011c56b0267a51f4c67e93c2fedbaa95782c484b.tar.gz
ChipDesign: Working solution
-rwxr-xr-xchip_design/generate-chipdesign.py27
-rw-r--r--part1.tex44
2 files changed, 43 insertions, 28 deletions
diff --git a/chip_design/generate-chipdesign.py b/chip_design/generate-chipdesign.py
index 23328ae..ca2f229 100755
--- a/chip_design/generate-chipdesign.py
+++ b/chip_design/generate-chipdesign.py
@@ -113,13 +113,28 @@ for i in range(len(powers), len(all_components)):
# (note: copied from above overlap check with '>='/'<=' -> '='.)
# Additionally: to "hit" the power resource over the X axis, an
# component Y coordinate must be within the power resource.
- # FIXME need to check whether there is an overlap
- pr_range = ' (>= x{j} )'
altpreds += fillin([
- '(and (= (+ y{j} h{j}) y{i})'' )',
- '(and (= (+ x{j} w{j}) x{i})'' )',
- '(and (= y{j} (+ y{i} h{i}))'' )',
- '(and (= x{j} (+ x{i} w{i}))'' )',
+ # Must have matching Y values and X in range.
+ # Assume that power resource is smaller than all others, so we do
+ # not need to check the case where the ends of a component is within
+ # the power component.
+ '(and ',
+ ' (or (= (+ y{j} h{j}) y{i})'
+ ' (= y{j} (+ y{i} h{i})))',
+ ' (or',
+ ' (and (<= x{i} x{j}) (<= x{j} (+ x{i} w{i})))',
+ ' (and (<= x{i} (+ x{j} w{j})) (<= (+ x{j} w{j}) (+ x{i} w{i})))',
+ ' )',
+ ')',
+ # Must have matching X values and Y in range.
+ '(and ',
+ ' (or (= (+ x{j} w{j}) x{i})'
+ ' (= x{j} (+ x{i} w{i})))',
+ ' (or',
+ ' (and (<= y{i} y{j}) (<= y{j} (+ y{i} h{i})))',
+ ' (and (<= y{i} (+ y{j} h{j})) (<= (+ y{j} h{j}) (+ y{i} h{i})))',
+ ' )',
+ ')',
], vars())
preds += ['(or %s)' % ' \n'.join(altpreds)]
diff --git a/part1.tex b/part1.tex
index c0d3ce5..75087b8 100644
--- a/part1.tex
+++ b/part1.tex
@@ -76,30 +76,30 @@ their centres should differ at least 17 in either the x direction or the y direc
%\draw[step=1,gray,very thin] (0, 0) grid (30, 30);
\draw[red,thick] (-.5, -.5) rectangle (30.5, 30.5);
-\draw[draw=red,fill=red] (27.01, 20.01) rectangle (29.99, 23.99);
-\node[align=center] at (28.500000,22.000000) {0\\(27,20)\\(3 x 4)};
-\draw[draw=green,fill=red] (7.01, 11.01) rectangle (9.99, 14.99);
-\node[align=center] at (8.500000,13.000000) {1\\(7,11)\\(3 x 4)};
-\draw[draw=blue] (10.01, 11.01) rectangle (14.99, 14.99);
-\node[align=center] at (12.500000,13.000000) {2\\(10,11)\\(5 x 4)};
-\draw[draw=cyan] (21.01, 21.01) rectangle (26.99, 24.99);
-\node[align=center] at (24.000000,23.000000) {3\\(21,21)\\(6 x 4)};
+\draw[draw=red,fill=red] (14.01, 5.01) rectangle (17.99, 7.99);
+\node[align=center] at (16.000000,6.500000) {0\\(14,5)\\(4 x 3)};
+\draw[draw=green,fill=red] (7.01, 22.01) rectangle (9.99, 25.99);
+\node[align=center] at (8.500000,24.000000) {1\\(7,22)\\(3 x 4)};
+\draw[draw=blue] (14.01, 0.01) rectangle (17.99, 4.99);
+\node[align=center] at (16.000000,2.500000) {2\\(14,0)\\(4 x 5)};
+\draw[draw=cyan] (14.01, 8.01) rectangle (17.99, 13.99);
+\node[align=center] at (16.000000,11.000000) {3\\(14,8)\\(4 x 6)};
\draw[draw=magenta] (10.01, 25.01) rectangle (29.99, 29.99);
\node[align=center] at (20.000000,27.500000) {4\\(10,25)\\(20 x 5)};
-\draw[draw=gray] (7.01, 15.01) rectangle (12.99, 23.99);
-\node[align=center] at (10.000000,19.500000) {5\\(7,15)\\(6 x 9)};
-\draw[draw=darkgray] (0.01, 24.01) rectangle (9.99, 29.99);
-\node[align=center] at (5.000000,27.000000) {6\\(0,24)\\(10 x 6)};
-\draw[draw=lightgray] (12.01, 0.01) rectangle (17.99, 10.99);
-\node[align=center] at (15.000000,5.500000) {7\\(12,0)\\(6 x 11)};
-\draw[draw=brown] (13.01, 15.01) rectangle (19.99, 22.99);
-\node[align=center] at (16.500000,19.000000) {8\\(13,15)\\(7 x 8)};
-\draw[draw=olive] (0.01, 11.01) rectangle (6.99, 22.99);
-\node[align=center] at (3.500000,17.000000) {9\\(0,11)\\(7 x 12)};
-\draw[draw=orange] (2.01, 1.01) rectangle (11.99, 10.99);
-\node[align=center] at (7.000000,6.000000) {10\\(2,1)\\(10 x 10)};
-\draw[draw=pink] (20.01, 0.01) rectangle (29.99, 19.99);
-\node[align=center] at (25.000000,10.000000) {11\\(20,0)\\(10 x 20)};
+\draw[draw=gray] (18.01, 1.01) rectangle (26.99, 6.99);
+\node[align=center] at (22.500000,4.000000) {5\\(18,1)\\(9 x 6)};
+\draw[draw=darkgray] (4.01, 6.01) rectangle (13.99, 11.99);
+\node[align=center] at (9.000000,9.000000) {6\\(4,6)\\(10 x 6)};
+\draw[draw=lightgray] (3.01, 0.01) rectangle (13.99, 5.99);
+\node[align=center] at (8.500000,3.000000) {7\\(3,0)\\(11 x 6)};
+\draw[draw=brown] (0.01, 22.01) rectangle (6.99, 29.99);
+\node[align=center] at (3.500000,26.000000) {8\\(0,22)\\(7 x 8)};
+\draw[draw=olive] (18.01, 7.01) rectangle (29.99, 13.99);
+\node[align=center] at (24.000000,10.500000) {9\\(18,7)\\(12 x 7)};
+\draw[draw=orange] (0.01, 12.01) rectangle (9.99, 21.99);
+\node[align=center] at (5.000000,17.000000) {10\\(0,12)\\(10 x 10)};
+\draw[draw=pink] (10.01, 14.01) rectangle (29.99, 23.99);
+\node[align=center] at (20.000000,19.000000) {11\\(10,14)\\(20 x 10)};
\end{tikzpicture}
\section*{Problem: Job scheduling}