code.kerkeslager.com Git - sandbox/blob - binarypuzzle/gen.py

   1 import itertools, math, re, sys
   2
   3 size = 4
   4
   5 if size % 2 != 0:
   6     raise Exception('Size must be an even number')
   7
   8 fmt = '{{:0{}b}}'.format(size)
   9
  10 valid_rows = []
  11
  12 num_zeroes = size // 2
  13
  14 for i in range(pow(2,size)):
  15     row = fmt.format(i)
  16
  17     if row.count('0') == num_zeroes and ('000' not in row) and ('111' not in row):
  18         valid_rows.append(row)
  19
  20 valid_rows_count = len(valid_rows)
  21
  22 print('{} valid rows of {} digits found.'.format(valid_rows_count, size))
  23 print('This will generate and test {} boards.'.format(math.prod(range(
  24     valid_rows_count - size + 1,
  25     valid_rows_count + 1,
  26 ))))
  27
  28 decision = input('Proceed with generation? (y/n) ')
  29
  30 while decision.lower() not in ('y', 'n'):
  31     decision = input('Proceed with generation? (y/n) ')
  32
  33 if decision == 'n':
  34     sys.exit(0)
  35
  36 valid_rows_set = set(valid_rows)
  37
  38 def rotate(board):
  39     return tuple(''.join(row) for row in zip(*board))
  40
  41 def all_rows_valid(board):
  42     return all((row in valid_rows_set) for row in board)
  43
  44 def all_rows_unique(board):
  45     return not any((r0 == r1) for r0, r1 in itertools.combinations(board, 2))
  46
  47 valid_boards = []
  48
  49 for board in itertools.permutations(valid_rows, size):
  50     # We know that all the rows are valid and unique but we don't know if the
  51     # columns are.
  52     board = rotate(board)
  53     # Now we know that all the columns are valid and unique but we don't know
  54     # if the rows are.
  55
  56     if all_rows_valid(board) and all_rows_unique(board):
  57         valid_boards.append(''.join(board))
  58         print('\n'.join(board) + '\n')
  59
  60 print('{} valid boards found.'.format(len(valid_boards)))
  61
  62 decision = input('Proceed with generation? (y/n) ')
  63
  64 while decision.lower() not in ('y', 'n'):
  65     decision = input('Proceed with generation? (y/n) ')
  66
  67 if decision == 'n':
  68     sys.exit(0)
  69
  70 area = size * size
  71 filters = { valid_boards[0]: ['.' * area] }
  72
  73 for board_count in range(1, len(valid_boards)):
  74     current_board = valid_boards[board_count]
  75
  76     new_filters = {}
  77
  78     new_filters[current_board] = set()
  79
  80     for previous_board in filters:
  81         differences = [i for i in range(size) if previous_board[i] != current_board[i]]
  82
  83         new_filters[previous_board] = set()
  84
  85         for old_filter in filters[previous_board]:
  86             if re.match(old_filter, current_board):
  87                 for d in differences:
  88                     new_filters[previous_board].add(
  89                         old_filter[:d] + previous_board[d] + old_filter[d + 1:]
  90                     )
  91                     new_filters[current_board].add(
  92                         old_filter[:d] + current_board[d] + old_filter[d + 1:]
  93                     )
  94
  95             else:
  96                 new_filters[previous_board].add(old_filter)
  97
  98     print('Round {} complete, {} filters'.format(board_count, len(new_filters)))
  99
 100     filters = new_filters
 101
 102     removed_count = 0
 103
 104     for b in filters:
 105         c = filters[b].copy()
 106
 107         for f0, f1 in itertools.permutations(c, 2):
 108             if re.match(f0, f1):
 109                 filters[b].remove(f1)
 110                 removed_count += 1
 111
 112     print(removed_count)
 113
 114
 115 with open('generated.txt', 'w') as gen_file:
 116     for f in filters:
 117         gen_file.write('\n'.join(f[i:i + size] for i in range(0, area, size)) + '\n\n')