API tools faq
paste
Advertisement
Hinski2

Untitled

Hinski2
May 15th, 2024
47
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 9.51 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, line):
  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 and line[i] != no: same_pixels.append([i, no])
  52.         elif sum[i] == poss_no and line[i] != yes: 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. def get_coll(matrix, j):
  123.     return [matrix[i][j] for i in range(len(matrix))]
  124.  
  125. def find_ans(matrix, rows_poss, cols_poss, rows_done, cols_done, rows, cols):
  126.     wypisz(matrix)
  127.     # szukam tego co moge ustawić
  128.     not_solved_rows = []
  129.     not_solved_cols = []
  130.     lines_todo = []
  131.    
  132.     #sprawdzenie
  133.     for j in range(len(rows_poss)):
  134.         if len(rows_poss[j]) == 0 and not rows_done[j]:
  135.             return []
  136.        
  137.     for j in range(len(cols_done)):
  138.         if len(cols_poss[j]) == 0 and not cols_done[j]:
  139.             return []
  140.    
  141.     # ustawiam to co moge
  142.     solved, change = False, True
  143.     while not solved and change:
  144.         change = False
  145.         not_solved_rows = select_not_solved(rows_poss, rows_done, row_enum)
  146.         not_solved_cols = select_not_solved(cols_poss, cols_done, col_enum)
  147.         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
  148.        
  149.         # ustawia pixele o których wiemy jak będą wyglądały
  150.         for ammount, i, enum in lines_todo:
  151.             if ammount == 0: return []
  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.                 line = matrix[i] if enum == row_enum else get_coll(matrix, i)
  155.                 same_pixels = get_same_pixels(poss, line)
  156.                
  157.                 for j, val in same_pixels:
  158.                     r_idx, c_idx = (i, j) if row_enum == enum else (j, i)
  159.                     if matrix[r_idx][c_idx] == idk:
  160.                         if matrix[r_idx][c_idx] != val:
  161.                             matrix[r_idx][c_idx] = val
  162.                             change = True
  163.  
  164.                             # usówamie możliwości które się nie zgadzająz nowym pixelem
  165.                             if enum != row_enum:
  166.                                 rows_poss[r_idx] = update_poss(rows_poss[r_idx], c_idx, val)
  167.                             else:
  168.                                 cols_poss[c_idx] = update_poss(cols_poss[c_idx], r_idx, val)
  169.                                
  170.                 update_done(enum, i, matrix, rows_done, cols_done) # sprawdza czy linia jest ukończona
  171.         solved = check_solved(rows_done, cols_done)
  172.  
  173.     # jeśli mam gotowy nonogram to go zwracam
  174.     #sprawdzenie
  175.     for j in range(len(rows_poss)):
  176.         if len(rows_poss[j]) == 0 and not rows_done[j]:
  177.             return []
  178.        
  179.     for j in range(len(cols_done)):
  180.         if len(cols_poss[j]) == 0 and not cols_done[j]:
  181.             return []
  182.        
  183.     if solved:
  184.         if valid(matrix, rows, cols): return matrix
  185.         else: return []
  186.    
  187.     # jeśli nie jsest gotowy to robie kopie oraz ustawiam ten wiersz / kolumne
  188.         # którą ma najmniej możliwości ustawienia
  189.         # jak ją już ustawie to robie wywołąnie find_ans jeśli zwróci [] to ustawiam kolejną możliwość
  190.         # dla wiersza/kolumny aż do końca możliwości
  191.         # jeśli przejżałem już wszystkie możliwości i nic nie znalazłem to zwracam []
  192.    
  193.     not_solved_rows = select_not_solved(rows_poss, rows_done, row_enum)
  194.     not_solved_cols = select_not_solved(cols_poss, cols_done, col_enum)
  195.     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
  196.    
  197.     _, i, enum = lines_todo[0]
  198.     to_check = deepcopy(rows_poss[i] if enum == row_enum else cols_poss[i])
  199.     for u in to_check:
  200.         _matrix = deepcopy(matrix)
  201.         _rows_poss = deepcopy(rows_poss)
  202.         _cols_poss = deepcopy(cols_poss)
  203.         _rows_done = deepcopy(rows_done)
  204.         _cols_done = deepcopy(cols_done)
  205.        
  206.         for j in range(len(u)):
  207.             val = u[j]
  208.             r_idx, c_idx = (i, j) if row_enum == enum else (j, i)
  209.             if _matrix[r_idx][c_idx] == idk:
  210.                 _matrix[r_idx][c_idx] = val
  211.  
  212.                 # usówamie możliwości które się nie zgadzająz nowym pixelem
  213.                 if enum != row_enum:
  214.                     _rows_poss[r_idx] = update_poss(_rows_poss[r_idx], c_idx, val)
  215.                 else:
  216.                     _cols_poss[c_idx] = update_poss(_cols_poss[c_idx], r_idx, val)
  217.                
  218.         update_done(enum, i, _matrix, _rows_done, _cols_done) # sprawdza czy linia jest ukończona
  219.        
  220.         if check_solved(_rows_done, _cols_done):
  221.             if valid(_matrix, rows, cols): return _matrix
  222.             else: continue
  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.     return []
  229.        
  230.  
  231. def policz(rows_no, cols_no, rows, cols):
  232.     matrix = [[idk for _ in range(cols_no)] for _ in range(rows_no)]
  233.    
  234.     rows_done = [0] * rows_no
  235.     cols_done = [0] * cols_no
  236.    
  237.     # liczenie wszystkich możliwych ustawień
  238.     rows_poss = make_poss(rows, cols_no)
  239.     cols_poss = make_poss(cols, rows_no)
  240.    
  241.     for u in rows_poss:
  242.         shuffle(u)
  243.     for u in cols_poss:
  244.         shuffle(u)
  245.    
  246.     return find_ans(matrix, rows_poss, cols_poss, rows_done, cols_done, rows, cols)
  247.    
  248. def main():
  249.     # wczytaj dane
  250.     input = open('zad_input.txt')
  251.     n, m = map(int, input.readline().split())
  252.     rows = [list(map(int, input.readline().split())) for _ in range(n)]
  253.     cols = [list(map(int, input.readline().split())) for _ in range(m)]
  254.     input.close()
  255.      
  256.     # policz
  257.     matrix = policz(n, m, rows, cols)
  258.    
  259.     #wpyisz dane
  260.     output = open('zad_output.txt', 'w')
  261.     for i in range(n):
  262.         for j in range(m):
  263.             output.write('#' if matrix[i][j] == yes else '.')
  264.         output.write('\n')
  265.    
  266.     output.close()
  267.  
  268. if __name__ == "__main__":
  269.     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!