GitOnUp · January 25, 2020 07:25 · Jan 25, 2020
diff --git a/crossword.py b/crossword.py
@@ -0,0 +1,171 @@
+from collections import namedtuple
+
+MIN_WORD = 3
+LETTER_TILE = "."
+BLOCK_TILE = "#"
+
+
+Point = namedtuple('Point', ['x', 'y'])
+
+
+class State:
+    def __init__(self, board, loc, tile, number, acrosses, downs):
+        self.board = board
+        self.loc = loc
+        self.tile = tile
+        self.number = number
+        self.acrosses = acrosses
+        self.downs = downs
+
+    def at(self, x, y):
+        if x == self.loc.x and y == self.loc.y:
+            return self.tile
+        else:
+            return self.board.at(x, y)
+
+    def advance_tile(self):
+        self.clear_numbers()
+        if self.tile is None:
+            self.tile = LETTER_TILE
+        elif self.tile == LETTER_TILE:
+            self.tile = BLOCK_TILE
+        else:
+            return None
+        return self.tile
+
+    def clear_numbers(self):
+        if self.number is None:
+            return
+        if len(self.acrosses) > 0 and self.acrosses[-1] == self.number:
+            self.acrosses.pop()
+        if len(self.downs) > 0 and self.downs[-1] == self.number:
+            self.downs.pop()
+        self.number = None
+
+    def next_state(self):
+        next_loc = self.board.next_loc(self.loc)
+        new_board = self.board.copy()
+        new_board.set(self.loc.x, self.loc.y, self.tile)
+        return State(new_board, next_loc, None, None, self.acrosses, self.downs)
+
+    def next_number(self):
+        across_max = self.acrosses[-1] if len(self.acrosses) > 0 else 0
+        downs_max = self.downs[-1] if len(self.downs) > 0 else 0
+        return max(across_max, downs_max) + 1
+
+
+class Board:
+    def __init__(self, side_length):
+        self.buffer = []
+        for _ in range(side_length):
+            self.buffer.append([None] * side_length)
+        self.side_length = side_length
+
+    def at(self, x, y):
+        if self.side_length <= x or x < 0:
+            return None
+        if self.side_length <= y or y < 0:
+            return None
+        return self.buffer[y][x]
+
+    def set(self, x, y, val):
+        self.buffer[y][x] = val
+
+    def print_board(self):
+        for row in self.buffer:
+            for column in row:
+                print(column, end='')
+            print()
+
+    def next_loc(self, loc):
+        x, y = loc
+        x += 1
+        if x >= self.side_length:
+            x = 0
+            y += 1
+        if y >= self.side_length:
+            return None
+        return Point(x, y)
+
+    def copy(self):
+        board = Board(self.side_length)
+        for i in range(len(board.buffer)):
+            board.buffer[i] = self.buffer[i][:]
+        return board
+
+
+def build(side_length, acrosses, downs):
+    states = [State(Board(side_length), Point(0, 0), None, None, [], [])]
+    while len(states):
+        state = states[-1]
+        while True:
+            tile = state.advance_tile()
+            if tile is None:
+                states.pop()
+                break
+
+            if tile == LETTER_TILE:
+                # check against expected numbering and word length
+                next_number = state.next_number()
+                if state.at(state.loc.x - 1, state.loc.y) in [None, BLOCK_TILE]:
+                    if len(state.acrosses) >= len(acrosses):
+                        continue
+                    if acrosses[len(state.acrosses)] != next_number:
+                        continue
+                    if side_length - MIN_WORD < state.loc.x:
+                        continue
+                    state.number = next_number
+                    state.acrosses.append(next_number)
+                if state.at(state.loc.x, state.loc.y - 1) in [None, BLOCK_TILE]:
+                    if len(state.downs) >= len(downs):
+                        continue
+                    if downs[len(state.downs)] != next_number:
+                        continue
+                    if side_length - MIN_WORD < state.loc.y:
+                        continue
+                    state.number = next_number
+                    state.downs.append(next_number)
+            else:
+                # check for lengths of words above and to the left
+                letter_tiles = 0
+                for x in range(state.loc.x - 1, -1, -1):
+                    if state.at(x, state.loc.y) == LETTER_TILE:
+                        letter_tiles += 1
+                    else:
+                        break
+                if MIN_WORD > letter_tiles > 0:
+                    continue
+                letter_tiles = 0
+                for y in range(state.loc.y - 1, -1, -1):
+                    if state.at(state.loc.x, y) == LETTER_TILE:
+                        letter_tiles += 1
+                    else:
+                        break
+                if MIN_WORD > letter_tiles > 0:
+                    continue
+
+            # enforce 180 rotation
+            flattened_loc = (state.loc.y * side_length) + state.loc.x
+            midpoint = (side_length * side_length) // 2
+            if flattened_loc > midpoint:
+                previous_flattened_loc = midpoint - (flattened_loc - midpoint)
+                if state.at(previous_flattened_loc % side_length, previous_flattened_loc // side_length) != state.tile:
+                    continue
+
+            # get next state, and check if we're done
+            next_state = state.next_state()
+            if next_state.loc is None:
+                if next_state.acrosses != acrosses or next_state.downs != downs:
+                    continue
+                next_state.board.print_board()
+                return
+            states.append(next_state)
+            state = next_state
+
+
+if __name__ == "__main__":
+    side_length = int(input('side-length: '))
+    acrosses = [int(x) for x in input('across numbers (comma separated): ').split(',')]
+    downs = [int(y) for y in input('down numbers (comma separated): ').split(',')]
+
+    build(side_length, acrosses, downs)