Forem: Bastian Heinlein

Solving the Game Show Problem with Python

Bastian Heinlein — Tue, 16 Mar 2021 20:07:15 +0000

You might have heard of the famous "Game Show Problem" (it's also known as the "Monty Hall Problem"). If you did, there's a good chance that it confused you. If you didn't know it yet, there's a good chance that it will confuse you. It's a pretty famous example for applied probability theory and often featured in movies because it's a bit counter-intuitive but still simple enough to be understandable for most people.

The Situation

You are participant in a game show where you can win a car. You are shown three closed containers, in one of which the car is. The other two contain goats.

The host initially let's you choose one of the containers. If you chose the one with the car, the car will be yours.

However, after you have chosen the container, the host always opens one of the two remaining containers and always reveals a goat. Now you are offered to change your decision and instead choose the other unopened container. How would you decide?

Our Approach

We will do several things in this article:

Reformulate the problem
Simulate the problem
Examine the problem in detail
Generalize the problem

Reformulate the Problem

We do this first step only to make sure we all understood the problem correctly. Hence, we write it a bit more "algorithmically":

Assumptions:

3 containers, one contains the car, two contain a goat
the probability that the car is in any specific container is 1/3
we don't know which one container contains what
we win if we chose the container with the car in the end
the host has full information about the content of each container and opens always a goat container

Procedure

We choose one container.
The game show host open a different container than the one we chose. This container contains a goat.
We are asked wether we want to switch to the container.
We switch the container or not.
The container we chose in the end is opened.

I hope that we are all on the same page now. If something isn't clear so far, feel free to ask in a comment.

Simulate the Problem

Instead of making a deep dive into probability theory, we try to simulate the situation at first. Such explorative simulations are often a good idea because we might discover counter-intuitive behaviour. If we later analyse the problem in a more theoretical way, we can check if the results match.

Case A: No Switching

We start with the easier case, namely we don't switch when we have the chance. In this situation, the procedure is a lot simpler:

Choose a container
Game host opens our container and reveals wether we won

Because we never switch, the moderator doesn't have to open a container. Hence, we can ignore this step of the game.

Our simulation consists of two parts: In the first part, we simulate the mechanisms of one game. In the second part, we perform several games to get a good estimate for the true probability.

A single game looks like this:

def gameshow_no_switching(user_choice:int) -> bool:
    """One gameshow with the user strategy "no switching".

    The car is behind one of the three containers `0,1,2`.

    Parameters
    ----------
    - `user_choice`: container chosen by the user

    Returns
    -------
    - `true` if the user chose the container with the car
    - `false` otherwise
    """
    car_container = randint(0,2)

    if user_choice == car_container:
        return True
    return False

randint(0,2) chooses a random integer in {0,1,2}.

Repeating the games is a now trivial thing:

def simulate_gameshow(n_times:int) -> None:
    """Simulates the game show `n_times` and prints the 
    estimates for the probabilites to choose the container with
    the car. 
    """
    n_car = 0 # saves how often we get the car

    for _ in range(n_times):
        if gameshow_no_switching(randint(0,2)):
            n_car += 1

    print("Probabilty to choose the right container: {:.1f}%".format(n_car/n_times*100))

In order to get a reliable estimate, we run the gameshow a million times. The output always should be approximately 33.3%.

That's of course what our intuition would suggest: We can only guess which of the three doors is the right one. Hence we have chance of 1/3 to choose correctly.

Case B: Switching

In this case, everything becomes a bit more complex. Hence, we will write down what we have to do if we switch all the time:

We choose initially a container.
The host opens a different container and reveals a goat.
We switch to the other closed container.
This container is opened and checked to see wether we won.

Again, we divide our simulation in two steps: We describe the mechanism of one game and then run repeated games.

A single game looks like this:

def gameshow_switching(user_choice:int) -> bool:
    """One gameshow with the user strategy "switching".

    The car is behind one of the three containers `0,1,2`.

    Parameters
    ----------
    - `user_choice`: container initially chosen by the user

    Returns
    -------
    - `true` if the user chose the container with the car
    - `false` otherwise
    """
    car_container = randint(0,2)

    ### Game host opens a container and reveals a goat ###
    open_candidates = [0,1,2]

    # Host doesn't open the container with the car inside
    open_candidates.remove(car_container)

    # Host doesn't open the container we chose
    if user_choice in open_candidates:
        open_candidates.remove(user_choice)

    # Host chooses the first remaining container
    opened_container = open_candidates[0]

    ### Player switches container ###
    switch_candidates = [0,1,2]

    # Don't switch to the opened container
    switch_candidates.remove(opened_container)

    # Don't choose the same container we already selected
    switch_candidates.remove(user_choice)

    new_user_choice = switch_candidates[0]

    # Check if we chose the right container
    if new_user_choice == car_container:
        return True
    return False

I tried my best to write readable code and provide meaningful comments, but if you have suggestions for improvements I'd be happy to hear them!

Again, running the game repeatedly is trivial and looks identical to the "Case A":


def simulate_gameshow(n_times:int) -> None:
    """Simulates the game show `n_times` and prints the 
    estimates for the probabilites to choose the container with
    the car. 
    """
    n_car = 0 # saves how often we get the car

    for _ in range(n_times):
        if gameshow_switching(randint(0,2)):
            n_car += 1

    print("Probabilty to choose the right container: {:.1f}%".format(n_car/n_times*100))

If we now run our simulation, we get a different probability estimate: We choose the correct container in approximately 66.7% of the cases. We effectively doubled our chances to win a car!

The only interesting question is: Why?

Examine the Problem in Detail

So, our simulation gave us some crazy results, but honestly it didn't do anything to help us understand why we get these. Hence, it seems like a good time to take a more theoretical look at the problem.

If you don't want to read my explanation, here's a clip from a nice movie in which the problem is explained:

In order to make our analysis simpler, we assume that we always choose container 0. However, the car is still randomly distributed in all containers, so this restriction doesn't change the problem (you can verify this by modifying your simulation).

Now, we basically write down the "decision tree" for this problem to examine all possible scenarios.

At first, the car is randomly distributed in one of the three containers. So far, our tree looks like this:

Note 1: We annotate on the branches the probability how likely the specific decision is.
Note 2: If we stopped here, we had the situation like in case A and we would immediately see that we have a probability of 1/3 to choose the correct container.

In the second step, the game show host opens a container. Remember, we already chose container 0. If the car is in container 0, the host can choose between opening container 1 or 2. We assume that this happens randomly (that's in fact not necessary: it's also fine if the host always chooses the smaller container).

If however the car is in container 1 or 2, he only has one choice! Hence, the extended tree looks now like this:

Finally, we choose to switch the container. What's now interesting is that in all cases, we don't have a choice to where we want to switch! Hence, the probability to switch to a given container is always 1. Our final tree looks now like this:

In order to get the probability for each possible situation, we just have to multiply the probabilities on consecutive branches. E. g., for the left branch, we get: 1/3 * 1/2 * 1 = 1/6.

We now see that in 2/3 of all cases, we will in fact have chosen the right container in the end! That's because we profoundly changed the problem by introducing conditional probabilities.

Generalized Problems

Finally, we want to generalise this problem to a situation where we might have 100s or even millions of containers.

N Containers, N-2 Opened Containers

We now want to consider a situation with N containers, where N is a positive integer larger than 2. Again, the car is randomly hidden in one of the containers. For simplicity, we still always choose container "0".

However, this time the game show host opens N-2 containers; in each we find a goat. Now, the question is how likely we will get the car if we switch. Spoiler alert: The probability to win the car becomes (N-1)/N!

So, if we had 100 containers, we'd have a chance of 99% to win the car if we employ our switching strategy! That's definitely a lot better than our 1% chance if we stay with our initial decision.

I'll try to outline how we arrive at these crazy results: Initially, the chance that we chose the container with the car was 1/N. Hence, the probability that the car was in one of the other containers is (N-1)/N. A bit more graphical:

If the host opens N-2 of the other containers and none of them contains the car, that doesn't change how likely we guessed initially the correct container. So all the "remaining probability" shifts into the one unknown container that we didn't choose. Now our situation looks like this:

I encourage you to simulate this situation as well and check this theoretical result.

N Containers, M Opened Containers

Finally, we want one more generalisation: What if the host doesn't open all but one of the remaining containers and instead only a few of them?

Again, we consider the situation after we initially chose the container 0. The situation is identical to before, we just draw it a bit differently:

If the host now opens M containers and all of them contain a goat, the uncertainty for these containers is eliminated. However, the probability that our initial guess was correct is still 1/N:

There are N-1-M containers left that we could switch to. But the probability that the goat is in one of these is still P=(N-1)/N. Hence, the probability that we choose the correct container if we switch is P/(N-1-M)=(N-1)/((N-1-M)*N)=(N-1)/(N^2-N-MN).

Sadly, this is not exactly a very nice result, but we still can evaluate it. Assume we have N=100 containers and after our initial guess, the host opens M=80 of the remaining ones and each contains a goat. Then switch improves our probability of being correct from 1% to 99/100 * 1/(19)=99/1900=5.52%. That's at least 5 times better than before!

If M was 85, we would improve to 7.1%. If M was 90, we would get 11% right. If M was 95, it would even be 24.8%.

Conclusion

I'd briefly like to recap what we looked at in this article:

Making sure to understand the problem in the beginning makes subsequent steps easier.
Simulations can be a fast way to get important results for complex problems.
A theoretical treatment of these problems reveals the underlying mechanisms. It is supported by simulation results that we can test our theories against.
From a theoretical perspective on a specific problem we usually can abstract to more general problems and get broader insights.

Classification Challenge: Where to go out after Corona?

Bastian Heinlein — Sat, 26 Dec 2020 20:49:06 +0000

Imagine a bright future. A vaccine has been distributed. No more masks, no distancing. Instead, everyone can go out again. But many people will have forgotten where to eat and drink!

Hence, you feel motivated to leverage your skills and build an app to help them figure that out. There are four options: Visit a people's fair, a bar, just meet at the food stall across the street or visit a proper restaurant.

To make your app very simple, you decide to base your recommendation only on three parameters: How hungry the users are, how much booze they want to drink and how many friends are going out.

The Challenge

Of course, your recommendation shouldn't be entirely based on your personal preference. Therefore, you decide to gather some data. You can find the full data set here:

bahe007 / ClassifierChallenge

A challenge to build a classifier that decides for you where to go out after a Corona vaccine has been distributed.

ClassifierChallenge

Learn everything about the challenge on dev.to.

You can find the dataset in the file TrainingData.csv above.

Happy Coding! 👩‍💻👨‍💻🧑‍💻

You are welcomed to present your solutions on dev.to as a comment. That's also a great place to discuss your approaches and their strenghts or weaknesses.

Disclaimer

This challenge is based on an artificially generated dataset. However, that shouldn't prevent you from having fun! In fact, it's especially designed to be solvable and demonstrate some important concepts of data science.

View on GitHub

Now, it's your task to develop a very accurate and robust classifier to fulfil this task.

You are free to use whatever language you like. Of course, you could use a framework, but it'd be more interesting to write a classifier entirely by yourself.

On whatever tools you decide, feel free to share you results here!

Happy coding! 👩‍💻🧑‍💻👨‍💻

Title image: Pixabay

Fundamentals of Numerical Stability

Bastian Heinlein — Wed, 29 Jul 2020 19:20:40 +0000

Mathematical operations are the basis of most algorithms. We increment counter variables, calculate percentages or measure distances between objects. And it just works.

Until it doesn't. Of course, there are obvious errors like reusing a variable without resetting its value or using the wrong formula for a problem. However, I'd like to shine light on a completely different issue: Numerical stability of algorithms.

Sounds fancy and it is kinda. Because this is such a broad and potentially difficult topic, we'll only look at a simple example.

The Task

I watched this great YouTube video the other day, which covered an 1869 MIT maths entrance exam. In exercise 5 this expression should be simplified:

\frac{ \frac{a+b}{a-b} + \frac{a-b}{a+b} }{ \frac{a+b}{a-b} - \frac{a-b}{a+b} }

The Programmer's Solution

As a programmer you could say: Wait, why would I do that? I have a super-fast computer. Let's just write a function to calculate this expression. We even use a simplification to make life simpler for the computer. We set: $c = a + b$ and $d = a - b$ . Now we got this:

\frac{ \frac{c}{d} + \frac{d}{c} }{ \frac{c}{d} - \frac{d}{c} }

Now the calculation can be completed in only two additions, two subtractions and five divisions. This is profoundly simpler than the initial five additions, five subtractions and five divisions. Note that we didn't change the expression's form.

We could go even further and find substitutes for $cd\frac{c}{d}$ and $dc\frac{d}{c}$ , but let's say it's good enough.

Now, we are ready to write our script:


    
function mit1869_naive(a, b) {
    const c = a+b;
    const d = a-b;
    return ( (c/d) + (d/c) )/( (c/d) - (d/c) );
}
mit1869_naive(1, 2);

Feel free to play around with the function a bit. You'll notice that you'll get NaN for a=1 and b=1 because d is zero if a == b. Other than that, everything is fine, isn't it?

At least for now, we don't have a reason to assume that this implementation might be wrong, because all we have done is copying the formula.

Simplifying the expression

We could call it a day and stop here. But how about actually solving the problem?

We'll use the already simplified version, form the main denominator in numerator and denominator, which we can then reduce. :

\frac{ \frac{c}{d} + \frac{d}{c} }{ \frac{c}{d} - \frac{d}{c} } = \frac{ \frac{c^2 + d^2}{cd} }{ \frac{c^2 - d^2}{cd} } = \frac{ c^2 + d^2 }{ c^2 - d^2 }

Because we can't simplify this expression anymore, we'll resubstitute c and d. Before we do that, we use the first and second binomial formula:

c^2 = (a+b)^2 = a^2 + 2ab + b^2

d^2 = (a-b)^2 = a^2 - 2ab + b^2

Now we resubstitute:

\frac{ c^2 + d^2 }{ c^2 - d^2 } = \frac{ a^2 + 2ab + b^2 + a^2 - 2ab + b^2 }{ a^2 + 2ab + b^2 - a^2 + 2ab - b^2 }

The last step is to simplify this expression and we get:

\frac{ 2(a^2 + b^2) }{ 4ab } = \frac{ a^2 + b^2 }{ 2ab }

We did it! If you check the video, you'll see the presenter found the same solution although we used a slightly different way.

However, is this solution really better? It requires one addition, four multiplications and one division. If we assume that every operation takes the same time (which isn't necessarily true), we have 6 operations instead of 9. However, if we'd have simplified mit1869_naive even more, we could've saved two divisions and end up with 7 operations. Not a big difference between those two.

But let's say, we implement this function as well:


    
function mit1869_simplified(a, b) {
    return ( a*a + b*b )/( 2*a*b );
}
mit1869_simplified(1, 2);

Comparing the two functions.

Looks fine. We can play around with some values and both functions will give us the same outputs. Ok, mit1869_naive returns 1.2500000000000002 instead of 1.25 for a=1 and b=2, but that doesn't seem like a relevant difference.

However, testers and engineers alike are more interested in extreme examples. So let's set a=0.1 and b=100. We get:

mit1869_naive(0.1, 100): 500.0005000000141
mit1869_simplified(0.1, 100): 500.0005

Again, the naive version seems to have some problems in the last few digits but nothing dangerous. However, the number of valid digits shrank quite a bit to 10 from 15. But two data points are not a trend. So, let's try more values.

a	b	naive	simplified
0.001	1,000	50000.00000509277	50000.000004999994
0.0001	10,000	4999999.9984685425	5000000.00000005
0.00001	100,000	499999972.5076038	500000000
0.000001	1,000,000	50000134641.22209	50000000000
1e-6	1e7	4998445757347.942	5000000000000
1e-7	1e8	486875635391405	500000000000000
1e-8	1e8	3602879701896397	5000000000000000
1e-8	1e9	-Infinity	50000000000000000

As we can see, starting with a= 0.00001 and b= 100,000 we don't have any valid decimal places at all. And if we use really extreme values, we get invalid results.

However, our two functions are mathematically equal. What happened?

Why do these function output different values?

The problem is: Two functions that are equal on paper don't need to be equal if you implement them in a computer because computers have only limited memory.

Hence, a computer cannot store real numbers exactly (sometimes it does, but you can't count on that, even 0.1 won't be stored precisely). Usually that is not a problem, because for floating point numbers like defined in IEEE-754 we have a guarantee: The relative error will always be smaller than or equal to $2^{-m}$ , where m is natural number depending on the amount of bits used. For a 32 bit IEEE-754 number, m would be 24.

Let's look at some examples where x is the number we want to represent:

x	order of magnitude	max absolute error
1	one	58*1e-9
100	hundred	5.9*1e-6
1e6	million	0.0596
1e9	billion	59.6
1e12	trillion	59.6*1e3
1e15	quadrillion	59.6*1e6

It's easy to see that you can be off quite a bit, but with respect to x the error will always be small. If you have one million dollars, usually you won't care about $0.06.

But there are situations in which you care. If we have a look at our example again, we could ask which implementation provides the correct or at least better results. To do that, we need the actual value.

Sadly, we cannot answer this question using another program [1]. Instead, we'll have to tackle the problem with pen and paper. Let's look at a=1e-8 and b=1e9.

At first we'll look at the simplified version:

\frac{ a^2 + b^2 }{ 2ab } = \frac{ (10^{-8})^2 + (10^9)^2 }{ 2 \cdot 10^{-8} \cdot 10^{9} } = \frac{ 10^{-16} + 10^{18} }{ 2 \cdot 10^{1} }

We simply inserted the values and simplified a bit. Now, we'll approximate $10−16≈010^{-16} \approx 0$ . This is a valid assumption because $10^{18}$ is much larger. In fact, a computer would do the same or something similar if you add these two numbers (feel free to insert console.log statements to test this). Now we get:

\frac{ 10^{18} }{ 2 \cdot 10^{1} } = \frac{ 10^{17} }{ 2 } = 50,000,000,000,000,000

This is exactly the value the second JS script calculated as well.

After this success, look at the naive implementation. Again, we'll assume $10−8≈010^{-8} \approx 0$ if we add or subtract a and b because a is much smaller.

\approx b = 10^9

\approx b = -10^9

Now we resubstitute:

\frac{ \frac{c}{d} + \frac{d}{c} }{ \frac{c}{d} - \frac{d}{c} } \approx \frac{ \frac{10^9}{-10^9} + \frac{-10^9}{10^9} }{ \frac{10^9}{-10^9} - \frac{-10^9}{10^9} } = \frac{ -1 - 1 }{ -1 + 1 } = \frac{ -2 }{ 0 }

Now you probably will say "But you cannot divide by zero!". And that's correct, however a computer does it. It simply assumes, that 0 is a very small number and if you divide something by something very small, you'll get something very big, in this case infinity. But because you divided a negative number by 0, you get -infinity.

Without the approximations, both versions would've delivered the same results. But as explained above, because there's only a finite amount of memory used for each number, the computer has to make this approximation. On a side note: This means that our second approximation wasn't valid from a mathematical standpoint as the result was obviously incorrect. Hence, approximations must always look at where the resulting values will be used and wether small differences will be relevant.

Generalizing the effects

There's an upper bound for the maximum relative error.

If you try to represent a real number x in a computer with a floating point number x', the following upper bound for the relative error exists [3]:

\frac{|x'-x|}{|x|} \leq 2^{-m} \text{ where } m \in \N

The value of m depends on the implementation and wether a 32 bit or 64 bit system is used.

This has an important consequence: If we add an (in magnitude) small to an (in magnitude) large number, it's possible that we loose information about the small number.

Different implementations of the same algorithm can cause different results.

This is a direct consequence of the rule above. Sometimes, a specific algorithm is always better than another, sometimes it might depend on the input values.

Definition: Condition of a problem A problem is well-conditioned, if small changes in the input values don't cause very large changes in the result. On the other hand, a problem is ill-conditioned if small changes in the input values do cause large changes in the result [4]. (In fact you could quantify this, but that's a large topic for itself.)

Definition: Stable algorithm An algorithm is stable, if the accumulated error resulting from rounding errors isn't larger than what we would expect for this problem with its given condition and errors in input values. [5]

Example 1: If we have a well-conditioned problem and only small input variations, a stable algorithm would cause only small output variations.
Example 2: If we have an ill-conditioned problem, even a stable algorithm couldn't ensure that small input variations will only cause small output variations because the big output variations are inherent to the problem!
Example 3: This article looked at one problem. However, we found two algorithms to solve it. One is stable, one is not.

Applying our gained knowledge

While this only scratches this important topic of computing, you still can use it in your programs. Here are some rules of thumb that'll be useful quite often:

Usually, it's better to use multiplications instead of sums. Especially if you'd add very large positive and very large negative numbers and expect an in magnitude small number as result.
Divisions by zero should be avoided. In some programming languages exceptions will be thrown, in others it'll result in infinite or NaN. Be careful if you divide by numbers that are almost zero.
Rounding errors can add up. Hence, it's better to use fresh values whenever possible. Read about a worst-case failure here.
The associative property of addition is not guaranteed on a computer. Often, it's preferable to add numbers in the same order of magnitude as long as possible to approximate this property as good as possible.

Disclaimer: These are rules of thumb. They can be wrong and in some instances, they will be wrong. Critical systems [6] always should be developed by professionals and not be based on articles from the internet, not even this one.

Comments, Sources

[1] Actually, you could use some tricks like symbolic computing which might work. Or you could just trust in Wolfram Alpha (which again uses symbolic computing in parts of its calculations).
[2] Be aware: Most likely, some (probably better educated) people might have different definitions for these terms. That doesn't necessarily mean that mine or their definition is wrong. However, it shows that you have to be aware of what definitions are applied in different contexts.
[3] Page 9 in "Einführung in die numerische Mathematik"
[4] Page 10 in "Einführung in die numerische Mathematik"
[5] Page 17 in "Einführung in die numerische Mathematik"
[6] Let's imagine you develop a payment system that does calculations with floating point numbers. It'd be very hard to assess all possible 'calculation chains' which could cause numerical problems.

Protect Your Contact Information From Crawlers

Bastian Heinlein — Mon, 24 Feb 2020 10:11:31 +0000

In Germany, we are required to publish contact information on every commercial website including email address and phone number. I never put much effort in protecting this data, but recently I've started to receive an increasing amount of spam on some public email addresses. While it still is manageable with a proper spam filter, I decided to take some counter steps when I updated agty.de in order to prevent bots from detecting my contact data.

Side Constraints

The solution should be accessible and have minimal CO2 impact (learn more). Hence, it shouldn't depend on jQuery or other frameworks. Instead it should only use pure JavaScript if any at all. Also, it shouldn't simply display the address on an image as this would increase both the page's size and difficulty for people depending on accessibility features.

And of course, it should look at least ok and be simple to use.

Simplifications

Because my project is very small and doesn't use a real database, I decided to not detect contact information like email addresses or phone numbers automatically. Instead, I searched for those manually.

Assumptions

While I'm no expert on entity recognition or information extraction, I made some educated guesses about these tasks:

It's trivial to detect an email address if it's used liked that <a href="mailto:hi@test.de">hi@test.de</a>.
You could probably create a simple regular expression to find email addresses that aren't embedded in <a> tags. Hence, it's no big help to just write an email address without any tags in a normal paragraph.
Most crawlers will simply load the HTML file and not even execute any JavaScript on startup.
Even more crawlers won't execute JavaScript if it's tied to an user action like clicking a button.
Yet, a lot of crawlers will apply their regular expressions also to JavaScript and CSS files.

A Simple Solution

Based on my assumptions, side constraints and simplifications, I came up with this solution:

Wherever you would write your email address, post this code snippet instead. The button tag is used in the hope of better accessibility although JavaScript is required.

<button class="show-email">Display E-Mail-Address <noscript>(requires JavaScript)</noscript></button>

Add event listeners to all email buttons that might be in this document. While we could use the onclick action of buttons, this way our email button's code is smaller.

document.addEventListener("DOMContentLoaded", function(e) {
    let emailButtons = document.getElementsByClassName("show-email");
    for (let i = 0; i < emailButtons.length; i++) {
        emailButtons[i].addEventListener("click", showEmail);
    }
});

This function does the actual stuff: Whenever an email button is clicked, its text is changed to the email address. In order to prevent bots from finding the address in JavaScript code, I cut it down into several parts.

function showEmail(evt) {
    let target = evt.target;
    let email = "test";
    email = email.concat("@");
    email = email.concat("test");
    email = email.concat(".de");
    target.innerHTML = email;
}

Some styles are always a good idea, of course it should be designed to fit your website's design.

.show-email {
    border: none;
    outline: none;

    padding: 0;
    margin: 0;

    box-shadow: none;
    background-color: white;

    font-size: 10pt;
    font-weight: bold;

    cursor: pointer;
}

.show-email:hover {
    text-decoration: underline;
}

Of course, you could also use this technique for other types of information like your name, phone number, social media profiles or whatever. Using this technique, I'd consider it likely to make the information available for humans but not for crawlers. At least that method should make it harder for crawlers to automatically detect your information.

Call For Action

While the proposed solution hopefully works, I invite you to share your own ideas about this problem. Most likely, you'll have much better thoughts than me!

Finding Links to 404 Pages

Bastian Heinlein — Sun, 14 Apr 2019 09:06:30 +0000

There are few things as annoying as links on websites that lead to a 404 error page. Hence, designers spend a lot of time carefully crafting these pages to make them a bit more pleasing. But for developers, the goal should be to supersede this work of designers by finding these faulty links.

Let’s Automate This!

Developers automate everything. If we see a nearly iterative task, we write a program for it. There are of course cases where this is only an excellent way to procrastinate, but for this specific problem there is no reasonable alternative to automation.

The problem consists in fact of two iterations: The iterative process of finding faulty links on the website and the iterative process of doing this over and over again. The latter is necessary as websites usually link to external sites, which can change routes without letting anyone know. Also, if websites do not use a strictly hierarchical structure, there are probably cross-links between articles within texts which can become very complex very fast.

Of course, you could create a CMS that automatically observes for links to 404 pages, but that seems complex and probably computationally intensive. But if you are aware of such an integrated system, it’d be awesome to let me know.

An Initial Idea

The first, naive idea was to look through the article database and scan it for <a>-Tags. Then you would search in your database and look if there is an article for this URL. The limitations and problems of this approach are obvious: You need to access your database, which means probably downloading it and setting it up in a way that allows your code to access it.
External links need extra treatment.

Depending on your CMS, it’s likely that there are different urls for one article. Hence, you need several regular expressions (or whatever technique you use) to treat those different cases. A great example of this problem is Joomla: If you access an article via the menubar, it has the url https://joomla-domain.com/index.php/menu-item-x/article-title, otherwise it’s https://joomla-domain.com/index.php/article-title. If you want to extract the article-title/-id it can be necessary to differentiate between such different urls.
You’ll need a custom implementation for every different CMS.
Hence, I decided to go another route (pun intented): Building a web crawler.

Crawler McCrawl

Counter-intuitively, this concept is a bit simpler than crawling through your database. As an extra, it’s a great example of graph theory. You choose a starting point/a start url; the crawler then visits this page and looks for all links there and remembers them. It then visits all these linked sites and looks again for all links on them. This process is then repeated until all pages are visited. In the end, you have a graph of your whole website and if a visited site returned a 404 HTTP Code, you can note this url in an extra list together with the site the link is on. Not exactly, rocket science, right?

As always, there are of course some potential pitfalls, you should consider when creating such an algorithm:

Links in <a>-tags are often absolute urls in the format /main-category/another-layer/landing-page, to make your crawler visit this site, you'll need to add the domain to create this format: https://tld.com/main-category/another-layer/landing-page.
The website probably has links to external sites. You don’t want to crawl these, hence you need to differentiate between your website of interest and external links, but of course, it makes sense to check if the external website exists! Maybe, it’d be useful to ignore some url paths, i. e. some calendar modules use php scripts that parse urls to return events (Joomla again :( ). This can generate thousands of urls you’d parse, if you don’t ignore them.
Most likely, you’ll run into loops. Landing page A links to landing page B and the other way around. If your algorithm doesn’t remember, which page it already visited, congratulations: You built an infinite loop.
Menu bars are the devil. You’ll have A LOT more operations, if you look at them on every page. Same with sidebars and footers. Hence, it might be helpful to ignore certain HTML elements by class or id.
Some servers have limits for how many accesses per minute they allow. Even if not, it’s a good practice to be polite, meaning waiting between requests for so and so many seconds.

You probably already noticed, but a lot of these problems are already solved in graph theory, hence it might be a great time to refresh your knowledge on this topic.

A ready-to-use Implementation

If you don’t want to build such a program yourself, you are lucky: There are several free online tools available that can find links to not existing pages.
Even better: I made my own implementation public some weeks ago. It has solutions for all the mentioned problems and has already helped me to find several dozen links to not existing pages on a client’s website. Also, it exports the results as a CSV file, so you can open it in Excel or whatever application you prefer and look through the data. It’s easily accessible via command line and is written in Python.
You can find it here: https://github.com/bahe007/tt404

Where to Start With Your Own Implementation

Quite often, I find it hard to get a foot in the door if I start a completely new project, hence here are two great libraries for an implementation in Python to make the first step a bit easier for you:

Beautiful Soup: An amazing HTML parser. Incredible work without which the project would’ve taken much longer.
requests: This is the basic Python library for HTTP requests. I highly recommend it as I used it successfully in several projects, although some people prefer urllib.

Feel free to leave feedback or link to your own project, I’d appreciate both. Thanks for reading!