The Riddler, 2017-07-21 edition

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.

Riddler Express

This is a classic combinatorics problem. Specifically, we’ll utilize binomial coefficients for n = 11. These coefficients are often written as:

    \[ \binom{n}{k} = \frac{n!}{(n-k)!k!} \]

(pronounced n-choose-k). In plain English, \binom{n}{k} denotes the number of ways k objects can be selected from n options. Thus, this week’s Riddler Express is relatively straightforward: \binom{11}{3} + \binom{11}{2} + \binom{11}{1} + \binom{11}{0} = 232 for the number of ways a ballot can be cast and \binom{11}{6} = 462 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 11 \times 10 = 110 possibilities. Similarly, selecting four candidates out of 11 would result in 11 \times 10 \times 9 \times 8 = 7920 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.

Riddler Classic

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[0] += n_points
                elif val_opp < val_mine:
                    points[1] += n_points
                else:
                    points[0] += n_points / 2
                    points[1] += n_points / 2

                # compute # of soldiers deployed
                total[0] += val_opp
                total[1] += val_mine

            # set results of the battle
            self.table.item(10, 0).setText(str(total[0]))
            self.table.item(10, 1).setText(str(total[1]))
            self.table.item(11, 0).setText(str(points[0]))
            self.table.item(11, 1).setText(str(points[1]))

        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 ¯\_(ツ)_/¯.