Haven’t made a post in a while1, so figured I’d break the trend with something fun. FiveThirtyEight is a website I frequent to read about politics, sports, and economics through a pure statistical perspective. Although I don’t necessarily agree with all of the conclusions 538 staff derive in their articles, it’s refreshing to see an analytical approach to issues in that are often dominated by opinion and non-empirical thought processes.
For the past couple of months, I’ve been taking cracks at 538’s “The Riddler” series. Many of them are challenging, and they serve as a nice break from the rigors of startup life. A good number of these problems (especially the “Classic” ones) can be solved by computational means, i.e. Monte Carlo simulations, numerical optimization, etc. I’ve decided to start a series on solving Riddler problems with code whenever possible, the first of which you’re reading right now.
Note: I may skip some weeks due to a busy work schedule, or if the problems are intractable from a computational perspective. There may also be instances where I mess up and get the wrong answer; feel free to correct and/or shame me in the comments.
Here’s a link to the problems for this week. Be sure to read them before proceeding.
This is a classic combinatorics problem. Specifically, we’ll utilize binomial coefficients for
n = 11. These coefficients are often written as:
(pronounced n-choose-k). In plain English, denotes the number of ways
k objects can be selected from
n options. Thus, this week’s Riddler Express is relatively straightforward: for the number of ways a ballot can be cast and for the number of ways six candidates can advance. Here’s how it’s done in Python:
from scipy.misc import comb def lazy_method(n, k): # thank you, SciPy return comb(n, k)
But this is a rather dull method of doing things. Let’s pretend like we don’t know about combinatorics or the
scipy.misc.comb function. We could then approach this problem recursively. Imagine a bag of 11 candidates, of which you randomly select two. For the first candidate, you have 11 options to choose from, leaving 10 options for the second candidate (and 9 options for the third candidate, etc…). This makes a total of possibilities. Similarly, selecting four candidates out of 11 would result in possibilities.
However, these options are ordered, which means that selecting some candidate X followed by some other candidate Y is separate from selecting candidate Y followed by candidate X. To remedy this, we can divide the number of options for selecting each candidate by the number of ways that selected candidate can be fit into one of the remaining slots. This effectively turns our ordered count into an unordered count.
Code for this is as follows:
def recursive_method(n, k): assert k >= 0, "k must be non-negative" assert n >= k, "too few to choose from" # base case if k == 0: return 1 # recursive call return n / k * recursive_method(n-1, k-1)
Running both pieces of code generates the same (aforementioned) results: 232 ways to cast a ballot and 462 ways for six candidates to move forward.
I enjoyed this week’s classic, and found it more challenging than last week’s. They key to solving this problem is treating it as a two-player game: your opponent is trying to maximize her chances of winning given knowledge of your spy, while you are trying to win the game given your opponent’s soldier distribution. Your optimal strategy can be solved for using integer programming, but that still doesn’t answer the question of what your opponent’s optimal strategy is.
As such, I’ll approach this problem from an intuitive perspective. We’ll start with the obvious: there are a total of 55 castle-points available, which means that you need 28 or more points to win. To help create battle plans, I’ve written a Python-based GUI using Qt4. An Excel spreadsheet would’ve done the job just fine, but there’s no fun in that, is there?
from PyQt4 import QtCore from PyQt4 import QtGui class BattlePlanner(QtGui.QMainWindow): def __init__(self, parent=None): super(BattlePlanner, self).__init__(parent) # create table table = QtGui.QTableWidget(12, 2) headers = ("Opponent", "Yours") table.setHorizontalHeaderLabels(headers) # create row for each castle for i in range(10): n_points = i + 1 name = QtGui.QTableWidgetItem("Castle " + str(n_points)) table.setVerticalHeaderItem(i, name) table.setItem(i, 0, QtGui.QTableWidgetItem("0")) table.setItem(i, 1, QtGui.QTableWidgetItem("0")) # set headers for last two rows name = QtGui.QTableWidgetItem("Total") table.setVerticalHeaderItem(10, name) name = QtGui.QTableWidgetItem("Points") table.setVerticalHeaderItem(11, name) # create row items for i in range(2): for j in range(2): item = QtGui.QTableWidgetItem() item.setFlags(QtCore.Qt.ItemIsSelectable | QtCore.Qt.ItemIsEnabled) table.setItem(i + 10, j, item) # action handler table.itemChanged.connect(self.update) self.table = table self.setCentralWidget(table) self.setWindowTitle("Battle planner") self.resize(self.sizeHint()) def update(self): try: total = [0, 0] points = [0, 0] for n in range(10): val_opp = int(self.table.item(n, 0).text()) val_mine = int(self.table.item(n, 1).text()) # compute # of points n_points = n + 1 if val_opp > val_mine: points += n_points elif val_opp < val_mine: points += n_points else: points += n_points / 2 points += n_points / 2 # compute # of soldiers deployed total += val_opp total += val_mine # set results of the battle self.table.item(10, 0).setText(str(total)) self.table.item(10, 1).setText(str(total)) self.table.item(11, 0).setText(str(points)) self.table.item(11, 1).setText(str(points)) except ValueError: self.clear() def clear(self): for i in range(2): for j in range(2): self.table.item(i+10, j).setText("")
Using the code shown above, we can start off trying an evenly distributed spread for your opponent:
However, this is clearly suboptimal - there's absolutely no reason for you to attack the low-value castles when the high-value castles are defended with the same number of soldiers. Alternatively, your opponent could also choose to stack the high-value castles:
Again, this is suboptimal - you now get to secure the low-value castles almost entirely for free. Alternatively, if your opponent stacks the low-value castles (which is an absolutely asinine decision, by the way), you get the secure the high-value castles.
It turns out that the optimal configuration for your opponent is one that takes into consideration the relative value of each castle. Specifically, castles worth more points should have proportionally more soldiers assigned to them. This sounds obvious, but may not be immediately evident without a bit of experimentation. Armed with this newfound knowledge, an optimal solution for your opponent would be to assign soldiers proportional to each castle's value:
This results in 56 soldiers. As a player in this game, you could also choose to pick a different set of castles to attack (such as castles 1-7, which would result in 28 points), but the result will remain the same: a minimum of 56 soldiers is needed to guarantee a win.
1 I remember saying a while ago that I was going to try writing posts more often. This is my first post in over a year; so much for that goal ¯\_(ツ)_/¯.