Created
December 13, 2024 15:44
-
-
Save FlorianLatapie/388ae197be5e836f6f0de2a8500ba872 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import os | |
| from typing import Generator | |
| from pathlib import Path | |
| os.chdir(os.path.dirname(__file__)) | |
| def get_constraints_from_file(filepath: str|Path) -> tuple[tuple[int, int], list[list[int]], list[list[int]]]: | |
| section_lines = "Lines:" | |
| section_columns = "Columns:" | |
| filepath = Path(filepath) | |
| with open(filepath, "r", encoding="utf-8") as f: | |
| file_data = f.readlines() | |
| if not file_data: | |
| raise ValueError("File is empty") | |
| # Parse grid size | |
| dimensions = file_data[0].split()[1].split("x") | |
| grid_size = (int(dimensions[0]), int(dimensions[1])) | |
| row_constraints = [] | |
| column_constraints = [] | |
| current_section = None | |
| # Parse constraints | |
| for file_line in file_data[1:]: | |
| file_line = file_line.strip() | |
| if not file_line: | |
| break | |
| if file_line == section_lines: | |
| current_section = "lines" | |
| continue | |
| elif file_line == section_columns: | |
| current_section = "columns" | |
| continue | |
| constraint = list(map(int, file_line.split(": ")[1][1:-1].split(","))) | |
| if current_section == "lines": | |
| row_constraints.append(constraint) | |
| elif current_section == "columns": | |
| column_constraints.append(constraint) | |
| # Validate parsed data | |
| if len(row_constraints) != grid_size[0]: | |
| raise ValueError(f"Expected {grid_size[0]} row constraints, got {len(row_constraints)}") | |
| if len(column_constraints) != grid_size[1]: | |
| raise ValueError( | |
| f"Expected {grid_size[1]} column constraints, got {len(column_constraints)}") | |
| return grid_size, row_constraints, column_constraints | |
| def get_all_combinations_single_block(size: int, constraint: int) -> list[list[int]]: | |
| return [[0] * i + [1] * constraint + [0] * (size - i - constraint) | |
| for i in range(size-constraint+1)] | |
| def get_all_combinations(size: int, constraints: list[int]) -> Generator[any, any, any]: | |
| #many thanks to zdimension for this implementation | |
| print(f"size: {size}, constraints: {constraints}") | |
| def inner(size: int, constraints: list[int]) -> Generator[any, any, any]: | |
| if len(constraints) == 0: | |
| yield [0] * size | |
| return | |
| first, *rest = constraints | |
| for start in range(0, size - sum(rest) - first + 1): | |
| head = [0] * start + [1] * (first - 1) + [0] | |
| for tail in inner(size - len(head), rest): | |
| yield head + tail | |
| for res in inner(size + 1, [x + 1 for x in constraints]): | |
| yield res[:-1] | |
| def get_possibilities(size: int, data_list: list[list[int]]) -> list[list[list[int]]]: | |
| return [list(get_all_combinations(size, data)) for data in data_list] | |
| def calculate_probabilities(possibilities: list[list[list[int]]], size: int) -> list[list[float]]: | |
| probabilities = [] | |
| for possibility_set in possibilities: | |
| result = [0.0] * size | |
| for possibility in possibility_set: | |
| for pos, bit in enumerate(possibility): | |
| result[pos] += bit / len(possibility_set) | |
| probabilities.append(result) | |
| return probabilities | |
| #################### | |
| ### --- Main --- ### | |
| #################### | |
| # Example input | |
| """ | |
| Size: 10x10 | |
| Lines: | |
| 1: [1] | |
| 2: [1, 3] | |
| 3: [4, 1, 1] | |
| ... | |
| Columns: | |
| 1: [1] | |
| 2: [3, 1] | |
| 3: [1, 3, 1] | |
| ... | |
| """ | |
| if __name__ == "__main__": | |
| print("parsing file") | |
| riddle_size, lines, columns = get_constraints_from_file("output_60x60_357.txt") | |
| print("computig possibilities lines") | |
| line_possibilities = get_possibilities(riddle_size[0], lines) | |
| print("computig possibilities columns") | |
| column_possibilities = get_possibilities(riddle_size[1], columns) | |
| print("computing probabilities") | |
| line_proba = calculate_probabilities(line_possibilities, riddle_size[0]) | |
| column_proba = calculate_probabilities(column_possibilities, riddle_size[1]) | |
| print("computing final probabilities") | |
| final_proba = [[0.0] * riddle_size[1] for _ in range(riddle_size[0])] | |
| final_proba_min = [[0.0] * riddle_size[1] for _ in range(riddle_size[0])] | |
| for i in range(riddle_size[0]): | |
| for j in range(riddle_size[1]): | |
| res_max = max( | |
| line_proba[i][j], | |
| column_proba[j][i], | |
| (line_proba[i][j] + column_proba[j][i]) / 2) | |
| res_min = min( | |
| line_proba[i][j], | |
| column_proba[j][i], | |
| (line_proba[i][j] + column_proba[j][i]) / 2) | |
| final_proba[i][j] = res_max | |
| final_proba_min[i][j] = res_min | |
| print("computing final extreme probabilities") | |
| final_extreme = [[0.0] * riddle_size[1] for _ in range(riddle_size[0])] | |
| for i in range(riddle_size[0]): | |
| for j in range(riddle_size[1]): | |
| final_val = final_proba[i][j] | |
| final_val_min = final_proba_min[i][j] | |
| if abs(final_val_min - 0.5) > abs(final_val - 0.5): | |
| final_extreme[i][j] = final_val_min | |
| else: | |
| final_extreme[i][j] = final_val | |
| print("displaying results") | |
| # display results | |
| import tkinter as tk | |
| def draw_grid(canvas_to_draw: tk.Canvas, data: list[list[float]], pixel_size: int, cell_gap: int) -> None: | |
| for i, row in enumerate(data): | |
| for j, val in enumerate(row): | |
| if val > 0.94: | |
| fill_value = f"#{16765005:02x}" | |
| else: | |
| color = 255 - int(val * 255) | |
| fill_value = f"#{color:02x}{color:02x}{color:02x}" | |
| x = j * pixel_size + (j // 5) * cell_gap | |
| y = i * pixel_size + (i // 5) * cell_gap | |
| canvas_to_draw.create_rectangle( | |
| x, y, | |
| x + pixel_size, | |
| y + pixel_size, | |
| fill=fill_value, | |
| width=1 | |
| ) | |
| root = tk.Tk() | |
| screen_height = root.winfo_screenheight() | |
| sqr_size = screen_height//riddle_size[0]//1.2 | |
| gap_size = sqr_size//9 | |
| root.title("Final Probabilities") | |
| root.geometry("+0+0") | |
| canvas = tk.Canvas(root, | |
| width=riddle_size[1] * sqr_size + (riddle_size[1] // 5) * gap_size, | |
| height=riddle_size[0] * sqr_size + (riddle_size[0] // 5) * gap_size) | |
| canvas.pack() | |
| # Create and position the second window | |
| extreme_window = tk.Toplevel() | |
| extreme_window.title("Final Probabilities Extreme") | |
| # Wait for the main window to be drawn | |
| root.update_idletasks() | |
| # Get main window position and dimensions | |
| main_x = root.winfo_x() | |
| main_y = root.winfo_y() | |
| main_width = root.winfo_width() | |
| extreme_window.geometry(f"+{main_x + main_width + int(gap_size)}+{main_y}") | |
| extreme_canvas = tk.Canvas(extreme_window, | |
| width=riddle_size[1] * sqr_size + (riddle_size[1] // 5) * gap_size, | |
| height=riddle_size[0] * sqr_size + (riddle_size[0] // 5) * gap_size) | |
| extreme_canvas.pack() | |
| draw_grid(canvas, final_proba, sqr_size, gap_size) | |
| draw_grid(extreme_canvas, final_extreme, sqr_size, gap_size) | |
| root.mainloop() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment