API tools faq
paste
Advertisement
Hinski2

Untitled

Hinski2
May 15th, 2024
50
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 10.17 KB | None | 0 0
raw download clone embed print report
  1. from queue import PriorityQueue
  2. from itertools import combinations
  3. from random import shuffle
  4. from copy import deepcopy
  5.  
  6. yes, idk, no = [1, 0, -1] # pseudo enum
  7. row_enum, col_enum = range(2) #psudo enum
  8.    
  9. def make_line_poss(empty_no, blocks_no, ones):
  10.     line_poss = []
  11.     for p in combinations(range(empty_no + blocks_no), blocks_no):
  12.         selected = [no] * (empty_no + blocks_no)
  13.         idx = 0
  14.         for val in p:
  15.             selected[val] = idx
  16.             idx += 1
  17.        
  18.         res = [ones[val] + [-1] if val > -1 else [-1] for val in selected]
  19.         res = [item for sublist in res for item in sublist][:-1]
  20.         line_poss.append(res)
  21.     return line_poss
  22.  
  23. def make_poss(lines, n):
  24.     lines_poss = []
  25.     for line in lines:
  26.         blocks_no = len(line)
  27.         empty_no = n - sum(line) - blocks_no + 1
  28.         ones = [[1] * pixel for pixel in line]
  29.         line_poss = make_line_poss(empty_no, blocks_no, ones)
  30.         lines_poss.append(line_poss)
  31.    
  32.     return lines_poss
  33.  
  34. # wybiera idx lini które jeszcze nie zostały rozwiązane całkowicie
  35. def select_not_solved(poss, done, enum):
  36.     s = [len(i) for i in poss]
  37.     return [(liczba_mozliwosci, i, enum) for i, liczba_mozliwosci in enumerate(s) if done[i] == 0]
  38.  
  39. def get_same_pixels(poss):
  40.     poss_no = len(poss)
  41.     if poss_no == 0: return []
  42.    
  43.     line_len = len(poss[0])
  44.     sum = [0] * line_len
  45.     for p in poss:
  46.         for i in range(line_len):
  47.             sum[i] += 1 if p[i] == yes else 0
  48.    
  49.     same_pixels = []
  50.     for i in range(line_len):
  51.         if sum[i] == 0: same_pixels.append([i, no])
  52.         elif sum[i] == poss_no: same_pixels.append([i, yes])
  53.    
  54.     return same_pixels
  55.  
  56. def check_done(i, enum, cols_done, rows_done):
  57.     if enum == row_enum: return rows_done[i]
  58.     return cols_done[i]
  59.  
  60. def check_solved(rows_done, cols_done):
  61.     return True if 0 not in rows_done and 0 not in cols_done else False
  62.  
  63. def get_col(matrix, j):
  64.     return [matrix[i][j] for i in range(len(matrix))]
  65.  
  66. def update_done(enum, i, matrix, rows_done, cols_done):
  67.     line = matrix[i] if enum == row_enum else get_col(matrix, i)
  68.     if idk not in line:
  69.         if enum == row_enum: rows_done[i] = 1
  70.         else: cols_done[i] = 1
  71.  
  72. def update_poss(poss, i, val):
  73.     return [p for p in poss if p[i] == val]
  74.  
  75. def removed_poss(poss, i, val):
  76.     return [p for p in poss if p[i] != val]
  77.  
  78. def valid(matrix, rows, cols):
  79.     def get_segments(line):
  80.         segments = []
  81.         count = 0
  82.         for value in line:
  83.             if value == 1:
  84.                 count += 1
  85.             elif count > 0:
  86.                 segments.append(count)
  87.                 count = 0
  88.         if count > 0:
  89.             segments.append(count)
  90.         return segments
  91.  
  92.     # Sprawdzamy wiersze
  93.     for i, row in enumerate(matrix):
  94.         if get_segments(row) != rows[i]:
  95.             return False
  96.  
  97.     # Sprawdzamy kolumny
  98.     num_cols = len(matrix[0])
  99.     for j in range(num_cols):
  100.         col = [matrix[i][j] for i in range(len(matrix))]
  101.         if get_segments(col) != cols[j]:
  102.             return False
  103.  
  104.     return True
  105.  
  106. def wypisz(matrix):
  107.     for i in range(len(matrix)):
  108.         for j in range(len(matrix[0])):
  109.             print(matrix[i][j], end=' ')
  110.             if matrix[i][j] != -1: print(' ', end='')
  111.         print()
  112.     print()
  113.    
  114. def give_back_removed_poss(enum, n, m, removed_poss_rows, removed_poss_cols, rows_poss, cols_poss):
  115.     if enum != row_enum:
  116.         for g in range(n):
  117.             rows_poss[g] += removed_poss_rows[g]
  118.     else:
  119.         for g in range(m):
  120.             cols_poss[g] += removed_poss_cols[g]
  121.    
  122.  
  123. def find_ans(matrix, rows_poss, cols_poss, rows_done, cols_done, rows, cols):
  124.     # wypisz(matrix)
  125.     # szukam tego co moge ustawić
  126.     not_solved_rows = []
  127.     not_solved_cols = []
  128.     lines_todo = []
  129.    
  130.     removed_poss_rows = [[] for _ in range(len(matrix))]
  131.     removed_poss_cols = [[] for _ in range(len(matrix[0]))]
  132.    
  133.     #sprawdzenie
  134.     for j in range(len(rows_poss)):
  135.         if len(rows_poss[j]) == 0 and not rows_done[j]:
  136.             return []
  137.        
  138.     for j in range(len(cols_done)):
  139.         if len(cols_poss[j]) == 0 and not cols_done[j]:
  140.             return []
  141.    
  142.     # ustawiam to co moge
  143.     solved, change = False, True
  144.     while not solved and change:
  145.         change = False
  146.         not_solved_rows = select_not_solved(rows_poss, rows_done, row_enum)
  147.         not_solved_cols = select_not_solved(cols_poss, cols_done, col_enum)
  148.         lines_todo = sorted(not_solved_cols + not_solved_rows) # sortuje je po najmniejszej ilości możliwości na które można ułożyć linie
  149.        
  150.         # ustawia pixele o których wiemy jak będą wyglądały
  151.         for _, i, enum in lines_todo:
  152.             if not check_done(i, enum, cols_done, rows_done):
  153.                 poss = rows_poss[i] if enum == row_enum else cols_poss[i] # możliwe wypełnienia lini
  154.                 same_pixels = get_same_pixels(poss)
  155.                
  156.                 for j, val in same_pixels:
  157.                     r_idx, c_idx = (i, j) if row_enum == enum else (j, i)
  158.                     if matrix[r_idx][c_idx] == idk:
  159.                         if matrix[r_idx][c_idx] != val:
  160.                             matrix[r_idx][c_idx] = val
  161.                             change = True
  162.  
  163.                             # usówamie możliwości które się nie zgadzająz nowym pixelem
  164.                             if enum != row_enum:
  165.                                 removed_poss_rows[r_idx] = removed_poss(rows_poss[r_idx], c_idx, val)
  166.                                 rows_poss[r_idx] = update_poss(rows_poss[r_idx], c_idx, val)
  167.                             else:
  168.                                 removed_poss_cols[c_idx] = removed_poss(cols_poss[c_idx], r_idx, val)
  169.                                 cols_poss[c_idx] = update_poss(cols_poss[c_idx], r_idx, val)
  170.                                
  171.                 update_done(enum, i, matrix, rows_done, cols_done) # sprawdza czy linia jest ukończona
  172.         solved = check_solved(rows_done, cols_done)
  173.  
  174.     # jeśli mam gotowy nonogram to go zwracam
  175.     #sprawdzenie
  176.     for j in range(len(rows_poss)):
  177.         if len(rows_poss[j]) == 0 and not rows_done[j]:
  178.             give_back_removed_poss(enum, len(matrix), len(matrix[0]), removed_poss_rows, removed_poss_cols, rows_poss, cols_poss)
  179.             return []
  180.        
  181.     for j in range(len(cols_done)):
  182.         if len(cols_poss[j]) == 0 and not cols_done[j]:
  183.             give_back_removed_poss(enum, len(matrix), len(matrix[0]), removed_poss_rows, removed_poss_cols, rows_poss, cols_poss)
  184.             return []
  185.        
  186.     if solved:
  187.         return matrix
  188.    
  189.     # jeśli nie jsest gotowy to robie kopie oraz ustawiam ten wiersz / kolumne
  190.         # którą ma najmniej możliwości ustawienia
  191.         # jak ją już ustawie to robie wywołąnie find_ans jeśli zwróci [] to ustawiam kolejną możliwość
  192.         # dla wiersza/kolumny aż do końca możliwości
  193.         # jeśli przejżałem już wszystkie możliwości i nic nie znalazłem to zwracam []
  194.    
  195.     not_solved_rows = select_not_solved(rows_poss, rows_done, row_enum)
  196.     not_solved_cols = select_not_solved(cols_poss, cols_done, col_enum)
  197.     lines_todo = sorted(not_solved_cols + not_solved_rows) # sortuje je po najmniejszej ilości możliwości na które można ułożyć linie
  198.    
  199.     _, i, enum = lines_todo[0]
  200.     to_check = deepcopy(rows_poss[i] if enum == row_enum else cols_poss[i])
  201.     for u in to_check:
  202.         _matrix = deepcopy(matrix)
  203.         removed_poss_rows2 = [[] for _ in range(len(matrix))]
  204.         removed_poss_cols2 = [[] for _ in range(len(matrix[0]))]
  205.         _rows_done = deepcopy(rows_done)
  206.         _cols_done = deepcopy(cols_done)
  207.        
  208.         for j in range(len(u)):
  209.             val = u[j]
  210.             r_idx, c_idx = (i, j) if row_enum == enum else (j, i)
  211.             if _matrix[r_idx][c_idx] == idk:
  212.                 _matrix[r_idx][c_idx] = val
  213.  
  214.                 # usówamie możliwości które się nie zgadzająz nowym pixelem
  215.                 if enum != row_enum:
  216.                     removed_poss_rows2[r_idx] = removed_poss(rows_poss[r_idx], c_idx, val)
  217.                     rows_poss[r_idx] = update_poss(rows_poss[r_idx], c_idx, val)
  218.                 else:
  219.                     removed_poss_cols2[c_idx] = removed_poss(cols_poss[c_idx], r_idx, val)
  220.                     cols_poss[c_idx] = update_poss(cols_poss[c_idx], r_idx, val)
  221.                
  222.         update_done(enum, i, _matrix, _rows_done, _cols_done) # sprawdza czy linia jest ukończona
  223.        
  224.         # wszystko już jest ustawione
  225.         ans = find_ans(_matrix, rows_poss, cols_poss, _rows_done, _cols_done, rows, cols)
  226.         if ans != []:
  227.             return ans
  228.        
  229.         # dodanie opcji które wcześniej usuneliśmy
  230.         give_back_removed_poss(enum, len(matrix), len(matrix[0]), removed_poss_rows2, removed_poss_cols2, rows_poss, cols_poss)
  231.    
  232.     give_back_removed_poss(enum, len(matrix), len(matrix[0]), removed_poss_rows, removed_poss_cols, rows_poss, cols_poss)
  233.     return []
  234.        
  235.  
  236. def policz(rows_no, cols_no, rows, cols):
  237.     matrix = [[idk for _ in range(cols_no)] for _ in range(rows_no)]
  238.    
  239.     rows_done = [0] * rows_no
  240.     cols_done = [0] * cols_no
  241.    
  242.     # liczenie wszystkich możliwych ustawień
  243.     rows_poss = make_poss(rows, cols_no)
  244.     cols_poss = make_poss(cols, rows_no)
  245.    
  246.     for u in rows_poss:
  247.         shuffle(u)
  248.     for u in cols_poss:
  249.         shuffle(u)
  250.    
  251.     return find_ans(matrix, rows_poss, cols_poss, rows_done, cols_done, rows, cols)
  252.    
  253. def main():
  254.     # wczytaj dane
  255.     input = open('zad_input.txt')
  256.     n, m = map(int, input.readline().split())
  257.     rows = [list(map(int, input.readline().split())) for _ in range(n)]
  258.     cols = [list(map(int, input.readline().split())) for _ in range(m)]
  259.     input.close()
  260.      
  261.     # policz
  262.     matrix = policz(n, m, rows, cols)
  263.    
  264.     #wpyisz dane
  265.     output = open('zad_output.txt', 'w')
  266.     for i in range(n):
  267.         for j in range(m):
  268.             output.write('#' if matrix[i][j] == yes else '.')
  269.         output.write('\n')
  270.    
  271.     output.close()
  272.  
  273. if __name__ == "__main__":
  274.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!