Skip to content

Instantly share code, notes, and snippets.

@jseakle

jseakle/flow_score.py

Created February 18, 2025 20:58
Show Gist options
  • Save jseakle/2d5b6d4062f708ba42fcb686c559c62c to your computer and use it in GitHub Desktop.
Save jseakle/2d5b6d4062f708ba42fcb686c559c62c to your computer and use it in GitHub Desktop.
Download ZIP
Raw
flow_score.py
import numpy as np
from scipy.stats import norm
from collections import defaultdict
def get_word_slots(grid):
"""Extract word slots from the grid."""
slots = []
n_rows, n_cols = len(grid), len(grid[0])
# Horizontal slots
for i in range(n_rows):
j = 0
while j < n_cols:
if not grid[i][j]:
start = j
while j < n_cols and not grid[i][j]:
j += 1
if j - start > 1:
slots.append(('h', i, start, j - 1))
else:
j += 1
# Vertical slots
for j in range(n_cols):
i = 0
while i < n_rows:
if not grid[i][j]:
start = i
while i < n_rows and not grid[i][j]:
i += 1
if i - start > 1:
slots.append(('v', j, start, i - 1))
else:
i += 1
return slots
def get_crosses(slots):
"""Get a dictionary of crosses between slots."""
crosses = defaultdict(list)
for i, slot1 in enumerate(slots):
for j, slot2 in enumerate(slots):
if i != j:
if slot1[0] == 'h' and slot2[0] == 'v':
if slot1[1] >= slot2[2] and slot1[1] <= slot2[3] and slot2[1] >= slot1[2] and slot2[1] <= slot1[3]:
crosses[i].append(j)
elif slot1[0] == 'v' and slot2[0] == 'h':
if slot1[1] >= slot2[2] and slot1[1] <= slot2[3] and slot2[1] >= slot1[2] and slot2[1] <= slot1[3]:
crosses[j].append(i)
return crosses
def simulate_solve(grid, num_simulations=100000, target_zero_percent=.15):
"""Simulate the solving process and calculate the flow score."""
slots = get_word_slots(grid)
crosses = get_crosses(slots)
flow_scores = []
means = {length: .3 * length for length in range(2, 16)}
stdevs = {mean: mean / norm.ppf(1 - target_zero_percent) for mean in means.values()} # Adjust std_dev to achieve the target
for _ in range(num_simulations):
# Assign difficulties
difficulties = []
for slot in slots:
length = slot[3] - slot[2] + 1
# Calculate mean and standard deviation to achieve the target percentage of zeros
# We want P(X <= 0) = target_zero_percent, where X ~ N(mean, std_dev)
# Using the inverse CDF (percent point function) of the normal distribution:
mean = means[length] # Center around 2/5 of the slot's length
std_dev = stdevs[mean]
# Sample from the normal distribution
difficulty = np.random.normal(loc=mean, scale=std_dev)
# Ensure difficulty is within bounds
if difficulty <= 0:
difficulty = 0 # Assign 0 if the value is <= 0
else:
difficulty = int(min(difficulty, length/2)) # Cap at slot's length
difficulties.append(difficulty)
#print(difficulties)
# Initialize solvability
solvable = [i for i, d in enumerate(difficulties) if d == 0]
solved = set(solvable)
while solvable:
current = solvable.pop()
for cross in crosses[current]:
if cross not in solved:
difficulties[cross] -= 1
if difficulties[cross] == 0:
solvable.append(cross)
solved.add(cross)
flow_scores.append(len(solved) / len(slots))
return np.mean(flow_scores)
# Example usage
grid = [
[False, False, False, True],
[False, True, False, False],
[False, False, False, True],
[True, False, False, False]
]
grid3 = [
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, True, False, False, False, False, False, False],
[False, False, False, False, False, False, False, False, True, False, False, False, False, False, False],
[False, False, False, True, False, False, False, False, False, False, False, True, False, False, False],
[False, False, False, False, True, False, False, False, False, False, True, False, False, False, False],
[False, False, False, False, False, True, False, False, False, True, False, False, False, False, False],
[True, True, True, False, False, False, False, False, False, False, False, False, False, False, True],
[True, True, False, False, False, False, False, False, False, True, False, False, False, True, True],
[True, False, False, False, False, False, False, False, False, False, False, False, True, True, True],
[False, False, False, False, False, True, False, False, False, True, False, False, False, False, False],
[False, False, False, False, True, False, False, False, False, False, True, False, False, False, False],
[False, False, False, True, False, False, False, False, False, False, False, True, False, False, False],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, True, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, True, True, False, False, False, False, False, False, False]
]
grid4 = [
[False, False, False, False, False, False, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, False, False, True, False, False, False, False, False],
[True, True, True, True, True, True, False, False, False, True, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, True, True, True, True, True, True],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
[False, False, False, False, False, True, False, False, False, False, False, False, False, False, False],
]
a = [
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, False, True, False, False, False, False, False, True, False, False, False, False],
[True, True, True, True, True, True, False, False, False, True, True, True, True, True, True],
[False, False, False, False, True, False, False, False, False, False, True, False, False, False, False],
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
]
b = [
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, True, False, False, False, False, False, False, False, True, False, False, False],
[True, True, True, True, True, True, False, False, False, True, True, True, True, True, True],
[False, False, False, True, False, False, False, False, False, False, False, True, False, False, False],
[False, False, False, False, False, False, True, True, True, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
[False, False, False, False, False, False, False, True, False, False, False, False, False, False, False],
]
grid2 = [
[False, False, False, True],
[False, False, False, False],
[False, False, False, True],
[True, False, False, False]
]
print(simulate_solve(a), simulate_solve(b))
# flow_score = simulate_solve(grid3,num_simulations=10)
# flow_score2 = simulate_solve(grid2,num_simulations=10)
# flow_score3 = simulate_solve(grid,num_simulations=1000)
# flow_score4 = simulate_solve(grid4,num_simulations=1000)
# print(f"Flow Score: {flow_score} {flow_score2} {flow_score3} {flow_score4}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment