This tutorial shows how to use a simple genetic algorithm to deduce physics formulas.

A genetic algorithm is an algorithm that borrows ideas from Darwin's theory of evolution to find solutions to optimisation problems. So, if you have a problem and if you have a way of determining how good or bad a solution is to that problem, then a genetic algorithm can be used to run a simulation that tries to find better solutions to that problem.

In order to be able to run a genetic algorithm, you need to be able to do a couple of different things:

- you need to be able to generate random possible solutions to the problem;
- you need a way to quantify how good, or how bad, a given solution is;
- you need to have a way to take two solutions and combine them to create a third solution; and
- you need to be able to make small random changes to existing solutions.

The steps of combining solutions and mutating solutions are supposed to emulate the natural process of evolution as described by Darwin's theory of evolution.

Step 1. is how the genetic algorithm starts.
You start by creating a number of random solutions, to which you call the *population*.
Each solution is an *individual*.

Then, you repeat steps 2 - 4 a number of times.
For each repetition, you figure out how good each individual in the population is.
You call *fitness* or *fitness level* to the value that quantifies how good a solution is.

In Darwin's theory of evolution, the fittest individuals of a species tend to survive and reproduce while the least fit tend to die. The same thing will happen in our genetic algorithm. We pick the fittest individuals, let them reproduce, give them a change to mutate, and then we repeat this.

Genetic algorithms can be implemented to any type of problem you can think of, as long as you're able to implement the different steps outlined above. In this article we will try to deduce the formula that determines the position of a body in motion as a function of time, given its initial position, initial velocity, and acceleration. The formula looks like this:

\[ x(t) = \frac12 a t^2 + v_0t + x_0\]

In the formula above, we have that

- \(x_0\) is the initial position of the body;
- \(v_0\) is the initial velocity of the body;
- \(a\) is the acceleration of the body;
- \(t\) is the time for which we want to compute the position; and
- \(x(t)\) is the position of the body after \(t\) seconds.

In our simulation, we'll have to start by creating random formulas that will be nowhere close to the correct formula shown above. Then, we'll figure out what are the formulas that better approximate the correct formula, we'll mix and match those formulas, and we'll mutate some of them. We'll repeat this a number of...

]]>How can you find the biggest free square in a 2D map with obstacles?

I just got a call from the President of Portugal. Portugal recently mapped out the Atlantic Ocean to the West of our coast. They want to build a sea platform to study the ecosystems of the Ocean. They need my help to figure out where to build that platform.

To show you what I'm working with, here is a portion of the map they created:

```
..o..
.o..o
.....
```

Each character represents a small square section of the sea.
The dots `.`

represent sections where the sea bed is uniform whereas the circles `o`

represent sections where the sea bed is not uniform, where there are shipwrecks, corals, and other things.

Their engineers said the platform must be square, so my job is to find the largest square region where the platform could be built.
For example, in the map below I'm marking the largest square region with crosses `x`

:

```
..o..
.oxxo
..xx.
```

They also told me that if there are two or more square regions of the same size, they'll prefer the one that's closer to the top, and then to the left, of the map.

So, if the mapped out region were

```
ooo.....
..o..o..
..ooo...
..o.....
..o.....
```

There would be plenty of possible locations:

```
oooxx.xx
xxoxxoxx
xxooo...
..oxx.xx
..oxx.xx
```

They'd prefer to build their platform here:

```
oooxx...
..oxxo..
..ooo...
..o.....
..o.....
```

They're sending me the sea map in a file with the format shown below:

```
...........................
....o......................
............o..............
...........................
....o......................
...............o...........
...........................
......o..............o.....
..o.......o................
```

Save this map in a file and try to solve this problem. You should be able to find this solution:

```
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxxo..............
.....xxxxxxx...............
....oxxxxxxx...............
.....xxxxxxx...o...........
.....xxxxxxx...............
......o..............o.....
..o.......o................
```

For bonus points, use the function below to generate more maps and test your solution on them:

```
import random
def create_map(map_path: str, width: int, height: int, obstacle_prob: float) -> None:
"""Creates a map with the given size."""
with open(map_path, "w") as file:
for _ in range(height):
for _ in range(width):
char = "o" if random.random() < obstacle_prob else "."
file.write(char)
file.write("\n")
```

Also, can your solution handle maps of all sizes? What if the maps are completely empty? What if the maps are completely full?

After you've solved the problem yourself you can keep reading to see how I did it.

The first thing I did was create a function that takes in a file path and retrieves the map from that file:

```
def read_map(pathname: str) -> list[str]:
"""Reads the map from a file."""
with open(pathname, "r") as file:
return [line.strip() for line in file]
```

We can do this by opening the file for reading and then using a list comprehension to go over the lines in the file and stripping them of the trailing newline.

Now, we must think about the way in which we'll approach the problem. What I'll do is traverse the whole map and I'll look at each position as...

]]>This article shows how to solve the N queens problem in 20 lines of code.

(You can skip to the solution or just see the code.)

“Do you understand what you have to do?”, Queen #6 asks.

“Uh, I– I think so.”

The challenge sounded simple enough but I was a bit intimidated by the Ten Queens all looking at me.

They stood tall in front of me. An impeccable pose, worthy of a Queen. Times ten.

They looked rigid and cold, wearing their white and black dresses. But if you looked carefully enough, they also looked… They looked… hopeful! They believed I would be able to help them.

I wasn’t feeling confident and Queen #8 picked up on that, so she decided to recap what they needed:
“Like my sister #6 said, we need to distribute ourselves on this 10 × 10 board.
The goal is to *count* in how many different ways this can be done.

We like to have room to pace a bit, so no two of us can be on the same row, column, or diagonal. This restriction is essential.”

I nodded along while she recapped. Then, I asked “How on Earth am I supposed to compute this? I can’t do this with pen and paper!”.

All Queens started laughing uncontrollably. Queen #1 managed to control herself for long enough to reply.

”You silly! You use Python, of course!” She waved.

The two pawns at the entrance of the room we were in opened the massive doors. As the huge doors creaked and opened slowly, four pawns came into the hall, carrying a computer. The computer was already turned on. As the computer moved closer, this is what I saw on the screen:

```
Python 3.12.0 (the Ten Queens build)
Type "help" for more information.
>>>
```

“You have one week. You can start now.”

I walked up to the computer and started working on the problem.

I was thinking aloud while I was typing.

“We know that no two queens can be on the same row or column. And that's easy to enforce in my code. I'll traverse the columns and put one of you in each column while also not repeating rows. It's the diagonals that I have to be careful about.”

I paused for a bit. Then I wrote this function:

```
def diagonally_safe(row, col, placements):
for qrow, qcol in enumerate(placements):
if row - col == qrow - qcol or row + col == qrow + qcol:
return False
return True
```

I proceeded to explain:

“I'll store a tuple called `placements`

with the positions of some of you.
The index is the column you're in and the value itself represents the row.
For example, if `placements`

is `(5, 0, 4)`

that means that the column `0`

has a queen in position `5`

, the column `1`

has a queen in position `0`

, and the column `3`

has a queen in position `4...`

Yesterday I spent the whole day tryint to patch a module global. This is what I ended up with.

`pytest`

Suppose you have a small project that has an April Fool's joke set up:

```
# constants.py
APRIL_FOOLS = False
```

```
# useful_code.py
from constants import APRIL_FOOLS
def add(a, b):
if APRIL_FOOLS:
result = a - b
else:
result = a + b
return result
```

Now, suppose you want to test your April Fool's joke with `pytest`

.
One thing I found online was that you could use the fixture `monkeypatch`

and its method `setattr`

, something like this:

```
# test_useful_code.py
import pytest
import constants
import useful_code
def test_add_on_april_fools(monkeypatch):
monkeypatch.setattr(constants, "APRIL_FOOLS", True)
assert useful_code.add(10, 5) == 5
```

(I'm sparing you from hearing about all of the embarrissingly dumb things I tried before getting to this point!)

If you run this test with `pytest test_useful_code.py`

you get a failure:

`FAILED test_useful_code.py::test_add_on_april_fools - assert 15 == 5`

What's happening, then? Take a moment to think about it...

What's happening is that when I import `useful_code`

into the testing file, that module will then run the line `from constants import APRIL_FOOLS`

, which sets the variable `APRIL_FOOLS`

inside the namespace of the module `useful_code`

, which is *separate* from the namespace of the module `constants`

!

After banging my head against the wall for a while, I realised I could tweak my code to work with this testing approach!
All I had to do was use `constants.APRIL_FOOLS`

instead of using `APRIL_FOOLS`

directly:

```
# useful_code.py
import constants
def add(a, b):
if constants.APRIL_FOOLS:
result = a - b
else:
result = a + b
return result
```

Now, if you run your test it will pass and the mocking of the variable will have succeeded!

The reason this works is that now we're accessing `APRIL_FOOLS`

via the `constants`

namespace, so when we patch the value of `APRIL_FOOLS`

in `constants`

, that patched value will be visible when the constant is used elsewhere.

You could also patch `APRIL_FOOLS`

directly in the module `useful_code`

, but if you have a constant that is used in many different modules, it is much easier (and better) to patch it *once* where it is defined versus patching it many times wherever it is imported.

I'm not claiming this is *the best solution* to this problem but it's certainly *a solution that works*.
If you have better ideas that have more or less the same complexity, let me know!

For reference, this is a simplification of a “real” issue I had when trying to add tests to this Textual PR of mine.

]]>This tutorial teaches how to work with the Python data structure `collections.deque`

and provides 7 example use cases.

`deque`

tutorialIf you already know how to manipulate a `deque`

, feel free to skip to the example use cases!

`deque`

?A `deque`

in Python is a data structure from the module `collections`

.
A `deque`

is often compared to a Python list because they are both ordered containers that let you append and pop elements from the right efficiently.

The code below shows the similarities:

```
from collections import deque
my_list = []
my_deque = deque() # Create a `deque`.
my_list.append(1)
my_deque.append(1) # Append an element to its end.
my_list.extend(range(2, 5))
my_deque.extend(range(2, 5)) # Extend the `deque` with more elements.
popped_from_list = my_list.pop()
popped_from_deque = my_deque.pop() # Pop an element from the end.
print(my_list, popped_from_list) # [1, 2, 3] 4
print(my_deque, popped_from_deque) # deque([1, 2, 3]) 4
```

There are two main differences between `deque`

s and lists:

- you can append and pop elements efficiently from the left on a
`deque`

(on a list, it becomes slower as the list grows); and - you can control the maximum size of a
`deque`

with its parameter`maxlen`

.

These two differences are the ones that play a key role when determining whether you should use a `deque`

, a list, or any other container.

`deque`

As I've shown above, an empty `deque`

can be created by simply typing `deque()`

:

```
from collections import deque
my_deque = deque()
print(my_deque) # deque([])
```

A `deque`

can also be seeded with elements from any other iterable:

```
from collections import deque
deque_with_chars = deque("hello!")
print(deque_with_chars) # deque(['h', 'e', 'l', 'l', 'o', '!'])
deque_with_ints = deque(range(5))
print(deque_with_ints) # deque([0, 1, 2, 3, 4])
deque_with_things = deque([True, None, {}, set()])
print(deque_with_things) # deque([True, None, {}, set()])
```

When you instantiate a `deque`

, you can also specify the parameter `maxlen`

.
The `deque`

parameter `maxlen`

will restrict the maximum length that your `deque`

can have.
For example, the `deque`

below has a maximum length of `2`

, which means that adding more than two elements will result in other elements being pushed off of the `deque`

:

```
from collections import deque
deque_size_2 = deque([1, 2], maxlen=2)
print(deque_size_2) # deque([1, 2])
deque_size_2.append(3) # This forces an element to pop from the left.
# Now, we'll see that the `1` is gone:
print(deque_size_2) # deque([2, 3])
```

The parameter `maxlen`

is what allows you to use Python's `deque`

for a number of interesting examples that I'll show below.

`deque`

The `deque`

documentation has a comprehensive list of all the methods that `deque`

s support but I'll show you the most common ones here.

`deque`

To add elements to a `deque`

, you'll typically do it in one of three ways:

- you'll initialise your
`deque`

with some initial elements; - you'll append elements, one at a time, to either end of the
`deque`

; or - you'll extend the
`deque...`

When will these two clocks synchronise again?

You have two digital clocks. One of them just displays the hours and minutes in the format HH:MM while the other is a stopwatch that displays minutes and seconds in the format MM:SS. The stopwatch wraps around at 59:59, when it goes back to 00:00.

On a certain day at 00:00, the stopwatch is turned on. When will the clock and the stopwatch have matching displays again? And how often does that happen?

Give it some thought!

The two clocks will have matching displays again at 01:01:01, then again at 02:02:02, 03:03:03, 04:04:04, ..., 23:23:23, so this happens 24 times per day.

To get to this conclusion, we start by realising that the stopwatch can actually be seen as a clock that shows the current time, but without the hours. Thus, the minutes display of the regular clock will always match the minutes display of the stopwatch.

To recap, the two clocks have displays in the format HH:MM and MM:SS and we already know that the MM sections always match. This means that for the two displays to display the same thing, we must have HH = MM = SS, which happens at 00:00:00, 01:01:01, ..., up to 23:23:23.

What if the stopwatch wraps around at 99:59 instead of 59:59?

]]>Learn how to find text patterns and replace them with dynamic content using regex.

The other day I was working on my problems book and I needed to update a markdown file to number the headings. In short, I had a markdown file like this:

```
# Problems
## Dancing triangle
...
## Bag full of numbers
...
## Quarrel in the Shire
...
```

I wanted to find all H2 headings and number them, so I'd end up with this file:

```
# Problems
## 01 – Dancing triangle
...
## 02 – Bag full of numbers
...
## 03 – Quarrel in the Shire
...
```

I thought about doing this manually but I'd need to do this to 2 documents, each with thousands of lines and 64 headings, so I decided to use a bit of Python and regex to do it.

The module `re`

, from the Python standard library, lets you do string replacements with the function `re.sub`

, which needs 3 parameters:

- the pattern we're looking for;
- the replacement for the pattern; and
- the string we're searching & replacing in.

`re.sub`

is like the string method `str.replace`

on steroids!

In my case, the pattern I was looking for was this:

`^## (.*)$`

This looks for a `##`

at the beginning of the line, followed by a space, and then the `(.*)$`

matches everything else until the end of the line.

We can see this in action if we use `re.findall`

and a dummy string:

```
>>> import re
>>> string = '# Problems\n\n## Dancing triangle\n\n...\n\n## Bag full of numbers\n\n...\n\n## Quarrel in the Shire\n\n...'
>>> re.findall("^## (.*)$", string, flags=re.MULTILINE)
[
'Dancing triangle',
'Bag full of numbers',
'Quarrel in the Shire'
]
```

The flag `re.MULTILINE`

was used so that the anchors `^`

and `$`

matche the beginning and end of each line, respectively, instead of the beginning and end of the string.

(Go to regex101 (an online regex playground), paste the regular expression `^## (.*)$`

in the top, middle bar, and copy and paste the first version of the `# Problems`

markdown in the big, central text area.)

The next thing I wanted was to be able to replace each title with a number followed by `–`

and then itself!
By using group references, adding the `–`

before the title is easy:

```
>>> print(
... re.sub("^## (.*)$", r"## xx – \1", string, flags=re.MULTILINE)
... )
# Problems
## xx – Dancing triangle
...
## xx – Bag full of numbers
...
## xx – Quarrel in the Shire
...
```

The “difficult” part is adding the number that must be incremented each time we add it.
Thankfully, the function `re.sub`

has a trick up its sleeve!

The second parameter of the function `re.sub`

, which is the replacement, can be a *function*.
This function must have a single parameter, which is the match object, and must return a string, which is the replacement for the given match.
Thus, by using a counter variable, I can add...

This article shows how to do base conversions in Python with the built-in int, how to write integer literals in other bases, and how to do base conversions in general.

In this article I'll assume you know what a number base is and how there are multiple number bases. My focus will be on showing you the tools that Python provides to work with multiple number bases, an in particular with the binary, octal, decimal, and hexadecimal, number bases.

Before diving right into the tools that Python gives you to work with different number bases I want to stress that a number base doesn't change the underlying number we're talking about, only its *representation*.

For example, many people around the world have three meals per day: breakfast, lunch, and dinner. It doesn't matter whether I write “three” in English, “três” in Portuguese, “3” in the decimal number base, or “11” in the binary number base. We're always talking about the same number of meals: breakfast, lunch, and dinner.

This is very important!

Python (and most programming languages) let you write integer literals in the decimal number base, and we typically don't even think about it. Python also lets you write integer literals in three other bases:

- binary;
- octal; and
- hexadecimal.

To write an integer literal in any base other than the decimal base, you always start your integer literal with a `0`

followed by the letter that identifies the base.
This is summarised in the table below:

Base | Prefix |
---|---|

binary | `0b` |

octal | `0o` |

hexadecimal | `0x` |

Thus, all four assignments below create the same integer literal:

```
svty_three = 73
svty_three_bin = 0b1001001
svty_three_oct = 0o111
svty_three_hex = 0x49
```

Because the base changes the representation but not the number, printing any of the four variables will print `73`

:

```
print(svty_three) # 73
print(svty_three_bin) # 73
print(svty_three_oct) # 73
print(svty_three_hex) # 73
```

In any of these bases, you can use the underscore `_`

to group digits to make the literals more readable.
For example, in the decimal base you can use the underscore `_`

as the thousands separator:

`huge_number = 17_532_546_253_000_000`

Python contains 3 built-ins that let you convert integers to *string* representations in the three other bases:

Base | Built-in |
---|---|

binary | `bin` |

octal | `oct` |

hexadecimal | `hex` |

Here's example usages of all three:

```
print(bin(73)) # 0b1001001
print(oct(73)) # 0o111
print(hex(73)) # 0x49
```

Notice that these converting functions include the base prefix in the converted representation!

If you want to use these string representations to represent the number in its base, you can discard the prefix and then convert each digit.
The code below uses a list comprehension and the built-in `bin`

to convert an integer to a list of its binary digits:

```
>>> [int(digit) for digit in bin(73)[2:]]
[1, 0, 0, 1, 0, 0, 1]
```

The prefix letters for the integer literals can...

]]>The built-in function max in Python is broken and this article explains why, drawing parallels with other programming and mathematics concepts.

`max`

is brokenDid you ever notice that in Python, you have:

```
sum([]) == 0
all([]) == True
any([]) == False
math.prod([]) == 1
```

Notice that the functions `sum`

, `all`

, `any`

, and `math.prod`

all have one thing in common:
they take a list of things and reduce it into a single result.
In all four cases above, if we pass the function an empty list we get a default value back.

However, `max`

is also a reduce function and `max`

doesn't have a nice default value.
Instead, it throws an error:

`max([]) # ValueError`

But why?
Isn't there a suitable default value for `max`

?

From a mathematical point of view, there is a suitable default value for `max`

, so the fact that the function raises an error instead of returning it is wrong and that is why I claim that `max`

is “broken”.
For `max`

to be mathematically correct, the default value for `max`

should be negative infinity, which you can get with `float("-inf")`

:

`max([]) == float("-inf")`

So, why does Python raise an error instead of being mathematically correct?
I'm guessing Python goes with the “practicality beats purity” approach and prefers to raise an error instead of returning infinity values to users, given that infinity can be quite an exotic thing...
Especially if we consider that `max`

should return *negative* infinity and `min`

should return infinity, which are different things.

(Right, I forgot to tell you but `min`

is also broken!)

But why “should” the return values be (negative) infinity?
That's because all of these reduction functions (`sum`

, `any`

, `all`

, `math.prod`

, `max`

, and `min`

) should return the identity element for their respective operations.

`sum`

performs addition and 0 is the identity element for addition.`any`

performs the Boolean operation “or” and False is the identity element for “or”.`all`

performs the Boolean operation “and” and True is the identity element for “and”.`math.prod`

performs multiplication and 1 is the identity element for multiplication.

Likewise, the identity element for the `max`

operation is `float("-inf")`

and the identity element for the `min`

operation is `float("inf")`

.

How can you know that `float("-inf")`

is the identity value for the operation `max`

?
Try to come up with a numerical value for `x`

such that `max(float("-inf"), x)`

is *different* from `x`

.
I bet you can't, and that's why `float("-inf")`

is the identity value for the operation `max`

; because `max(float("-inf"), x) == x`

for any number `x`

.

Do you get what I'm saying? Feel free to leave a comment below if you don't!

`max`

To fix `max`

in a mathematical sense you'll need to set its `default`

parameter to `float("-inf")`

.
The version below uses
`functools.partial`

to freeze the parameter `default`

:

```
from functools import partial
pedantic_max = partial(max, default=float("-inf"))
```

]]>
This article teaches you how to use `functools.partial`

, how it works, and when to use it, with clear examples.

`functools.partial`

`functools.partial`

?`functools.partial`

is a tool from the standard module `functools`

that allows you to curry positional and keyword arguments in functions.
In a certain way, it's as if `partial`

creates a specialised version of the function you pass it in, with certain arguments frozen.

For example, the built-in `int`

converts objects to integers:

```
>>> int("14")
14
>>> int(14.5)
14
```

Maybe you didn't know that the built-in `int`

also accepts a second argument that specifies the base from which the number must be converted:

```
>>> bin(99) # 99 in binary is 1100011
'0b1100011'
>>> int("1100011", base=2)
99
>>> hex(99) # 99 in hexadecimal is 63
'0x63'
>>> int("63", base=16)
99
```

By using `functools.partial`

, you can create specialised versions of `int`

where the parameter `base`

was fixed to a certain base:

```
# `partial` lives inside the module `functools`:
>>> from functools import partial
>>> from_bin = partial(int, base=2)
>>> from_bin("1100011")
99
>>> from_hex = partial(int, base=16)
>>> from_hex("63")
99
```

The two examples above show that the first argument to `partial`

is the function whose argument(s) we want to freeze.
Then, we can provide as many positional or keyword arguments as needed.
In our case, we just specified the parameter `base`

as a keyword parameter.
Here's how you could read both examples of `partial`

:

`partial(int, base=2)`

- create a new version of`int`

where the parameter`base`

is always set to`2`

; and`partial(int, base=16)`

– create a new version of`int`

where the parameter`base`

is always set to`16`

.

`functools.partial`

The example above showed briefly how `partial`

works and this section will go over the most important details.
For demonstration purposes, let us create a function with a couple of parameters:

```
def foo(a, b, *, c, d=10):
print(a, b, c, d)
```

The function `foo`

above has 4 parameters, of which `c`

and `d`

are keyword-only and `d`

has a default value of `10`

.

`functools.partial`

and positional arguments`partial`

can be given positional parameters, which will be passed in, in order, to the function that is the first argument to `partial`

.
When you call the new function, the other positional arguments you pass in are appended to the ones you already specified.
So, `bar = partial(foo, 1)`

is a function that has 3 parameters and that corresponds to `foo(1, b, *, c, d=10)`

.
Similarly, `baz = partial(foo, 1, 2)`

is a function that has 2 parameters and that corresponds to `foo(1, 2, *, c, d=10)`

.

```
>>> bar = partial(foo, 1)
>>> bar(20, c=30, d=40)
1 20 30 40
>>> baz = partial(foo, 1, 2)
>>> baz(c=30, d=40)
1 2 30 40
```

Notice that `partial`

doesn't do any type of validation whatsoever regarding the number of arguments you pass in.
This means that a call to `partial`

might succeed but then produce a function that is unusable.

The...

]]>