Commit my random junk

[sandbox] / binarypuzzle / gen.py

diff --git a/binarypuzzle/gen.py b/binarypuzzle/gen.py
new file mode 100644 (file)
index 0000000..2ee7395
--- /dev/null
+++ b/binarypuzzle/gen.py
@@ -0,0 +1,117 @@
+import itertools, math, re, sys
+
+size = 4
+
+if size % 2 != 0:
+    raise Exception('Size must be an even number')
+
+fmt = '{{:0{}b}}'.format(size)
+
+valid_rows = []
+
+num_zeroes = size // 2
+
+for i in range(pow(2,size)):
+    row = fmt.format(i)
+
+    if row.count('0') == num_zeroes and ('000' not in row) and ('111' not in row):
+        valid_rows.append(row)
+
+valid_rows_count = len(valid_rows)
+
+print('{} valid rows of {} digits found.'.format(valid_rows_count, size))
+print('This will generate and test {} boards.'.format(math.prod(range(
+    valid_rows_count - size + 1,
+    valid_rows_count + 1,
+))))
+
+decision = input('Proceed with generation? (y/n) ')
+
+while decision.lower() not in ('y', 'n'):
+    decision = input('Proceed with generation? (y/n) ')
+
+if decision == 'n':
+    sys.exit(0)
+
+valid_rows_set = set(valid_rows)
+
+def rotate(board):
+    return tuple(''.join(row) for row in zip(*board))
+
+def all_rows_valid(board):
+    return all((row in valid_rows_set) for row in board)
+
+def all_rows_unique(board):
+    return not any((r0 == r1) for r0, r1 in itertools.combinations(board, 2))
+
+valid_boards = []
+
+for board in itertools.permutations(valid_rows, size):
+    # We know that all the rows are valid and unique but we don't know if the
+    # columns are.
+    board = rotate(board)
+    # Now we know that all the columns are valid and unique but we don't know
+    # if the rows are.
+
+    if all_rows_valid(board) and all_rows_unique(board):
+        valid_boards.append(''.join(board))
+        print('\n'.join(board) + '\n')
+
+print('{} valid boards found.'.format(len(valid_boards)))
+
+decision = input('Proceed with generation? (y/n) ')
+
+while decision.lower() not in ('y', 'n'):
+    decision = input('Proceed with generation? (y/n) ')
+
+if decision == 'n':
+    sys.exit(0)
+
+area = size * size
+filters = { valid_boards[0]: ['.' * area] }
+
+for board_count in range(1, len(valid_boards)):
+    current_board = valid_boards[board_count]
+
+    new_filters = {}
+
+    new_filters[current_board] = set()
+
+    for previous_board in filters:
+        differences = [i for i in range(size) if previous_board[i] != current_board[i]]
+
+        new_filters[previous_board] = set()
+
+        for old_filter in filters[previous_board]:
+            if re.match(old_filter, current_board):
+                for d in differences:
+                    new_filters[previous_board].add(
+                        old_filter[:d] + previous_board[d] + old_filter[d + 1:]
+                    )
+                    new_filters[current_board].add(
+                        old_filter[:d] + current_board[d] + old_filter[d + 1:]
+                    )
+
+            else:
+                new_filters[previous_board].add(old_filter)
+
+    print('Round {} complete, {} filters'.format(board_count, len(new_filters)))
+
+    filters = new_filters
+
+    removed_count = 0
+
+    for b in filters:
+        c = filters[b].copy()
+
+        for f0, f1 in itertools.permutations(c, 2):
+            if re.match(f0, f1):
+                filters[b].remove(f1)
+                removed_count += 1
+
+    print(removed_count)
+
+
+with open('generated.txt', 'w') as gen_file:
+    for f in filters:
+        gen_file.write('\n'.join(f[i:i + size] for i in range(0, area, size)) + '\n\n')