July 11th, 2018

Father’s Day, Perf and PII

For Father’s Day this year my daughter presented me with a sheet of paper containing a variety of “my dad…” statements e.g.

  • My dad’s favorite color is:__________
  • My dad always says:__________

My thoughts drifted to The Newlywed Game as I wondered how many of the questions I would have answered with the same exact answer she had given. She definitely got my favorite color. The more open ended questions all had “correct” answers e.g.

  • My dad’s job is: to work to make money for our house
  • My dad and I like to: eat ice cream sundaes

Then I began to wonder if I would have been able to answer the questions about her with the same accuracy. I’m fairly certain I know her favorite color; I’m pretty sure I know her favorite food (when not qualified with “healthy”).

For better or worse, I next started to think of it from a performance review angle. Over the last 12 years I’ve worked at companies that have fairly rigorous performance review cycles and every now and then I’m surprised by what my peers and/or manager think I do well, could improve, as well as what things they felt were worth mentioning in general and what they omitted. For example, I may have spent a lot of time providing what I thought were insightful comments in design documents, taking great care to word them so as not to provoke knee jerk defensive reactions, only to have none of my co-workers mention it. Meanwhile they might mention they appreciated how open I was to being interrupted at my desk to answer random questions and that they wished I didn’t jump on production issues so they had more chances to learn how to handle them.

So while it’s certainly true my daughter loves to eat ice cream sundaes and I’d be hard pressed to say no if one were offered to me, I wonder what other things she thinks we both like to do together. What if she thought about it for a while and nothing else came up?

There were two topics that came up multiple times, pizza and juggling. I suppose it’s not the end of the world if those are the most prominent things that come to her mind when she thinks of me since they’re both things I enjoy as activities with her. However, they’re not the top two characteristics that (I think) define me; so I’ve been feeling pressure to alter the time I spend with her so she has a chance to discover other things that are more important to me than pizza and juggling (though perhaps I should spend some time learning how to juggle pizzas).

Looking at the links I’ve chosen to display on this blog, there are 3 related to hiking. My daughter has been very resistant to going hiking, she still often refuses to walk when we walk the dog (instead riding in a stroller). On my birthday she threw such a fit regarding going for a short hike, partially because it was just what I wanted to do that we aborted. It would have been her first actual hike. We have been trying to work through this need to defy and control for some time now as she did the same thing for Mother’s Day and also my wife’s birthday. For Father’s Day we tried again and she agreed to go hiking and actually enjoyed it. Perhaps over time it will supplant pizza or juggling when she thinks of me.

The last unwonted association I’ll make between Father’s Day and my job revolves around personally identifiable information or PII. It’s a topic that comes up often at work…I shudder to think how much effort was put into companies regarding General Data Protection Regulation (GDPR) and over time I’ve become less and less open about things I post. As a kid BBSes and AOL were my first introduction to the ability to connect with arbitrary people all over the world (other than a few random digit dialing pranks via a landline telephone). Shortly after I discovered HTML followed by animated GIFs then JavaScript, setting up presences on http://members.aol.com and GeoCities. One of the pages I had on AOL was called Ask The Singularity. No one in their right mind should fill out that form, even though inspecting the source it’s clear none of the data was transmitted out of the client’s browser. Yet, 20+ years ago plenty of people probably did. In fact that page won a Worst of the Web award on 1997-08-13 for whatever that’s worth…

In this post, I did not include my favorite color because it’s possible that has been used as security question on one or more websites I might have an account with. I haven’t included my daughter’s name (though I have revealed my child’s current gender). I must really be getting old because I yearn for the time when there both seemed to be less to fear about being open online and I was less concerned about the potential damage.

May 4th, 2018

Crossover Dates

My wife and I recently crossed a round number year anniversary of the date we first met in person. It occurred to me that it was actually more than half my lifetime and (in hindsight) thought that “crossover date” might have been another moment in time worth paying attention to.

Below is a quick and dirty form that will calculate the crossover date given a start date e.g. my birth date, and an event date e.g. when I first met my wife. Any textual representation of a date that the JavaScript Date Constructor recognizes should work e.g. 2018-05-04 for May 4, 2018.

Start Date: Event Date:
Crossover Date:

In my case, the crossover date of meeting my wife was three weeks before this most recent round number year anniversary. According to Vanguard there’s an 80%+ chance that I’ll live long enough to reach the crossover date of my daughter being born i.e. I’ll have spent more years alive with her than without. Sadly (without some significant advances in veterinary medicine) it will not be possible to reach the crossover date of when we adopted our dog.

August 25th, 2017

The Sneaky Snacky Squirrel

Previously I wrote about a board game our daughter enjoys playing, Hi Ho! Cherry-O. One of the things that makes it somewhat uninteresting to adults is the lack of any applicable strategy; luck completely determines the outcome. Another game she enjoys is The Sneaky Snacky Squirrel. While luck determines much of the outcome, there are also two opportunities to strategize, when the result of a spin allows one to:

  1. Pick 1 or 2 acorns of needed color(s).
  2. Steal an acorn of a needed color from another player.

Our daughter understands what colors she needs to pick but not that there might be a better strategy than just picking her favorite color or always picking from mama’s log. When playing with her it’s also difficult to test if a non-naive strategy actually matters since she doesn’t appreciate it when people take acorns from her (unless there’s no other option). It’s also difficult to round up other adults to play a bunch of rounds of the game…so once again a simulator is the best option.

For the picking strategy, instead of just picking any color acorn(s) needed, it might be more advantageous to pick the color(s) that the most people already have. That way if another player has an opportunity to steal, it’s less likely they’ll be able to steal from you.

For the stealing strategy, instead of just picking any color acorn needed from any player, it again might be more advantageous to pick the color that the most people have, from the player with the most acorns. That way again if another player has an opportunity to steal, it’s less likely they’ll be able to steal from you and you’ll make it take longer for the player closest to winning to win.

In order to do this I created 4 “strategies”, 2 for picking: BasicPickStrategy and PickColorsLeastLikelyToBeStolenStrategy and then 2 for stealing: BasicStealStrategy and StealColorsLeastLikelyToBeStolenStrategy. Each player needs one of each strategy, which conveniently results in 4 players to cover all possible combinations:

  • Player 0: BasicPickStrategy, BasicStealStrategy
  • Player 1: BasicPickStrategy, StealColorsLeastLikelyToBeStolenStrategy
  • Player 2: PickColorsLeastLikelyToBeStolenStrategy, BasicStealStrategy
  • Player 3: PickColorsLeastLikelyToBeStolenStrategy, StealColorsLeastLikelyToBeStolenStrategy

I then had the program play 1,000,000 games between the 4 players, randomizing the order of the players:
$ ./sneaky_snacky_squirrel.py 1000000

The output was:
mean,std,wins
22.121029,8.412456,Counter({3: 296961, 1: 289553, 0: 207117, 2: 206369})

That means on average it took 22.1 turns with a standard deviation of 8.4 to complete a game and Player 3 won 29.7% of the time, Player 1 won 29.0% of the time, Player 0 won 20.7% of the time and Player 2 won 20.6% of the time. So it seems that a non-naive stealing strategy makes the most difference and a non-naive picking strategy also has a small positive effect. There are certainly other strategies, if you’d like to try them just add a new strategy to the code below. I’ve also posted unit tests so you can be more confident things are augmented properly.

#!/usr/bin/python

import itertools
import random
import sys
from collections import Counter
from collections import defaultdict
from math import sqrt


class Color(object):
  """Enumeration of all possible colors"""
  COLORS = set(range(0, 5))
  BLUE, GREEN, PURPLE, RED, YELLOW = COLORS


class SpinResult(object):
  """Enumeration of all possible spin results."""
  RESULTS = set(range(0, 10))
  BLUE, GREEN, PURPLE, RED, YELLOW, WIND, PICK_ONE, PICK_TWO, STEAL, SLEEP = (
      RESULTS)


def GetColorCounts(player, all_players):
  """Count all the colors all the other players have.

  Args:
    player: The player to exclude from the counts.
    all_players: All the players in the game.

  Returns:
    A dict of color->count.
  """
  color_counts = defaultdict(int)
  for other_player in all_players:
    if player == other_player:
      continue  # Don't count player's colors.
    for color in other_player.log:
      color_counts[color] += 1
  return color_counts


class BasicPickStrategy(object):
  """A naive acorn picking strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    self.all_players = all_players

  def pick(self, player, num_acorns=1):
    """Pick the first acorn color needed.
    
    Args:
      num_acorns: The number of acorns to pick.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    while num_acorns > 0 and available_colors:
      player.log.add(available_colors.pop())
      num_acorns -= 1


class BasicStealStrategy(object):
  """A naive acorn stealing strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    self.all_players = all_players

  def steal(self, player):
    """Steal the first acorn color needed from the first viable player..
    
    Args:
      player: The player performing the steal.
    """
    if player.filled_log():
      return
    for other_player in self.all_players:
      if player == other_player:
        continue
      available_colors = other_player.log.difference(player.log)
      if available_colors:
        picked_color = available_colors.pop()
        player.log.add(picked_color)
        other_player.log.remove(picked_color)
        break


class PickColorsLeastLikelyToBeStolenStrategy(BasicPickStrategy):
  """A less naive acorn picking strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    BasicPickStrategy.__init__(self, all_players)

  def pick(self, player, num_acorns=1):
    """Pick the most prevalent color acorns; they're least likely to be stolen.
    
    Args:
      num_acorns: The number of acorns to pick.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    color_counts = GetColorCounts(player, self.all_players)
    # Pick the most prevalent color(s).
    for color in sorted(color_counts, key=color_counts.get, reverse=True):
      if num_acorns > 0 and color in available_colors:
        player.log.add(color)
        available_colors.remove(color)
        num_acorns -= 1
    # If colors owned by other players are exhasted, pick any needed colors.
    while num_acorns > 0 and available_colors:
      player.log.add(available_colors.pop())
      num_acorns -= 1


class StealColorsLeastLikelyToBeStolenStrategy(BasicStealStrategy):
  """A less naive acorn stealing strategy."""

  def __init__(self, all_players):
    """Constructor.
  
    Args:
      all_players: A list of all Player objects playing the game.
    """
    BasicStealStrategy.__init__(self, all_players)

  def steal(self, player):
    """Steal most prevalent color acorn from the player with the most acorns.
    
    Args:
      player: The player performing the steal.
    """
    if player.filled_log():
      return
    available_colors = Color.COLORS.difference(player.log)
    color_counts = GetColorCounts(player, self.all_players)
    players = sorted(self.all_players, key=lambda p: len(p.log),
        reverse=True)
    for color in sorted(color_counts, key=color_counts.get, reverse=True):
      if color in available_colors:
        player.log.add(color)
        for p in players:
          if color in p.log:
            p.log.remove(color)
            break


class Player(object):
  """Represents a player."""

  def __init__(self, pick_strategy_cls, steal_strategy_cls, number):
    """Constructor.
  
    Args:
      pick_strategy_cls: A class to use for picking acorns.
      steal_strategy_cls: A class to use for stealing acorns.
      number: A unique identifier.
    """
    self.log = set()
    self.pick_strategy_cls = pick_strategy_cls
    self.steal_strategy_cls = steal_strategy_cls
    self.pick_strategy = None
    self.steal_strategy = None
    self.number = number

  def reset(self, all_players):
    """Reset the state of the player.

    Args:
      all_players: A list of Player objects playing the game.
    """
    self.log = set()
    self.pick_strategy = self.pick_strategy_cls(all_players)
    self.steal_strategy = self.steal_strategy_cls(all_players)

  def filled_log(self):
    """Returns True if the player has filled their log, otherwise False."""
    return len(self.log) == len(Color.COLORS)

  def spin(self, value):
    """Process a spin of the wheel.

    Args:
      value: The value of the spin.

    Returns:
      The spun value.
    """
    if value < len(Color.COLORS):
      # Add the selected colored acorn to player's log.
      self.log.add(value)
    elif value == SpinResult.WIND:  # Lose all acorns.
      self.log = set()
    elif value == SpinResult.PICK_ONE:  # Pick any colored acorn.
      self.pick_strategy.pick(self)
    elif value == SpinResult.PICK_TWO:  # Pick any 2 colored acorn.
      self.pick_strategy.pick(self, 2)
    elif value == SpinResult.STEAL:  # Steal an acorn from any other player.
      self.steal_strategy.steal(self)
    elif value == SpinResult.SLEEP: # Skip player's turn.
      pass
    return value

  def __str__(self):
    return  '[%d, %s, %s]' % (self.number, self.pick_strategy_cls.__name__,
        self.steal_strategy_cls.__name__)


def play(players):
  """Plays a single game.

  Args:
    players: List of players playing the game.

  Returns:
    The number of spins performed to complete the game and the winning player.
  """
  num_spins = 0
  for player in players:
    player.reset(players)
  game_over = False
  winner = None
  while not game_over:
    for player in players:
      value = player.spin(random.randint(0, 9))
      num_spins += 1
      game_over = player.filled_log()
      if game_over:
        winner = player
        break

  return num_spins, winner


def mean(data):
  """Compute the mean of data."""
  n = len(data)
  return sum(data) / float(n)


def stddev(data):
  """Compute the standard deviation of data."""
  c = mean(data)
  ssd = sum((x - c) ** 2 for x in data)
  v = ssd / (len(data) - 1)
  return sqrt(v)


def trials(players, num_games):
  """Play games and compute basic statistics.
  
  Args:
    players: A list of Player objects playing the game.
    num_games: The number of games to play when computing statistics.

  Returns:
    Mean number and standard deviation of spins needed to finish a game.
  """
  game_result = []  # (number of_spins, winning player #)
  while num_games > 0:
    random.shuffle(players)
    game_result.append(play(players))
    num_games -= 1
  spin_results = [x[0] for x in game_result]
  winners = [x[1].number for x in game_result]
  return (mean(spin_results), stddev(spin_results), Counter(winners))


if __name__ == '__main__':
  """Play a bunch of games and output the results."""
  num_games = int(sys.argv[1])
  pick_strategies = [BasicPickStrategy, PickColorsLeastLikelyToBeStolenStrategy]
  steal_strategies = [BasicStealStrategy,
      StealColorsLeastLikelyToBeStolenStrategy]
  strategy_combinations = list(
      itertools.product(pick_strategies, steal_strategies))
  players = []
  for i, strategies in enumerate(strategy_combinations):
    players.append(Player(strategies[0], strategies[1], i))
  mean_spins, stddev_spins, win_counts = trials(players, num_games)
  print 'mean,std,wins'
  print '%f,%f,%s' % (mean_spins, stddev_spins, win_counts)

Here are some unit tests:

#!/usr/bin/python

import random
import unittest

from sneaky_snacky_squirrel import BasicPickStrategy
from sneaky_snacky_squirrel import BasicStealStrategy
from sneaky_snacky_squirrel import Color
from sneaky_snacky_squirrel import PickColorsLeastLikelyToBeStolenStrategy
from sneaky_snacky_squirrel import Player
from sneaky_snacky_squirrel import SpinResult


class FakePickStrategy(object):

  def __init__(self, all_players):
    self.pick_called_with = (None, None)

  def pick(self, player, num_acorns=1):
    self.pick_called_with = (player, num_acorns)


class FakeStealStrategy(object):

  def __init__(self, all_players):
    self.steal_called_with = None

  def steal(self, player):
    self.steal_called_with = player


class TestPickColorsLeastLikelyToBeStolenStrategy(unittest.TestCase):

  def setUp(self):
    self.players = set()
    self.player_1 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakeStealStrategy, 1)
    self.player_2 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakePickStrategy, 2)
    self.player_3 = Player(PickColorsLeastLikelyToBeStolenStrategy,
      FakePickStrategy, 3)
    self.players.add(self.player_1)
    self.players.add(self.player_2)
    self.players.add(self.player_3)
    self.player_1.reset(self.players)
    self.player_2.reset(self.players)
    self.player_3.reset(self.players)

  def testPick(self):
    random_color = random.randint(0, len(Color.COLORS) - 1)
    self.player_2.log.add(random_color)
    self.player_3.log.add(random_color)
    random_color_1 = None
    while True:
      random_color_1 = random.randint(0, len(Color.COLORS) - 1)
      if random_color_1 != random_color:
        self.player_2.log.add(random_color_1)
        break
    self.player_1.pick_strategy.pick(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertTrue(random_color in self.player_1.log)
    self.player_1.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player_1.log))
    self.player_1.pick_strategy.pick(self.player_1, num_acorns=2)
    self.assertEqual(2, len(self.player_1.log))
    self.assertTrue(random_color in self.player_1.log)
    self.assertTrue(random_color_1 in self.player_1.log)


class TestBasicPickStrategy(unittest.TestCase):

  def testPick(self):
    strategy = BasicPickStrategy(None)
    player = Player(None, None, None)
    self.assertEqual(0, len(player.log))
    strategy.pick(player)
    self.assertEqual(1, len(player.log))
    strategy.pick(player, num_acorns=4)
    self.assertEqual(5, len(player.log))
    strategy.pick(player)
    self.assertEqual(5, len(player.log))


class TestBasicStealStrategy(unittest.TestCase):

  def testSteal(self):
    self.players = set()
    self.player_1 = Player(FakePickStrategy, BasicStealStrategy, 1)
    self.player_2 = Player(FakePickStrategy, BasicStealStrategy, 2)
    self.players.add(self.player_1)
    self.players.add(self.player_2)
    self.player_1.reset(self.players)
    self.player_2.reset(self.players)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(0, len(self.player_1.log))
    self.assertEqual(0, len(self.player_2.log))
    random_color = random.randint(0, len(Color.COLORS) - 1)
    self.player_2.log.add(random_color)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertEqual(0, len(self.player_2.log))
    self.assertTrue(random_color in self.player_1.log)
    self.player_2.log.add(random_color)
    self.player_1.steal_strategy.steal(self.player_1)
    self.assertEqual(1, len(self.player_1.log))
    self.assertEqual(1, len(self.player_2.log))
    self.assertTrue(random_color in self.player_1.log)
    self.assertTrue(random_color in self.player_2.log)


class TestPlayer(unittest.TestCase):

  def setUp(self):
    self.player = Player(FakePickStrategy, FakeStealStrategy, 1)
    self.player.reset(None)

  def testFilledLog(self):
    self.player.log.add(Color.BLUE)
    self.assertFalse(self.player.filled_log())
    self.player.log.update(Color.COLORS)
    self.assertTrue(self.player.filled_log())
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinSpecificColor(self):
    value = random.randint(0, len(Color.COLORS) - 1)
    self.player.spin(value)
    self.assertEqual(1, len(self.player.log))
    self.assertTrue(value in self.player.log)
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinWind(self):
    self.player.log.add(random.randint(0, len(Color.COLORS) - 1))
    self.assertEqual(1, len(self.player.log))
    self.player.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player.log))
    self.player.log.update(Color.COLORS)
    self.assertEqual(len(Color.COLORS), len(self.player.log))
    self.player.spin(SpinResult.WIND)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinPickOneColor(self):
    self.player.spin(SpinResult.PICK_ONE)
    self.assertEqual(
        (self.player, 1), self.player.pick_strategy.pick_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinPickTwoColors(self):
    self.player.spin(SpinResult.PICK_TWO)
    self.assertEqual(
        (self.player, 2), self.player.pick_strategy.pick_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertIsNone(self.player.steal_strategy.steal_called_with)

  def testSpinSteal(self):
    self.player.spin(SpinResult.STEAL)
    self.assertEqual(self.player, self.player.steal_strategy.steal_called_with)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)

  def testSpinSleep(self):
    self.player.spin(SpinResult.SLEEP)
    self.assertEqual(0, len(self.player.log))
    self.assertEqual((None, None), self.player.pick_strategy.pick_called_with)
    self.assertIsNone(self.player.steal_strategy.steal_called_with)


if __name__ == '__main__':
  unittest.main()