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…

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

4 thoughts on “The 538 Riddler: River Crossing”

  1. Again, congrats on the programming. My approach to a proof largely ditches a lot of the math, and deals with it more like a geometry problem.
    Building on your Bridg-it game, I think of this problem in terms of routes. Either there will be a successful route across the river, or there won’t. Now imagine a tall ship is coming down the river, whose mast is too tall for the ship to pass under any bridges. From the ship’s perspective, it is also looking for a successful route- a navigable route downstream past the islands. Similar to the two sides in Bridg-it, there can either be a successful land route, or a successful water route, but there cannot be both (any land route would block any water route, and vice versa). Now for any N by N+1 configuration, there are is going to be a predictable grid of possible bridge routes. For N=1, the route grid looks like an H. For any N, the grid has N+1 possible starting points, and N+1 minimum ‘steps’ (bridges which may or may not exist). Now that you’ve visualised how these route grids will always look, given N, now think about the same configuration of islands from the ship’s perspective. For a given N, what does the ship’s route grid look like? For N=1, the ships route grid looks like an H on its side. For any N, the ship will also always face N+1 possible starting points (gaps between landmasses, whether the shore or islands), and a minimum N+1 possible ‘steps’ (points where a bridge could block a route.) Now these ‘steps’ are shared by both land and water routes. A bridge is a passable land route and block water route. A missing bridge is a blocked land route and passable water route. So regardless of N, the possible land routes and water routes will always look the same, which the same chance of failure/success, given the 50/50 chances of any one step being blocked/passable.
    So any N has a 1/2 chance of a possible successful land route.

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s