# Why I'm making my app free

I'm an Indie Hacker and I've decided to make my app free. Sounds like a terrible decision, right?

I'm making a browser extension that provides smart subtitles for Chinese videos, partly provided by my OCR subtitle extraction tool. I'm not doing it for the money, for that there's always the risk free alternative of regular employment. Then is it to become rich? Clearly not, then I'd definitely not target the fairly saturated niche of language learning. Besides, a one-man project is unlikely to generate that kind of revenue, that is left for the VC funded startups of the world. Why a one-man project then? It's mainly that at this point in our life with small kids, we want as much freedom as possible. That includes deciding when and where to work. Involving other people means meetings, oh so many meetings, specific work hours, less creative freedom and many a large pressure to turn a profit.

What I really want is to create as much value as possible while covering our expenses as a family. So the calculus is simple: maximize the "value" I can provide to other people, i.e. "number of users" times "value provided per user", subject to the constraint of paying most of our bills at some point in the future.

My conclusion after thinking about it for a long time is that the "normal" path of building an app with subscription or premium features is not what I want to do. It would probably be the fastest way to meet the constraint of covering our expenses, but it would severly impact how much value I could create. People are getting more comfortable paying for software nowadays, but it is still a very tiny minority who are willing to do that. Freemium with some features hidden behind a paywall is one way to go, but it creates this tension where you need to inconvenience people just enough so that enough people pay up. I don't like that dynamic, and usually it means hiding some very valuable features behind paywalls.

So here's my simple plan: make anything that can be provided for free, free (some things may not, like anything that requires a back-end server to run). Then try to make some money at the margins like this:

1. Patreon: give some perks to patrons like the ability to vote on features, request specific TV shows to import, and even get the binary to run OCR themselves
2. VPN ads: I suspect people learning Chinese (either foreigners or heritage learners) have a greater than average need for a VPN, both for traveling to China, but also to access Chinese services from abroad. VPN companies also happen to pay out great commissions.
3. OCR as a service: Perhaps there is some small market for providing OCR on video subtitles as a service. At some point I'll create a separate landing page and buy some keywords to try this out.

This strategy is quite freeing from a technological and UX perspective. When building a subscription service on the web, it's almost a requirement to put most of your code on the server, so as to protect against piracy and hacking. This often makes sense when there are significant need for centralized coordination between user accounts, like social features, or there is a need for heavy processing that can't be done client-side.

My feeling though is that in many cases it's purely a user hostile choice, as a way to silo the data and protect against compentition. Making the app free simultaneously incentivices me to make it cheap to host, with a close to zero marginal cost per new user. This also happens to be in the user's best interest, as it means the app is less likely to disappear as it's not highly dependent on a server to run, and the user has complete control over their client-side data! There may be social features incorporated at some point, and there will be a need for some kind of back-end for syncing data between clients, but with a very limited server-side functionality this should not be too expensive to run.

# We can meet in VR instead of polluting our way across the globe

In the past few years I've noticed an increasing trend of techno-pessimism in the West, whether it's the (perhaps legitimate) fear of Social Media corrupting our youth, critique of billionaires going to space instead of feeding the poor, AI-infused murder bots, or a dystopian VR Metaverse run by Mark Zuckerberg. Out of these I think VR is perhaps the most misunderstood.

It's been interesting to have witnessed the very rapid shift in public sentiment in the last few years. When I bought my Oculus Devkit 2 back in 2014, VR was still mainly a curiousity. The reaction from friends and family at that time was mainly "neat!". By the time they tried the HTC Vive I think they could see a bit more clearly what potential VR has, and there was still not much of a negative sentiment. But when Meta, then Facebook, started pushing the idea of a Metaverse, the sentiment pushed firmly into "dystopian" territory. I think it was at this point that people seriously started considering what a future with this technology would look like, and it's just too alien for most people. But in my view, VR is not dystopian, it's probably a necessity for the survival of the planet.

We live in a finite world, with finite resources. VR essentially creates an infinite world for us to live in. We can meet in VR instead of polluting our way across the globe. We can "own" and use virtual objects instead of objects made out of finite atoms mined in Australia, reshaped in China and finally sent on a huge boat across the Pacific. We can have deep experiences that rival anything the world of atoms can provide. We can actually be more social in VR, because the cost of meeting and hanging out is approximately zero. I don't see it as dystopian at all. What's dystopian is 7 billion people all trying to live the American dream while the planet dies.

I don't think we'll completely stop living in the real world, nor should we, but I think moving some activities to VR can alleviate many of the problems we're facing. At the same time we should definitely invest in transitioning to renewable energy, electrification of transportation and industry and other environmental technologies. As a self-proclaimed techno-optimist, I also think that technology can enable us to consume less resources while maintaining our standard of living. One such example is self-driving cars: they would allow us to have overall fewer cars on the road while maintaining the same transportation capacity, while also reducing the need for garages and parking lots. However, the phenomenon of induced demand means that in the end there will probably not be any fewer cars on the road. Living more virtually however, would reduce our need for transportation, our need for stuff. It's not the whole solution, but I think it's an important part of it.

(Note: some of the benefits of VR are also true of AR, but to a lower degree since it's always anchored to the real world)

# Solving Minesweeper

Many years ago I took a class in Artificial Intelligence, in which the final group project was to build a program that played Minesweeper (although this would hardly be considered AI today!). Like most group projects everybody prioritized other classes, me included. Eventually I tried to pull an all-nighter to implement it, in a language I had just "learned": C++. Never doing that again. But I've always wanted to actually finish it, so here it goes. This time I'm using Python, numpy, and other libraries which makes the task much easier. I'll try to do things without looking at other implementations, because where's the fun in that?

### The Algorithm¶

The problem is how to deduce which squares have mines and which don't based on the neighboring constraints which tell us how many neighboring mines there are. Most of the closed squares don't have any explicit constraints on them, so unless we're left with no choice, we'll focus on the edges which do have constraints. If we have an edge region of N squares with interlocking constraints, there are $2^N$ mine configurations that could be considered. Brute-forcing this can start to get prohibitively slow real fast. Luckily, we can use the constraints to limit how many configurations we have to try.

Consider this partially solved board:

First, it would be helpful to display our updated constraints for this partially solved board. Let's do this by showing two pieces of information per square:

1. The number of remaining neighboring mines, i.e. once we flag a square as a mine, we decrement this number
2. The number of remaining closed and unflagged neighbors. Again, we decrement this number for the neighbors when we open a square.

Here is what that looks like:

In the right image squares, the upper left number is the number of remaining mine neighbors, and the lower right number is the number of remaining unopened neighbors.

We can now set up two simple rules:

1. If a square says there are K neighboring mines left, and K closed and unflagged neighbors, we know that all those neighbors have to have mines
2. If a square has no neighoring mines left, then we can safely open all closed neighbors

Applying these rules to the board above, we see that the square with the green box can be safely opened, and the square with the red box definitely has a mine:

Suprisingly, repeatedly applying these two simply rules and updating the constraints solves many beginner and intermediate boards all by itself, but sometimes (and more so for expert difficulty) we get stuck. Let's look at such a case that happens later on:

In this case, there is no simple rule we can apply. We have to try all possible configurations and then make a decision based on the result. This can be done by a constraint satifaction search. Essentially, we go through the squares in order one by one, and assigns it a mine or not mine. Then we check what happens with our constraints:

1. If we assigned "mine" and a neigboring constraint now has -1 number of mines, the board is inconsistent
2. If we assigned "not mine" and a neighboring constraint says there are more neigboring mines than there are closed squares, the board is also inconsistent.

If an assignment is consistent, we continue on to the next square.

If both possible assignments are inconsistent, we backtrack and try different assignments on the previous squares. Here's what this looks like in action:

The result of this search can give us many different consistent configurations, possibly with differing number of mines.

Since we have all possible configurations, we can look at each individual square and see how many times it was a mine versus not a mine. The search above yielded 3 possible solutions (starting from the top right corner):

|1|0|0|1|0|0|1|0|0|1|0|0|1|0|
|1|0|0|1|0|0|0|1|0|0|1|0|0|1|
|0|1|0|0|1|0|0|0|0|1|0|0|1|0|

If we average the result for each square, we get:

|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{1}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|$\frac{0}{3}$|$\frac{2}{3}$|$\frac{1}{3}$|

The same result shown on the board:

Each square shows the probability of having a mine in percentage points. Highlighted in green are the squares with zero probability, meaning we can safely open them.

This begs the question of what to do if there are no 0% squares. Then we simply have to take a chance on the lowest probability square. But at this point we also have to consider other squares that are not at the edge. They may also be worth opening. If you look at the bottom row, these squares have a 17% probability, how do we go about calculating this?

Well, we know how many mines there are in total and how many we've flagged, let's call those $M_t$ and $M_f$ respectively. Then we also have the probabilities for each edge square being a mine $P(S_i = mine)$. Then we have the number of "inner" closed squares, $N$.

The expected, or average number of mines in the edge is simply the sum of the probabilities: $\sum_{i} P(S_i = mine)$. Again, it's possible that some configurations have more mines than others, so this estimate doesn't have to be a round integer.

The final probability for the "inner" closed squares is then: $$\frac{max(M_t - M_f - \sum_{i} P(S_i = mine), 0)}{N}$$

Let's calculate it for the case above: $$\frac{10 - 4 - (6*0.33 + 4*0.67)}{8} = 0.1675$$

Using these inner probabilities, we can now pick the lowest probability square overall, not only those at the edge.

What if we have many choices of lowest probability square? Here's where it gets a little bit complicated.

If we have multiple choices, we probably want to choose the one that gives us the most valuable information. One way to look at it is that we'd prefer if the square we pick has a higher chance of being a "zero", meaning it has no constraints at all. What happens in that case is that we automatically expand the whole area underneath. This gives us more information than if we hit a numbered square right away, in which case we probably have to make another risky choice for the next square.

What is the probability of a square being a "zero" then? Well, it depends on the mine probabilities of its neighbors. If a neighbor has a 90% chance of being a mine, then this square would have at least a 90% chance of having a constraint. So we want to combine the probabilites of the square and its neighbors. Since they are independent events, we can calculate that as the probability of the whole neighborhood being not mines: $$P(S_i = zero) = \prod_{j \in N(i)}{P(S_j = \neg mine)}$$ Where $N(i)$ is the neighborhood of square i.

Let's look at the starting board. The mine probabilities are uniform since we have no information:

But the probability of being a zero is higher along the edges, and highest in the corners, because they have fewer neighbors that could be mines:

This explains the common strategy of opening the corners first, since the difference is quite big for this beginner board: 22% vs 51% chance of being zero. This strategy of course also applies later in the game, but then incorporates the mine probabilities from the configuration search.

We can test the different strategies by running the solver on a large number of boards and comparing the win ratios:

def estimate_win_ratio(num_runs, **board_kwargs):
wins, losses = 0, 0
for i in range(num_runs):
m = MinesweeperBoard(seed=i, **board_kwargs)
step = m.solve()
if m.dead and step == 0: # Lost on first guess
continue
else:
losses += 1
else:
wins += 1
return wins / (wins + losses)

num_runs = 10000
print(f'Win ratios for strategies over {num_runs} runs:')
print(f'Random lowest probability mine: {estimate_win_ratio(num_runs, difficulty="expert", max_solutions=2000, prob_pick_strategy="random")}')
print(f'Max zero probability: {estimate_win_ratio(num_runs, difficulty="expert", max_solutions=2000, prob_pick_strategy="prob_zero")}')

Win ratios for strategies over 10000 runs:
Random lowest probability mine: 0.4014
Max zero probability: 0.4945


Using the max zero probability strategy is clearly better, by almost 10 percentage points. Note that for these win rations I excluded runs that immediately hit mines.

Now, I don't think the algorithm is optimal quite yet. Have a look at this impasse, where we end up picking the corner square based on the reasoning above:

While opening the corner improves our chances of a zero square, perhaps we would get even more information by picking a square close to the edge, in order to loosen up the deadlock. Intuitively, we'd want to pick the square which reduces the uncertainty about the edge probabilities. We could use all the configurations produced by the search, and figure out if there is a square we can open to disambiguate between them.

We can also see that the difference in probability between the corner square and the 33% edge squares is 1%. This is such a small difference that it could make sense to pick one of those edge squares in order to split the edge region in half, divide and conquer style.

In the end, it will probably boil down to a tradeoff between minimizing mine probability and maximizing expected information gain. Exacly how to go about doing that I'll leave for a later time. For now, I'll leave you with the solving of an "expert" difficulty board:

m = MinesweeperBoard(difficulty='expert', seed=10,
visualize_constraints=False, visualize_lvl=1,
visualize_output='video')
m.solve()
m.display_video(framerate=10, controls=True, autoplay=True, loop=True, max_width='100%')


And the code for the whole thing:

import os
import math
import glob
import random
import warnings
import subprocess
from time import time
from base64 import b64encode

import cv2
import numpy as np
import PIL.Image
from IPython.display import display, HTML
import IPython.display
from matplotlib.animation import FuncAnimation
import matplotlib.pyplot as plt
from skimage.measure import label
from scipy.ndimage.morphology import distance_transform_edt

np.set_printoptions(precision=2)

IMG_SQUARE_SIZE = 20
IMAGES = {}
for name in list(range(9)) + ['bomb', 'facingDown', 'flagged']:
IMAGES[str(name)] = cv2.resize(img, (IMG_SQUARE_SIZE, IMG_SQUARE_SIZE))

def draw_text_centered(img, text, size, color, thickness=1):
font = cv2.FONT_HERSHEY_SIMPLEX
text_size = cv2.getTextSize(text, font, size, 2)[0]

# get coords based on boundary
text_x = (img.shape[1] - text_size[0]) // 2
text_y = (img.shape[0] + text_size[1]) // 2
return cv2.putText(img, text, (text_x, text_y), font, size, color,
thickness=thickness)

def count_neighbors(board):
"""
For each square, counts the number of neighboring squares that are "on".
Uses a sum convolution to count neighbors.
board: a boolean matrix or numerical 0/1 matrix
"""
return cv2.filter2D(board.astype(float), -1, np.ones((3,3)),
borderType=cv2.BORDER_CONSTANT).astype(int)

class MinesweeperBoard:
def __init__(self, width=None, height=None, num_mines=None, difficulty=None,
seed=None, max_solutions=None, prob_pick_strategy='prob_zero_near_edge',
visualize_constraints=True, visualize_lvl=0, visualize_zero_probs=None,
visualize_output='video', visualize_crop=None, visualize_frames=None,
"""
width: width of the board
height: height of the board
num_mines: number of mines on the board
difficulty:
'beginner', 'intermediate' or 'expert', if this is set, width/height/num_mines are not used
seed: the seed for randomization
max_solutions: stop the search once this many solutions have been found
prob_pick_strategy:
'random': pick one of the lowest probability mine squares randomly
'prob_zero': pick the lowest probability mine with the
highest probability of being a zero-numbered square
'prob_zero_near_edge': same as prob_zero, but pick the square nearest
an unresolved edge if there are multiple choices
visualize_constraints:
True: Displays number of neighboring mines and empty squares left
False: Displays the number of neighboring mines
visualize_lvl:
0: no visualization
1: visualize final square picks
2: visualize all search steps
visualize_zero_probs:
If True, will visualize the probability of a zero-numbered square
visualize_output:
'video': outputs video
'image': outputs individual frames
visualize_crop:
A tuple with (y, x, height, width) crop in squares to visualize
visualize_frames:
A tuple with the range of frames to visualize
visualize_iterations:
A tuple with the range of iterations to visualize
Font size of the text mask
"""
difficulties = {
'beginner': (8, 8, 10),
'intermediate': (16, 16, 40),
'expert': (24, 24, 99)
}
assert difficulty in [None, 'beginner', 'intermediate', 'expert'] # TODO: Use enum class?
assert difficulty is not None or (width is not None and height is not None and num_mines is not None)
if difficulty in difficulties:
self.width, self.height, self.num_mines = difficulties[difficulty]
else:
self.width, self.height, self.num_mines = width, height, num_mines
self.num_squares = self.width*self.height
self.max_solutions = max_solutions
assert prob_pick_strategy in ['random', 'prob_zero', 'prob_zero_near_edge'] # TODO: Use enum class?
self.prob_pick_strategy = prob_pick_strategy
assert self.num_mines < self.num_squares
assert 0 <= visualize_lvl <= 2
assert visualize_output in ['video', 'image']
self.visualize_constraints = visualize_constraints
self.visualize_lvl = visualize_lvl
self.visualize_zero_probs = visualize_zero_probs
self.visualize_output = visualize_output
self.visualize_frames = visualize_frames
self.visualize_iterations = visualize_iterations
self.visualize_crop = visualize_crop

# Generate the mine locations
if seed is not None:
np.random.seed(seed)
random.seed(seed)
self.mines = np.zeros((self.height, self.width), dtype=bool)
# NOTE: sample indices without replacement
mine_indices = random.sample(range(self.width*self.height), self.num_mines)
self.mines.ravel()[mine_indices] = True
assert self.mines.sum() == self.num_mines, (self.mines.sum(), self.num_mines)

# Add mines that look like the text
color=1, thickness=1)
# Remove mines within 2 steps of the text, so that we can see the text better
np.ones((3, 3), 'uint8'), iterations=2) > 0

# Pre-calculate a map of neighboring mine counts
self.neighboring_mine_count = count_neighbors(self.mines)

# Create an map of labeled empty regions
self.empty_regions = label(self.neighboring_mine_count == 0, connectivity=1)

# Create 2D arrays for keeping track of the state of the board and our belief about it
self.opened = np.zeros((self.height, self.width), dtype=bool)
self.flagged = np.zeros((self.height, self.width), dtype=bool)
self.neighboring_mines_left = self.neighboring_mine_count.copy()
self.neighboring_unresolved_left = 8*np.ones((self.height, self.width), dtype='uint8')
self.prob_mine = 2*np.ones((self.height, self.width), dtype=float)
self.dead = False # Set to true if we hit a mine

# Variables used for visualization and debugging
self.iteration = 0
self.frame_idx = 0

def solve(self):
""" Solves the board or dies trying """
self.t0 = time()
self.visualize() # Draw once to see the empty board

while not self.solved and not self.dead:
# Get the next square index to open
open_indices, mine_indices, *rest = self.solve_step()
prev_opened = self.opened.copy()

for open_idx in open_indices:
# Check if there's an empty region under the square
region = self.empty_regions[open_idx[0], open_idx[1]]
if region > 0:
# Dilate the region to open the neighboring squares with neighboring mine counts
reveal = cv2.dilate((self.empty_regions == region).astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1)
self.opened[reveal > 0] = True
else:
# There was no empty region underneath, just a mine count, so just reveal this square
self.opened[open_idx[0], open_idx[1]] = True

# Check if there is a mine there
if self.mines[open_idx[0], open_idx[1]]:
break

for mine_idx in mine_indices:
# Remove the mine from neighboring mine counts
ns = self.neighborhood_slice(mine_idx)

self.neighboring_mines_left[ns] -= 1
self.flagged[mine_idx[0], mine_idx[1]] = True

# Recalculate closed and unflagged neighbors
self.neighboring_unresolved_left = count_neighbors(self.unresolved)

# Clear the cached probabilities in the regions where we made picks
labels, unresolved_edges, unresolved_non_edge = rest
self.prob_mine[unresolved_non_edge] = 2
just_opened_dilated = cv2.dilate((self.opened & ~prev_opened).astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1)
for i in range(1, labels.max()+1):
search_map = (labels == i) & unresolved_edges
if (just_opened_dilated & search_map).any():
self.prob_mine[search_map] = 2 # Reset

# Reset open/mine_indices and display the new board
self.visualize()

self.iteration += 1

self.t1 = time()

def solve_step(self):
""" Returns the next board square indices to open and the
squares we want to mark as mines"""

# Now we're trying to find a configuration of mines/not mines that agrees with
# the neighboring mine counts. We split up the problem by connected components in
# the squares with non-zero neighbor count. For each component, we find the assignment
# that agrees with neigboring unopened squares. If there are multiple possible assignments
# we pick a square to open with the lowest probability of being a mine over all

# Get the neighbors of the numbered squares (i.e. the squares we want to
# find an assignment for)
has_constraints = (self.neighboring_mines_left > 0) | (self.neighboring_unresolved_left > 0)
numbered_dilated = cv2.dilate((has_constraints & self.opened).astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1)
unresolved_edges = self.unresolved & (numbered_dilated > 0)
unresolved_non_edge = self.unresolved & (numbered_dilated == 0)

# Find connected components of unresolved edges connected by constraints
# Since that numbered square represents constraints on both components,
# we have to join them in the optimization
unresolved_edges_dilated = cv2.dilate(unresolved_edges.astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1)
joined_edges = unresolved_edges | (unresolved_edges_dilated & has_constraints & self.opened)
labels, num_labels = label(joined_edges, connectivity=2, return_num=True)

# Check for simple cases, where
# 1. There are as many neighboring mines left as there are closed (unassigned) squares
#    This means all neighbors are mines
# 2. If there are no neighboring mines left, then all neighboring closed squares
#    must be empty
all_mines = (self.opened & (self.neighboring_mines_left > 0) &
(self.neighboring_mines_left == self.neighboring_unresolved_left))
all_empty = (self.opened & (self.neighboring_mines_left == 0) &
(self.neighboring_unresolved_left > 0))
if all_mines.any() or all_empty.any():
all_mines_dilated = cv2.dilate(all_mines.astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1) > 0
mine_indices = np.vstack(np.where(all_mines_dilated & self.unresolved)).T

all_empty_dilated = cv2.dilate(all_empty.astype('uint8'),
np.ones((3, 3), 'uint8'), iterations=1) > 0
empty_indices = np.vstack(np.where(all_empty_dilated & self.unresolved)).T
self.visualize(open_indices=empty_indices, mine_indices=mine_indices)
return empty_indices, mine_indices, labels, unresolved_edges, unresolved_non_edge

for i in range(1, num_labels+1):
search_map = (labels == i) & unresolved_edges
if np.count_nonzero(search_map) == 0:
continue

if not (self.prob_mine[search_map] == 2).any():
# Result is cached, so skip
continue

search_squares = self.visit_in_order(search_map)
self.visualize(lvl=1, duplicate_num_frames=5, search_squares=search_squares)
# Assignment map: -1 = no assignment, 0 = not mine, 1 = mine
assignments = -1*np.ones((self.height, self.width), 'int')
search_idx = 0
solutions = [] # keeps track of all consistent solutions found
num_search_squares = len(search_squares)
while search_idx < num_search_squares:
p = search_squares[search_idx]
ns = self.neighborhood_slice(p)

prev_assignment = assignments[p[0], p[1]]
reached_max_solutions = (self.max_solutions is not None
and len(solutions) >= self.max_solutions)
if prev_assignment == 0 or reached_max_solutions:
# We've cycled through mine/not mine assignemnts, so backtrack
self.neighboring_unresolved_left[ns] += 1
if prev_assignment == 1:
self.neighboring_mines_left[ns] += 1

assignments[p[0], p[1]] = -1
search_idx -= 1

if search_idx < 0:
# We've checked all possible solutions, so exit loop
break
self.visualize(lvl=2, assignments=assignments, search_squares=search_squares)
continue

# We cycle through mine -> not mine
new_assignment = 1 if prev_assignment == -1 else 0

if new_assignment == 0 and prev_assignment == 1:
self.neighboring_mines_left[ns] += 1

assignments[p[0], p[1]] = new_assignment
if new_assignment:
# Decrement mines_left
self.neighboring_mines_left[ns] -= 1

# No matter whether we think there's a mine or not, we decrement number
# of closed neighbors
if prev_assignment == -1:
self.neighboring_unresolved_left[ns] -= 1

# If number of mines left is negative, we're in an inconsistent state
inconsistent_mines = (self.neighboring_mines_left[ns] < 0) & self.opened[ns]
inconsistent_mines_left = inconsistent_mines.any()
# If number of closed squares is less than number of mines left, we're in an ainconsistent state
inconsistent_closed = (self.neighboring_unresolved_left[ns] < self.neighboring_mines_left[ns]) & self.opened[ns]
inconsistent_closed_left = inconsistent_closed.any()

inconsistent = np.zeros((self.height, self.width), dtype=bool)
inconsistent[ns] = inconsistent_mines | inconsistent_closed
self.visualize(lvl=2, inconsistent=inconsistent, assigning_idx=p,
assignments=assignments, search_squares=search_squares)
is_inconsistent = inconsistent_mines_left or inconsistent_closed_left

if not is_inconsistent and search_idx == num_search_squares - 1:
# We have a possible solution at the last search square, so save it
solution = assignments[search_squares[:, 0], search_squares[:, 1]]
self.visualize(lvl=2, duplicate_num_frames=5, solution=solution,
assignments=assignments, search_squares=search_squares)
solutions.append(solution)
elif not is_inconsistent:
# Not inconsistent, so progress to the next square
search_idx += 1

# Tally up the solutions and return the empty squares and mines we're 100% sure about
# If we have no such squares, we return the lowest mine probability square to be opened.
num_mine = np.zeros(len(search_squares), dtype=float)
num_not_mine = np.zeros(len(search_squares), dtype=float)
solutions_array = np.vstack(solutions)
num_mine = (solutions_array == 1).sum(axis=0)
num_not_mine = (solutions_array == 0).sum(axis=0)

num_total = num_mine + num_not_mine
sq = search_squares
self.prob_mine[sq[:, 0], sq[:, 1]] = num_mine / num_total

# Now calculate the mine probability not only the search squares, but also the
# inside squares. First, we calculate how many mines there are in the edges of
# all unresolved components, so we can subtract that (and the flagged mines) from
# the mine count

# NOTE: num_edge_mines doesn't have to be an integer, since it's possible
# that different solutions have different number of mines. It's also possible
# that some solutions have more mines than there are mines left on the board
num_mines_left = self.mines.sum() - self.flagged.sum()
num_edge_mines = min(self.prob_mine[(self.prob_mine < 2) & unresolved_edges].sum(),
num_mines_left)
if unresolved_non_edge.any():
self.prob_mine[unresolved_non_edge] = ((self.mines.sum() - num_edge_mines - self.flagged.sum())
/ unresolved_non_edge.sum())

# If there are squares with 0 probability mine, we return those and the sure mines
empty_indices = np.vstack(np.where(self.unresolved & (self.prob_mine == 0))).T
mine_indices = np.vstack(np.where(self.unresolved & (self.prob_mine == 1))).T
if len(empty_indices) == 0:
# There are no obvious squares to open, so find the lowest mine probability square
# and pick the one with the highest probability of being a zero-numbered square
# NOTE: Although the mine probability would be the same, we prefer zero-numbered
# squares because they open up 3-8+ new squares with constraints.

# Calculate the probability that each unresolved square is has zero neighboring mines
# This is calculated as the product of the probability of all squares in the neighorhood is _not_ a mine
# NOTE: we do this by a convolution in the log space, since the sum of logs equals
# the log of the product. Then we exponentiate to get the probability
prob_zero = np.zeros((self.height, self.width), dtype=float)
# NOTE: if 1-prob_mine is zero, then log(1-prob_mine) is NaN, and during the
# convolution these NaNs will spread to the neighbors. We _want_ this to happen
# so that we can set all NaNs to 0 probability of being a zero-numbered square, since
# a NaN means there is a mine neighbor
warnings.filterwarnings('ignore') # Ignore the NaN warning
prob_zero = np.exp(cv2.filter2D(
np.log(1 - self.prob_mine), -1, np.ones((3,3)), borderType=cv2.BORDER_CONSTANT))
warnings.resetwarnings()
prob_zero[np.isnan(prob_zero)] = 0

self.visualize(duplicate_num_frames=5)
if self.visualize_zero_probs:
self.visualize(lvl=1, duplicate_num_frames=5, prob_zero=prob_zero)

# Now we pick the lowest probability mine to open, but with the highest
# probability of a zero underneath (no neighboring mines)
is_min_mine_prob = self.prob_mine == self.prob_mine[self.unresolved].min()
is_max_zero_prob = prob_zero == prob_zero[is_min_mine_prob].max()
is_min_mine_max_zero = is_min_mine_prob & is_max_zero_prob
if self.prob_pick_strategy == 'random':
best_choices = np.vstack(np.where(is_min_mine_prob)).T
elif self.prob_pick_strategy == 'prob_zero':
best_choices = np.vstack(np.where(is_min_mine_max_zero)).T
elif self.prob_pick_strategy == 'prob_zero_near_edge':
distance_from_edge = distance_transform_edt(~unresolved_edges)
is_one_square_away = distance_from_edge <= math.sqrt(2)
if (is_min_mine_max_zero & is_one_square_away).any():
best_choices = np.vstack(np.where(is_min_mine_max_zero & is_one_square_away)).T
print('Here')
else:
best_choices = np.vstack(np.where(is_min_mine_max_zero)).T
#is_min_dist = distance_from_edge == distance_from_edge[is_min_mine_max_zero].min()
#best_choices = np.vstack(np.where(is_min_mine_max_zero & is_min_dist)).T

best_choice = random.choice(best_choices)
empty_indices = np.array([best_choice])
self.visualize(duplicate_num_frames=5, open_indices=empty_indices,
mine_indices=mine_indices)
else:
self.visualize(duplicate_num_frames=10, open_indices=empty_indices,
mine_indices=mine_indices)
return empty_indices, mine_indices, labels, unresolved_edges, unresolved_non_edge

@property
def solved(self):
return (np.array_equal(self.mines, self.flagged)
and (self.opened | self.flagged).all())

def visit_in_order(self, search_map):
""" Returns the indices of search_map > 0 in order, starting at the edges
of the components if there are any, and then in a BFS fashion """
left_to_visit = search_map.copy()
ordered_search_squares = []
while left_to_visit.any():
search_squares = np.vstack(np.where(left_to_visit)).T
queue = []
for square in search_squares:
ns = self.neighborhood_slice(square)
num = search_map[ns].sum()
# NOTE: if there <= 2 squares in this slice, then it has to be a start/end point
# If there are 3 or more, it means square is in the center of a path
if num <= 2:
queue.append(square)
break

if len(queue) == 0:
# There were no start/end points, so must be a loop. Pick any square
queue.append(search_squares[0])

while len(queue) > 0:
s = queue.pop(0)
left_to_visit[s[0], s[1]] = False
ordered_search_squares.append(s)
ns, offset = self.neighborhood_slice(s, return_offset=True)
neighbors = np.vstack(np.where(search_map[ns])).T + offset
l1_neighbors, l2_neighbors = [], []
for n in neighbors:
if not left_to_visit[n[0], n[1]]: continue
if np.linalg.norm(n - s) > 1: l2_neighbors.append(n)
else: l1_neighbors.append(n)

left_to_visit[n[0], n[1]] = False
for n in l1_neighbors: queue.append(n)
for n in l2_neighbors: queue.append(n)

return np.array(ordered_search_squares)

def draw_frame(self, **kwargs):
""" Draw the current board / solver state as an image """
if not self.visualize_constraints:
return self._draw_board(**kwargs)

# Draw normal board and constraints board side-by-side with a white space between
normal = self._draw_board(**kwargs)
constraints = self._draw_board(visualize_constraints=True, **kwargs)
I = IMG_SQUARE_SIZE
crop = self.visualize_crop or (0, 0, self.height, self.width)
img = 255*np.ones((I*crop[2], I*(crop[3]*2+1), 3), dtype='uint8')
img[:, :I*crop[3]] = normal
img[:, I*(crop[3]+1):] = constraints
return img

@property
def unresolved(self):
""" Returns the unresolved squares, i.e. the ones that have neither been
opened nor flagged as mines """
return ~self.opened & ~self.flagged

def neighborhood_slice(self, p, return_offset=False):
"""
Convenience function to get a numpy slice object for the neighborhood around a
point p _within_ the board dimensions. Can return the offset to the board origin
"""
ns = np.s_[max(p[0]-1, 0):min(p[0]+2, self.height),
max(p[1]-1, 0):min(p[1]+2, self.width)]
if return_offset:
offset = np.array([p[0]+(0 if p[0] == 0 else -1),
p[1]+(0 if p[1] == 0 else -1)])
return ns, offset
return ns

def visualize(self, lvl=1, duplicate_num_frames=1, **kwargs):
"""
Visualizes current state of the solver and either outputs it as an HTML image
element, or saves the frame for future video creation.
"""
if self.visualize_lvl < lvl:
return

not_in_frame_range = (self.visualize_frames is not None and
(self.frame_idx < self.visualize_frames[0] or
self.frame_idx >= self.visualize_frames[1]))
not_in_iteration_range = (self.visualize_iterations is not None and
(self.iteration < self.visualize_iterations[0] or
self.iteration >= self.visualize_iterations[1]))

if not_in_frame_range or not_in_iteration_range:
self.frame_idx += 1
return

img = self.draw_frame(**kwargs)
if self.visualize_output == 'image':
if self.visualize_frames is None:
print(f'Iteration {self.iteration} frame {self.frame_idx}')
IPython.display.display(PIL.Image.fromarray(img[..., ::-1]))
else:
for i in range(duplicate_num_frames):
cv2.imwrite(f'board{self.frame_idx:04}-{i:02}.png', img)

self.frame_idx += 1

def _draw_board(self, visualize_constraints=None, open_indices=[], mine_indices=[],
search_squares=[], solution=None, assignments=None, assigning_idx=None,
inconsistent=None, prob_zero=None):
I = IMG_SQUARE_SIZE
crop = self.visualize_crop or (0, 0, self.height, self.width)
img = np.zeros((crop[2] * I, crop[3] * I, 3), 'uint8')

def _highlight_square(y, x, color=0, thickness=2):
y_crop = y - crop[0]
x_crop = x - crop[1]
s = np.s_[y_crop*I:(y_crop+1)*I, x_crop*I:(x_crop+1)*I]
t = thickness
smaller = np.s_[y_crop*I+t:(y_crop+1)*I-t, x_crop*I+t:(x_crop+1)*I-t]

def _mark_img(img, color=0):
img = img.copy()
img[I//3:I-I//3, I//3:I-I//3, :] = color
return img

for y in range(crop[0], crop[0]+crop[2]):
for x in range(crop[1], crop[1]+crop[3]):
y_crop = y - crop[0]
x_crop = x - crop[1]
s = np.s_[y_crop*I:(y_crop+1)*I,
x_crop*I:(x_crop+1)*I]

if self.opened[y, x]:
if self.flagged[y, x]: img[s] = IMAGES['flagged']
elif self.mines[y, x]: img[s] = IMAGES['bomb']
else:
# Display mines left in upper left corner, and closed left in lower right
if visualize_constraints:
square = IMAGES['0'].copy()
if not (self.neighboring_mines_left[y, x] == 0 and
self.neighboring_unresolved_left[y, x] == 0):
tl_crop = np.s_[:I//2, :I//2]
br_crop = np.s_[I//2:, I//2:]
mines_left = self.neighboring_mines_left[y, x]
size = 0.2 if mines_left < 0 else 0.4 # make it smaller for -1 so it fits
square[tl_crop] = draw_text_centered(
square[tl_crop], str(mines_left), size, color=(0, 0, 160))
square[br_crop] = draw_text_centered(
square[br_crop], str(self.neighboring_unresolved_left[y, x]), 0.4, color=(255, 0, 0))
img[s] = square
else:
img[s] = IMAGES[str(self.neighboring_mine_count[y, x])]

if inconsistent is not None and inconsistent[y, x]:
_highlight_square(y, x, color=(0, 0, 255))
else:
if self.flagged[y, x] or (assignments is not None and assignments[y, x] == 1):
# If it's a text mine, flip the channels so that the flags are blue
# instead of red, to increase visual contrast
img[s] = IMAGES['flagged'][..., ::-1]
else:
img[s] = IMAGES['flagged']
elif assignments is not None and assignments[y, x] == 0:
img[s] = _mark_img(IMAGES['facingDown'])
else:
if prob_zero is not None and prob_zero[y, x] != 0:
text = str(int(round(100*prob_zero[y, x])))
img[s] = draw_text_centered(IMAGES['facingDown'].copy(), text,
size=0.3, color=0)
elif self.prob_mine is not None and self.prob_mine[y, x] < 2:
text = str(int(round(100*self.prob_mine[y, x])))
img[s] = draw_text_centered(IMAGES['facingDown'].copy(), text,
size=0.3, color=0)
else:
img[s] = IMAGES['facingDown']

# Draw various highlights
for open_idx in open_indices:
_highlight_square(*open_idx, color=(0, 255, 0))

for mine_idx in mine_indices:
_highlight_square(*mine_idx, color=(0, 0, 255))

for search_idx in search_squares:
color = 255 if solution is None else (0, 255, 0)
_highlight_square(*search_idx, color=color, thickness=2)

if assigning_idx is not None:
_highlight_square(*assigning_idx, color=0)

return img

@property
def time(self):
if None in [self.t0, self.t1]: return None
return self.t1 - self.t0

def display_video(self, framerate=2, autoplay=False, loop=False, controls=False,
width=None, max_width=None):
"""
Displays a video of the step by step board solution by using the images
writted to disk and combining them with ffmpeg, finally displaying it as an HTML
video element
"""
if self.visualize_output != 'video':
return

# Call ffmpeg to create video
command = [
'ffmpeg', '-y', '-framerate', str(framerate), '-pattern_type', 'glob', '-i', '"board*.png"',
'-c:v', 'libx264', '-r', '30', '-pix_fmt', 'yuv420p', 'tmp.mp4'
]
subprocess.call(' '.join(command), shell=True, stderr=subprocess.STDOUT)

# Remove the images
for filename in glob.glob('board*.png'):
os.remove(filename)

# Create a data url with the video data
with open('tmp.mp4', 'rb') as f:
# Remove the video
os.remove('tmp.mp4')

width_str = 'width="'+width+'"' if width is not None else ""
max_width_str = 'style="max-width:'+max_width+'"' if max_width is not None else ""
# Display the video HTML element
html = (f'<video {"controls" if controls else ""}'
f'       {width_str}'
f'       {max_width_str}'
f'       {"autoplay" if autoplay else ""}'
f'       {"loop" if loop else ""}>'
f'   <source src="{data_url}" type="video/mp4">'
f'</video>')
display(HTML(html))


# Are parents picking less common names?

I think we all have the gut feeling that parents nowadays try to pick more unique names, or at least not names that are too common. Instead of relying on a gut feeling or anectdata, let's check!

Being Swedish, of course I'm mostly interested in Swedish name statistics, and luckily SCB (the central statistics bureau) provides an Excel spread sheet with the frequency statistics of the top 100 names for boys and girls from 1998 to 2017. Let's download it:

! wget -O stats.xlsx https://www.scb.se/hitta-statistik/statistik-efter-amne/befolkning/amnesovergripande-statistik/namnstatistik/pong/tabell-och-diagram/nyfodda--efter-namngivningsar-och-tilltalsnamn-topp-100/Namn-1998-/


Now we can read the spreadsheet with Python and pandas/numpy (I bet it would be easier to just do this in Excel, but I'm not an Excel-ninja...) and collect the statistics.

Let's load the Excel file and look at the data:

import pandas as pd
import numpy as np

START_YEAR, END_YEAR = 1998, 2017
GENDERS = ['girls', 'boys']

data = pd.DataFrame(columns=['year', 'name', 'gender', 'count', 'percent'])

f = open('stats.xlsx', 'rb')
for year in range(START_YEAR, END_YEAR+1):
for gender_idx, gender in enumerate(GENDERS):
sheet_idx = 2*(year - START_YEAR) + gender_idx + 1
count_col = 'Antal' if 'Antal' in df.columns else 'Antal bärare'
counts = df[count_col].values[1:]
name_col_idx = list(df.columns).index(count_col) - 1
names = df.iloc[1:, name_col_idx].str.strip() # NOTE: need to strip spaces
# When there are ties in count, there will be more than 100 rows. Keep the top 100
counts, names = counts[:100], names[:100]
years = [year]*len(counts)
genders = [gender]*len(counts)
data = data.append(
pd.DataFrame(data={'year': years, 'gender': genders, 'name': names, 'count': counts,
'percent': counts.astype(float) / counts.sum()}),
sort=True)

print(data)

    count gender    name   percent  year
1    1468  girls    Emma  0.043336  1998
2    1171  girls   Julia  0.034568  1998
3    1043  girls    Elin  0.030790  1998
4    1037  girls  Amanda  0.030613  1998
5    1006  girls   Hanna  0.029697  1998
..    ...    ...     ...       ...   ...
96    145   boys    Thor  0.004173  2017
97    142   boys  Milian  0.004087  2017
98    141   boys    Levi  0.004058  2017
99    141   boys    Vide  0.004058  2017
100   139   boys     Neo  0.004000  2017

[4000 rows x 5 columns]


Let's plot what the top 100 names looked like in 1998 and 2017:

import seaborn as sns
import matplotlib.pyplot as plt

for year in [1998, 2017]:
fig, ax = plt.subplots(figsize=(15, 5))
girls_year = data[(data['year'] == year) & (data['gender'] == 'girls')]
ax = sns.barplot(x='name', y='percent', data=girls_year,
color='blue')
ax.set_xticklabels(ax.get_xticklabels(), rotation=90);
ax.set(ylim=(0, 0.05));
ax.set_title(f'Girls {year}');