The 538 Riddler:New Casino Game

Welcome to my weekly look at 538’s The Riddler. Happily my answer to last week’s riddle proved to be correct once again, and I was happy to see some commenters who came to the same conclusions. Thanks for reading and commenting.

Due to a lack of time with Easter and all, I’m not very confident of my answer to this week’s Riddler, but I’ll let you decide. Here’s the riddle:

Suppose a casino invents a new game that you must pay $250 to play. The game works like this: The casino draws random numbers between 0 and 1, from a uniform distribution. It adds them together until their sum is greater than 1, at which time it stops drawing new numbers. You get a payout of $100 each time a new number is drawn.

For example, suppose the casino draws 0.4 and then 0.7. Since the sum is greater than 1, it will stop after these two draws, and you receive $200. If instead it draws 0.2, 0.3, 0.3, and then 0.6, it will stop after the fourth draw and you will receive $400. Given the $250 entrance fee, should you play the game?

Specifically, what is the expected value of your winnings?

Okay, when I read that part it seemed like this was going to be a no-brainer, but then Ollie added:

[Editor’s note: You know how sometimes your boss/teacher asks you not to bring your laptop to a meeting/class, and you’re all like, “Jeez, how am I gonna tweet during the meeting/class, then?” Well, I’m going to pull rank and ask that you don’t bring laptops to this Riddler. Next week I will highlight — nay, celebrate! — the elegant, pencil-and-paper solutions over the brutal, cold, silicon ones. We’re all on the honor system with one another, right? RIGHT?]

No computers! Pencil and paper? Egads. Okay, so I did a little bit of working this out and I came up with an answer I thought might be right. First of all, I assumed that you are guaranteed to see at least 2 numbers, because with all the real numbers between 0 and 1, the chances of getting 1 exactly are one over infinity, or zero. So the minimum amount you are going to lose in this game is $50. And it seems to me that the chances of seeing a third number are 50%, since the average value of the first number will be 0.5 and the chances that the second number will be greater than 0.5 is… 0.5, or 50%.

Okay, so right away we see that there’s a 50% chance we lose $50 (-$250 + $200), and a 50% chance that we win $50 (-$250 + $300), with the possibility of more money to come. This is a wonderful casino game; I would very much like to find the casino that offers it. A game like this might explain how somebody could bankrupt a casino. (Sad!)

So we have a 50% chance of seeing only 2 numbers and losing $50. What are the chances of seeing only 3 numbers? Well, I figure if 2 random numbers are below 1, then there’s a 2/3 chance that the 3rd number will break the ceiling. So 2/3 of what is remaining (1/2) is 1/3. So 1/2 the time we see 2 and only 2 numbers and 1/3 of the time we see 3 and only 3 numbers, and now we have 1/6 (1/2 – 1/3) remaining.

Chance of only 2 numbers: 1/2. 1 – 1/2 = 1/2 remaining.
* 2/3  =
Chance of only 3 numbers: 1/3. 1/2 – 1/3 = 1/6 remaining.
* 3/4 =
Chance of only 4 numbers: 1/6 * 3/4 = 1/8. 1/6 – 1/8 = 1/24 remaining.
* 4/5 =
Chance of only 5 numbers: 1/24 * 4/5 = 1/30. 1/24 – 1/30 = 1/120 remaining.
* 5/6 =
Chance of only 6 numbers: 1/120 * 5/6 = 1/144.

And so on.

So to get the Expected Value (EV) we can take the odds of each payout * its value and get:

$-50/2 + $50/3 + $150/8 + $250/30 + $350/144 = $21.18

Plus some increasingly smaller numbers for seeing 7, 8, 9, 10? numbers.

Ok, now that we got our EV answer, let’s cheat! (If you don’t want to see whether a computer confirms or disproves my EV answer, stop reading here.)

I wrote some code in Go (are you sick of Go yet, because I am not.)

package main

import (
	"fmt"
	"math/rand"
)

func doFloatTrial() int {
	total := 0.0
	numbers := 0
	
	for {
		numbers++
		total += rand.Float64()
		if total >= 1.0 {
			break;
		}
	}
	return numbers
}


func main() {

	trials := 1000000
	
	var results []int
	
	cash := 0.0
	
	for i := 0; i < trials; i++ {
		cash -= 250.0
		numbers := doFloatTrial()
		cash += 100.0 * float64(numbers)
		for a := len(results); a <= numbers; a++ {
			results = append(results, 0)
		}	
		results[numbers]++
	}

	fmt.Printf("EV = %.3f\n", cash / float64(trials));
	for i := 0; i < len(results); i++ {
		fmt.Printf("Results[%d] = %d (%.2f) \n", i, results[i], float64(trials)/float64(results[i]))
	}

}

 

And here’s the output:

EV = 21.826
Results[0] = 0 (+Inf) 
Results[1] = 0 (+Inf) 
Results[2] = 499604 (2.00) 
Results[3] = 334041 (2.99) 
Results[4] = 124717 (8.02) 
Results[5] = 33341 (29.99) 
Results[6] = 6939 (144.11) 
Results[7] = 1157 (864.30) 
Results[8] = 184 (5434.78) 
Results[9] = 15 (66666.67) 
Results[10] = 2 (500000.00)

Hurray! Our EV from the code is $21.83 and we can see that the odds of drawing each count of numbers is (with variance) what we had calculated by hand. Math! Follow this link to run the code yourself in your browser.

Thanks for reading. I’m not 100% sure of this one so I look forward to better approaches to this problem in the comments.

Conducting Technical Interviews, Part II: The Whiteboard

Last week I shared some thoughts about interviewing software engineers and some basic do’s and don’t’s for the interviewer. In this post I will concentrate on one of the more recently controversial aspects of the process: the whiteboard interview.

As I said last week, a lot of people really hate whiteboard interviews, and they have some valid reasons for not liking them. (My thoughts are kind of like the Winston Churchill quote: “Democracy is the worst form of government except for all those others that have been tried from time to time.”) These reasons include, but are not limited to:

  • Nobody writes code on a whiteboard so why should we evaluate people on a skill that they never do?
  • Writing code on a whiteboard makes people nervous and more likely to make mistakes, so it’s a terrible way to evaluate people.
  • Whiteboard interviews favor confident people with good presentation skills, not necessarily good coders.
  • There are all sorts of posts, and even entire books, written about how to do well on whiteboard interview questions.
  • Whiteboard interviews are prone to bias, rewarding candidates who resemble the interviewer instead of candidates who would perform well in the job.

Okay, so I don’t necessarily disagree with any of those points, but the thing is, a lot of those statements are also true for just about any type of interview. If you are interacting with the candidate in any way, candidates who are confident and poised will tend to do better than other candidates. That has nothing to do with a whiteboard. Interviewers are prone to bias regardless of whether they are reading a resume, or reviewing an application, or having a one-on-one conversation, or conducting a whiteboard interview. To be sure, interviewers need to guard against all those things, but I don’t think they are more or less associated with whiteboard exercises.

I should also say that I myself have had some really embarrassing experiences with whiteboard interviews as a candidate. I have completely bombed some interviews. It can happen to anyone, or at least anyone only as skilled as myself. This isn’t a case of me thinking, well, I am good at this thing so I’m looking for other people who are good at this thing. But I think that experience has given me some insight as to what to look for and a little bit of empathy.

The strongest argument against whiteboards would be that nobody writes code on a whiteboard, and this is absolutely true. Some companies prefer to give candidates a problem to be worked on at home; some have candidates do a joint coding exercise with potential teammates. Blizzard Entertainment has candidates do a joint coding project with other candidates, which I feel is just crazy, but you can’t argue with their results, I guess. My concern with take-home exercises or joint coding exercises is that you’re kind of putting all your eggs in one basket. When I give a whiteboard exercise, I’m not the only one doing so. We have several people giving them. It’s possible that someone could bomb my portion and do well enough in another session to get an offer. With a coding project, you’re probably getting one (larger, yes, but still solitary) piece of data to make a judgement on.

At Carbine we did sort of a pseudo-whiteboard exercise. Instead of a whiteboard, we had candidates type into a plain text editor (Notepad++) that was projected onto a screen that everyone could see. That solved the problem of bad penmanship but I think it had other drawbacks. For one, I can’t do my awesomely terrible curly brace squiggles in a text editor, and that’s actually something I want to do to try to make the candidate more comfortable. More importantly, the presence of an actual text editor seems to make candidates pay even more attention to things I don’t care about like making sure their brackets line up or semi-colons. Also, you can’t draw in a text editor.

The great thing about whiteboards is that if you want to draw a Venn diagram, you just… draw a Venn diagram. If you want to outline a tree structure, draw a tree structure. Finally, and this might just be my perception, people who are typing don’t seem as talkative as people who are using a whiteboard. Something about typing seems to focus more attention on that task, whereas drawing on a whiteboard seems to allow people to still talk. And I am mostly interested in what they are saying as they draw diagrams and write sloppy code on the whiteboard. So, yeah, I use the whiteboard.

One other reason for continuing to use whiteboards will sound really terrible, an appeal to authority or perhaps a bit of cargo cult logic: Google and Amazon still use them. Now, doing something just because someone else does it is not a great reason, but I know a couple things about Google: one, they are obsessive about measuring things. And two, they used to ask “lateral thinking” type questions and they stopped because their metrics showed that there was no correlation between those types of questions and whether someone was a good employee or not.

(An example of a lateral thinking question: “A man rides an elevator down from his 10th floor apartment every day. When he comes home from work, he rides up to the 5th floor and walks the remaining five stories to his apartment, unless it has been raining or there are other people in the elevator, in which case he rides all the way. Explain why.” Don’t ask that question; it won’t help you hire good engineers.)

So Google’s continued use of whiteboards suggest to me that they still have some value, but the real reason I use them is because my own experience has led me to trust them. I find value in them, because I’ve had good results. If they don’t work for you, then don’t use them on my account. The important thing is that you have a set of questions you want to answer about the candidate and a method of getting those answers. Whether that is whiteboard questions, take home projects, joint coding exercises, or whatever works for you, as long as you are comfortable with that process and you are getting good results, that’s what you should use.

So those are my basic thoughts about whiteboards and why I still use them, despite the legitimate concerns that people have about them. As I said in Part I, if you design the very best possible interview process, you will still be left with incomplete information. Whiteboard questions might be the worst way to evaluate engineers, except for all the others.

Okay, so that’s about a thousand words and I still haven’t given an example of an actual whiteboard question yet. I have several questions that I use in interviews, but I’m not going to tell you what they are because… I still use them. Also, at least three of them are whiteboard questions that I myself have been given by other companies at one time, and it would be rude of me to post answers here. So I’m going to share one that I made up, and I think is pretty good, but I don’t ever plan on actually asking a candidate.

Imagine you are given some number of integer arrays, each with some number of integers in them. I need a function that will return all the integers, in order, that appear in one, and only one, of these arrays.

I will then draw a Venn diagram that looks something like this:

venn_setintersection

 

And I will draw (after apologizing for my horrible curly braces!) an example of the data that might be passed to this function:

{2, 4, 6, 10, 30}

{3, 6, 9, 15, 30}

{5, 10, 15, 25, 30}

And my expected result: {2, 3, 4, 5, 9, 25}

Then I hand them the marker and say, “go.” Usually what happens next is that they stand at the whiteboard and stare at it. After about 2 seconds I’ll say, “Oh, and by the way, if you stare silently at the whiteboard for 10 minutes and then write out a perfect solution, that would be really impressive but I would much rather you think out loud so I can get a feel for how you’re thinking about this problem.”

So, if you are thinking to yourself, “wait, wait, that’s not enough information” then you are exactly right. I have been deliberately vague in defining this problem because I want to get an answer to one of my questions about this candidate: “Did she ask clarifying questions?” There are several questions that could be asked about this problem as I have defined it. First, are the input arrays always sorted? (Yes.) Are there ever duplicate values in any of the input arrays? (Nope.) Are the sizes of the input arrays always the same? (No.) Can I modify the input arrays? (Hmm, let’s say no.) What language should I use? (Your choice.) How about Haskell? (Um… no.) So hopefully the candidate will ask at least one of these questions or possibly some other questions.

(Note that while I will often be deliberately vague in defining a whiteboard question, I won’t mislead the candidate. I don’t do trick questions. I’m not trying to stump anyone.)

If the candidate asks one of those questions, I will respond with “good question!” and give them the answer. I really want to reward them for asking a good question and hope they will continue to do so. You’re doing great, keep it up. Also, I get to make a little plus in my notebook.

So if they don’t ask any of these questions and just start writing code I’ll observe for a bit to see if they are operating under the correct assumptions. If they are, then I’ll let them go, but if I think they might not be, I’ll interrupt and say, “oh, I should have said that the input arrays are sorted,” or whatever. I phrase that deliberately to make it my fault that I didn’t give them all the information. Hey, we’re all human here; relax, you’re doing fine.

So if they don’t ask a clarifying question is that a deal breaker? No, not even close. It’s definitely a plus if they do, but it’s just one piece of information, especially if the assumptions they have made all turn out to be correct. (The way I’ve written out the problem implies the answer to those questions, but it’s better to confirm them.)

As soon as they start writing code I get an opportunity to answer another one of my questions, “Did he ‘define the contract’ (API)”? Basically I’m looking for the function signature for the code about to be written. This is really important because it defines what the customer (in this case, me) wants from the program and what the engineer is promising to deliver. Nailing this down is really important. I’ve had candidates just start writing code with some variable definitions and a for loop. When this happens I will stop them and say, “let’s write the function declaration first.”

Depending on the problem this can lead to some interesting questions and discussions. Should the output be a return value or a pointer/reference parameter? Should any of the parameters be constant and why/why not? You can sometimes get a feel for a candidate’s experience level how this API is defined. Again, be cautious; it’s one data point, not a deal breaker if they screw this up. They could be trying something clever to impress you or they could just have a brain freeze; it happens.

For this particular problem, let’s assume that they come up with a function declaration that looks like this:

void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)

This is C++ of course, using the standard template library. UMI stands for Union Minus Intersection, which is kind of clumsy but okay. We’re going to accept a pointer to an array of constant int arrays, the number of arrays, and a reference to an out array parameter. Is this the best possible function declaration? Probably not, but I’m using it because it is convenient for showing different approaches to solving the problem.

Okay, so let’s assume that your candidate starts drawing and talking and after 10 minutes or so comes up with something like this:

void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
    out.clear();
    for(int i = 0; i < arrayCount; i++)
    {
        const vector<int> &a = arrays[i];
        for(auto ai = a.begin(); ai != a.end(); ai++)
        {
            bool duplicate = false;
            for(int k = 0; k < arrayCount; k++)
            {
                if(k == i)
                    continue;
                const vector<int> &a2 = arrays[k];
                for(auto ki = a2.begin(); ki != a2.end(); ki++)
                {
                    if(*ai == *ki)
                    {
                        duplicate = true;
                    }
                }
            }
            if(!duplicate)
            {
                out.push_back(*ai);
            }
        }
    }
    std::sort(out.begin(), out.end());
}

 

Okay, so good news is that we’ve answered one question, “Did she get a valid solution?” affirmatively here. This code will run and it will get the right answer. That’s not insignificant. Sadly, many candidates you interview will not get a valid solution to the problem you are presenting, so something like this isn’t the worst thing you’ll see. That said, it’s not great.

This is an n2 solution, where n is the total number of items in all the arrays. Now, for the small data set that I’ve given in my example, this will run in 0.0 milliseconds. No problem. But as n grows…. yeah, things get messy.

So now we can start to answer some of our other questions, “could he have a discussion about complexity?” Ask the candidate what the runtime complexity in big-O notation of this solution is. Can he tell you it is n2? Does he understand that is not desirable? I’ve had candidates tell me they don’t know all the big-O notations for common algorithms by heart, and I’m like, that’s fine, that’s easily found. But I’ve also had candidates tell me that they don’t really care about big-O notation, and that’s… not as fine. I mean, it’s a weird thing to say to an interviewer because obviously I asked about it so I probably care.

So I often get n2 or similar type answers to whiteboard problems, and I will ask, “how can we improve this answer?” We’ll talk about it some more and I will often give them enough hints to get to a better answer. Sometimes they will offer improvements on the solution they’ve already provided. For example, in the solution above, the candidate might suggest breaking out of the innermost for loop when the inner value being tested exceeds the outer value. That’s a pretty good improvement, but it’s only an incremental change. It doesn’t fundamentally change the runtime complexity of the solution; it will still be n2. Do they understand that? There’s a lot of room for discussion here and a lot of information about the candidate that can be discerned.

So would this solution be a deal breaker? Again, no. A lot of candidates will go right to the naive solution because they want to get a working, valid solution on the board. I’ve had really good engineers say they always start with the naive solution and use it as a test case to confirm their trickier, more optimal solutions. The important thing is that they should be able to understand why the complexity matters.

Okay, now let’s look at another possible solution to this problem, this time using an ordered map.

void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
    map<int, int> counts;

    out.clear();
	for(int a = 0; a < arrayCount; a++)
	{
		for(auto i = arrays[a].begin(); i != arrays[a].end(); i++)
		{
			auto mitr = counts.find(*i);
			if(mitr == counts.end())
				counts[*i] = 1;
			else
				mitr->second++;
		}
	}

	for(auto mitr = counts.begin(); mitr != counts.end(); mitr++)
	{
		if(mitr->second == 1)
			out.push_back(mitr->first);
	}
}

 

Okay, so this code is much better. It dumps all the values from all the arrays into a map and keeps track of all their counts. Afterwards, it adds any value with a count of one to the out array. The runtime complexity of this solution is n log n, which is a major improvement.

Again, if someone comes up with this solution, we can answer all those questions that we answered before. Does she understand why the complexity is n log n? Can she have a discussion about it?

So if I got this solution I’d still ask the candidate, can we make this solution better? This is going to be harder to do; it’s not as low-hanging fruit as the naive solution. The key to getting a better solution here is to point out that the arrays are already sorted, so putting them all into a map is duplicating effort. We don’t need to do that. Instead we can look at the “frontier” (the first element) of all our arrays and look for the lowest value. If that lowest value is unique, then we can add it to the out array and increment the iterator on that array. If it is not unique, we increment all the iterators for that value and look at the next lowest value. We do this until we have looked at all elements in all arrays.

This is the kind of problem where I think the whiteboard is a help. The way to implement what I described is to have a heap (or priority queue) of all the arrays. With a whiteboard a candidate can just say, “I’m going to make a heap of all these arrays, sorted such that the lowest value pops to the top” and I’ll say, “yep, sure.” I don’t need them to write that heap. If someone describes a weird data structure that I’m not familiar with, I might ask them to sketch out how it works, but I’m good with just hand-waving a heap. I don’t care if they don’t get the exact syntax right for defining their templates or the exact function calls (is it pop() or pop_front() or…?) for using them.

Here’s the code to implement that algorithm.

class BookmarkedArray
{
	const vector<int>			*m_array;
	vector<int>::const_iterator	m_itr;
public:
	BookmarkedArray(const vector<int> *ar) : m_array(ar)
	{
		m_itr = m_array->begin();
	}

	bool operator < (const BookmarkedArray &other) const 
	{
		return (*m_itr < *other.m_itr);
	}
	bool operator > (const BookmarkedArray &other) const 
	{
		return (*m_itr > *other.m_itr);
	}
	const BookmarkedArray &operator =(const BookmarkedArray &other)
	{
		m_array = other.m_array;
		m_itr = other.m_itr;
		return *this;
	}

	bool AtEnd() const 
	{
		return m_itr == m_array->end();
	}

	int	Value() const
	{
		return *m_itr;
	}
	void	Next() 
	{
		m_itr++;
	}
	
};

void UMI(const vector<int> *arrays, int arrayCount, vector<int> &out)
{
	priority_queue<BookmarkedArray, vector<BookmarkedArray>, std::greater<BookmarkedArray>> q;

	for(int i = 0; i < arrayCount; i++)
	{
		q.push(BookmarkedArray(arrays + i));
	}

	out.clear();
	int currentValue = 0;
	int currentCount = 0;
	while(!q.empty())
	{
		if(currentCount == 0)
		{
			BookmarkedArray ba = q.top();
			q.pop();

			currentValue = ba.Value();
			currentCount = 1;
			ba.Next();

			if(!ba.AtEnd())
				q.push(ba);
		}
		else
		{
			BookmarkedArray ba = q.top();
			q.pop();

			int value = ba.Value();
			ba.Next();
			if(!ba.AtEnd())
				q.push(ba);

			if(value == currentValue)
			{
				currentCount++;
			}
			else
			{
				if(currentCount == 1)
				{
					out.push_back(currentValue);
				}
				currentCount = 1;
				currentValue = value;
			}
		}
	}
	if(currentCount == 1)
	{
		out.push_back(currentValue);
	}
}

 

On a whiteboard, I don’t care about the BookmarkedArray class. Saying you have a heap of arrays is fine. But in a full IDE, I have to define it, and it’s wasting time. I want to talk about this algorithm, not waste time getting the syntax exactly right.

So the time-complexity of this function is n log q, where q is the count of arrays instead of the number of items in the data set, or n. That can be a pretty significant savings. So running all these different approaches to the same problem on a data set of 421,021 items in 15 arrays leads to some eye-opening results. (Source code here.) All three of these approaches produce the exact same output, but the time is significantly different:

UMI naive (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 110367
UMI using map (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 319
UMI using heap (15 arrays) = {19999 multiples of 5}
Array sizes = {28033, 28081, 28150, 28065, 28074, 28094, 28037, 28111, 28035, 28
071, 28103, 28038, 27978, 28071, 28080, } = 421021 total elements.
Elapsed ticks = 10

Complexity matters! Now I’ve heard people in the game industry say that our datasets are usually small enough that understanding complexity isn’t crucial, but I completely disagree. I have seen, and the industry is full of similar stories, cases where a designer comes up with a feature request and an engineer codes it up and it works great. It sails through QA with no problems. Then it gets released out into the wild and the whole game blows up because the largest number of concurrent players it was tested with was like 2. And it’s an n2 or worse, n! solution. And 22 is only 4 and 2! is only 2, but 1,0002 is a million and 10! is even bigger. This stuff matters.

Okay, so I hope that has given you something to think about as you think of how to go about evaluating potential engineering candidates. As I’ve said, whiteboard exercises work for me, but they might not work for you, and that’s okay. The important thing is that you have a strategy for answering the questions about the candidate that you need answered to make the best decision you can.

Thanks for reading. I hope to post some thoughts about diversity soon.

Part I here.

The 538 Riddler: Free Throw Grannies

Hello, and welcome to this week’s look at the 538 Riddler. Last week concerned optimal strategy for a (very) simple game show, and happily my answer was correct. This week’s Riddler concerns free throws again.

Consider the following simplified model of free throws. Imagine the rim to be a circle (which we’ll call C) that has a radius of 1, and is centered at the origin (the point (0,0)). Let V be a random point in the plane, with coordinates X and Y, and where X and Y are independent normal random variables, with means equal to zero and each having equal variance — think of this as the point where your free throw winds up, in the rim’s plane. If V is in the circle, your shot goes in. Finally, suppose that the variance is chosen such that the probability that V is in C is exactly 75 percent (roughly the NBA free-throw average).

But suppose you switch it up, and go granny-style, which in this universe eliminates any possible left-right error in your free throws. What’s the probability you make your shot now? (Put another way, calculate the probability that |Y| < 1.)

So I’ve been doing all these Riddler exercises in C++ but this week I thought I’d mix it up and give the Go language a shot. I’ve never written anything in Go but a friend of mine sent me this text a while back:

text_from_sean

As you can see, I have an exciting social life. So anyway I’ve been wanting to try it out for a while and I figured this blog would be a good opportunity. I’ve been doing the Go tutorials that you can find here.

Another benefit of doing the code (when possible) in Go is that I can link to a version of my code that you can run yourself in the browser, and then make changes to see the impact of those changes. I’m not sure that anyone was copying my C++ code into a compiler, creating a project, building, then running it. But this way running the code is literally just a click away.

Okay, so I thought this week’s Riddler was pretty straightforward from a “getting an answer” point of view. (Which probably means I’m totally wrong.) If I simulate a normalized random distribution of 2D points with some variance such that 75% of those points fall inside a circle with radius 1, then what would be the probability of falling in the circle if the x-component was always 0?

Luckily, Go has a really nice NormFloat64 function that generates normalized random numbers with a standard deviation of 1. With such variance, about 40% of random points will be inside the circle, using the good old Pythagorean Theorem. If I understand the problem correctly all I need to do is find the standard deviation that will result in 75% of points falling inside the circle. Then, I can calculate the magnitude of points where the x-component is 0, and find how frequently they fall in the circle.

So the big task here was to find the right value for the deviation factor. I did this with trial and error and came up with 0.60054. I’m sure there’s a math way to find this value (or a better value) and I look forward to seeing it (Attn: Alex!). Once you start generating x- and y-components, find their magnitude using Sqrt(x*x + y*y) and see if it is below 1. If it is, then that’s a made shot. Also, check to see what would happen if the x-component is 0. You can do that as Sqrt(0*0 + y*y) or Sqrt(y*y) or Abs(y).

Here’s the code in Go:

// 538 Riddler: Should You Shoot Free Throws Underhand?
// http://fivethirtyeight.com/features/should-you-shoot-free-throws-underhand/
// Jon Wiesman, somedisagree.com
package main

import (
	"fmt"
	"math"
	"math/rand"
)

func main() {

	overhand := 0
	granny := 0

	trials := 1000000
	r := rand.New(rand.NewSource(int64(538)))

	dev := 0.60054
	
	for i := 0; i < trials; i++ {
		x := r.NormFloat64() * dev
		y := r.NormFloat64() * dev

		d := math.Sqrt(x*x + y*y)
		g := math.Abs(y)

		if d < 1 {
			overhand++
		}
		if g < 1 {
			granny++
		}
	}

	fmt.Printf("Overhand = %f%%\n", float64(overhand)*100.0/float64(trials))
	fmt.Printf("Granny = %f%%\n", float64(granny)*100.0/float64(trials))
}

 

And here’s a link that will take you to a Go playground where you can run that code and see these results:

Overhand = 75.000800%
Granny = 90.439500%

Try it! You can also play around with different random seed values (I used 538, natch) and see what happens. I think the actual make percentage for Granny-style is more like 90.41%, depending on random seed and number of trials.

Thanks for reading!

The 538 Riddler: Hot New Game Show

Hello again, faithful reader(s). Happily my solution to last week’s Riddler turned out to be correct once again, although I didn’t get to write much interesting code for it. This week’s Riddler on the other hand is right up my alley, featuring a puzzle that was ripe for a code-based solution.

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

So, right away a naive solution would be to suggest that contestants should reject any number below 0.5 and accept anything equal to or above 0.5. I wrote a quick Monte Carlo (natch) to test various thresholds for two contestants. Here’s that code:

#define PRECISION "%.8f"

double GetScore(double thresh)
{
    double score = RandDouble();
    if(score >= thresh)
        return score;
    return RandDouble();
}

int GameShow(double aThresh, double bThresh)
{
    double a = GetScore(aThresh);
    double b = GetScore(bThresh);

    if(a > b)
        return 0;
    if(b > a)
        return 1;

    return -1;
}

double MCGameShow(int trials, double a, double b, bool verbose = false)
{
    int aWins = 0;
    int bWins = 0;

    for(int i = 0; i < trials; i++)
    {
        int res = GameShow(a, b);
        if(res == 0)
            aWins++;
        if(res == 1)
            bWins++;
    }
    double pct = (double)aWins / (double)(aWins + bWins);
    if(verbose)
    {
        printf("MC: With A " PRECISION " and B " PRECISION ", A wins " PRECISION "%%.\n"
            , a, b, pct * 100.0);
    }
    return pct;
}

 

And here’s some output for various thresholds:

MC: With A 0.50000000 and B 0.75000000, A wins 51.55000000%.
MC: With A 0.50000000 and B 0.25000000, A wins 54.83000000%.
MC: With A 0.50000000 and B 0.60000000, A wins 49.77000000%.
MC: With A 0.50000000 and B 0.40000000, A wins 51.73000000%.

Okay, so we can see that 0.5 is not the best number because it loses more often than not against 0.6 for example. So it’s obvious that we’re going to need some better analysis to figure this one out.

This problem is an example of trying to find a Nash Equilibrium, a set of values for each contestant such that any deviation from those values by one contestant results in an advantage for the other contestant. So my strategy for finding this equilibrium is to start with some threshold, say 0.5, and make small adjustments to it. If the new value does better against the previous value, keep going further. When I find a value that seems to represent a local maxima, begin again with smaller adjustments. Continue this process until the size of adjustments falls below some threshold.

Here’s some code do do that:

double FindNashMC(bool verbose = false)
{
    const int trials = 100000;
    double a = 0.5;
    double inc = 0.1;
    while(true)
    {
        double pctInc = MCGameShow(trials, a + inc, a, verbose);

        if(pctInc > 0.5)
        {
            a = a + inc;
        }
        else 
        {
            double pctDec = MCGameShow(trials, a - inc, a, verbose);
            if(pctDec > 0.5)
            {
                a = a - inc;
            }
            else
            {
                inc /= 10.0;
                if(inc < 0.000000001)
                    break;
            }
        }
    }
    if(verbose)
    {
        printf("Nash rejection rate = " PRECISION "\n", a);
    }
    return a;
}

 

And here’s some output from that:

MC: With A 0.60000000 and B 0.50000000, A wins 50.49901996%.
MC: With A 0.70000000 and B 0.60000000, A wins 49.63398536%.
MC: With A 0.50000000 and B 0.60000000, A wins 49.35948078%.
MC: With A 0.61000000 and B 0.60000000, A wins 50.09150641%.
MC: With A 0.62000000 and B 0.61000000, A wins 50.30101204%.
... [lots snipped]
MC: With A 0.64089890 and B 0.64089900, A wins 49.82999320%.
MC: With A 0.64089901 and B 0.64089900, A wins 49.96599932%.
MC: With A 0.64089899 and B 0.64089900, A wins 49.88349417%.
MC: With A 0.64089900 and B 0.64089900, A wins 49.96049881%.
MC: With A 0.64089900 and B 0.64089900, A wins 49.89749282%.
Nash rejection rate = 0.64089900

Well, that seems… reasonable. But is it correct? Running this code over and over shows some pretty high variance. In order to reduce that variance, it’s necessary to increase the number of trials to 100,000 or even 1,000,000, but then it’s slow. And still not necessarily correct.

Here are some other rejection thresholds that this same code spits out:

0.61001981
0.60980422
0.60098909
0.63110990
0.59025124

That’s a pretty wide variance there, and it makes sense. The algorithm depends on lots of decisions to be made based on Monte Carlo simulations, all of which will have a good deal of variance. If any of those decisions are wrong, the end result is doomed. Unless we are willing to run literally billions of trials, we are not going to be able to get a precise answer beyond a few decimal places.

So we really need a better way to do this. Is it possible to use, ugh, math to find the answer? Of course it is. So this game show boils down to one of four possibilities that might happen. These are: 1) both contestant A’s and B’s first numbers are below their thresholds, 2) A’s first number is good, but B’s is rejected, 3) A rejects and B accepts the first number, and 4) both A and B accept their first number.

The odds of each of these scenarios is: 1) a * b, 2) (1-a) * b, 3) a * (1-b), and 4) (1-a) * (1-b).

Okay, so now we know the odds of each scenario, now we must multiply those likelihoods by the likelihood that a will win in each scenario. This boils down to… you know what? Let me just show you the code:

double AWinPct(double a, double b, bool verbose = false)
{
    if(a == b)
        return 0.5;

    double odds1 = a * b; // (a < thresh, b < thresh)
    double odds2 = (1 - a) * b; // a > thresh, b < thresh
    double odds3 = a * (1 - b); // a < thresh, b > thresh
    double odds4 = (1 - a) * (1 - b); // a > thresh, b > thresh

    double aWins1 = 0.5;
    double aWins2 = a + (1 - a) * 0.5;
    double aWins3 = (1 - b) * 0.5;
    double aWins4 = AOverB(1 - b, 1 - a);

    double pct = odds1 * aWins1 + odds2 * aWins2 + odds3 * aWins3 + odds4 * aWins4;
    if(verbose)
    {
        printf("Math: With A " PRECISION " and B " PRECISION ", A wins " PRECISION "\n", a, b, 100.0 * pct);
    }
    return pct;
}

 

Okay, so the first scenario is easy. Both contestants reject their first number and accept whatever their second number is, so 50% that either will win.

In the second scenario we know that A’s score is at least as high as a. So there’s an a chance that B’s second number will be below that number. If B’s second number exceeds a, then it will be uniformly spread between a and 1, so can be represented by (1-a) * 0.5.

The third scenario is the opposite of scenario 2. We know that B’s number is higher than b, so A’s number needs to exceed it. There is a (1-b) chance that it will do that, and then there’s a 50% chance that it will exceed B’s number.

The fourth scenario is one in which both contestants were happy with their first numbers. What are the chances that A beats B here? So, in order to answer that we need another function called AOverB, which takes two ranges and calculates the odds of the first value being higher than the second. But we are going to pass 1-b for A, and 1-a for B. Why? Okay, bear with me here. Let’s say that A’s threshold is 0.6 and B’s threshold is 0.5. Now we know that A’s number will be between 0.6 and 1.0 and B’s will be between 0.5 and 1.0, and that they will be evenly distributed. So B’s range is 0.5 and A’s is only 0.4, but we need to reverse those because A’s range starts at 0.6.

I hope that makes sense. Here’s the code for AOverB:

double AOverB(double a, double b, bool verbose = false)
{
    double dPct = 0.5;
    if(a > b)
    {
        double dOddsOver = (a - b) / a;
        dPct = dOddsOver + (1 - dOddsOver) * 0.5;
    }
    else if(a < b)
    {
        dPct = 1 - AOverB(b, a);
    }
    if(verbose)
    {
        printf("Math " PRECISION " over " PRECISION " = " PRECISION "\n", a, b, dPct);
    }
    return dPct;
}

 

Okay, so now we have all our scenario odds and all our chances of winning each scenario. The final answer is obtained by adding up the products of each scenario’s occurrence rate with its win rate.

Now, at long last, we can rewrite our Nash function to use AWinPct to find the exact winning percentage for any two rejection thresholds and almost immediately:

double FindNash(bool verbose = false)
{
    double a = 0.5;
    double inc = 0.1;
    while(true)
    {
        double pctInc = AWinPct(a + inc, a, verbose);

        if(pctInc > 0.5)
        {
            a = a + inc;
        }
        else 
        {
            double pctDec = AWinPct(a - inc, a, verbose);
            if(pctDec > 0.5)
            {
                a = a - inc;
            }
            else
            {
                inc /= 10.0;
                if(inc < 0.000000001)
                    break;
            }
        }
    }
    if(verbose)
    {
        printf("Nash rejection rate = " PRECISION "\n", a);
    }
    return a;
}

 

And here’s the output:

Math: With A 0.60000000 and B 0.50000000, A wins 50.50000000
Math: With A 0.70000000 and B 0.60000000, A wins 49.40000000
Math: With A 0.50000000 and B 0.60000000, A wins 49.50000000
Math: With A 0.61000000 and B 0.60000000, A wins 50.01200000
Math: With A 0.62000000 and B 0.61000000, A wins 50.00090000
Math: With A 0.63000000 and B 0.62000000, A wins 49.98970000
Math: With A 0.61000000 and B 0.62000000, A wins 49.99910000
Math: With A 0.62100000 and B 0.62000000, A wins 49.99969900
Math: With A 0.61900000 and B 0.62000000, A wins 50.00018900
Math: With A 0.62000000 and B 0.61900000, A wins 49.99981100
Math: With A 0.61800000 and B 0.61900000, A wins 50.00007710
Math: With A 0.61900000 and B 0.61800000, A wins 49.99992290
Math: With A 0.61700000 and B 0.61800000, A wins 49.99996530
Math: With A 0.61810000 and B 0.61800000, A wins 49.99999957
Math: With A 0.61790000 and B 0.61800000, A wins 49.99999931
Math: With A 0.61801000 and B 0.61800000, A wins 50.00000003
Math: With A 0.61802000 and B 0.61801000, A wins 50.00000002
Math: With A 0.61803000 and B 0.61802000, A wins 50.00000001
Math: With A 0.61804000 and B 0.61803000, A wins 50.00000000
Math: With A 0.61802000 and B 0.61803000, A wins 49.99999999
Math: With A 0.61803100 and B 0.61803000, A wins 50.00000000
Math: With A 0.61803200 and B 0.61803100, A wins 50.00000000
Math: With A 0.61803300 and B 0.61803200, A wins 50.00000000
Math: With A 0.61803400 and B 0.61803300, A wins 50.00000000
Math: With A 0.61803500 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803300 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803410 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803390 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803401 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803399 and B 0.61803400, A wins 50.00000000
Math: With A 0.61803400 and B 0.61803399, A wins 50.00000000
Math: With A 0.61803398 and B 0.61803399, A wins 50.00000000
Math: With A 0.61803399 and B 0.61803399, A wins 50.00000000
Math: With A 0.61803399 and B 0.61803399, A wins 50.00000000
Nash rejection rate = 0.61803399

Comparing Nash rejection rate vs. 50% via math and Monte Carlo:
Math: With A 0.61803399 and B 0.50000000, A wins 50.43052317
MC: With A 0.61803399 and B 0.50000000, A wins 50.43086405%.

Finally, after finding the Nash rejection rate, I called AWinPct with it and 0.5 and compared that number to calling MCGameShow with it and 0.5, and one million trials. The results were very close, so I felt pretty good about the AWinPct function, but not 100% sure; there were all sorts of ways I could have done something wrong. But then as I was looking at it I had a terrible thought: what is the Golden Ratio? And the answer is… 1.61803399. So my proposed answer is the fractional part of the Golden Ratio? Seems legit.

Here’s the link to the source code.

Thanks for reading!

 

Follow up to Duck vs. Dog

Okay, well, my luck has officially run out. I was definitely, most certainly wrong wrong wrong about how much faster the dog could travel and still allow the duck to escape. Thanks once again to commenters Alex Mahdavi and Lego Haryanto who found the right answer. Alex pointed me to this DataGenetics blog post from a few years ago that answered the question with a monster and a rower in a boat. As I suspected the answer was more mathy than my simulation could handle, although a lot of it was algebra and trig, with a bit of calculus.

The nice thing was that once I understood the solution, it was really easy to rewrite the SmartDuckStrategy to use the “J” strategy outlined in the post. The result is exactly what was predicted by Datagenetics. Here’s a GIF:

duckvdog_Correct

Yay! It’s nice when things work out, even if I didn’t solve this one (or get close) myself. The new code is a little simplistic in that it assumes the dog will start at a position of 0 degrees, but here it is:

DPoint SmartDuckStrategy::GetDestinationVector(Pond *pond)
{
    if(pond->GetBeeline())
        return pond->GetLastDuckVector();

    DPoint focus(0, -1 / (pond->GetDogSpeed() * 2.0));

    DPoint duckPos = pond->GetDuckPos();

    DPoint delta = duckPos - focus;

    double angleFromFocus = atan2(delta.y, delta.x);

    if(angleFromFocus > -PI / 2.0 && angleFromFocus < 0)
    {
        pond->SetBeeline();
        return DPoint(1, 0);
    }
    angleFromFocus += PI / 2.0;

    DPoint vec(cos(angleFromFocus), sin(angleFromFocus));

    return vec;
}

So I take some comfort that my underlying simulation was solid enough that just changing the behavior of the duck was sufficient to illustrate the right answer. It’s not much, but it’s all I have!

Thanks again to Alex and Lego for posting comments. It means a lot.

Tweaking the Secret Election code

While waiting to see the results of this week’s Riddler, I started thinking about my solution to the problem. In my last post, I outlined two ways of solving the problem: one by hand on paper, and one using C++ and recursion with memoization.

If you look at the way I solved the puzzle by hand, you might recognize it as a form of dynamic programming (my coworker thinks I’m obsessed with finding ways to use dynamic programming; mea culpa). So I decided to write a version of the SimulateElection function using it instead of recursion. Here it is:

// initialize winner array with candidates
char winner[CANDIDATE_COUNT+1] = &quot;&quot;;
for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
winner[i] = 'A' + i;

for(int cand = CANDIDATE_COUNT - 1; cand &gt; 0; cand--)
{
// now simulate election for cand vs. winners in each 'row'
for(int i = 0; i &lt; cand; i++)
winner[i] = RawVote(winner[i], winner[cand]);
}

Pretty short! The key here is to start our array of winners with the candidates in the order in which their secret elections happen, so “ABCDE”. Then in each round, starting from the last election, we hold a raw election between the current value we are evaluating, and the values in each of the preceding indices. So:

“ABCDE” – Starting values. Now we pit E vs. first four values, A, B, C, and D.

“ABEDE” – Values after round 1, because E defeated C, but lost to A, B, and D. Now pit D vs. values in first 3 spots, A, B, and E.

“DDDDE” – Values after round 2, because D defeated A, B, and E. Now pit 3rd value, D, vs. first two spots, D and D.

“DDDDE” – Values after round 3, Now pit 2nd value, D, vs. 1st value A.

“DDDDE” – We are done. Our first value, D, is the winner.

And this is how it goes when we allow candidate A to select candidate E as a proxy:

“ABCDE” – Starting values.

“AEEEE” – After round 1. Candidate E defeated everyone but A. Rounds 2 and 3 will pit E vs. E. The final round will pit A vs. E again, and A will win.

I think it’s easier to look at the recursive code and understand what is going on conceptually. Sometimes it’s hard to see how dynamic programming is “working” when you examine the code, but that might be my own bias.

I did some performance testing on the dynamic programming vs. the recursion. I also made a version of SimulateElection that used recursion but NOT memoization, meaning that all recursive branches were visited. The complexity for the recursive algorithm is n-factorial with n storage, but using memoization reduces it to n-squared with n-squared storage. Using dynamic programming is still n-squared time, but only n storage. Although dynamic programming and memoization are both n-squared time, there’s a little less overhead in the dynamic programming. Here are some time trial results for all three methods:

Elapsed ticks 100000 trials using recursion and memoization = 355 ms.
Elapsed ticks 100000 trials using recursion = 476 ms.
Elapsed ticks 100000 trials using dynamic programming = 283 ms.

All of them are pretty fast because the data is so small. I had to run 100,000 trials just to get decent numbers to compare.

Full source code here.

The 538 Riddler: Secret Election

Well, I’m 3-for-3 so far in finding answers to the 538 Riddler and for last week’s answer I got another shoutout from Ollie. This week’s Riddler concerns a secret cabal of politicians who decide to bypass that pesky democratic process and decide among themselves who will become president.

Suppose that five politicians, disgusted with the current two-party system, come together to choose a third-party candidate to run in the 2016 presidential election. The politicians’ names are Anders (A), Blinton (B), Cubio (C), Drump (D) and Eruz (E). Not wanting to spend all their time campaigning in Iowa and New Hampshire in winter, they decide instead to pick which of them will be the candidate at a secret meeting with just the five of them. The voting procedure is as follows: They will first hold a vote of A versus B. (The five politicians are the only voters.) The winner of that vote will then be paired against C. That winner will be paired against D, and finally that winner will be paired against E. They will declare the winner of that last matchup to be their candidate.

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge. Their preferences are as follows (“X > Y” means Candidate X is preferred to Candidate Y):

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

All of the politicians are forward-looking and vote strategically.

Question 1: Who will be chosen as the presidential candidate?

So I was able to work this one out on paper, but I decided to write a program to confirm my answer, which I will show below.

 

So, first let’s look at how I figured out “by hand” the winner of the election. The key here is to look at the last election first, when candidate Eruz will face off against one of the four winners of the previous elections. Using the candidates stated preferences we find:

Aanders vs. Eruz – Aanders would win 4-1.

Blinton vs. Eruz – Blinton would win 3-2.

Cubio vs. Eruz – Eruz would win 3-2.

Drump vs. Eruz – Drump would win 3-2.

Poor candidate Cubio! He literally cannot win no matter what happens with the current voting schedule. What we also see is that any other candidate who survives to the last election vs. Eruz will win. Since all the preferences are known, each of the candidates knows this. Now let’s take a step back and look at the previous election. One of the first three candidates (Aanders, Blinton, or Cubio) will be facing off against candidate Drump.

If these were the last elections, we would see that Drump would beat all three of the preceding candidates. However since we know that Eruz waits to take on the winner, each of these elections becomes a decision between the winner and Eruz:

Aanders vs. Drump = (Aanders vs. Eruz) vs. (Drump vs. Eruz) = (Aanders vs. Drump)

Blinton vs. Drump = (Blinton vs. Eruz) vs. (Drump vs. Eruz) = (Blinton vs. Drump)

Cubio vs. Drump = (Cubio vs. Eruz) vs. (Drump vs. Eruz) = (Eruz vs. Drump)

In all three of those matchups, Drump wins, and so according to the rules setup by the cabal, candidate Drump will win the secret election. It’s interesting to note that even if Cubio were favored in a head-to-head matchup with Drump in the 3rd round, game theory would dictate that the other candidates would still vote for Drump since they know Cubio would be destined to lose to Eruz in the final round, and they prefer Drump over Eruz.

Here’s my “scratch pad” answer to the first question:

Normal election:
AvE = A
BvE = B
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = BvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

Let’s look at the remaining questions from 538:

Now assume that A has the flu and is forced to miss the voting meeting. He is allowed to transfer his vote to someone else, but he can’t make that other person commit to vote against her own self-interest.

Question 2: To whom should he transfer his vote, given his candidate preference outlined above (A > B > C > D > E)?

Question 3: Who will win the candidacy now?

Question 4: A month before the meeting, Candidate A must decide whether or not to get the flu vaccine. Should he get it?

Okay, so now we have a wrinkle where candidate Aanders has the opportunity to select another candidate as a proxy. I should say that my answer to these questions about who Aanders should choose as a proxy, and whether Aanders should purposely miss the vote, depend on the idea that all candidates will know who Aanders has chosen as a proxy, and who that person will vote for. If that’s not the case, then I think it could get pretty tricky.

Here are the four different scenarios for elections where Aanders misses the vote, and chooses Blinton, Cubio, Drump, and Eruz as proxies:

A selects B as a proxy:
AvE = A
BvE = B
CvE = E
DvE = E
so...
AvD = (AvE)v(DvE) = AvE = A
BvD = (BvE)v(DvE) = BvE = B
CvD = (CvE)v(DvE) = EvE = E
so...
AvC = (AvD)v(CvD) = AvE = A
BvC = (BvD)v(CvD) = BvE = B
so...
AvB = (AvC)v(BvC) = AvB = B
B wins the election.

_______________________________________
A selects C as a proxy:
AvE = A
BvE = E
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = EvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

_______________________________________
A selects D as a proxy:
AvE = A
BvE = B
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = BvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

_______________________________________
A selects E as a proxy:
AvE = A
BvE = E
CvE = E
DvE = E
so...
AvD = (AvE)v(DvE) = AvE = A
BvD = (BvE)v(DvE) = EvE = E
CvD = (CvE)v(DvE) = EvE = E
so...
AvC = (AvD)v(CvD) = AvE = A
BvC = (BvD)v(CvD) = EvE = E
so...
AvB = (AvC)v(BvC) = AvE = A
A wins the election!

So if Aanders chooses Blinton, Blinton wins. If Aanders chooses Cubio or Drump, then Drump wins. (Poor Cubio can’t even win when controlling two votes!) But Aanders can win the election by choosing his most ideologically opposed candidate as a proxy. Weird! So the answer to question 4 is, yes of course get the flu vaccine (vaccines are good), but pretend to be sick anyway and name candidate Eruz as your proxy, Mr. Aanders.

As I said, I was able to do this on paper by hand, but I decided to write a program to do it anyway. I set up a C++ class called Candidate which is initialized with a list of other candidate preferences in the form of a 5-character string like “ABCDE” for Aanders. Those preferences are used to give a score to each candidate and then the Candidate class can be queried for its preference between two candidates.

It’s possible to designate a proxy candidate which will be queried instead by calling SetProxy. Here’s Candidate:

#define CANDIDATE_COUNT 5

class Candidate
{
char m_id;
int m_scores[CANDIDATE_COUNT];
const Candidate *m_proxy;

public:
Candidate(const char *rankings) : m_proxy(NULL)
{
m_id = rankings[0];
for(int cand = 0; cand &lt; CANDIDATE_COUNT; cand++)
{
m_scores[rankings[cand] - 'A'] = CANDIDATE_COUNT - cand;
}
}
// allow another candidate to vote for me
void SetProxy(const Candidate *proxy) {m_proxy = proxy;}

bool RawPreference(char a, char b) const
{
// if a proxy has been designated, ask it
if(m_proxy != NULL &amp;&amp; m_proxy != this)
return m_proxy-&gt;RawPreference(a, b);

// otherwise return true if our score for the first candidate is
// greater than the second's score
if(m_scores[a - 'A'] &gt; m_scores[b - 'A'])
return true;
return false;
}
};

Now we need a class to represent the election called, well, Election. Election creates 5 candidates with their respective preferences. A function called SimulateElectionWithAbsenteeAndProxy allows the election to be run, and if values are set for the absentee and proxy parameters, any candidate can be set as absent with any other candidate set as its proxy. (A function called SimulateElection calls it with absentee and proxy set to 0 to signify no absentees.) Here’s Election:

class Election
{
public:
Election()
{
const char *c_rankings[] = {
&quot;ABCDE&quot;, &quot;BAEDC&quot;, &quot;CDAEB&quot;, &quot;DBAEC&quot;, &quot;EDBCA&quot;
};

for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
{
m_candidates[i] = new Candidate(c_rankings[i]);
}
}
virtual ~Election()
{
for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
delete m_candidates[i];
}

void SimulateElection()
{
SimulateElectionWithAbsenteeAndProxy(0, 0);
}

void SimulateElectionWithAbsenteeAndProxy(char absentee, char proxy)
{
m_matchups.clear();
if(absentee != proxy &amp;&amp; absentee &gt;= 'A' &amp;&amp; absentee &lt;= 'E')
{
GetCandidate(absentee)-&gt;SetProxy(GetCandidate(proxy));
printf(&quot;Simulating election with %c selecting %c as a proxy:\n&quot;, absentee, proxy);
}
else
{
printf(&quot;Simulating normal election:\n&quot;);
}
char winner = Vote('A', 'B');

if(absentee != proxy)
{
printf(&quot;When %c was the proxy for %c, %c won.\n\n&quot;, proxy, absentee, winner);
GetCandidate(absentee)-&gt;SetProxy(NULL);
}
else
{
printf(&quot;In a normal election, %c wins.\n\n&quot;, winner);
}
}

private:
Candidate *m_candidates[CANDIDATE_COUNT];

std::hash_map&lt;std::string, char&gt; m_matchups;

Candidate *GetCandidate(char c)
{
return m_candidates[c - 'A'];
}

char Vote(char c1, char c2)
{
char resultKey[4] = &quot;XvX&quot;;
resultKey[0] = min(c1, c2);
resultKey[2] = max(c1, c2);

auto itr = m_matchups.find(resultKey);
if(itr != m_matchups.end())
{
return itr-&gt;second;
}

if(c2 &lt; 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

int c1Score = 0;
for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
{
if(GetCandidate('A' + i)-&gt;RawPreference(c1, c2))
c1Score++;
}

char winner = (c1Score &gt;= 3) ? c1 : c2;
printf(&quot; Evaluating %s is same as (%cv%c) = %c\n&quot;, resultKey, c1,c2, winner);
m_matchups[resultKey] = winner;

return winner;
}
};

The key to the SimulateElection function is the Vote function. Vote is recursive and hinges on these lines:

if(c2 &lt; 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

If the second candidate passed into Vote is not Eruz, then we know that we need to look ahead to find out what the results of picking each candidate would be in future rounds of voting. This is done by setting the c1 and c2 variables to be the result of recursively calling Vote with (c1, c2+1) and (c2, c2 + 1).

Once I get the results of all future round combinations, I can compare the returned c1 and c2 candidates to see which each of the candidates prefer. That candidate is then considered the winner of that matchup between the two original candidates. (This means that the stored winner of the matchup “BvC” might be “D”.)

With the number of candidates at only 5 we could safely just use the recursive method here and not worry about it, but I use memoization to keep runtime complexity reasonable; I cache previous results using a hash_map so I can quickly look them up.

Finally, once I was able to specify any candidate as an absentee with any other candidate as a proxy, I decided to check all possible absentee/proxy combinations. It should come as no surprise that candidate Eruz can’t win the election no matter what happens; however, candidate Cubio CAN win the election for several of these combinations. Here’s the output of all the different combinations:

Simulating normal election:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
In a normal election, D wins.

Simulating election with A selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for A, B won.

Simulating election with A selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When C was the proxy for A, D won.

Simulating election with A selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for A, D won.

Simulating election with A selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvE) = E
 Evaluating BvC is same as (EvE) = E
 Evaluating AvB is same as (AvE) = A
When E was the proxy for A, A won.

Simulating election with B selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When A was the proxy for B, C won.

Simulating election with B selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for B, C won.

Simulating election with B selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for B, D won.

Simulating election with B selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When E was the proxy for B, D won.

Simulating election with C selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (AvD) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvD) = B
 Evaluating AvB is same as (AvB) = B
When A was the proxy for C, B won.

Simulating election with C selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for C, B won.

Simulating election with C selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for C, D won.

Simulating election with C selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When E was the proxy for C, B won.

Simulating election with D selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (AvC) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvC) = B
 Evaluating AvB is same as (AvB) = A
When A was the proxy for D, A won.

Simulating election with D selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for D, B won.

Simulating election with D selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for D, C won.

Simulating election with D selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvE) = E
 Evaluating BvC is same as (EvE) = E
 Evaluating AvB is same as (AvE) = A
When E was the proxy for D, A won.

Simulating election with E selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (AvC) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvC) = B
 Evaluating AvB is same as (AvB) = A
When A was the proxy for E, A won.

Simulating election with E selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (AvD) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvD) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for E, B won.

Simulating election with E selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for E, C won.

Simulating election with E selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for E, D won.

And here’s the entire SecretElection.cpp file:

// SecretElection.cpp : Defines the entry point for the console application.
//

#include &quot;stdafx.h&quot;
#include &lt;hash_map&gt;
#include &lt;string&gt;

#define min(a,b) ((a) &lt; (b)) ? (a) : (b)
#define max(a,b) ((a) &gt; (b)) ? (a) : (b)

#define CANDIDATE_COUNT 5

class Candidate
{
char m_id;
int m_scores[CANDIDATE_COUNT];
const Candidate *m_proxy;

public:
Candidate(const char *rankings) : m_proxy(NULL)
{
m_id = rankings[0];
for(int cand = 0; cand &lt; CANDIDATE_COUNT; cand++)
{
m_scores[rankings[cand] - 'A'] = CANDIDATE_COUNT - cand;
}
}
// allow another candidate to vote for me
void SetProxy(const Candidate *proxy) {m_proxy = proxy;}

bool RawPreference(char a, char b) const
{
// if a proxy has been designated, ask it
if(m_proxy != NULL &amp;&amp; m_proxy != this)
return m_proxy-&gt;RawPreference(a, b);

// otherwise return true if our score for the first candidate is
// greater than the second's score
if(m_scores[a - 'A'] &gt; m_scores[b - 'A'])
return true;
return false;
}
};

class Election
{
public:
Election()
{
const char *c_rankings[] = {
&quot;ABCDE&quot;, &quot;BAEDC&quot;, &quot;CDAEB&quot;, &quot;DBAEC&quot;, &quot;EDBCA&quot;
};

for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
{
m_candidates[i] = new Candidate(c_rankings[i]);
}
}
virtual ~Election()
{
for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
delete m_candidates[i];
}

void SimulateElection()
{
SimulateElectionWithAbsenteeAndProxy(0, 0);
}

void SimulateElectionWithAbsenteeAndProxy(char absentee, char proxy)
{
m_matchups.clear();
if(absentee != proxy &amp;&amp; absentee &gt;= 'A' &amp;&amp; absentee &lt;= 'E')
{
GetCandidate(absentee)-&gt;SetProxy(GetCandidate(proxy));
printf(&quot;Simulating election with %c selecting %c as a proxy:\n&quot;, absentee, proxy);
}
else
{
printf(&quot;Simulating normal election:\n&quot;);
}
char winner = Vote('A', 'B');

if(absentee != proxy)
{
printf(&quot;When %c was the proxy for %c, %c won.\n\n&quot;, proxy, absentee, winner);
GetCandidate(absentee)-&gt;SetProxy(NULL);
}
else
{
printf(&quot;In a normal election, %c wins.\n\n&quot;, winner);
}
}

private:
Candidate *m_candidates[CANDIDATE_COUNT];

std::hash_map&lt;std::string, char&gt; m_matchups;

Candidate *GetCandidate(char c)
{
return m_candidates[c - 'A'];
}

char Vote(char c1, char c2)
{
char resultKey[4] = &quot;XvX&quot;;
resultKey[0] = min(c1, c2);
resultKey[2] = max(c1, c2);

auto itr = m_matchups.find(resultKey);
if(itr != m_matchups.end())
{
return itr-&gt;second;
}

if(c2 &lt; 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

int c1Score = 0;
for(int i = 0; i &lt; CANDIDATE_COUNT; i++)
{
if(GetCandidate('A' + i)-&gt;RawPreference(c1, c2))
c1Score++;
}

char winner = (c1Score &gt;= 3) ? c1 : c2;
printf(&quot; Evaluating %s is same as (%cv%c) = %c\n&quot;, resultKey, c1,c2, winner);
m_matchups[resultKey] = winner;

return winner;
}
};

int _tmain(int argc, _TCHAR* argv[])
{
Election e;

e.SimulateElection();
for(char absentee = 'A'; absentee &lt;= 'E'; absentee++)
{
for(char proxy = 'A'; proxy &lt;= 'E'; proxy++)
{
if(absentee != proxy)
e.SimulateElectionWithAbsenteeAndProxy(absentee, proxy);
}
}

return 0;
}

Thanks for reading!

UPDATE: For a dynamic programming example of how to solve this, see my next post. And since WordPress has once again destroyed my code formatting, here’s a post with all the latest links to the code.