The Riddler, 2017-09-22 edition

After an extended 1+ month break, we’re back with a vengeance. Here’s a link to the problems. No code this week.

Riddler Express

We know the width of the top rectangle since we already have its area and length: \frac{24}{4} = 6. From here, we can determine the width of the lower rectangle by adding the two width differences: 6 + 3 + 2 = 11. This implies that the height of the bottom rectangle is \frac{44}{11} = 4, giving us our final answer of 4 inches1.

Riddler Classic

Let the height and width of the unknown rectangle be l and w, respectively. Now, we can derive two separate equations from the top-left and bottom-right rectangles:

(1)   \begin{align*} (11 - h) \times w &= 32 \\ (14 - w) \times h &= 45 \end{align*}

This is a system of equations with two variables and two unknowns which we can solve for using the quadratic equation (or, if you’re lazy like me, WolframAlpha):

(2)   \begin{align*} (h, w) &= (\frac{11}{2}, \frac{64}{11}) \\ (h, w) &= (\frac{45}{7}, 7) \end{align*}

The third rectangle will now allow us to determine which of the prior two is the correct solution. The first solution set (unknown area computes to \frac{11}{2} \times \frac{64}{11} = 32) gives us \frac{34}{11 - \frac{11}{2}} \approx 6.18 as the width of the upper-right rectangle, which is valid since \frac{64}{11} + 6.18 < 14. The second solution set (unknown area computes to \frac{45}{7} \times 7 = 45) gives us \frac{34}{11 - \frac{45}{7}} \approx 7.44 as the width, which is invalid since 7 + 7.44 > 14. Hence, the area of the unknown rectangle is 32 square inches.

1 Shame on you, FiveThirtyEight, for not using the metric system!

The Riddler, 2017-08-11 edition

Here’s a link to the problems. I usually try to solve Riddlers with code if I can, but this week’s problems were relatively straightforward, so no code was necessary.

Riddler Express

The most efficient way to do this is to represent each staffer as an unsigned 7-bit binary number, with each bit representing knowledge/no-knowledge of one of the seven fake stories that you and your chief of staff have come up with:

    \[ \begin{tabular}{|c|c c c c c c c|}   \hline              & S0     & S1     & S2     & S3     & S4     & S5     & S6     \\ \hline   Staffer 0  & 0      & 0      & 0      & 0      & 0      & 0      & 0      \\   Staffer 1  & 0      & 0      & 0      & 0      & 0      & 0      & 1      \\   Staffer 2  & 0      & 0      & 0      & 0      & 0      & 1      & 0      \\   Staffer 3  & 0      & 0      & 0      & 0      & 0      & 1      & 1      \\   \vdots     & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\   Staffer 99 & 1      & 1      & 0      & 0      & 0      & 1      & 1      \\   \hline \end{tabular} \]

Armed with this, we can pinpoint the miscreant staffer by tracking each story’s status. For example, if no stories were leaked, we know that staffer 0 is the culprit since she had no knowledge of any stories. Similarly if only S0 (story 0) was leaked, the leaker must be staffer 64 (64 in decimal = 1000000 in binary), since he was the only one that was told only S0. Thus, by intelligently distributing distinct combinations of 7 stories to all 100 staffers, we can determine who the pesky leaker is.

In any case, don’t forget to watch your chief-of-staff as well 😉

Riddler Classic

Imagine gluing together five tetrahedrons as shown on the FiveThirtyEight webpage (displayed below for convenience):

However, instead of looking at the resulting object from top-down, imagine holding it flush in your palm and raising it to eye level such that your new perspective is horizontal. If you then flatly slice the object along the edge closest to you (parallel to your palm), you can easily see that the slice is made of five isosceles triangles – one for each tetrahedron. The figure below should help visualize this:

The blue vertical plane shows were our horizontal cut was made. This plane will allow us to determine the central angle created by the five-tetrahedron setup. To compute this angle, we first need to determine the length of the slice as projected onto a face opposite the edge closest to us:

Armed with all side lengths of each slice (\frac{\sqrt{3}s}{2}, \frac{\sqrt{3}s}{2}, and s), we can now find the central angle:

Basic trigonometry tells us that the central angle is 2*sin^{-1}(\frac{1}{\sqrt{3}})\approx70.5288\dots degrees. There are five of these altogether, bringing the total central angle to approximately 352.6439 degrees. Thus, the empty space has an angle of 7.3561 degrees (0.1284 radians).

The Riddler, 2017-08-04 edition

Here’s a link to the problems and a link to the code on Github.

Riddler Express

A fun way to solve this problem is through the use of a Monte Carlo simulation: The code for this is relatively straightforward:

from __future__ import division, print_function

from multiprocessing import Pool
import sys

import numpy as np


def simulate(n_kids):

    # create array to track kids + teacher
    had_potato = np.zeros(n_kids + 1, dtype=np.bool)
    pos = n_kids // 2

    # move the position by either -1 or 1 until complete
    while np.sum(had_potato) < n_kids:
        had_potato[pos] = True
        pos += np.random.randint(2) * 2 - 1
        pos %= had_potato.size

    return np.argmin(had_potato)


if __name__ == "__main__":

    if len(sys.argv) >= 2:
        n_kids = int(sys.argv[1])
    else:
        n_kids = 30

    # initialize random number generator
    np.random.seed()

    # simulate for "enough" times
    n_sim = int(1e6)
    pool = Pool(processes=8)
    winners = pool.map(simulate, [n_kids] * n_sim)
    probs = np.bincount(winners) / float(n_sim)

    print("Win probabilities")
    print(probs)

For each simulation run, I maintain a list of positions that the potato has “touched”. At each iteration, we select a random direction to pass the potato, encoded as -1 or 1. This occurs continuously until only one child (the winner) remains. To speed up the simulation, I used a pool1 of worker processes to run several distinct simulations in parallel. The result of a single run is below:

[ 0.034032  0.03448   0.033488  0.03324   0.0334    0.033272  0.033864
  0.03368   0.033328  0.032984  0.032872  0.033432  0.032656  0.032552
  0.033936  0.        0.033576  0.033336  0.03268   0.034328  0.033424
  0.03312   0.032728  0.033016  0.03312   0.032848  0.033464  0.033424
  0.033296  0.033552  0.032872]

Running this for a million iterations, we see that each child actually has the same win probability, i.e. 1/30! The teacher’s position (index 15 in the code above) can never win since that’s the position the potato starts off at.

Riddler Classic

This problem can also be solved with a Monte Carlo simulation. I took a stab at an analytical solution first, drawing out the graph of bathroom-user interactions as a finite state machine. I got stuck trying to determine the “long-term” probability of each state, though I am fairly certain there is indeed an analytical solution (I seem to have forgotten all the material I learned in my stats classes at Stanford ¯\_(ツ)_/¯). Back to Monte Carlo simulations!

For the time being, we can ignore the fact that the bathroom is occupied exactly 50% of the time – that just helps normalize our prior probabilities. Instead, simply encoding the states of the bathroom (user, sign state, actual state) during each function call is enough:

from __future__ import division, print_function

import sys

import numpy as np


def simulate(prob, state):

    # make new user if bathroom is unoccupied
    if not state[1]:
        state[0] = np.random.random()

    # update actual state
    state[1] = not state[1]

    # update sign state
    if state[0] < prob:
        pass
    elif state[0] < 2 * prob:
        state[2] = True
    else:
        state[2] = state[1]


if __name__ == "__main__":

    if len(sys.argv) >= 2:
        prob_co = float(sys.argv[1])
    else:
        prob_co = 1 / 3.0

    # initialize random number generator
    np.random.seed()

    # prob := probability that person totally ignores the sign
    # prob := probability that person forgets sign upon leaving
    prob = (1 - prob_co) / 2

    # (user type, actual state, sign state)
    state = [0, False, False]

    # track # of sign state count and # of times correct
    n_sign = [0, 0]
    n_valid = [0, 0]

    # simulate for "enough" times
    n_sim = int(1e6)
    for _ in range(n_sim):
        simulate(prob, state)

        n_sign[state[2]] += 1
        if state[1] == state[2]:
            n_valid[state[2]] += 1

    print("P(occ|sign_occ) = " + str(n_valid[1] / n_sign[1]))
    print("P(vac|sign_vac) = " + str(n_valid[0] / n_sign[0]))

As shown, the simulate function simply runs one bathroom entrance or exit per iteration, keeping track of the user type between two consecutive runs as necessary. I ran the code with n_sim = int(1e9) and xrange instead of range to avoid unnecessary memory consumption (Python 2 is still my preferred interpreter):

P(occ|sign_occ) = 0.624993716521
P(vac|sign_vac) = 0.749989913933

With some obvious rounding, we arrive at probabilities of 0.625 and 0.75. Hence our final answer of 5/8, 3/4.

1 I have an 4-core processor with hyperthreading, bringing the total “CPU count” to 8, hence processes=8; you can check yours with python -c "import multiprocessing; print(multiprocessing.cpu_count())".

The Riddler, 2017-07-28 edition

Here’s a link to the problems and a link to the code on Github.

Riddler Express

Not much to explain here. I figured from previous “you-versus-other-Riddlers” questions, there’d around 2000 to 2500 submissions, with a fair percentage of them being trolls who will submit 1 just for the lolz. Given this, I threw game theory out of the window and prayed for luck-of-the-draw. I figured a mid-to-high two-digit prime number might be a winner; a bit more number crunching and coin flipping resulted in my final guess of 67.

Riddler Classic

I could not think of an “elegant” solution off the top of my head, so I resorted to a brute-force approach. Our good old friend recursion becomes helpful here:

from __future__ import print_function

import math
import sys


def divs_and_mults(num, maxval):

    valid = set()

    # compute divisors
    mid = math.ceil(math.sqrt(num))
    for n in range(1, int(mid) + 1):
        if num % n == 0:
            valid.add(n)
            div = num / n
            if div != n:
                valid.add(div)
            
    # compute multiples
    mult = 2 * num
    while mult <= maxval:
        valid.add(mult)
        mult += num

    return valid


def valid_next(chain, valid, maxval):

    if len(chain) == 0:
        return set(range(1, maxval + 1))
    else:
        return valid[chain[-1]] - set(chain)


def build_recursive(chain, valid, maxval):

    longest = list(chain)

    # loop through all valid next links
    for n in valid_next(chain, valid, maxval):
        chain.append(n)
        result = build_recursive(chain, valid, maxval)
        if len(result) > len(longest):
            longest = result
        chain.pop()

    return longest


def longest_chain(maxval):

    # compute valid "next" links for all values
    valid = {}
    for n in range(1, maxval + 1):
        valid[n] = divs_and_mults(n, maxval)

    return build_recursive([], valid, maxval)


if __name__ == "__main__":

    if len(sys.argv) >= 2:
        maxval = int(sys.argv[1])
    else:
        maxval = 100

    assert maxval > 2, "invalid maximum value"

    chain = longest_chain(maxval)
    print("Found chain of length {0}.".format(len(chain)))
    print(chain)

Allow me to explain my reasoning. As with any recursive program, I looked to minimize the amount of computation required within the actual recursive call. Thus, I precomputed all divisors and multiples for each number from 1 to 100 and used these precomputed values to create a set of “valid” next links during each recursive call. The rest was easy: maintain the longest known chain and remove links from the “current” chain once all possible links are exhausted. This brute-force method works, but is unfortunately incredibly inefficient: running this with maxval = 30 takes a whopping 2.5 minutes on a single 3.4GHz i7 core, with exponentially increasing runtime as maxval grows bigger.

Following this debacle, I tried replacing the recursion with a single loop in an attempt to improve efficiency. This allowed me to collapse functions valid_next, build_recursive, and longest_chain into a single function:

def longest_chain(maxval):

    # compute valid "next" links for all values
    valid = {}
    for n in range(1, maxval + 1):
        valid[n] = divs_and_mults(n, maxval)

    # maintain a stack to store "recursive" data
    longest = []
    chain = []
    stack = []

    links = range(maxval, 0, -1)
    while True:

        # last set of links was exhausted, back up and try again
        if not links:
            if len(chain) > len(longest):
                longest = list(chain)
            if len(chain) == 0:
                break
            chain.pop()
            links = stack.pop()

        # add new link to chain
        else:
            chain.append(links.pop())
            stack.append(links)
            links = valid[chain[-1]] - set(chain)

    return longest

Easy enough, but this still took way too long – around 1.5 minutes for maxval = 30 – to run, making the problem intractable for maxval = 100 (where’s a Hadoop cluster when you need one). Undeterred, I decided to run the program that I had written for a select set of lower maxvals, hoping to see a pattern:

#    result              example chain
5    4  possibilities    [2, 4, 1, 3]
10   9  possibilities    [4, 8, 1, 5, 10, 2, 6, 3, 9]
15   13 possibilities    [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9]
20   17 possibilities    [7, 14, 2, 8, 16, 4, 12, 6, 18, 9, 3, 15, 5, 10, 20, 1, 19]
25   21 possibilities    [9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 1, 11, 22, 2, 14, 7, 21, 3, 15, 5, 25]
30   26 possibilities    [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
31   26 possibilities    [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
32   27 possibilities    [11, 22, 1, 13, 26, 2, 32, 16, 8, 24, 12, 6, 18, 9, 27, 3, 21, 7, 14, 28, 4, 20, 10, 30, 15, 5, 25]
33   28 possibilities    [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]
34   28 possibilities    [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]

One pattern jumps out very quickly: prime numbers greater than half of maxval are nowhere to be found unless they are at the beginning or end of the chain. The reason for this becomes obvious once we treat each number as a node in a graph: its only possible link to the rest of the chain is the number 1. Once we reach maxval = 34, our chain starts to miss 17 and 34 as well. These are missing for a similar reason: their only link to the rest of the chain is 1 and 2, and 2 has already been used to link other values. For maxval = 100, a similar argument can be made for 31, 62, and 93 as well. Thus, our longest possible chain for maxval = 100 will exclude 31, 37, 41, 43, 47, 53, 59, 61, 62, 67, 71, 73, 74, 79, 82, 83, 86, 89, 93, 94, and 97, which gives us a longest possible length of 79.

DISCLAIMER: This is very much an educated guess. Wish I had a bit more time to figure this one out – it’s an interesting Riddler and deserves a bit more attention.

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