From 011c56b0267a51f4c67e93c2fedbaa95782c484b Mon Sep 17 00:00:00 2001 From: Peter Wu Date: Mon, 12 Dec 2016 13:25:13 +0100 Subject: ChipDesign: Working solution --- chip_design/generate-chipdesign.py | 27 +++++++++++++++++------ part1.tex | 44 +++++++++++++++++++------------------- 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} -- cgit v1.2.1