| from collections import namedtuple |
| import pprint |
| from enum import Enum |
| |
| |
| class Direction(Enum): |
| NO_SIDE = 0 |
| LEFT = 1 |
| RIGHT = 2 |
| TOP = 3 |
| BOTTOM = 4 |
| RIGHT_LEFT = 5 |
| RIGHT_BOTTOM = 6 |
| RIGHT_BOTTOM_LEFT = 7 |
| TOP_RIGHT = 8 |
| TOP_BOTTOM = 9 |
| TOP_LEFT = 10 |
| TOP_RIGHT_BOTTOM = 11 |
| TOP_RIGHT_LEFT = 12 |
| TOP_BOTTOM_LEFT = 13 |
| TOP_RIGHT_BOTTOM_LEFT = 14 |
| BOTTOM_LEFT = 15 |
| |
| |
| # Track (aka Channel) is a wire that runs from one position to another along X or Y axis |
| Track = namedtuple('Track', 'direction x_low x_high y_low y_high') |
| |
| |
| def print_tracks(tracks): |
| pprint.pprint(tracks) |
| |
| |
| def make_tracks(xs, ys, points, grid_width=None, grid_height=None): |
| """ Give a list of xs columns and ys rows and points, return a list of |
| Track's and connections between the tracks. |
| |
| An assert will fail if each point in the point list is not covered by |
| a column in xs or a row in ys. |
| |
| Connections will be models as indicies into the track list. |
| |
| Return: |
| [Track], [(index into track list, index into track list)] |
| |
| >>> pos = [ |
| ... (1,1), (3,1), |
| ... (1,2), (2,2), (3,2), |
| ... (1,3), (3,3), |
| ... (1,4), (2,4), (3,4), |
| ... (1,5), (3,5), |
| ... ] |
| >>> xs = [1, 3] |
| >>> ys = [2, 4] |
| >>> tracks, connections = make_tracks(xs, ys, pos) |
| >>> print_tracks(tracks) |
| [Track(direction='Y', x_low=1, x_high=1, y_low=1, y_high=5), |
| Track(direction='Y', x_low=3, x_high=3, y_low=1, y_high=5), |
| Track(direction='X', x_low=1, x_high=3, y_low=2, y_high=2), |
| Track(direction='X', x_low=1, x_high=3, y_low=4, y_high=4)] |
| >>> print(sorted(connections)) |
| [(2, 0), (2, 1), (3, 0)] |
| |
| >>> pos = [ |
| ... (68,48), (69,48), |
| ... (68,49), (69,49), |
| ... (69,50), |
| ... (69,51), |
| ... (69,52), |
| ... (69,53), (70,53), (71,53), (72,53)] |
| >>> xs = [68, 69] |
| >>> ys = [53] |
| >>> tracks, connections = make_tracks(xs, ys, pos) |
| >>> print_tracks(tracks) |
| [Track(direction='Y', x_low=68, x_high=68, y_low=48, y_high=53), |
| Track(direction='Y', x_low=69, x_high=69, y_low=48, y_high=53), |
| Track(direction='X', x_low=68, x_high=72, y_low=53, y_high=53)] |
| >>> print(connections) |
| [(2, 0), (2, 1)] |
| |
| |
| """ |
| x_set = set(xs) |
| y_set = set(ys) |
| |
| for x, y in points: |
| if x > 0: |
| in_x_set = x in x_set or x - 1 in x_set, (x, x_set) |
| else: |
| in_x_set = x in x_set |
| |
| if y > 0: |
| in_y_set = y in y_set or y - 1 in y_set, (y, y_set) |
| else: |
| in_y_set = y in y_set |
| |
| assert in_x_set or in_y_set |
| |
| all_xs, all_ys = zip(*points) |
| x_min = min(all_xs) |
| x_max = max(all_xs) |
| y_min = min(all_ys) |
| y_max = max(all_ys) |
| |
| tracks = [] |
| x_tracks = [] |
| y_tracks = [] |
| for x in xs: |
| y_low = max(y_min, 1) |
| y_high = y_max |
| if grid_height is not None: |
| y_high = min(y_max, grid_height - 2) |
| |
| tracks.append( |
| Track( |
| direction='Y', |
| x_low=x, |
| x_high=x, |
| y_low=y_low, |
| y_high=y_high, |
| ) |
| ) |
| y_tracks.append(len(tracks) - 1) |
| |
| for y in ys: |
| x_low = max(x_min, 1) |
| x_high = x_max |
| if grid_width is not None: |
| x_high = min(x_high, grid_width - 2) |
| |
| tracks.append( |
| Track( |
| direction='X', |
| x_low=x_low, |
| x_high=x_high, |
| y_low=y, |
| y_high=y, |
| ) |
| ) |
| x_tracks.append(len(tracks) - 1) |
| |
| if len(tracks) == 1: |
| return tracks, [] |
| |
| # If there is more than 1 track, there must be a track in each dimension |
| assert len(xs) >= 1 and len(ys) >= 1 |
| |
| connections = set() |
| |
| # Always just connect X tracks to the first Y track, and Y tracks to the |
| # first X tracks. |
| # |
| # To dedup connections, the x channel track will appear first in the |
| # connection list. |
| for idx, track in enumerate(tracks): |
| if track.direction == 'X': |
| connections.add((idx, y_tracks[0])) |
| else: |
| assert track.direction == 'Y' |
| connections.add((x_tracks[0], idx)) |
| |
| return tracks, list(connections) |
| |
| |
| class Tracks(object): |
| """Tracks groups tracks and their connections (AKA Node). |
| """ |
| |
| def __init__(self, tracks, track_connections): |
| self.tracks = tracks |
| self.track_connections = track_connections |
| |
| self.track_cache = {} |
| |
| def verify_tracks(self): |
| """ Verify that all tracks are connected to all other tracks. """ |
| track_connections = {} |
| |
| for idx, _ in enumerate(self.tracks): |
| track_connections[idx] = set((idx, )) |
| |
| for conn_a, conn_b in self.track_connections: |
| if track_connections[conn_a] is track_connections[conn_b]: |
| continue |
| |
| assert self.tracks[conn_a].direction != self.tracks[conn_b |
| ].direction |
| |
| track_connections[conn_a] |= track_connections[conn_b] |
| |
| for track_idx in track_connections[conn_a]: |
| track_connections[track_idx] = track_connections[conn_a] |
| |
| assert len( |
| set(id(s) for s in track_connections.values()) |
| ) == 1, track_connections |
| |
| def is_wire_adjacent_to_track(self, idx, coord): |
| """returns direction if wire at coord is adjacent to track at index idx |
| returns NO_SIDE if not adjacent. |
| """ |
| track = self.tracks[idx] |
| wire_x, wire_y = coord |
| |
| if track.direction == 'X': |
| pin_top = track.y_low == wire_y |
| pin_bottom = track.y_low == wire_y - 1 |
| adjacent_channel = (pin_top or pin_bottom) and ( |
| track.x_low <= wire_x and wire_x <= track.x_high |
| ) |
| |
| if adjacent_channel: |
| if pin_top: |
| return Direction.TOP |
| elif pin_bottom: |
| return Direction.BOTTOM |
| else: |
| assert False, (coord, track) |
| else: |
| return Direction.NO_SIDE |
| |
| elif track.direction == 'Y': |
| pin_right = track.x_low == wire_x |
| pin_left = track.x_low == wire_x - 1 |
| adjacent_channel = (pin_right or pin_left) and ( |
| track.y_low <= wire_y and wire_y <= track.y_high |
| ) |
| |
| if adjacent_channel: |
| if pin_right: |
| return Direction.RIGHT |
| elif pin_left: |
| return Direction.LEFT |
| else: |
| assert False, (coord, track) |
| else: |
| return Direction.NO_SIDE |
| else: |
| assert False, track |
| |
| def get_tracks_for_wire_at_coord(self, coord): |
| """Returns map of direction to track indicies for valid connections. |
| |
| There may be multiple connections to tracks at a particular coordinate, |
| this method only returns a possible connection in each direction to |
| this track. |
| |
| Parameters |
| ---------- |
| coord : (int, int) |
| Coordinate to attach to track |
| |
| Returns |
| ------- |
| dict(Direction -> int) |
| Dictionary of pin direction to track index. |
| |
| """ |
| |
| if coord in self.track_cache: |
| return self.track_cache[coord] |
| else: |
| wire_x, wire_y = coord |
| |
| conns = {} |
| for idx, track in enumerate(self.tracks): |
| pin_dir = self.is_wire_adjacent_to_track(idx, coord) |
| if pin_dir != Direction.NO_SIDE: |
| conns[pin_dir] = idx |
| |
| self.track_cache[coord] = conns |
| return conns |
| |
| |
| def main(): |
| import doctest |
| |
| print('Doctest begin') |
| failure_count, test_count = doctest.testmod(optionflags=doctest.ELLIPSIS) |
| assert test_count > 0 |
| assert failure_count == 0, "Doctests failed!" |
| print('Doctest end') |
| |
| |
| if __name__ == "__main__": |
| main() |
