skyscraper puzzle

main.py

# Import required modules
from itertools import permutations, product, accumulate
from collections import defaultdict
import pprint

# Function to calculate the visibility score using differences between adjacent maximum heights
def visibility_score_with_diff(perm):
    max_heights = list(accumulate(perm, func=max))
    differences = [b - a for a, b in zip(max_heights[:-1], max_heights[1:])]
    score = sum(diff != 0 for diff in differences) + 1
    return score

# Generate all permutations of size N and store them by visibility score
def precompute_permutations(N):
    perm_dict = defaultdict(list)
    for perm in permutations(range(1, N + 1)):
        left_score = visibility_score_with_diff(perm)
        right_score = visibility_score_with_diff(tuple(reversed(perm)))
        perm_dict[(left_score, right_score)].append(perm)
    return perm_dict

# Function to find the valid row and column permutations
def find_valid_permutations(clues, perm_dict):
    return [perm_dict.get(clue, []) for clue in clues]

# Function to solve the Skyscraper puzzle with additional debugging print statements focused on the grid and transposed grid
def solve_skyscraper_debug(row_clues, col_clues, N):
    perm_dict = precompute_permutations(N)
    valid_row_perms = find_valid_permutations(row_clues, perm_dict)
    valid_col_perms = find_valid_permutations(col_clues, perm_dict)
    
    
    debug_log = []
    
    debug_log.append(f"Plausible rows - "+pprint.pformat(valid_row_perms))
    debug_log.append(f"Plausible cols - "+pprint.pformat(valid_col_perms))
    
    valid_grids = []
    
    for row_perm in product(*valid_row_perms):
        grid = list(row_perm)
        transposed_grid = list(zip(*grid))
        
        if any(len(set(row)) < N for row in transposed_grid):
            continue
        
        debug_log.append("Grid:")
        debug_log.append(pprint.pformat(grid))
        debug_log.append("Transposed Grid:")
        debug_log.append(pprint.pformat(transposed_grid))
        
        valid_grids_from_col_clues = tuple(product(*valid_col_perms))
        for i, _grid in enumerate(valid_grids_from_col_clues):
            debug_log.append(f"Match {i+1}: "+ pprint.pformat(_grid))
        
        
        if tuple(transposed_grid) in valid_grids_from_col_clues:
            debug_log.append("Match found!")
            valid_grids.append(grid)
    
    return debug_log, valid_grids

# Given row and column clues for debugging
row_clues = [(2, 3), (3,1), (3, 2), (1, 3)]
col_clues = [(2, 1), (1, 2), (3, 2), (2, 3)]
N = 4


debug_log, result = solve_skyscraper_debug(row_clues, col_clues, N)

# Run the debug version of the algorithm with additional print statements
debug=True
if debug:
    for log in debug_log:
        print(log)
print(result)