The 538 Riddler:Weird Guy in Trench Coat

Hello, and welcome to my look at 538’s Riddler. Last week I managed to get the correct answer using a Monte Carlo, and Go’s really nice NormFloat64 function. Commenters squareandrare, mathisallaround, and guyshavit all shared voodoo mathy ways to get the answer, which I appreciated, including the chi-squared distribution. Thanks for reading and commenting!

This week’s Riddler concerns talking to strange men in trench coats.

A man in a trench coat approaches you and pulls an envelope from his pocket. He tells you that it contains a sum of money in bills, anywhere from $1 up to $1,000. He says that if you can guess the exact amount, you can keep the money. After each of your guesses he will tell you if your guess is too high, or too low. But! You only get nine tries. What should your first guess be to maximize your expected winnings?

Obviously if a man in a trench coat offers you money the answer is to run. But let’s answer the question anyway. My immediate first guess for this was $744, which was wrong. But only because I’m pretty sure the answer is $745.

How did I get this number? Well, the guessing game where someone tells you whether your guess is higher or lower is a classic example of a binary search, which is one of the most important algorithms in computer science. With 9 guesses, we know that we can guarantee coverage of 511 (2^9 – 1) values. That leaves 489 values for which we are going to not be able to guess the right answer. Sad!

Now the question is, which values do we want to cover? Well, without any knowledge to the contrary we should assume that all values between $1 and $1000 are equally likely, assuming our trench-coated friend is trustworthy (and aren’t they all?). So since there is just as much chance that there is $1000 in the envelope as $1, we might as well make sure we cover the top 511 values.

Put another way, imagine the man in the trench coat offers you only one guess. What should you do? (Run.) Well, you have just as much chance of being right by guessing $1000 as $1, so guess $1000 and hope for the best. Your expected value (EV) is the odds of being right times the payout, so if you guess $1000, your EV is $1. If you guess $1, your EV is $.001, which is… less.

So covering the top 511 values would be everything from $490 to $1000. The middle value between those two numbers is $745. I wrote some code to show this, and then ran 1000 simulations for each amount of money that is in the envelope. Here it is in Go:

package main
// Jon Wiesman, somedisagree.com

import "fmt"

func binSearchRecursive(min, max, value, guesses int) bool {

	if guesses == 0 {
		return false
	}
	if min > max {
		return false
	}

	guess := (min + max) / 2
	if guess == value {
		return true
	}

	if guess < value {
		return binSearchRecursive(guess+1, max, value, guesses-1)
	} else {
		return binSearchRecursive(min, guess-1, value, guesses-1)
	}

	return false
}

func binSearchIterative(min, max, value, guesses int) bool {
	for ; guesses > 0; guesses-- {
		if min > max {
			return false
		}

		guess := (min + max) / 2
		if guess == value {
			return true
		}

		if guess < value {
			min = guess + 1
		} else {
			max = guess - 1
		}

	}
	return false
}

func DoTrialRecursively(min, max int) {
	trials := 1000
	found := 0
	totalEarned := 0

	for i := 1; i <= 1000; i++ {
		if binSearchRecursive(min, max, i, 9) {
			found++
			totalEarned += i
		}
	}

	fmt.Printf("Recursively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned)
}

func DoTrialIteratively(min, max int) {
	trials := 1000
	found := 0
	totalEarned := 0

	for i := 1; i <= 1000; i++ {
		if binSearchIterative(min, max, i, 9) {
			found++
			totalEarned += i
		}
	}

	fmt.Printf("Iteratively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned)
}

func main() {
	DoTrialIteratively(489, 1000)
	DoTrialIteratively(490, 1000)
	DoTrialRecursively(490, 1000)
	DoTrialRecursively(491, 1000)

}

 

And here’s a link to the Go playground for this code where you can play with the numbers and run it in your browser. Doing so gives this output:

Iteratively, with first value = 744, 511/1000 success, total earned = 380184
Iteratively, with first value = 745, 511/1000 success, total earned = 380695
Recursively, with first value = 745, 511/1000 success, total earned = 380695
Recursively, with first value = 745, 510/1000 success, total earned = 380205

So your EV if you start with a first guess of $745 is $380.695, and you’ve got a 51.1% chance of making some money. Pretty good deal. (You should still run.)

My binary search function differs from most binary searches in one small way. Here, I pass in the number of guesses and decrement it with each recursive call. When it reaches 0, I return false. I used recursion here first because it’s easiest for me to write but iteration might be easier for non CS people to follow so I wrote it iteratively as well. Both work.

If you call either function with min and max at $1 and $1000, respectively, giving a first guess of $500, you will still succeed 511 times but your expected value would only be $255.175. This is because the 489 missed values would be evenly distributed instead of all at the bottom. Try it.

So, that’s my answer: $745. I believe it is right unless there is some method to guarantee more than 511 found values with only 9 guesses. As always, I’m always willing to admit I am wrong so if I am, I’d love to know.

Thanks for reading.

 

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!

Conducting Technical Interviews, Part I

Generally speaking, job interviews can be awful. They are stressful for the candidate and a huge time sink for the interviewer, often time that has not been accounted for in milestone planning. And the end result of this awfulness is very likely to be an incomplete, perhaps even inaccurate, set of data from which a hiring decision will need to be made.

This week marks my one-year anniversary of working at MobilityWare, and over this last year I have been asked to conduct quite a few interviews of software engineering candidates. I’ve probably conducted interviews at about three times the rate I did them at Carbine. I used to really dread being tasked with an interview, mostly because I suspected that I wasn’t very good at them. And I was right, I used to be terrible. But over the last couple of years as I’ve done more, I’ve started to really enjoy it, and I hope that is because I have gotten better.

Sometimes I interview people alone but often I will be paired with another interviewer, and sometimes we will have three people interviewing a candidate. This has given me an opportunity to not only see how others conduct interviews but also get feedback from peers on my own interviewing. So over the years, and the past year especially, I’ve learned quite a bit. Our HR director and I are doing an in-house presentation on interviewing techniques, and so I’m using these blog posts as kind of a way to organize my thoughts about that.

If you do a web search on “how to conduct a technical interview” you will find all sorts of advice and quite a bit of it will be contradictory. A lot of the writers will be very adamant that their way to conduct interviews is the right way and the way others do interviews is the wrong way. So right off the bat I just want to say that these thoughts about interviewing engineers are what I’ve found work for me. I don’t know if they’re the best ideas and I’m sure that there will be things that you may disagree with. If you are looking for how to conduct a technical interview, then I suggest looking at as many of those search results as possible. If this post also helps you, then great, but the mere fact that you have actively sought out ways to improve your interviewing skills probably means you will be better than 80% of the people out there conducting interviews.

I should say that if you just have time to read one and only one post about technical interviews, it should probably be this one by Joel Spolsky. I mean, I don’t agree with all of it and I think you should keep reading mine, but if you only have time for one, then yeah, follow that link. It’s cool.

Interviewing: Really Important

Interviewing is really important because hiring is really important. Employees are what truly differentiate one company from any other company, and companies that want to do great things must find and hire great people, and it’s really hard to do it well. In my 8 years at Carbine we grew from about 25 people to over 225, and since I started at MobilityWare we’ve almost doubled in size and we are still growing. This has meant a lot of interviewing, and a lot of decisions on whether to hire or, more commonly, not hire candidates.

Don’t Avoid Interviewing

You should want to do interviews. This goes for everyone, but especially for engineers. I know they are a time sink and I know they interfere with whatever tasks you are currently working on, but you should want to be involved in the process of choosing who you will be working with and with whose work you will be interacting. It’s hard to find good engineers and you will often have to be involved in tough “no” decisions, but the consequences of a bad hire are far more costly than missing out on a good candidate. If you have ever worked with engineers who seemed completely unfit for their jobs and you’ve wondered how they got those jobs in the first place, then you should want to make sure it doesn’t happen again.

Even if you are unconvinced that this stuff is really important, I guarantee your HR director thinks it is, so at the very least, you should be happy to be asked to help out with the process. If you haven’t been asked, volunteer. Ask to be part of the process as an observer. Take some initiative and learn how to do this. It’s important. (Have I mentioned it is important?)

Becoming a good interviewer will make you better at doing your job, regardless of what kind of job it is, but especially for engineering. In preparing to conduct an interview you need to be proficient in whatever you are interviewing for. You will need to be prepared to answer questions about the problems you are posing. Despite all that preparation you will sometimes be surprised at a new approach to the problems you discuss in your interview. Remember that many of the engineers you interview will actually be really good at engineering, and so you will actually learn from them as you evaluate them.

The Challenge

So if you are still reading, then hopefully you agree that this stuff is important, but here’s the thing: it’s also really hard. If you conduct the perfect interview, or design the perfect interview process, you will still collect only a fraction of the information necessary to truly evaluate a candidate. You are going to have to make a decision based on incomplete information, so it’s really important that you maximize the time that you have to get as much information as you can to make that decision.

You’ve no doubt heard the expression, “there’s no such thing as a stupid question.” Well, that’s wrong. Or at least it’s wrong if you are interviewing someone. Just as lawyers are taught to never ask a question in a courtroom when you don’t already know the answer, interviewers should never ask a question if the answer won’t help determine whether to hire the candidate or not. You have a finite number of questions; don’t waste them. If I ask the candidate’s favorite baseball team and learn it is the Minnesota Twins, what can I do with that information? (If it’s the Dodgers, sure, that’s a no-hire, but the Twins? I got nothing.)

Preparation

Prepare a list of questions for yourself about the candidate. These aren’t questions you will be asking the candidate, but questions you hope to answer during the interview. Every question/problem/scenario you pose to the candidate should be about helping you answer these questions. For one of my programming questions, these questions are things like:

  • Did she ask clarifying questions?
  • Did he “define the contract” (API)?
  • Did she get a valid solution? Naive, better, optimal?
  • What was the time/space complexity of her solution(s)?
  • Could he have a discussion about complexity?

Once you have defined the questions you want answered, you need to find questions/problems that will help you answer those questions. I use whiteboard programming questions. Now, some of you just read that last sentence and are preparing your virtual torches and pitchforks. If you look at that list of search results that I linked above, you will find all sorts of very angry writers who have declared that whiteboard questions are dead, that they are worthless, and that they have no place in an interview process. I’ll go into more detail about why I like whiteboard questions, with examples, in a future post, but for now I will just say that I understand why people don’t like them, but I still find them useful.

Make sure to prepare more questions than you will ever need for the time you have been allotted. Do NOT find yourself in an interview with 30 minutes to kill and no questions to ask, or nothing to talk about. I like to have some tough problems ready for candidates who sail through my standard questions and some easier questions for people who just flame out on the standard questions.

In general, don’t try out a brand new interview question on a candidate for the first time. Ask a coworker first, so you can see how it is answered. Your cool new problem might have a really simple solution that you didn’t think of, or it might be too complex for a 45- to 60-minute interview. It might have only one solution, or all the solutions might be of equal time/space complexity, and you probably want to have bad/okay/better/best solutions. Again, I’ll talk about some examples in a later post.

Finally, get together with your fellow interviewers and make sure you have a plan for how you will be tackling the interview(s). Make sure everyone knows what questions they will be asking and when they will be asking them. Don’t find yourself in a situation where you are desperately trying to fill time because all of your questions were asked already. It’s unprofessional and you’re wasting precious time.

The Interview

Now that you’re prepared it’s time to do the actual interview. First and foremost, please try to remember your first job interview. If you’re a normal person you were probably really nervous. Likewise, the person you are interviewing is probably going to be nervous as well. Try to do something to make them more comfortable.

Since I do whiteboard problems, one of the first things I do is write on the whiteboard some information about the first problem. This always involves me needing to draw a set of curly braces { }. I cannot draw curly braces. At all. If I’m really lucky, they end up looking like a capital E and a 3, but more often they end up looking like weird, mismatched squiggles.

After drawing these weird squiggles, I apologize to the candidate and explain that I can’t draw curly braces and ask them to imagine those weird squiggles are curly braces. I do this every time. My fellow interviewers are sick of me doing this. But I’m trying to accomplish a couple things. One, I just want to poke fun at myself to let the candidate know I’m not taking myself too seriously here. Two, I want to “give permission” to the candidate to not worry too much about their own writing. I don’t care at all about penmanship. Or how neatly they draw semi-colons or brackets or even if the brackets are lined up. I’m not always successful with this; I’ve had candidates draw and erase the same line of code several times because they think it’s sloppy and are really trying to make a good impression. I try to encourage them to move on, but sometimes you need to let them do whatever they need to do to cope with the situation. Show some empathy here; it’s tough.

I’ll talk more about the whiteboard problems in Part Two. Regardless of what kind of interview you are conducting there are a couple things you should keep in mind. First, remember that the purpose of this interview is for you to evaluate the technical qualifications of the candidate. You are not there to prove to the candidate how smart you are. I’ve seen this from interviewers that seem to feel the need to show that they belong in the room; trust me, the candidate believes you are a smart person. You don’t need to prove it.

That leads me to the second thing to remember. You are representing your company. Be nice to the candidates! If you end up being impressed with them, you want them to accept a job offer; candidates are much less likely to want to work with you if you demonstrate a thin skin or insecurity in the interview. In fact, you want the candidate to walk away from the interview excited about the possibility of working at your company, even if you ultimately decide (or have already decided) that this person is a no.

After the Interview

Eventually, the interview ends and you have to make a decision. I fill out a score card with notes I’ve taken and I immediately give a thumbs up or down on whether I think we should hire the candidate. There is no maybe. On this particular point, I am in agreement with Joel Spolsky: if the candidate is a maybe, that’s a no. I make this decision before talking with any other interviewers because I don’t want to be influenced. Afterwards, if there is disagreement, and there often is, we will have a meeting where we discuss the candidate. I can be persuaded of course, but I record that initial score immediately.

Finally, and this is something I will talk about in another post at more length, it’s really important to do as much as possible to eliminate bias from your decision. All people have bias of course, but diversity is so important to healthy successful companies. Many companies rate prospective candidates on “culture fit” and that’s okay, but be careful to ensure that you are talking about the company culture, not your personal culture. You want to choose candidates that you can work with, not necessarily candidates that you want to hang out with. Don’t let your company turn into a bunch of carbon copies of yourself; that might sound great to you, but it’s a recipe for disaster.

Of course one way to protect against that is to make sure interviews are not conducted by the same people all the time. Once you have become a regular interviewer at your company start reaching out to other engineers to get them involved in the interview process. Convince them that it is in their best interest to have a say in the process. It will make them better engineers and it will help your company hire better engineers.

Thanks for reading! If you found this helpful or at least hilarious in its wrongness, look for Part Two next week.

 

The 538 Riddler: Air Travel Nightmare

So last week’s Riddler was a good news/bad news situation. The bad news is that I was wrong, although I did illustrate the correct answer in a follow-up post. The good news is that I still managed to get a shout-out from Ollie in this week’s Riddler, even earning the honorary title of FotR, which I hope means Friend of the Riddler.

Anyway, this week’s Riddler concerns the worst person alive and a full airplane.

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

So the answer is 1/2, half, 50%, however you want to say it. And this is true for the last passenger no matter how many passengers are on a (full) plane. I actually worked this out before writing any code (but don’t worry, I still wrote the code!) It’s trivial to show for the case where there are only two passengers: there are two seats, and the person in front of you is the worst person alive. He either takes his seat, or yours, randomly. Fifty percent, done.

For three people (1. Worst Person Alive, 2. Rando Calrissian, and 3. You) and three seats, we can still do it in our heads. WPA takes one of three seats, so right away you have a 1/3 chance of not getting your seat. But there is also a 1/3 chance that he takes Rando’s seat, in which case Rando will randomly take one of the two remaining seats, yours or WPA’s assigned seat. One-third times one-half is 1/6, so there is a 1/6 chance you will find Rando sitting in your seat, and a 1/3 chance WPA will be sitting there. So 1/3 + 1/6 = 1/2. Boom, done.

Once I saw that the probability remained at 50% for three passengers, I suspected that it would be 50% for any number of passengers. I wrote a Monte Carlo to show that.

// AirplaneSeating.cpp : Defines the entry point for the console application.
// www.somedisagree.com, Jon Wiesman

#include "stdafx.h"
#include <vector>

#define SEAT_COUNT 100
#define EVIL_COUNT 1
#define AVAILABLE -1

class Plane
{
    std::vector<int>    m_seats;
    int                 m_available;

public:
    Plane(int seats)
    {
        m_seats.resize(seats);
        for(int i = 0; i < seats; i++)
            m_seats[i] = AVAILABLE;
        m_available = seats;
    }

    void    ClaimSeat(int seat, int passenger) 
    {
        m_seats[seat] = passenger;
        m_available--;
    }

    int     FindUnclaimedSeat() const
    {
        if(m_available == 0)
            return -1;
        int nth = rand() % m_available;

        int empty = 0;
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(IsSeatAvailable(i))
            {
                empty++;
                if(empty > nth)
                    return i;
            }
        }
        return -1;
    }

    bool    IsSeatAvailable(size_t seat) const
    {
        return (seat >= 0 && seat < m_seats.size() && m_seats[seat] == AVAILABLE);
    }

    void    GetSeat(int passenger, bool evil)
    {
        if(evil || !IsSeatAvailable(passenger))
        {
            int seat = FindUnclaimedSeat();
            ClaimSeat(seat, passenger);
        }
        else
        {
            ClaimSeat(passenger, passenger);
        }
    }

    void    SimulateBoarding(size_t evilCount)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            GetSeat(i, (i < evilCount));
        }
    }

    void    CompileStats(std::vector<int> &stats, int &wrongSeats)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(m_seats[i] == i)
                stats[i]++;
            else
                wrongSeats++;
        }
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> stats;
    int wrongSeats = 0;
    stats.resize(SEAT_COUNT);

    int trials = 100000;

    for(int i = 0; i < trials; i++)
    {
        Plane plane(SEAT_COUNT);

        plane.SimulateBoarding(EVIL_COUNT);
        plane.CompileStats(stats, wrongSeats);
    }

    printf("After %d trials with %d evil passengers:\n", trials, EVIL_COUNT);
    for(int i = 0; i < SEAT_COUNT; i++)
    {
        printf("Passenger %d seated properly %.2f%% of time\n", i, 100.0 * (double)stats[i]/(double)trials);
    }
    printf("Average of %.2f wrongfully seated passengers\n", (double)wrongSeats / (double)trials);

	return 0;
}

 

This code (download) is pretty simple. The Plane class keeps an array of seats and who (which passenger) is seated in each seat. It also keeps the number of empty seats at any time to make it easier to quickly choose a random seat. (For the purpose of this simulation it was convenient to say that the passenger index and seat assignment are the same.)

The constructor initializes the seat array to all available and sets the available count to the seat count. SimulateBoarding tells each passenger to find a seat. Finding a seat is easy. If you’re not evil and your seat is available, sit down. Otherwise, find a random available seat. Either way, call ClaimSeat to sit down and decrease the available member variable. A CompileStats function will increment the number of correct passenger-seat assignments and keep a running count of wrong ones. Finally we run this simulation 100,000 times and print out the results.

After 100000 trials with 1 evil passengers:
Passenger 0 seated properly 1.00% of time
Passenger 1 seated properly 99.03% of time
Passenger 2 seated properly 99.00% of time
Passenger 3 seated properly 99.00% of time
Passenger 4 seated properly 99.01% of time
Passenger 5 seated properly 98.93% of time
Passenger 6 seated properly 98.97% of time
Passenger 7 seated properly 98.95% of time
Passenger 8 seated properly 98.92% of time
Passenger 9 seated properly 98.98% of time
Passenger 10 seated properly 98.87% of time
.....
Passenger 90 seated properly 90.86% of time
Passenger 91 seated properly 90.03% of time
Passenger 92 seated properly 88.83% of time
Passenger 93 seated properly 87.42% of time
Passenger 94 seated properly 85.39% of time
Passenger 95 seated properly 83.11% of time
Passenger 96 seated properly 79.98% of time
Passenger 97 seated properly 74.74% of time
Passenger 98 seated properly 66.45% of time
Passenger 99 seated properly 49.95% of time
Average of 5.19 wrongfully seated passengers

So I ran this code really just to confirm that my guess of 50% would be correct. However, I saw something which kind of jogged my memory. The average number of wrongfully seated passengers out of 100 was 5.19. This was the average number of traffic jams with 100 cars from two weeks ago! (The exclamation point at the end of the last sentence might be the nerdiest exclamation point ever.) It turns out that the number of wrongfully seated passengers follows a Harmonic Series.

What this means is that the odds of anyone getting a wrong seat follows this pattern, starting from the last passenger to board: 1/2 + 1/3 + 1/4 + … You can see from the output that the chances of each passenger not getting their seat is indeed following that pattern, with a little Monte Carlo variance thrown in.

“But wait,” you say, probably not, but let’s pretend you do, “a Harmonic Series starts with one and you don’t have a one in there.” Oh but I do. But it comes at the end. Remember that in our simulation, Worst Person Alive boards first and therefore has a 99/100 chance of sitting in the wrong seat. The next person to board, let’s call him Rando Paul, has a 1/100 chance of finding WPA in  his seat. 99/100 + 1/100 = 1. The next person then has a 1/99 chance and on down to 1/2 for the last passenger. So the average number of wrongly seated passengers for N passengers with the Worst Person Alive seating first boils down to 1 + 1/2 + 1/3 + … + 1 / (N – 1).

Traffic jams and airline travel: unexpected sources of harmony. Thanks for reading!

 

The 538 Riddler: Traffic Jam

Hello reader(s)! Well, I’m 4-for-4 on the Riddlers so far and I’m having a lot of fun writing the code and talking about my approach, and also reading about the approaches that others have taken. I hope to keep doing this.

This week’s Riddler concerns my daily commute to work on most mornings, seemingly. Here it is:

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be Ngroups — no car ever gets stuck behind a slower car.

So my first approach to this was just to get some ballpark answers so I would know what kind of real answers to expect. I think a real mathematician would have taken a very different route to get to this answer, but I’m a programmer, so the first thing I did was write a Monte Carlo to just simulate what was happening on the road, man.

int TrafficJam(int carCount)
{
    int currentSpeed = 0;
    int packs = 0;
    int packSize = 0;

    for(int i = 0; i < carCount; i++)
    {
        int speed = 1 + rand();
        if((speed < currentSpeed) || (currentSpeed == 0))
        {
            if(packSize > 0)
            {
                //printf("%d cars in pack.\n", packSize);
            }
            packs++;
            currentSpeed = speed;
            //printf("New pack forming at %d, ", speed);
            packSize = 1;
        }
        else
        {
            packSize++;
        }
    }
    //printf("%d cars in pack.\n", packSize);
    //printf("With %d cars, %d packs formed.\n\n", carCount, packs);
    return packs;
}

void TrafficJamMC(int carCount)
{
    const int c_nTrials = 10000;
    int totalPacks = 0;
    for(int i = 0; i < c_nTrials; i++)
    {
        totalPacks += TrafficJam(carCount);
    }

    double avgPacks = (double)totalPacks / (double)c_nTrials;
    printf("After %d trials, average pack count with %d cars is %.3f or %.3fn\n"
        , c_nTrials, carCount, avgPacks, avgPacks / (double)carCount); 
}

 

Here’s the output for up to 25 cars:

After 10000 trials, average pack count with 1 cars is 1.000 or 1.000n
After 10000 trials, average pack count with 2 cars is 1.504 or 0.752n
After 10000 trials, average pack count with 3 cars is 1.826 or 0.609n
After 10000 trials, average pack count with 4 cars is 2.087 or 0.522n
After 10000 trials, average pack count with 5 cars is 2.302 or 0.460n
After 10000 trials, average pack count with 6 cars is 2.462 or 0.410n
After 10000 trials, average pack count with 7 cars is 2.572 or 0.367n
After 10000 trials, average pack count with 8 cars is 2.725 or 0.341n
After 10000 trials, average pack count with 9 cars is 2.824 or 0.314n
After 10000 trials, average pack count with 10 cars is 2.922 or 0.292n
After 10000 trials, average pack count with 11 cars is 3.016 or 0.274n
After 10000 trials, average pack count with 12 cars is 3.108 or 0.259n
After 10000 trials, average pack count with 13 cars is 3.170 or 0.244n
After 10000 trials, average pack count with 14 cars is 3.245 or 0.232n
After 10000 trials, average pack count with 15 cars is 3.314 or 0.221n
After 10000 trials, average pack count with 16 cars is 3.363 or 0.210n
After 10000 trials, average pack count with 17 cars is 3.436 or 0.202n
After 10000 trials, average pack count with 18 cars is 3.489 or 0.194n
After 10000 trials, average pack count with 19 cars is 3.522 or 0.185n
After 10000 trials, average pack count with 20 cars is 3.585 or 0.179n
After 10000 trials, average pack count with 21 cars is 3.643 or 0.173n
After 10000 trials, average pack count with 22 cars is 3.693 or 0.168n
After 10000 trials, average pack count with 23 cars is 3.732 or 0.162n
After 10000 trials, average pack count with 24 cars is 3.759 or 0.157n
After 10000 trials, average pack count with 25 cars is 3.816 or 0.153n

 

So this code works ok and gives us reasonable answers, but it has some obvious flaws. As with most Monte Carlos it will never give exact answers.

Also, simulating speeds might be fun, but it’s not really getting to the heart of the problem. What we really want to do is order all the cars and see how many jams would result. For any n number of cars we know that there are n-factorial variations of ordering.

For 2 cars, there are only 2 orders, for 3 cars there are 6 orders, and for 4 cars there are 24 different orders. They produce packs like this:

2 cars:
0 1 – 1 pack
1 0 – 2 packs

3/2 packs

3 cars:
0 1 2 – 1 pack
0 2 1 – 1 pack
1 0 2 – 2 packs
1 2 0 – 2 packs
2 0 1 – 2 packs
2 1 0 – 3 packs
—-
11/6 packs

4 cars:
0 1 2 3 – 1 pack
0 1 3 2 – 1 pack
0 2 1 3 – 1 pack
0 2 3 1 – 1 pack
0 3 1 2 – 1 pack
0 3 2 1 – 1 pack
1 0 2 3 – 2 packs
1 0 3 2 – 2 packs
1 2 0 3 – 2 packs
1 2 3 0 – 2 packs
1 3 0 2 – 2 packs
1 3 2 0 – 2 packs
2 0 1 3 – 2 packs
2 0 3 1 – 2 packs
2 1 0 3 – 3 packs
2 1 3 0 – 3 packs
2 3 0 1 – 2 packs
2 3 1 0 – 3 packs
3 0 1 2 – 2 packs
3 0 2 1 – 2 packs
3 1 0 2 – 3 packs
3 1 2 0 – 3 packs
3 2 0 1 – 3 packs
3 2 1 0 – 4 packs

50/24 packs

Let’s write some code to run through them all and count the jams. Yay, we get to use next_permutation, one of my favorite std algorithms. Here’s a function that will run through all permutations of n-factorial cars and tell you precisely how many jams you have:

#define MAX_CARS_FOR_PERMS 10
void TrafficJamPerm(int carCount)
{
    if(carCount > MAX_CARS_FOR_PERMS)
        return;

    int order[MAX_CARS_FOR_PERMS] = {};
    for(int i = 0; i < carCount; i++)
        order[i] = i;

    int totalPacks = 0;
    int perms = 0;
    do
    {
        int packs = 0;
        int currentSpeed = 0;
        for(int i = 0; i < carCount; i++)
        {
            if(i == 0 || order[i] < currentSpeed)
            {
                packs++;
                currentSpeed = order[i];
            }
        }
        totalPacks += packs;
        perms++;
    }
    while(next_permutation(order, order + carCount));
    
    printf("Using permutations, packs for %d cars = %d / %d = %.3f or %.3fn\n"
        , carCount, totalPacks, perms, (double)totalPacks / (double)perms, ((double)totalPacks / (double)perms) / (double)carCount);
}

 

And here’s the output:

Using permutations, packs for 1 cars = 1 / 1 = 1.000 or 1.000n
Using permutations, packs for 2 cars = 3 / 2 = 1.500 or 0.750n
Using permutations, packs for 3 cars = 11 / 6 = 1.833 or 0.611n
Using permutations, packs for 4 cars = 50 / 24 = 2.083 or 0.521n
Using permutations, packs for 5 cars = 274 / 120 = 2.283 or 0.457n
Using permutations, packs for 6 cars = 1764 / 720 = 2.450 or 0.408n
Using permutations, packs for 7 cars = 13068 / 5040 = 2.593 or 0.370n
Using permutations, packs for 8 cars = 109584 / 40320 = 2.718 or 0.340n
Using permutations, packs for 9 cars = 1026576 / 362880 = 2.829 or 0.314n
Using permutations, packs for 10 cars = 10628640 / 3628800 = 2.929 or 0.293n

 

Ok, cool, but do you see the problem? Yeah, this code only handles up to 10 cars and that’s because factorials get really big, really fast. The first 9 calls to this function return almost immediately but the 10th one starts to chug a little. A 32-bit integer could handle up to 12-factorial and 64 bits could get us to 20-factorial, but it doesn’t matter because we don’t have enough time to run through all those permutations. So this function works and is useful, but… it’s not great.

So there IS a math solution to this problem that doesn’t rely on Monte Carlos or permutations. I found it but I don’t know how to prove it. I’m not really a mathematician, I’m a programmer, so here’s my best explanation:

Average number of packs A(n) is equal to: Num(n) / Denom(n) where:
    Num(1) = 1, Denom(1) = 1.
    Num(n) = Num(n – 1) * n + Denom(n – 1).
    Denom(n) = Denom(n – 1) * n.  (this is n-factorial).

Okay, so I found that because I happened to see the pattern when I was looking at those numerators and denominators. I don’t really know why this is true. I can kind of work it out if I look at the lists of permutations between 2 cars and 3 cars and 4 cars, but I can’t really explain it well.

Anyway, here’s a function to calculate the average number of jams using math. I used a class called InfInt written by Sercan Tutar for this. This allows me to calculate factorials for very large numbers.

void TrafficJamMath(int carCount)
{
    InfInt num = 1;
    InfInt denom = 1;

    for(int i = 2; i <= carCount; i++)
    {
        num *= i;
        num += denom;
        denom *= i;
    }

    num *= 1000000;
    int l = (num / denom).toInt();

    double avg = (double)l / 1000000.0;
    double perN = avg / (double)carCount;

    printf("Using math, number of Traffic Jams for %d cars = %.3f or %.6fn\n", carCount
        , avg, perN); 
}

 

I ran this function to calculate the average traffic jams for 100, 1000, and 10000 cars.

Using math, number of Traffic Jams for 100 cars = 5.187 or 0.051874n
Using math, number of Traffic Jams for 1000 cars = 7.485 or 0.007485n
Using math, number of Traffic Jams for 10000 cars = 9.788 or 0.000979n

 

Let me just say that 10000-factorial is a very large number. It’s kind of interesting how we quickly get to 3 traffic jams with 10 cars, but with 10,000 cars we are still at only about 10 very large, frustrating jams. This explains Southern California freeways pretty well, actually.

Finally, crossing my fingers, but I think I found a pretty good solution for displaying source code in this blog. Special thanks to Alexander Kojevnikov for hilite.me. Here’s the complete source code for this post. You will need the InfInt class linked above.

Thanks for reading!

UPDATE: Alex Mahdavi points out that my really complicated equation can just be written as 1 + 1/2 + 1/3 + 1/4 + … + 1/n, also known as a Harmonic Series. Thanks Alex!

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.

The 538 Riddler: River Crossing

Well, the answer was published to last week’s Riddler, and I was right. I’m two-for-two so far, so I might as well keep going. This week’s Riddler is a real fun one because I got to do some basic pathfinding. Here’s the problem from Ollie:

You’re on the north shore of a river, and want to cross to the south, via a series of 13 bridges and six islands, which you can see in the diagram below. But, as you approach the water, night falls, a bad storm rolls in, and you’re forced to wait until morning to try to cross. Overnight, the storm could render some of the bridges unusable — it has a 50 percent chance of knocking out each of the bridges. (The chance is independent for each bridge.)

roeder-riddler-diagram-11

Question 1: What’s the probability you will be able to cross the river in the morning? (You have no boat, can’t swim, can’t fix the bridges, etc. No tricks.)

Now imagine a different, wider river, with many more islands — in fact, arbitrarily many. Specifically, imagine that the islands are arrayed in an N-rows-by-N+1-columns grid — similar to before, where N happened to equal two — and connected by bridges to each adjacent island in the same way. Each island adjacent to the shore is also connected by a bridge to the shore. It would look something like this:

roeder-riddler-diagram-21

Question 2: What’s the probability you’ll be able to cross this river in the morning, after the same storm — with the same independent 50 percent chance of knocking out each bridge — rolls through?

Cool!

I read this Friday morning and got to think about it all day at work before I could actually do any work on it. Even before I did any programming I was already pretty sure what the answers to questions one and two were: 50%. This is not because of any great critical thinking on my part, but because of a board game I used to play way back in the day called Bridg-It!

Bridgit

Bridg-It! was one of those games that seem really fun until you discover that whoever goes first always wins, unless a mistake is made. It consists of two sets of interleaved NxN+1 “islands” that belong to each player. Placing a bridge between two of your islands blocks your opponent from placing a bridge between two of theirs. Whoever completes a bridge from their start to destination first is the winner. One player is moving “North-to-South” while the other move “East-to-West.” Each player is playing on an NxN+1 board while defending against an N+1xN board. It’s neat.

Anyway, I suspected that the answer was going to be 50% for any arbitrary NxN+1 group of islands so I set out to test it. One way to handle these “N+1” types of problems is to reduce N to its simplest form first, then work from there. The simplest form for N would be N=0, giving a river with 0 rows of islands and 1 column of bridges, or a single bridge across a river. Obviously if a storm has a 50% chance of knocking out the bridge, you’ll have a 50% chance of crossing in the morning.

So the next step is a river with 1 row of two islands, as below:

RiverCrossing0

Now I decided to modify the story a bit to make it a little more realistic.

A certain governor has decided to block access to bridges in towns in which their mayors refused to endorse him in his reelection campaign. If, on average, 50% of the mayors chose to endorse the governor, what are the chances that commuters will be able to travel from the South bank to the North bank? (Way more realistic than storms knocking out bridges. C’mon!)

Since there are 5 bridges in our map, and each bridge may be blocked (with a traffic cone) or clear, there are 32 (2^5) possible combinations to consider, each equally likely. Here they are:

RiverCrossing

We can quickly count that there are 16 happy commuter faces and 16 angry commuter faces. Bad governor!

Once you get past a 1×2 problem, the number of bridges grows pretty quickly. For 2×3 it grows to 13 bridges and for 3×4 it’s 25 bridges. In fact, the number of bridges is defined as (rows + 1) * columns + (columns – 1) * rows. If you stick to NxN+1 arrangements this becomes N-squared + (N+1)-squared, but there’s no reason to do that, except that it has the interesting (proposed) property of always being 50%.

I wrote a program (of course) to calculate the odds of being able to cross the river given arbitrary island arrangements, even allowing you to specify the failure rate of bridges (or endorsement rate of mayors.)

Calculating whether a path to the goal is present is straightforward for a 1×2 or even a 2×3 arrangement, but gets a little more complicated as the number of bridges increases. I wrote a simple breadth-first search (no need for A* here) to do the trick. Here’s the code:

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

#include "stdafx.h"
#include <vector>
#include 	<list>
#include <hash_set>

using namespace std;

enum EDir
{
    D_North,
    D_East,
    D_South,
    D_West,
};

struct Island
{
    int m_row;
    int m_col;

    Island(int row = 0, int col = 0) : m_row(row), m_col(col) {}
};

class River
{
public:
    static int BridgeCount(int rows, int cols)
    {
        return (rows + 1) * (cols) + (rows) * (cols - 1);
    }

    River(int rows, int cols) : m_rows(rows), m_cols(cols)
    {
        int bridgeCount = BridgeCount(rows, cols);
        for(int i = 0; i < bridgeCount; i++)
        {
            m_bridges.push_back(true);
        }
        m_goodBridges = bridgeCount;
    }

    void Storm(double destroyPct)
    {
        for(auto itr = m_bridges.begin(); itr != m_bridges.end(); itr++)
        {
            double d = (double)rand() / (double)RAND_MAX;
            if(d < destroyPct)
            {
                *itr = false;
                m_goodBridges--;
            }
        }
    }

    void NthPermutation(unsigned long long perm)
    {
        // we can only handle rivers with <= 64 bridges (5 x 6)         if(m_bridges.size() > sizeof(perm) * 8)
            return;
        m_goodBridges = 0;
        for(int i = 0; i < (int)m_bridges.size(); i++)
        {
            if((perm & (1LL << i)) != 0)
            {
                m_bridges[i] = true;
                m_goodBridges++;
            }
            else
            {
                m_bridges[i] = false;
            }
        }
    }

    bool CanCross() const
    {
        // weed out some obvious cases
        if(m_goodBridges < m_rows) // not enough bridges to go straight across             return false;         if(m_goodBridges > (int)m_bridges.size() - m_cols) // not enough out bridges to block path 
            return true;

        hash_set<int> islandsVisited;

        list<Island> listToVisit;
        listToVisit.push_back(Island(-1, 0));

        while(!listToVisit.empty())
        {
            Island current = listToVisit.front();
            listToVisit.pop_front();

            list<Island> neighbors = GetNeighbors(current);

            for(auto itr = neighbors.begin(); itr != neighbors.end(); itr++)
            {
                if(islandsVisited.find(IslandIndex(*itr)) != islandsVisited.end())
                    continue;
                if(itr->m_row >= m_rows)    // we've crossed the river!
                    return true;
                islandsVisited.insert(IslandIndex(*itr));
                listToVisit.push_back(*itr);
            }
        }

        return false;
    }

    void PrintRiver()
    {
        printf("-----------------------------\n");
        for(int row = 0; row <= m_rows; row++)
        {
            for(int col = 0; col < m_cols; col++)
            {
                Island isle(row, col);
                if(CheckBridge(isle, true))
                {
                    printf(" |    ");
                }
                else
                {
                    printf("      ");
                }
            }
            printf("\n");
            if(row == m_rows)
                break;

            printf("XXX");
            for(int col = 1; col < m_cols; col++)
            {
                Island isle(row, col);
                if(CheckBridge(isle, false))
                {
                    printf("===XXX");
                }
                else
                {
                    printf("   XXX");
                }
            }
            printf("\n");
        }
        printf("-----------------------------\n");
    }

    static double TestCanCross(int rows, int cols, double destroyPct)
    {
        if(rows < 0 || cols <= 0)
            return 0;
        int bridgeCount = BridgeCount(rows, cols);
        printf("Testing river with %dx%d islands, %d bridges, %.2f%% chance of bridge failure:\n",
            rows, cols, bridgeCount, 100.0 * destroyPct);

        int trials = 0;
        int crossings = 0;

        if(bridgeCount <= 25 && destroyPct == 0.5)
        {
            // we can permutate for up to 3 x 4 if destroyPct is 50%
            trials = 1 << bridgeCount;
            crossings = 0;
            River river(rows, cols);
            for(int i = 0; i < trials; i++)
            {
                river.NthPermutation(trials - i - 1);
                if(river.CanCross())
                {
                    crossings++;
                }
            }
            printf("Crossings = %d of %d permutations (%.3f%%)\n\n", crossings, trials, (double)crossings * 100.0 / (double)trials);
        }
        else
        {
            trials = 10000;
            crossings = 0;
            for(int i = 0; i < trials; i++)
            {
                River river(rows, cols);
                river.Storm(destroyPct);
                if(river.CanCross())
                {
                    crossings++;
                }
            }
            printf("Crossings = %d of %d Monte Carlo trials (%.3f%%)\n\n", crossings, trials, (double)crossings * 100.0 / (double)trials);
        }

        return (double)crossings / (double)trials;
    }

private:
    int m_rows;        // vertical islands 
    int m_cols;        // horizontal islands 
    int m_goodBridges;

    vector<bool>    m_bridges;    // (m_rows + 1) * (m_cols) + (m_rows) * (m_cols - 1)

    int    BridgeIndex(const Island &isle, bool vertical) const
    {
        if(vertical)
        {
            if(isle.m_col < 0 || isle.m_col >= m_cols)
                return -1;
            if(isle.m_row < 0 || isle.m_row > m_rows)
                return -1;
            return isle.m_row * m_cols + isle.m_col;
        }
        else
        {
            if(isle.m_col < 1 || isle.m_col >= m_cols)
                return -1;
            if(isle.m_row < 0 || isle.m_row >= m_rows)
                return -1;
            return (m_rows + 1) * m_cols + isle.m_row * (m_cols - 1) + isle.m_col - 1;
        }
    }

    bool CheckBridge(const Island &isle, bool vertical) const
    {
        int idx = BridgeIndex(isle, vertical);
        if(idx < 0 || idx >= (int)m_bridges.size())
            return false;
        return m_bridges[idx];
    }

    int IslandIndex(const Island &isle) const 
    {
        if(isle.m_row < 0)             return -1;         if(isle.m_row >= m_rows)
            return m_rows * m_cols;
        return isle.m_row * m_cols + isle.m_col;
    }

    list<Island> GetNeighbors(const Island &isle) const
    {
        Island next;
        list<Island> neighbors;

        // special case if isle.m_row == -1, then it's north shore
        if(isle.m_row < 0)
        {
            next.m_row = 0;
            for(next.m_col = 0; next.m_col < m_cols; next.m_col++)             {                 if(CheckBridge(next, true))                 {                     neighbors.push_back(next);                 }             }             return neighbors;         }         // get north island         if(isle.m_row > 0)
        {
            // check vertical bridge to current island
            if(CheckBridge(isle, true))
            {
                next.m_row = isle.m_row - 1;
                next.m_col = isle.m_col;
                neighbors.push_back(next);
            }
        }
        // get south island
        if(isle.m_row <= m_rows)         {             next.m_row = isle.m_row + 1;             next.m_col = isle.m_col;             // check vertical bridge to south island             if(CheckBridge(next, true))                 neighbors.push_back(next);         }         // get west island         if(isle.m_col > 0)
        {
            // check horizontal bridge to current island
            if(CheckBridge(isle, false))
            {
                next.m_row = isle.m_row;
                next.m_col = isle.m_col - 1;
                neighbors.push_back(next);
            }
        }
        // get east island
        if(isle.m_col < m_cols)
        {
            next.m_col = isle.m_col + 1;
            next.m_row = isle.m_row;
            if(CheckBridge(next, false))
            {
                neighbors.push_back(next);
            }
        }

        return neighbors;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    River::TestCanCross(1, 2, 0.5);
    River::TestCanCross(2, 3, 0.5);
    River::TestCanCross(3, 4, 0.5);
    River::TestCanCross(10, 11, 0.5);
    River::TestCanCross(20, 21, 0.5);

    return 0;
}

This code is a little more “C-plus-plusy” than the previous two problems; I made a class called River which takes parameters of how many rows and columns of islands to add. It then creates the necessary bridges. A Storm() function takes a parameter for how likely it is to destroy a bridge and then it applies that to all the bridges on the River. A CanCross function uses the breadth-first search to find a path if it exists. Finally, a static function called TestCanCross will take those parameters and do an exhaustive test to find how often a path can be found.

A note on programming and probability and permutations and Monte Carlos. If you can “do the math” to find a solution, that’s preferred. For example, if you want to calculate the odds of flopping a set in poker when you hold a pocket pair, it’s best to know that the odds are: 1 – (48 * 49 * 50) / (50 * 51 * 52) = 11.756%. Similarly if you want to calculate the odds of flopping quads, it’s best to know that the odds are: 1 / (50 * 49) but multiplied by 3-factorial (6) because the order of the cards in the flop don’t matter, so 0.244%. If you don’t know the math but know all the permutations (and they are equally likely), then simulating all the permutations is better. Permutations can give you the precise answer, but can be slow.

If you don’t know the math and the permutations are unknown or too vast or not evenly distributed, then the last refuge of the scoundrel simulator programmer is the Monte Carlo, usually with some number of trials like 10,000. Monte Carlos will have more variance with fewer trials, so you need to balance the need for speed with the need for precision. I didn’t really feel like doing the Boolean Algebra to prove this answer, so I did a combination of permutations and Monte Carlos. The number of permutations for a given river is 2^(number of bridges) assuming that the chance of bridge failure is 50%. The TestCanCross function checks to see if the failure rate is 50% and if the number of bridges is less than or equal to 25 (so I could do 3×4). If so, it uses permutations and gives an exact number. A 3×4 configuration results in 25 bridges and 33 million permutations. Anything more than 25 bridges and the program says, “lol, no, it’s Monte Carlo time” and does 10,000 trials. With that in mind, here’s the output:

Testing river with 1x2 islands, 5 bridges, 50.00% chance of bridge failure:
Crossings = 16 of 32 permutations (50.000%)
Testing river with 2x3 islands, 13 bridges, 50.00% chance of bridge failure:
Crossings = 4096 of 8192 permutations (50.000%)
Testing river with 3x4 islands, 25 bridges, 50.00% chance of bridge failure:
Crossings = 16777216 of 33554432 permutations (50.000%)
Testing river with 10x11 islands, 221 bridges, 50.00% chance of bridge failure:
Crossings = 5007 of 10000 Monte Carlo trials (50.070%)
Testing river with 20x21 islands, 841 bridges, 50.00% chance of bridge failure:
Crossings = 4963 of 10000 Monte Carlo trials (49.630%)

This was a lot of fun, although technically I didn’t prove the answer; I just showed that for all tested NxN+1 configurations the answer remains the same. I’m a little embarrassed to admit that I spent more time working on the bad programmer art than I did programming, but what the heck, it was fun. I look forward to seeing the mathematical proof of what I demonstrated.

UPDATED: UUUUUGGGGGGGHHHHHH. WordPress, why are you so awful? I can’t get the spacing right in the code section. I hand edited each line to add spaces, saved, published, and… no change. I’ll try to get it fixed this weekend, but not right now. Copy/pasta then run it through beautify if you are a coder…