Skip to main content

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.

Advanced Strategies

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:
      if m.dead:
        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)

# Load the minesweeper tiles
IMG_SQUARE_SIZE = 20
IMAGES = {}
for name in list(range(9)) + ['bomb', 'facingDown', 'flagged']:
  img = cv2.imread(f'minesweeper/{name}.png')
  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,
               visualize_iterations=None, visualize_mask_text=None,
               visualize_mask_text_size=0.7):
    """
      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
      visualize_mask_text: 
        Masks out squares using text
      visualize_mask_text_size: 
        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
    self.visualize_mask_text = visualize_mask_text
    self.visualize_mask_text_size = visualize_mask_text_size

    # 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)

    self.text_mask = None
    if self.visualize_mask_text is not None:
      # Add mines that look like the text
      mask = np.zeros_like(self.mines, dtype='uint8')
      mask = draw_text_centered(mask, self.visualize_mask_text, self.visualize_mask_text_size,
                                color=1, thickness=1)
      # Remove mines within 2 steps of the text, so that we can see the text better
      mask_dilated = cv2.dilate(mask.astype('uint8'),
                                np.ones((3, 3), 'uint8'), iterations=2) > 0
      self.mines[mask_dilated > 0] = False
      self.mines[mask > 0] = True
      self.text_mask = mask > 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]]:
            self.dead = True
            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:
          # Add back a mine
          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
        # to start with
        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]
      mask = np.zeros(img.shape[:2], dtype=bool)
      mask[s] = True
      mask[smaller] = False
      img[mask, :] = color

    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 self.text_mask is not None and self.text_mask[y, x]:
              # 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:
      data_url = "data:video/mp4;base64," + b64encode(f.read()).decode()
    # 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
        df = pd.read_excel(f, sheet_name=sheet_idx, header=6, usecols='B:D')
        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}');