Word Aligned

Priority queues in Python

tag@wordaligned.org (Thomas Guest) — 2022-02-25

In the previous article I noted that Python’s heapq module is the only part of standard Python I could think of which deals with sorting, but which doesn’t give you full control over the sort order.

That means you need to take care when using a heapq as a priority queue.

For example, the A* search algorithm is a best first path finder. It maintains a priority queue of possible steps to take, ordered by an estimate of the total distance of the path routed through these steps. At each stage it pops the next step — the one with the shortest estimated total distance — from the queue, then updates based on the new position.

import heapq

def a_star(start, heuristic, moves):
    """A* graph search

    - start: initial state
    - heuristic(s): estimates path length from state s to finish. 
                    heuristic(s) == 0 => finished
    - moves(s): neighbours of s

    Returns the shortest path to the finish and its cost, on success.
    None otherwise.
    """
    costs = {start: 0}
    prev = {start: None}
    frontier = [(heuristic(start), start)]
    heapq.heapify(frontier)

    def path(s):
        return [] if s is None else path(prev[s]) + [s]

    while frontier:
        priority, state = heapq.heappop(frontier)
        if heuristic(state) == 0:
            return costs[state], path(state)
        for n in moves(state):
            n_cost = costs[state] + 1
            if n not in costs or n_cost < costs[n]:
                costs[n] = n_cost
                heapq.heappush(frontier, (n_cost + heuristic(n), n))
                prev[n] = state

The code above is a Python A* implementation. For simplicity, we’ll assume the cost of each step is 1. It’s easy enough to adapt the function if this isn’t the case.

The priority queue here is named frontier, the collection of states we need to explore. The sequence heapify, heappop, heappush maintains the priority ordering. (The call to heapify isn’t even needed since a list with one element is already a heap.) So, each time we pop a state from the queue, we get the one with the lowest estimated cost. Then, based on the moves we can make from this new step, we update our internal records of costs and previous nodes.

Note that the items on the queue are (cost, state) pairs. The costs will be numbers, typically positive integers — the exact values depend on the heuristic function.

Exactly what gets used as state is up to the caller which supplies start, the initial state, and moves, which steps from a state to its neighbours.

However, if items on the queue are tied on cost, the heapq may need to compare state values. If the states have no defined ordering this results in a runtime error.

>>> class State: pass
... 
>>> x1, x2 = State(), State()
>>> (1, x1) < (2, x2)
True
>>> (1, x1) < (1, x2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'State' and 'State'

We cannot supply a sort key to the heapq functions. Does this mean clients must ensure state objects — whatever they actually are — can be compared? As the code stands, yes, but the module documentation has advice on handling this situatation:

[…] store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added. And since no two entry counts are the same, the tuple comparison will never attempt to directly compare two tasks.

This strategy gives a more usable a_star.

import heapq
import itertools

def a_star(start, heuristic, moves):
    costs = {start: 0}
    prev = {start: None}
    seq = itertools.count().__next__
    frontier = [(heuristic(start), seq(), start)]

    def path(s):
        return [] if s is None else path(prev[s]) + [s]

    while frontier:
        _, _, state = heapq.heappop(frontier)
        if heuristic(state) == 0:
            return costs[state], path(state)
        for n in moves(state):
            n_cost = costs[state] + 1
            if n not in costs or n_cost < costs[n]:
                costs[n] = n_cost
                heapq.heappush(frontier, (n_cost + heuristic(n), seq(), n))
                prev[n] = state

Binary search gets a sort key

tag@wordaligned.org (Thomas Guest) — 2022-02-15

Suppose you have an list of distinct elements which has been sorted and rotated. How would you look up an element within that list?

For example, the list:

[7, 11, 13, 19, 2, 3, 5]

is sorted (the first 7 primes, in order) and rotated (to put 7 first).

With this list as input, then:

look up 13 returns 2 since 13 is at index 2
look up 2 returns 4
look up 4 returns the sentinel value -1

The obvious technique is to just search the list:

def lookup(values, v):
    try:
        return values.index(v)
    except IndexError:
        return -1

This is a linear algorithm which processes the entire list. Is there a way to take advantage of its sorted+rotated-ness?

If the list was sorted then we could apply a binary search for a logarithmic lookup. And in fact, by applying a custom ordering, the list is sorted.

How can we apply a custom ordering in Python?

The way to do this has changed as Python has developed. The table below shows the evolution of standard Python functions which sort and compare.

Version	Year	Functions	Notes
2.0	2000	max, min, list.sort([cmp]), bisect.bisect	Note that [cmp] slows the sorting process down considerably
2.3	2003	heapq	Also known as the priority queue algorithm
2.4	2004	sorted(iterable[, cmp[, key[, reverse]]]), list.sort([cmp[, key[, reverse]]]), itertools.groupby(iterable[, key)	In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function
2.4	2004	heapq.nlargest, heapq.nsmallest	Heapq extended
2.5	2006	max([key]), min([key]), heapq.nlargest(…[, key]), heapq.smallest(…[, key])
2.6	2008	heapq.merge	Heapq extended again
3.0	2008	sorted(iterable, key[, reverse]), list.sort(key[, reverse])	No more `cmp`
3.5	2015	heapq.merge(…, key)
3.10	2021	bisect.bisect(…, key) etc	That leaves the low-level `heapq` functions

The earliest versions of Python allowed you to sort lists, and the sort was customised using a cmp function — though the documentation warned there would be a performance penalty[*]. The builtin min and max functions could not be cutomised, and nor could the comparison used in the bisect module — which is Python’s binary search implementation.

At 2.3 the heapq module appeared, but, like bisect, there was no way to customise the ordering of heap elements.

2.4 introduced the key argument to customise ordering, noting this should be preferred to cmp. Unlike cmp which compares two elements, key takes a single element and returns a sort rank for that element. The key argument was added alongside cmp in list.sort and the new sorted builtin function; and key was the only way to customise the grouping in itertools.groupby.

2.5 added key to min and max, and also to heapq.nlargest, heapq.nsmallest. Although these heapq functions now accept a key, the lower level heap functions to heapify, push, pop and replace do not.

2.6 introduced heapq.merge, a handy function to merge sorted inputs using a heap, but with no option to specify a sort key.

3.0 got rid of cmp, making key the only way to customise sorting. To migrate from Python 2 to 3 any cmp functions need converting to key functions. As with Python 2.5, at 3.0 you could apply a key to list.sort, sorted, min, max, itertools.groupby, heapq.nlargest, heapq.nsmallest — but not to bisect or other heapq functions.

3.5 added key to heapq.merge, aligning it with heapq.nlargest and heapq.nsmallest, though it remained impossible to use a sort key with the lower level heap functions.

The next change came in 3.10, when the key parameter was added to the bisect module. As far as I can tell that means the only part of standard Python which doesn’t let you fully customise ordering is the heapq module.

Bisect with a search key

So, to return to the original puzzle, consider our example sorted+rotated list:

>>> values = [7, 11, 13, 19, 2, 3, 5]

The first four elements are greater than or equal to the first element, 7. The last three elements are less than 7.

>>> [v < values[0] for v in values]
[False, False, False, False, True, True, True]

Since False < True the result of the list comprehension above is sorted. Extending this idea, the following comprehension is also sorted.

>>> [(v < values[0], v) for v in values]
[(False, 7), (False, 11), (False, 13), (False, 19), (True, 2), (True, 3), (True, 5)]

Now we have a logarithmic lookup using binary search:

from bisect import bisect_left

def lookup(values, v):
    key = lambda x: (x < values[0], x)
    i = bisect_left(values, key(v), key=key)
    return i if (i < len(values) and values[i] == v) else -1

Don’t search for v, search for its key

I was surprised to realise the value v being looked up has to have the key function applied before calling bisect_left. That is, to find where v should go in values to maintain the sort order, we pass key(v) to bisect_left. This doesn’t match the interface to binary search in other languages. It also means in our example we have to handle empty lists as a special case.

def lookup(values, v):
    if not values: return -1
    key = lambda x: (x < values[0], x)
    i = bisect_left(values, key(v), key=key)
    return i if (i < len(values) and values[i] == v) else -1

[*] Before the introduction of the sort key, the standard pattern was decorate-sort-undecorate.

Python maths updates

tag@wordaligned.org (Thomas Guest) — 2021-01-03

A quick note on some useful updates made to standard Python maths support. Math.prod does for * what sum does for +. It was added at Python 3.8.

>>> math.prod([3, 4, 5])
60
>>> math.prod([])
1

Added in 3.9, math.lcm, returns the least common multiple of its integer arguments. As with math.prod, an empty list of arguments returns 1. Extended in 3.9, the related function math.gcd now accepts an arbitrary list of arguments.

For Euclidean geometry, math.hypot now supports n-dimensional points, and math.dist has been added, again working on any pair of n-dimensional points.

These useful additions and extensions are all in the standard math module (along with several others not mentioned here). Previously you’d have to roll your own or rely on e.g. numpy.

I also wanted to mention a nice extension to the power function; in this case to the builtin pow — math.pow remains as it was. Builtin pow takes an optional third parameter pow(base, exp[, mod]). If mod is specified it must be a non-zero integer, and both base and exp must also be integers. The significant but subtle change made at 3.8 is that exp can now be a negative integer, enabling modular inverse calculations.

Quoting the documentation:

… If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.
Here’s an example of computing an inverse for 38 modulo 97:
>>> pow(38, -1, mod=97) 23 >>> 23 * 38 % 97 == 1 True

Complex numbers for planar geometry

tag@wordaligned.org (Thomas Guest) — 2020-12-12

Once again, I’m enjoying solving Eric Wastl’s excellent Advent of Code puzzles.

Today, day 12 involved a ship navigating in a 2D plane. The ship follows a series of instructions taking the form of actions and values such as F10 N3 F7 R90 F11 ..., where, for the first part:

actions N, S, E, W step by the value in the compass directions N, S, E, W
actions L, R turn the ship left and right by the number of degrees specified by the value
action F advances the ship in the direction it faces by the given value

Perhaps the most obvious way to model this is by implementing a Point class, with x and y values, and suitable methods to advance and rotate.

Another way is to use complex numbers, which are natively supported by Python — and many other languages. The complex plane is a 2D plane. The point (x, y) is represented by a single complex number p = x + y * j. Stepping in any direction corresponds to addition, and rotation to multiplication.

So, the instructions N, S, E, W map to adding complex numbers j, -j, 1, -1.

Quarter turns left and right map to multiplication by j and -j.

def ship_position(instructions):
    '''Return the final position of the ship after following the instructions

    Instructions are a series of (action, value) pairs.
    '''
    ship, direction = 0, 1 # Start at the origin facing E
    step = {'N':1j, 'W':-1, 'S':-1j, 'E': 1}
    turn = {'R':-1j, 'L':1j}
    for action, value in instructions:
        if action in 'NSEW':
            ship += value * step[action]
        elif action in 'LR':
            assert value % 90 == 0 # check rectilinear motion
            direction *= turn[action] ** (value//90)
        else:
            assert action == 'F'
            ship += value * direction
    return ship

It’s also possible to implement the conditionals above arithmetically. We can think of each instruction advancing the ship (possibly by zero) and turning it (possibly by zero degrees).

def ship_position(instructions):
    ship, direction = 0, 1
    step = {'N':1j, 'W':-1, 'S':-1j, 'E': 1}
    turn = {'R':-1j, 'L':1j}
    for action, value in instructions:
        ship += value * (step.get(action, 0) + (action=='F') * direction)
        direction *= turn.get(action, 1) ** (value//90)
    return ship

More solutions here, and thanks again to Eric Wastl.

Aligning the first line of a triple-quoted string in Python

tag@wordaligned.org (Thomas Guest) — 2019-02-17

Python’s triple-quoted strings are a convenient syntax for strings where the contents span multiple lines. Unescaped newlines are allowed in triple-quoted strings. So, rather than write:

song = ("Happy birthday to you\n"
        "Happy birthday to you\n"
        "Happy birthday dear Gail\n"
        "Happy birthday to you\n")

you can write:

song = """Happy birthday to you
Happy birthday to you
Happy birthday dear Gail
Happy birthday to you
"""

The only downside here is that the first line doesn’t align nicely with the lines which follow. The way around this is to embed a \newline escape sequence, meaning both backslash and newline are ignored.

song = """\
Happy birthday to you
Happy birthday to you
Happy birthday dear Gail
Happy birthday to you
"""

Python Counters @PyDiff

tag@wordaligned.org (Thomas Guest) — 2019-01-19

On Monday I gave a talk at PyDiff on the subject of Python Counters. A Counter is a specialised dict which has much in common with a set. Of course all dicts are like sets, but with Counters the resemblance is even stronger. The documentation states:

The Counter class is similar to bags or multisets in other languages.

Alongside set operations of union, intersection and is-a-subset, Counter also supports addition and subtraction — natural and unsurprising operations for a container whose job is to keep count of its elements. If you want to unite the contents of two Counters, it’s probably + you want rather than |.

Counters came to mind as a lightning talk subject since I had a go at the Advent of Code last year and used no fewer than 12 Counters in my solutions to 25 puzzles — and that total could well increase since I haven’t finished yet.

The talk itself is on github.

Creating a dict of lists in Python

tag@wordaligned.org (Thomas Guest) — 2018-04-29

Suppose you have a list of objects which you want to convert into a dict mapping from some object key to the (sub-)list of objects with that key. To provide a simple example, let’s start with a list of fruits.

from collections import namedtuple

Fruit = namedtuple('Fruit', 'name colour')

def banana():     return Fruit('banana', 'yellow')
def grape():      return Fruit('grape', 'green')
def pear():       return Fruit('pear', 'green')
def strawberry(): return Fruit('strawberry', 'red')
def cherry():     return Fruit('cherry', 'red')

fruits = [
    banana(), pear(), cherry(), cherry(), pear(),
    grape(), banana(), grape(), cherry(), grape(),
    strawberry(), pear(), grape(), cherry()]

We’d like to arrange a fruitbowl — a dict which groups fruits by colour. This can be done by creating an empty bowl, then iterating through the fruits placing each in the correct list.

fruitbowl = {}

for fruit in fruits:
    fruitbowl.setdefault(fruit.colour, []).append(fruit)

Dict.setdefault is a bit of an oddity in Python, both doing something and returning a value, but it’s a convenient shorthand in this case. Despite this convenience it’s more common to use a defaultdict.

from collections import defaultdict

fruitbowl = defaultdict(list)

for fruit in fruits:
    fruitbowl[fruit.colour].append(fruit)

Here’s a function to display the fruitbowl.

def print_bowl(bowl):
    print('\n'.join(
        '{}: {}'.format(colour,
                        ', '.join(f.name for f in fruits))
        for colour, fruits in bowl.items()))

If we call this function, we see the fruits have indeed been grouped by colour.

>>> print_bowl(fruitbowl)
yellow: banana, banana
green: pear, pear, grape, grape, grape, pear, grape
red: cherry, cherry, cherry, strawberry, cherry

This is all fine and idiomatic Python, but whenever I see an empty dict being created followed by a loop to populate it, I wonder if a comprehension could be used.

Is there a way to declare and initialise the dict in a single expression? Here’s the best I came up with.

from operator import attrgetter
from itertools import groupby

colour = attrgetter('colour')

fruitbowl = {
    col: list(fts)
    for col, fts in groupby(sorted(fruits, key=colour), colour)}

Is this better than the defaultdict solution. Probably not, but it’s a technique worth remembering. Maybe the fruitbowl isn’t needed, and we actually just need to iterate through the fruits grouped by colour. For example, which colour is most popular?

>>> max(fruitbowl.items(), key=lambda kv: len(kv[1]))[0]
'green'

Using groupby, we don’t need the bowl.

>>> def grouplen(k_gp):
...     return sum(1 for _ in k_gp[1])
>>> max(groupby(sorted(fruits, key=colour), colour), key=grouplen)[0]
>>> 'green'

In this case, we don’t need groupby either. There is more than one way to do it.

>>> from collections import Counter
>>> Counter(map(colour, fruits)).most_common(1)
[('green', 7)]

TIMTOWTDI vs TSBO-APOO-OWTDI

tag@wordaligned.org (Thomas Guest) — 2018-04-19

TIMTOWTDI

TIMTOWTDI stands for “There is more than one way to do it”, an approach promoted by the Perl community.

The mindset behind it gets explored in more detail by the language’s creator, Larry Wall, in a talk given in 1999: “Perl, the first postmodern computer language”. He attributes the slogan to his daughter, Heidi, who says it’s a strategy which works well in her maths class; and she associates it with another saying used at school: “Tsall Good”. This doesn’t mean everything is good, or even everything has good bits. It means, overall, things are good. See the big picture.

Perl epitomises this. It’s eclectic and inclusive, supporting a variety of styles. One-liner? Fine! Like a shell script? Sure! Structured programming, object-oriented, functional? Why not! Tsall good.

I like that.

But do I feel that way about programming?

TSBO-APOO-OWTDI

A contrasting mantra appears in the Zen of Python, a list of aphorisms which summarise the guiding principles behind Python’s design. Item number 13 states “There should be one — and preferably only one — obvious way to do it.”

Perhaps realising this sounds overly prescriptive, this rule is tempered by item 14, “Although that way may not be obvious at first unless you’re Dutch.”

Guido van Rossum, Python’s BDFL — Benevolent Dictator For Life — would be the Dutch person who finds things obvious. That’s right: Dictator. Programmers don’t like being told what to do any more than two year olds. How then has Python become so popular?

Maybe emphasis falls on should. There should be only one obvious way to do it: it’s just that — Dutch or otherwise — we haven’t got there yet.

TIMTOP

For example, there is more than one Python. Obviously there’s Python 2 and Python 3, but it’s less obvious which to use. Don’t forget PyPy. Increasingly Python comes packaged with data processing and visualisation extensions, served up as a Jupyter notebook.

TIMTOPOM

There is more than one program options module.

When I started with Python there was getopt, the one and only command line handler. Coming from a C/C++ background I was quite happy to use something resembling GNU’s getopt. Then optparse appeared. Now there’s argparse. All of these libraries are readily available. Which should I use? Not optparse, that’s deprecated, unless I’m already using it and it works, that is. Regarding the other contenders, the documentation archly notes:

Users who are unfamiliar with the C getopt() function or who would like to write less code and get better help and error messages should consider using the argparse module instead.

There are other non-standard Python options for parsing a command line too: ones which generate code from the usage notes, or by inspecting the code you want to expose.

There is more than one way to do it.

TIMTOUTF

There is more than one unit test framework. The obvious one, unittest, like getopt, draws inspiration from elsewhere — in this case Java’s Junit. Unfortunately the port is too faithful, and you’ll have to inherit from super classes etc to test something. I much prefer PyTest, which flexes the language itself to deliver test assertions as asserts.

There’s also a doctest module in the standard library which executes and checks code found in strings (hold that thought!), and there are many other non-standard testing frameworks.

There is more than one way to do it.

TIMTOWOFS

There is more than one way of formatting strings.

As we’ve seen there’s more than one Python, and libraries are always up for reinvention. This is arguably evolution rather than a multiplicity of options. That is, the most recent way to do it should be preferred.

When it comes to string formatting, though, there has always been more than one way to do it, and more ways are still being added.

Do you use 'single' or "double" quotes for a string? """Triple""" quotes. Raw strings? Raw with an r or Raw with an R? TIMTOWTDI.

What if you want to embed the value of a variable in a string? Users familiar with C’s printf() function might prefer % formatting. Fans of $shell $parameter $expansion can use template strings.

Advanced string formatting — str.format — appeared in Python 3.0, backported to Python 2.6. No doubt it has advantages over % formatting, but for me it’s a little more obscure and a little less obvious. Python 3.6 introduces f-strings which build on str.format and knock down my reservations. The syntax allows you to evaluate expressions in strings: evidently Python is heading in Perl’s direction.

APSDOTADIW

Let’s finish by returning to Perl, and to Larry Wall’s 1999 talk.

How many times have we heard the mantra that a program should do one thing and do it well?

Perl is not that program. Perl wants to do everything well. It integrates features and makes no attempt to homogenise them.

You’ve all heard the saying: If all you have is a hammer, everything starts to look like a nail.

Perl is no hammer: it has memorably been described as a Swiss army chainsaw, but Larry Wall likens it to a more conventional tool.

If all you have is duct tape, everything starts to look like a duct. Right. When’s the last time you used duct tape on a duct?

Python may aspire to offer a single obvious way to do something. It fails splendidly, being more duct tape than hammer.

I presented this blog post as a lightning talk at PyDiff a couple of days ago. The slides are here. The talk was recorded too: I appear about 24 minutes in.

Advent of Code 2017

tag@wordaligned.org (Thomas Guest) — 2018-01-12

A big thanks to Eric Wastl for another great Advent of Code. Inspired by Peter Norvig, I’ve published my solutions as a Jupyter notebook.

Unleash the test army

tag@wordaligned.org (Thomas Guest) — 2017-05-29

Are the tests adequate?

Recently I described a solution to the problem of dividing a list into evenly sized chunks. It’s a simple enough problem with just two inputs: the list (or other sliceable container) xs and the number of chunks n. Nonetheless, there are traps to avoid and special cases to consider — what if n is larger than the list, for example? Must the chunks comprise contiguous elements from the original list?

The tests I came up with are straightforward and uninspiring. They were developed within the context of my own assumptions about the solution and the special cases I could imagine. They were written after the implementation — which is to say, development wasn’t driven by tests. They are whitebox tests, designed to cover the various paths through the code based on my insider knowledge.

Are these tests adequate? Certainly they don’t accurately represent the data which will hit the algorithm in practice. Can we be sure we haven’t missed anything? Would the tests still cover all paths if the implementation changed?

Property based testing

David R MacIver described another, complementary, approach at a talk I attended at ACCU 2016. In the talk abstract he characterises the (class of) tests I’d written as anecdotal — “let me tell you about this time I called a function … and then it returned this .. and then it raised an exception … etc. etc.”

How about if the test suite instead describes the properties required of the system under test, and then conjures up inputs designed to see if these properties hold under stress? So, rather than our test suite being a limited set of input/output pairs, it becomes an executable specification validated by a robot army.

Hypothesis

This approach sounds compelling but I had my doubts. I also had my doubts about the adequacy of both my code and tests. A perfect opportunity, then, to try out Hypothesis, an open source property-based testing library developed by David MacIver.

I used the Python version of the library, which is the primary implementation. The rest of this article describes my experience of using hypothesis for the first time: I’m not claiming expertise.

First impressions

Excellent!

Installation was the usual pip invocation. The documentation is written with care. It’s evident the library is mature, supported and actively developed. It’s licensed under the Mozilla Public License.

My first test

Recall that the code I wanted to test reads:

def chunk(xs, n):
    '''Split the list, xs, into n evenly sized chunks'''
    L = len(xs)
    assert 0 < n <= L
    s, r = divmod(L, n)
    t = s + 1
    return ([xs[p:p+t] for p in range(0, r*t, t)] +
            [xs[p:p+s] for p in range(r*t, L, s)])

I also proposed a second itertools based version:

from itertools import accumulate, chain, repeat, tee

def chunk(xs, n):
    '''Split the list, xs, into n evenly sized chunks'''
    assert n > 0
    L = len(xs)
    s, r = divmod(L, n)
    widths = chain(repeat(s+1, r), repeat(s, n-r))
    offsets = accumulate(chain((0,), widths))
    b, e = tee(offsets)
    next(e)
    return [xs[s] for s in map(slice, b, e)]

The first thing you notice when thinking about a property based test is that the specification — the function’s docstring — doesn’t describe the exact form of the output. In fact, as a comment on the article pointed out, my own interpretation of the specification is not the only one, and allowing the chunks to be formed from non-contiguous items permits a particularly elegant solution.

Also, if the list doesn’t divide exactly into n chunks, what should the result be? Well, although I’d have been happy with any evenly-chunked solution, my conventional unit tests assumed an implementation which placed the larger chunks first.

def test_chunk():
    assert chunk('', 1) == ['']
    assert chunk('ab', 2) == ['a', 'b']
    assert chunk('abc', 2) == ['ab', 'c']

    xs = list(range(8))
    assert chunk(xs, 2) == [[0, 1, 2, 3], [4, 5, 6, 7]]
    assert chunk(xs, 3) == [[0, 1, 2], [3, 4, 5], [6, 7]]
    assert chunk(xs, 5) == [[0, 1], [2, 3], [4, 5], [6], [7]]

    rs = range(1000000)
    assert chunk(rs, 2) == [range(500000), range(500000, 1000000)]

Notice, by the way, that although the docstring only mentions lists, I can’t resist demonstrating the algorithm also behaves for strings and ranges — for any sliceable sequence, in fact.

Here’s what I started with when I tried specifying the “evenly sized” property using hypothesis.

def test_evenly_chunked(xs, n):
    chunks = chunk(xs, n)
    assert len(chunks) == n
    chunk_lens = {len(c) for c in chunks}
    assert len(chunk_lens) in {1, 2}
    assert max(chunk_lens) - min(chunk_lens) in {0, 1}

This first test case defines “evenly sized”, stating that the result comprises n chunks, that the set of the lengths of these chunks is either 1 (all chunks the same size) or 2, and the maximum chunk length is equal to or one more than the minumum chunk length.

This doesn’t fully specify the function. We also need assertions which confirm that recombining the chunks produces the original sequence.

def test_combining_chunks(xs_n):
    pass # We'll come back to this!

We’ll come back to this later!

Now, test_evenly_chunked() looks quite like a conventional test function. It just needs some input values. Rather than poke the function with some hand-chosen values, we can let hypothesis have a go.

Based on a read of the Quick start guide I tried this:

import hypothesis as ht
import hypothesis.strategies as st

@ht.given(xs=st.lists(), n=st.integers())
def test_evenly_chunked(xs, n):
    chunks = chunk(xs, n)
    assert len(chunks) == n
    chunk_lens = {len(c) for c in chunks}
    assert len(chunk_lens) in {1, 2}
    assert max(chunk_lens) - min(chunk_lens) in {0, 1}

As you can see, the test function pre-conditions are encapsulated in a hypothesis.given decorator, which specifies the use of hypothesis.strategies.lists() and hypothesis.strategies.integers() to generate test values for xs and n respectively.

The result was a lengthy but helpful failure, which printed out the documentation of the lists() strategy and the usage error:

hypothesis.errors.InvalidArgument: Cannot create non-empty lists without an element type

OK then. The function doesn’t really care about the element type. Integers will do.

@ht.given(xs=st.lists(st.integers()), n=st.integers())
def test_evenly_chunked(xs, n):
    ....

This gave me an error, along with a minimal test case which produces it.

xs = [], n = 0

    def chunk(xs, n):
        '''Split the list, xs, into n evenly sized chunks'''
        L = len(xs)
>       assert 0 < n <= L
E       AssertionError

Our function, chunk() requires the value n to be in the closed range (0, len(xs)]. Looking more closely at the failure, we can see that the function under test, chunk(), isn’t great, since we won’t be able to split an empty list into any number of chunks since, in this case, L is zero and no value of n satisfies 0 < n <= L.

At this point I had to makes some choices:

should my tests confirm chunk() was checking pre-conditions (by catching the AssertionError)?
should my function handle the case when n > L? It’s not the intended use of the function, but it can be handled.
what about when n == 0? Splitting a non-empty list into 0 chunks is impossible, but I guess an empty list can be split into 0 chunks.

My second test

I made some decisions.

I decided not to test the pre-condition assertions. Instead, I’d modify the test strategy to pass in valid inputs.
I decided I’d go with the itertools chunk function which naturally handles n > L.
I decided my function needn’t handle n == 0, even when xs == [].

Here’s the modified test code

@ht.given(xs=st.lists(st.integers()),
          n=st.integers(min_value=1))
def test_evenly_chunked(xs, n):
    chunks = chunk(xs, n)
    assert len(chunks) == n
    chunk_lens = {len(c) for c in chunks}
    assert len(chunk_lens) in {1, 2}
    assert max(chunk_lens) - min(chunk_lens) in {0, 1}
    ....

When I tried running the tests again, they appeared to hang until I interrupted them.

> py.test
============================= test session starts =============================
platform win32 -- Python 3.5.3, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
....
plugins: hypothesis-3.8.3
collected 1 items

test_chunk.py   C-c C-c

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! KeyboardInterrupt !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
to show a full traceback on KeyboardInterrupt use --fulltrace

Now, I had a suspicion that chunk() couldn’t really handle any input integers — it was designed for a value of n equal to multiprocessing.cpu_count() — but I wanted to see what would happen with no upper limits. Here was my answer. Running and interrupting again with --fulltrace set, I got several pages of output ending with the test inputs:

xs = [50], n = 67108865

Evidently my code was taking a while to create a list comprising a single list [50] and over 67 million empty lists [], [], [], ....

Once again, I had a decision to make. Perhaps unsurprisingly, it’s a decision I’d already faced. I could make chunk() a generator function, yielding the chunks one at a time — a trivial and natural change to the itertools based implementation — or I could constrain the tests to more suitable values of n.

In this case I decided to stick with what I had: my function would accept a list and return a list (of lists). In an attempt to get some passing tests, I set a maximum value on n.

@ht.given(xs=st.lists(st.integers()),
          n=st.integers(min_value=1, max_value=100))
def test_evenly_chunked(xs, n):
    ....

At last, I had a passing test.

py.test 
============================= test session starts =============================
platform win32 -- Python 3.5.3, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
rootdir: /work/sliced-python, inifile:
plugins: hypothesis-3.8.3
collected 1 items

test_chunk.py .

========================== 1 passed in 0.23 seconds ===========================

Building on this success, I wanted to confirm the function also handled other sliceable types — strings and bytes specifically. Hypothesis provides a one_of strategy for combining other strategies.

@ht.given(xs=st.one_of(st.text(),
                       st.binary(),
                       st.lists(st.integers())),
          n=st.integers(min_value=1, max_value=100))
def test_evenly_chunked(xs, n):
    chunks = chunk(xs, n)
    assert len(chunks) == n
    chunk_lens = {len(c) for c in chunks}
    assert len(chunk_lens) in {1, 2}
    assert max(chunk_lens) - min(chunk_lens) in {0, 1}

Again, the test passes.

py.test
============================= test session starts =============================
platform win32 -- Python 3.5.3, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
rootdir: /work/sliced-python, inifile:
plugins: hypothesis-3.8.3
collected 1 items

test_chunk.py .

========================== 1 passed in 0.30 seconds ===========================

This output is rather inscrutable. Generally, passing tests shouldn’t draw attention to themselves, but what inputs had my test strategies generated? Were they sufficient?

A commandline switch provides a little more detail.

py.test --hypothesis-show-statistics

....

test_chunk.py::test_evenly_chunked:

  - 200 passing examples, 0 failing examples, 0 invalid examples
  - Typical runtimes: < 1ms
  - Stopped because settings.max_examples=200

It’s also possible to peek at examples produced by the test strategy.

>>> s=st.one_of(st.text(), st.binary(), st.lists(st.integers()))
>>> s.example()
b''
>>> s.example()
b'\xc2\xfd6['
>>> s.example()
':\nú&\U000ea7e8'
>>> s.example()
b'\xe7z'
>>> s.example()
''
>>> s.example()
[184, 36, -205, 1486638017]

Complete test suite

Here’s my final test suite. Rather than hard code a maximum value for n, I used a composite strategy which adapts n to the size of xs. I’ve also added a test which confirms the result does comprise chunks of the input sequence.

import functools

import hypothesis as ht
import hypothesis.strategies as st

@st.composite
def items_and_chunk_count(draw):
    xs = draw(st.one_of(st.text(),
                        st.binary(),
                        st.lists(st.integers())))
    n = draw(st.integers(min_value=1,
                         max_value=max(1, len(xs))))
    return xs, n


@ht.given(xs_n=items_and_chunk_count())
def test_evenly_chunked(xs_n):
    '''Verify there are n evenly sized chunks'''
    xs, n = xs_n
    chunks = chunk(xs, n)
    assert len(chunks) == n
    chunk_lens = {len(c) for c in chunks}
    assert len(chunk_lens) in {1, 2}
    assert max(chunk_lens) - min(chunk_lens) in {0, 1}


@ht.given(xs_n=items_and_chunk_count())
def test_combining_chunks(xs_n):
    '''Verify recombining the chunks reproduces the original sequence.'''
    xs, n = xs_n
    chunks = chunk(xs, n)
    assert functools.reduce(lambda x, y: x+y, chunks) == xs

Quality of failure

In the comments to my original article Mike Edey put forward an elegant solution to the original problem of evenly subdividing a sequence into an exact number of chunks:

def chunk(xs, n):
    return [xs[index::n] for index in range(n)]

This is a delightful piece piece of code, and an approach I simply hadn’t considered. If the input list xs represents a number of tasks to be distributed amongst n workers, this does the job evenly. In my actual motivating example, though, however, the input sequence was a document which caused a problem, and what I wanted to do was split that document up into a number of sections and see which of these exhibited the same problem: that is, I needed the chunks to be contiguous blocks of text from the original document. This is the property which test_combining_chunks() checks.

Running Mike Edey’s implementation through the test suite, we get:

py.test
============================= test session starts =============================
platform win32 -- Python 3.5.3, pytest-3.0.7, py-1.4.33, pluggy-0.4.0
rootdir: /work/sliced-python, inifile:
plugins: hypothesis-3.8.3
collected 2 items

test_chunk.py .F

================================== FAILURES ===================================
____________________________ test_combining_chunks ____________________________

    @ht.given(xs_n=items_and_chunk_count())
>   def test_combining_chunks(xs_n):

test_chunk.py:29: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
d:\venvs\slackbot\lib\site-packages\hypothesis\core.py:634: in wrapped_test
    state.run()
d:\venvs\slackbot\lib\site-packages\hypothesis\core.py:531: in run
    print_example=True, is_final=True
d:\venvs\slackbot\lib\site-packages\hypothesis\executors.py:58: in default_new_style_executor
    return function(data)
d:\venvs\slackbot\lib\site-packages\hypothesis\core.py:113: in run
    return test(*args, **kwargs)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

xs_n = ('001', 2)

    @ht.given(xs_n=items_and_chunk_count())
    def test_combining_chunks(xs_n):
        '''Verify recombining the chunks reproduces the original sequence.'''
        xs, n = xs_n
        chunks = chunk(xs, n)
>       assert functools.reduce(lambda x, y: x+y, chunks) == xs
E       AssertionError: assert '010' == '001'
E         - 010
E         + 001

test_chunk.py:33: AssertionError
--------------------------------- Hypothesis ----------------------------------
Falsifying example: test_combining_chunks(xs_n=('001', 2))
===================== 1 failed, 1 passed in 0.52 seconds ======================

Hypothesis has discovered a minimal failing example: the string 001 splits into 2 chunks as 01, 0.

Conclusions

Hypothesis worked well for this particular example.

it forced me to pin down the function specification
I had to consider the special cases: would the function behave in the face of logically permissable inputs, and not just the ones I had in mind when I wrote it
it increased my confidence the function was correct
and particularly appealing, in this case — the tests were not tied to a detail of the implementation, and would continue to work if, for example, the larger chunks were to appear at the end of the results.

More generally, I found the hypothesis library solid. It’s well designed and documented, as well as being a fine example of how to use Python decorators.

I’d say property based testing complements example based testing. Example based unit tests show you how a function is used, for instance; with hypothesis, this useful demonstration happens behind the scenes (though note that your hypothesis tests can include explicit @examples). Example based unit tests are typically one or two orders of magnitude quicker to execute. It’s not a problem if a couple of tests take half a second to run, but what if you have a couple of thousand tests?

In my case the built-in strategies were good enough to generate inputs to my function. I can imagine that’s not the case for functions higher up a software stack. Test setup functions can be hard work and I suspect test setup strategies would be harder.

In closing, I’d like to quote from the section of the Hypothesis documentation which describes its purpose.

Software is, as they say, eating the world. Software is also terrible. It’s buggy, insecure and generally poorly thought out. This combination is clearly a recipe for disaster.

And the state of software testing is even worse. Although it’s fairly uncontroversial at this point that you should be testing your code, can you really say with a straight face that most projects you’ve worked on are adequately tested?

A lot of the problem here is that it’s too hard to write good tests. Your tests encode exactly the same assumptions and fallacies that you had when you wrote the code, so they miss exactly the same bugs that you missed when you wrote the code.

— The Purpose of Hypothesis

Lazy sequences working hard

tag@wordaligned.org (Thomas Guest) — 2017-05-16

I gave a talk @PyDiff this evening in the computer science department at Cardiff University.

Lazy Sequences working hard

Python has no problem handling large and even infinite streams of data. Just write lazy programs — code which defers data access until the last minute. This talk examines Python’s language and library support for such delaying tactics. There will be live coding, and we’ll draw parallels with similar features in other languages, in particular the Unix shell.

Being unsure where to pitch it, I started off easy and kept going until I’d lost everybody — including myself.

The room was well set up with a good quality projector and whiteboard, along with a desk to sit down when I wanted to write and run code and plenty of space to move around in otherwise. I did feel a bit like a jack-in-the-box by the end.

I’d based the talk on a Jupyter notebook which I replayed with the ingenious RISE reveal.js extension written by Damian Avila. This worked well, since I got the pretty graphics along with the interactive coding. A static version of the slides is available here.

Thanks to everyone who came. Sorry I had to rush off after. If anyone would like to talk at Swansea, please let me know: you’d be most welcome.

Slicing a list evenly with Python

tag@wordaligned.org (Thomas Guest) — 2017-05-14

Here’s a problem I came up against recently.

The task was to chop a list into exactly n evenly slized chunks. To give a little more context, let’s suppose we want to divide a list of jobs equally between n workers, where n might be the number of CPU cores available.

We can build the result by repeatedly slicing the input:

def chunk(xs, n):
    '''Split the list, xs, into n chunks'''
    L = len(xs)
    assert 0 < n <= L
    s = L//n
    return [xs[p:p+s] for p in range(0, L, s)]

This looks promising

>>> chunk('abcdefghi', 3)
['abc', 'def', 'ghi']

but if the size of the list is not an exact multiple of n, the result won’t contain exactly n chunks.

>>> chunk('abcde', 3)
['a', 'b', 'c', 'd', 'e']
>>> chunk('abcdefgh', 3)
['ab', 'cd', 'ef', 'gh']
>>> chunk('abcdefghij', 3)
['abc', 'def', 'ghi', 'j']

(By the way, I’m using strings rather than lists in the examples. The code works equally well for both types, and strings make it slightly easier to see what’s going on.)

One way to fix the problem is to group the final chunks together.

def chunk(xs, n):
    '''Split the list, xs, into n chunks'''
    L = len(xs)
    assert 0 < n <= L
    s, r = divmod(L, n)
    chunks = [xs[p:p+s] for p in range(0, L, s)]
    chunks[n-1:] = [xs[-r-s:]]
    return chunks

Now we have exactly n chunks, but they may not be evenly sized, since the last chunk gets padded with any surplus.

>>> chunk('abcde', 3)
['a', 'b', 'cde']
>>> chunk('abcdefgh', 3)
['ab', 'cd', 'efgh']
>>> chunk('abcdefghij', 3)
['abc', 'def', 'ghij']

What does “evenly sized” actually mean? Loosely speaking, we want the resulting chunks as closely sized as possible.

More precisely, if the result of dividing the length of the list L by the number of chunks n gives a size s with remainder r, then the function should return r chunks of size s+1 and n-r chunks of size s. There are choose(n, r) ways of doing this. Here’s a solution which puts the longer chunks to the front of the results.

def chunk(xs, n):
    '''Split the list, xs, into n evenly sized chunks'''
    L = len(xs)
    assert 0 < n <= L
    s, r = divmod(L, n)
    t = s + 1
    return ([xs[p:p+t] for p in range(0, r*t, t)] +
            [xs[p:p+s] for p in range(r*t, L, s)])

Here’s a second implementation, this time using itertools. Chaining r copies of s+1 and n-r copies of s gives us the n chunk widths. Accumulating the widths gives us the list offsets for slicing — though note we need to prepend an initial 0. Now we can form a (this, next) pair of iterators over the offsets, and the result is the accumulation of repeated (begin, end) slices taken from the original list.

from itertools import accumulate, chain, repeat, tee

def chunk(xs, n):
    assert n > 0
    L = len(xs)
    s, r = divmod(L, n)
    widths = chain(repeat(s+1, r), repeat(s, n-r))
    offsets = accumulate(chain((0,), widths))
    b, e = tee(offsets)
    next(e)
    return [xs[s] for s in map(slice, b, e)]

This version does something sensible in the case when the number of slices, n, exceeds the length of the list.

>>> chunk('ab', 5)
['a', 'b', '', '', '']

Finally, some tests.

def test_chunk():
    assert chunk('', 1) == ['']
    assert chunk('ab', 2) == ['a', 'b']
    assert chunk('abc', 2) == ['ab', 'c']

    xs = list(range(8))
    assert chunk(xs, 2) == [[0, 1, 2, 3], [4, 5, 6, 7]]
    assert chunk(xs, 3) == [[0, 1, 2], [3, 4, 5], [6, 7]]
    assert chunk(xs, 5) == [[0, 1], [2, 3], [4, 5], [6], [7]]

    rs = range(1000000)
    assert chunk(rs, 2) == [range(500000), range(500000, 1000000)]

From bytes to strings in Python and back again

tag@wordaligned.org (Thomas Guest) — 2017-03-24

Low level languages like C have little opinion about what goes in a string, which is simply a null-terminated sequence of bytes. Those bytes could be ASCII or UTF-8 encoded text, or they could be raw data — object code, for example. It’s quite possible and legal to have a C string with mixed content.

char const * mixed =
    "EURO SIGN "          // ASCII
    "UTF-8 \xE2\x82\xAC " // UTF-8 encoded EURO SIGN
    "Latin-9 \xA4";       // Latin-9 encoded EURO SIGN

This might seem indisciplined and risky but it can be useful. Environment variables are notionally text but actually C strings, for example, meaning they can hold whatever data you want. Similarly filenames and command line parameters are only loosely text.

A higher level language like Python makes a strict distinction between bytes and strings. Bytes objects contain raw data — a sequence of octets — whereas strings are Unicode sequences. Conversion between the two types is explicit: you encode a string to get bytes, specifying an encoding (which defaults to UTF-8); and you decode bytes to get a string. Clients of these functions should be aware that such conversions may fail, and should consider how failures are handled.

Simply put, a string in Python is a valid Unicode sequence. Real world text data may not be. Programmers need to take charge of reconciling any discrepancies.

We faced such problems recently at work. We’re in the business of extracting meaning from clinical narratives — text data stored on medical records systems in hospitals, for example. These documents may well have passed through a variety of systems. They may be unclear about their text encoding. They may not be encoded as they claim. So what? They can and do contain abbreviations, mispellings, jargon and colloquialisms. Refining the signal from such noise is our core business: if we can correctly interpret positional and temporal aspects of a sentence such as:

Previous fracture of left neck of femur

then we can surely deal with text which claims to be UTF-8 encoded but isn’t really.

Our application stack is server-based: a REST API to a Python application handles document ingest; lower down, a C++ engine does the actual document processing. The problem we faced was supporting a modern API capable of handling real world data.

It’s both undesirable and unnecessary to require clients to clean their text before submitting it. We want to make the ingest direct and idiomatic. Also, we shouldn’t penalise clients whose data is clean. Thus document upload is an HTTP POST request, and the document content is a JSON string — rather than, say, base64 encoded binary data. Our server, however, will be permissive about the contents of this string.

So far so good. Postel’s prescription advises:

Be liberal in what you accept, and conservative in what you send.

This would suggest accepting messy text data but presenting it in a cleaned up form. In our case, we do normalise the input data — a process which includes detecting and standardising date/time information, expanding abbreviations, fixing typos and so on — but this normalised form links back to a faithful copy of the original data. What gets presented to the user is their own text annotated with our findings. That is, we subscribe to a more primitive prescription than Postel’s:

Garbage in, garbage out

with the caveat that the garbage shouldn’t be damaged in transit.

Happily, there is a simple way to pass dodgy strings through Python. It’s used in the standard library to handle text data which isn’t guaranteed to be clean — those environment variables, command line parameters, and filenames for example.

The surrogateescape error handler smuggles non-decodable bytes into the (Unicode) Python string in such a way that the original bytes can be recovered on encode, as described in PEP 383:

On POSIX systems, Python currently applies the locale’s encoding to convert the byte data to Unicode, failing for characters that cannot be decoded. With this PEP, non-decodable bytes >= 128 will be represented as lone surrogate codes U+DC80..U+DCFF.

This workaround is possible because Unicode surrogates are intended for use in pairs. Quoting the Unicode specification, they “have no interpretation on their own”. The lone trailing surrogate code — the half-a-pair — can only be the result of a surrogateescape error handler being invoked, and the original bytes can be recovered by using the same error handler on encode.

In conclusion, text data is handled differently in C++ and Python, posing a problem for layered applications. The surrogateescape error handler provides a standard and robust way of closing the gap.

Unicode Surrogate Pairs

Code Listing

>>> mixed = b"EURO SIGN \xE2\x82\xAC \xA4"
>>> mixed
b'EURO SIGN \xe2\x82\xac \xa4'
>>> mixed.decode()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeDecodeError: 'utf-8' codec can't decode byte 0xa4 in position 14:
  invalid start byte
>>> help(mixed.decode)
Help on built-in function decode:

decode(encoding='utf-8', errors='strict') method of builtins.bytes instance
    Decode the bytes using the codec registered for encoding.

    encoding
      The encoding with which to decode the bytes.
    errors
      The error handling scheme to use for the handling of decoding errors.
      The default is 'strict' meaning that decoding errors raise a
      UnicodeDecodeError. Other possible values are 'ignore' and 'replace'
      as well as any other name registered with codecs.register_error that
      can handle UnicodeDecodeErrors.

>>> mixed.decode(errors='surrogateescape')
'EURO SIGN € \udca4'
>>> s = mixed.decode(errors='surrogateescape')
>>> s.encode()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeEncodeError: 'utf-8' codec can't encode character '\udca4' in position 12:
  surrogates not allowed
>>> s.encode(errors='surrogateescape')
b'EURO SIGN \xe2\x82\xac \xa4'

24 Puzzles

tag@wordaligned.org (Thomas Guest) — 2017-03-08

On The Universe of Discourse Mark Dominus discusses the classic 24 Puzzle:

You are given a sequence of four digits, say 1, 2, 3, 4, and your job is to combine them with ordinary arithmetic operations (+, -, ×, and ÷) in any order to make a target number, typically 24. For example, with 1, 2, 3, 4, you can go with ((1+2)+3)×4=24 or with 4×((2×3)×1)=24.

Here’s a solver for such puzzles. It uses itertools to generate possible expressions, fractions to get the arithmetic right, and eval to evaluate expressions. It’s limited to expressions formed from 4 numbers which means I don’t have to programmatically calculate different ways of parenthesising: there are only 5.

# http://blog.plover.com/math/24-puzzle.html
import re
import math

# Use fractions for exact calculations
from fractions import Fraction

# Solve for 4 numbers only!
N = 4 

# So these are the only expression templates
# where X is a number and @ is an operation
templates = '''\
((X @ X) @ X) @ X
(X @ (X @ X)) @ X
X @ ((X @ X) @ X)
X @ (X @ (X @ X))
(X @ X) @ (X @ X)'''.splitlines()

import itertools as its

def defrac(s):
    return re.compile(r'Fraction\((\d+)\)').sub(r'\1', s)

def evaluate(nums, ops, template):
    fracs = ('Fraction(%s)' % n for n in nums)
    ops = iter(ops)
    expr = ''.join(next(fracs) if c == 'X' else
                   next(ops) if c == '@' else c
                   for c in template)
    try:
        return expr, eval(expr)
    except ZeroDivisionError:
        return expr, None        

def solve(spec, ops):
    numbers = re.compile(r'\d+').findall(spec)
    assert len(numbers) == N + 1
    result = Fraction(numbers.pop())
    seqs = its.product(its.permutations(numbers),
                       its.product(ops, repeat=N-1),
                       templates)
    print(defrac(next((e for e, v in its.starmap(evaluate, seqs)
                       if v == result),
                      'Impossible')))

def main():
    solve('2,5,6,6 => 17', '+-/*')
    solve('3,3,8,8 => 24', '+-/*')

main()

Here’s a second attempt, which doesn’t assume there will just be 4 numbers on the left hand side of the equation. Given a sequence of numbers and a set of operators, it repeatedly reduces the sequence length by picking pair of numbers and combining them using one of the operators, iterating over all possible ways of doing this. The first sequence of length 1 which equals the target value gives a solution and terminates the search.

# http://blog.plover.com/math/24-puzzle.html
from fractions import Fraction
import itertools as its
import operator
import re

def pick2(xs):
    return ((p[:2], p[2:]) for p in its.permutations(xs))

def allow(op, l, r):
    return op != '/' or eval(r) != 0

def apply(op, l, r):
    return '(%s%s%s)'%(l, op, r)

def values(xs, ops):
    L = [xs]
    while L:
        xs = L.pop()
        if len(xs) == 1:
            yield xs.pop()
        else:
            L.extend([apply(op, *lr)] + list(tl)
                     for op, (lr, tl) in its.product(ops, pick2(xs))
                     if allow(op, *lr))

def solve(spec, ops):
    numbers = ['Fraction(%s)'%n for n in re.compile(r'\d+').findall(spec)]
    target = eval(numbers.pop())
    print(next((v for v in values(numbers, ops) if eval(v) == target), 'Impossible'))

def main():
    solve('2,5,6,6 => 17', '+-/*')
    solve('3,3,8,8 => 24', '+-/*')

main()

Negative Sequence Indices in Python

tag@wordaligned.org (Thomas Guest) — 2016-08-01

Supply a negative index when accessing a sequence and Python counts back from the end. So, for example, my_list[-2] is the penultimate element of my_list, which is much better than my_list[len(my_list)-2] or even *(++my_list.rbegin()).

That final example uses one of C++’s reverse iterators. It gets the penultimate element of a collection by advancing an iterator from the reversed beginning of that collection. If you’re addicted to negative indices you can use them with C++ arrays, sort of.

Negative array indices in C++

#include <iostream>

int main()
{
    char const * domain = "wordaligned.org";
    char const * end = domain + strlen(domain);
    std::cout << end[-3] << end[-2] << end[-1] << '\n';
    return 0;
}

Compiling and running this program outputs the string “org”.

Going back to Python, the valid indices into a sequence of length L are -L, -L+1, … , 0, 1, … L-1. Whenever you write code to calculate an index used for accessing a sequence, and especially if you’re catching any resulting IndexErrors, it’s worth checking if the result of the calculation can be negative, and if — in this case — you really do want the from-the-back indexing behaviour.

…

W

O

R

D

A

L

I

G

N

E

D

…

-14

-13

-12

-11

-10

-9

-8

-7

-6

-5

-4

-3

-2

-1

The power of negative indices increases with slicing. Take a slice of a sequence by supplying begin and end indices.

>>> domain = 'wordaligned.org'
>>> domain[4:9]
'align'
>>> domain[4:-4]
'aligned'
>>> digits = list(range(10))
>>> digits
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> digits[3:4]
[3]
>>> digits[1:-1]
[1, 2, 3, 4, 5, 6, 7, 8]

Omitting an index defaults it to the end of the sequence. Omit both indices and both ends of the sequence are defaulted, giving a sliced copy.

>>> domain[-3:]
'org'
>>> domain[:4]
'word'
>>> digits[:]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

I prefer the list(digits) form for copying digits but you should certainly be familiar with the digits[:] version.

You can supply any indices as slice limits, even ones which wouldn’t be valid for item access. Imagine laying your sequence out on an indexed chopping board, slicing it at the specified points, then taking whatever lies between these points.

>>> digits[-1000000]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>> digits[1000000]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>> digits[-1000000:1000000]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Sequence slicing also takes a step parameter.

>>> digits[::2]
[0, 2, 4, 6, 8]
>>> digits[1::2]
[1, 3, 5, 7, 9]

This parameter too can be negative. The sign of the step affects which limiting values the begin and end slice parameters default to. It’s subtle behaviour, but you soon get used to it.

>>> digits[0:10:-2]
[]
>>> digits[::-2]
[9, 7, 5, 3, 1]
>>> digits[-2::-2]
[8, 6, 4, 2, 0]

How do you reverse a string? Slice it back to front!

>>> domain[::-1]
'gro.dengiladrow'

To recap: the default slice limits are the start and end of the sequence, 0 and -1, or -1 and 0 if the step is negative. The default step is 1 whichever way round the limits are. When slicing, s[i:j:k], i and j may take any integer value, and k can take any integer value except 0.

The zero value creates another interesting edge case. Here’s a function to return the last n items of a sequence.

>>> def tail(xs, n)
...     return xs[-n:]
...

It fails when n is 0.

>>> tail(digits, 3)
[7, 8, 9]
>>> tail(digits, 2)
[8, 9]
>>> tail(digits, 1)
[9]
>>> tail(digits, 0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

By the way, we’ve already seen slicing working well with lists and strings. It also works nicely with range objects.

>>> r = range(10)
>>> r[::2]
range(0, 10, 2)
>>> r[1::2]
range(1, 10, 2)

Python Streams vs Unix Pipes

tag@wordaligned.org (Thomas Guest) — 2016-07-28

I chanced upon an interesting puzzle:

Find the smallest number that can be expressed as the sum of 5, 17, 563, 641 consecutive prime numbers, and is itself a prime number.

Here, the prime numbers are an infinite steam:

2, 3, 5, 7, 11, 13 ...

and sums of N consecutive primes are similarly infinite. For example, the sum of 2 consecutive primes would be the stream:

2+3, 3+5, 5+7, 7+11, 11+13 ...

which is:

5, 8, 12, 18, 24 ...

and the sum of 3 consecutive primes is:

10 (=2+3+5), 15, 23, 31 ...

Had we been asked to find the smallest number which can be expressed as the sum of 3 consecutive primes and as the sum of 5 consecutive primes and is itself prime, the answer would be 83.

>>> 23 + 29 + 31
83
>>> 11 + 13 + 17 + 19 + 23
83

Infinite series and Python

My first thought was to tackle this puzzle using Python iterators and generators. Here’s the outline of a strategy:

starting with a stream of primes
tee the stream to create 4 additional copies
transform these copies into the consecutive sums of 5, 17, 563 and 641 primes
now merge these consecutive sums back with the original primes stream
group the elements of this merged stream by value
the first group which contains 5 elements must have occurred in every source, and is therefore a prime and representable as the consecutive sum of 5, 17, 563 and 641 primes
which solves the puzzle!

Note that when we copy an infinite stream we cannot consume it first. We will have to be lazy or we’ll get exhausted.

Courtesy of the Python Cookbook, I already had a couple of useful recipes to help implement this strategy:

def primes():
    '''Generate the sequence of prime numbers: 2, 3, 5 ... '''
    ....

def stream_merge(*ss):
    '''Merge a collection of sorted streams.

    Example: merge multiples of 2, 3, 5
    >>> from itertools import count, islice
    >>> def multiples(x): return (x * n for n in count(1))
    >>> s = stream_merge(multiples(2), multiples(3), multiples(5))
    >>> list(islice(s, 10))
    [2, 3, 4, 5, 6, 6, 8, 9, 10, 10]
    '''
    ....

Both these functions merit a closer look for the cunning use they make of standard containers, but we’ll defer this inspection until later. In passing, note that stream_merge()’s docstring suggests we might try using it as basis for primes():

form the series of composite (non-prime) numbers by merging the streams formed by multiples of prime numbers;
the primes remain when you remove these composites from the series of natural numbers.

This scheme is hardly original — it’s a variant of Eratosthenes’ sieve — but if you look carefully you’ll notice the self-reference. Unfortunately recursive definitions of infinite series don’t work well with Python 1, hence primes() requires a little more finesse. We’ll take a look at it later.

Moving on, to solve the original puzzle we need a consecutive sum filter. This will transform a stream of numbers into a stream of consecutive sums of these numbers:

def consecutive_sum(s, n):
    '''Generate the series of sums of n consecutive elements of s

    Example: 0, 1, 2, 3, 4 ... => 0+1, 1+2, 2+3, 3+4, ...
    >>> from itertools import count, islice
    >>> list(islice(consecutive_sum(count(), 2), 10))
    [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    '''
    lo, hi = itertools.tee(s)
    csum = sum(next(hi) for _ in range(n))
    while True:
        yield csum
        csum += next(hi) - next(lo)

Here we can think of the summed elements as lying within a sliding window: each time we slide the window an element gets added to the top and an element gets removed from the bottom, and we adjust csum accordingly.

So, now we have:

the series of prime numbers, primes()
a stream_merge() connector
a consecutive_sum() filter

The remaining stream adaptors come from the standard itertools module. Note that the stream_merge() works here since all the consecutive sum series are strictly increasing. Note also that the stream of prime numbers can be treated as consecutive_sum(s=primes(), n=1), handling the “and is itself a prime number” requirement.

>>> lens = 1, 5, 17, 563, 641
>>> N = len(lens)
>>> from itertools import tee, groupby
>>> ps = tee(primes(), N)
>>> csums = [consecutive_sum(p, n) for p, n in zip(ps, lens)]
>>> solns = (n for n, g in groupby(stream_merge(*csums)) 
             if len(list(g)) == N)

Here, solns is yet another stream, the result of merging the N input consecutive sum streams then filtering out the numbers which appear N times; that is, the numbers which can be expressed as sums of 1, 5, 17, 563 and 641 consecutive primes.

The first such number solves the original puzzle.

>>> next(solns)
7002221

Here’s a picture of how these stream tools link up to solve this particular puzzle. The great thing is that we can reconnect these same tools to solve a wide range of puzzles, and indeed more practical processing tasks. To use the common analogy, we direct data streams along pipes.

Infinite series in Other Languages

Python is the language I find most convenient most of the time, which explains why I reached for it first. It’s an increasingly popular language, which helps explain why I didn’t need to write the tricky parts of my solution from scratch: they’d already been done. Python is also a language which makes compromises. Having used Python to find a solution to the puzzle I wondered if there wasn’t some other language better suited to this kind of problem.

Haskell makes no compromises when it comes to functional programming. Its lazy evaluation and inductive recursion make it a perfect fit for this kind of puzzle — but my approach of teeing, filtering and merging made me consider the Unix Shell. Now, I use Bash every day and page through its manual at least once a week. Scripting appeals and I’m comfortable at the command line. How hard could it be to solve this puzzle using Bash? After all, I already knew the answer!

Partial sums.

Here’s a simple shell function to generate partial sums. I’ve used awk, a little language I gave up on a long time ago in favour of more rounded scripting languages like Perl and then Python. Now I look at it again, it seems to fill a useful gap. Awk processes a file sequentially, applying pattern-action rules to each line, a processing template which I’ve reinvented less cleanly many times. Despite my rediscovery of awk, I’ll be keeping its use strongly in check in what follows.

$ psum() { awk '{ print s += $1 }'; }

Much like Perl, awk guesses what you want to do. Here, it conjures the summation variable, s, into existence, assigning it a default initial value of 0. (Good guess!) Since we’re doing arithmetic awk converts the first field of each input line into a number. We can test psum by using jot to generate the sequence 1, 2, 3, 4, 5 (this is on a Mac — on a Linux platform use seq instead of jot).

$ jot 5 | psum
1
3
6
10
15

Consecutive sums

You may be wondering why we’ve bothered creating this partial sum filter since it’s the sums of consecutive elements we’re after, rather than the sum of the series so far. Well, notice that if P[i] and P[i+n] are two elements from the series of partial sums of S, then their difference, P[i+n] - P[i], is the sum of the n consecutive elements from S.

So to form an n-element consecutive sum series we can tee the partial sums streams, advance one of these by n, then zip through them in parallel finding their differences. An example makes things clear:

$ mkfifo pipe
$ jot 5 | psum | tee pipe | tail -n +2 | paste - pipe
3       1
6       3
10      6
15      10
        15

Here, jot 5 generates the sequence 1, 2, 3, 4, 5, which psum progressively accumulates to 1, 3, 6, 10, 15. We then tee this partial sum series through two pipes: the first, pipe, is an explicitly created named pipe created by mkfifo, the second is implicitly created by the pipeline operator, |. The remainder of the command line delays one series by one (note that tail numbers lines from 1, not 0, so tail -n +1 is the identity filter) then pastes the two series back together 2.

By appending a single awk action to the pipeline we get a consecutive sum series.

$ jot 5 | psum | tee pipe | tail -n +2 | paste - pipe | awk '{print $1 - $2}'
2
3
4
5
15

The output 2, 3, 4, 5 is the series of consecutive sums of length 1 taken from the original series 1, 2, 3, 4, 5. The trailing 15 and the 1 missed from the start are edge case problems, and easily corrected.

Accumulating an increasing series of numbers in order to find the differences between elements lying a given distance apart on this series isn’t a very smart idea on a computer with a fixed word-size, but it’s good to know (e.g.) that awk doesn’t stop counting at 32 bits.

$ let "N=1<<32" && echo $N | tee >(awk '{print $1 * $1}')
4294967296
18446744073709551616

Exactly if and when awk stops counting, I’m not sure. The documentation doesn’t say and I haven’t looked at the source code.

Bug Fixes

Let’s capture these tiny functions and name them. Here, then, are revised psum() and sdiff() filters. The edge case problems should now be fixed.

$ psum()  { awk 'BEGIN { print 0 }{print s += $1 }'; }
$ delay() { let "n = $1 + 1" && tail +$n; } 
$ sdiff() { mkfifo p.$1 && tee p.$1 | delay $1 | paste - p.$1 | \
            awk 'NF == 2 {print $1 - $2 }'; }

A quick test:

$ jot 5 | psum | sdiff 3
6
9
12

The output is, as expected, the series of sums of consecutive triples taken from 1, 2, 3, 4, 5 (6=1+2+3, 9=2+3+4, 12=3+4+5).

There’s a pernicious bug, though. These functions can’t handle infinite series so they are of limited use as pipeline tools. For example, if we stream in the series 0, 1, 2, … (generated here as the partial sums of the series 1, 1, 1, …) nothing gets output and we have to interrupt the process.

# This command appears to hang
$ yes 1 | psum | sdiff 1
^C

To work around this is, we can use Gnu stdbuf to prohibit tail and paste from using output buffers.

$ psum()  { awk 'BEGIN { print 0 }{print s += $1 }'; }
$ delay() { let "n = $1 + 1" && stdbuf -o 0 tail +$n; } 
$ sdiff() { mkfifo p.$1 && tee p.$1 | delay $1 | \
            stdbuf -o 0 paste - p.$1 | \
            awk 'NF == 2 {print $1 - $2 }'; }

Now the data flows again:

# Accumulate the stream 1 1 1 ...
# and print the difference between successive elements
$ yes 1 | psum | sdiff 1
1
1
1
1
^C

Merging Streams

The Unix shell merges streams rather more succinctly than Python. Sort -m does the job directly. Note that a standard sort cannot yield any output until all its inputs are exhausted, since the final input item might turn out to be the one which should appear first in the output. Merge sort, sort -m, can and does produce output without delay^[3].

$ yes | sort
^C
$ yes | sort -m
y
y
y
y
y
^C

Generating Primes

No doubt it’s possible to generate the infinite series of prime numbers using native Bash code, but I chose to reuse the Python Cookbook recipe for the job.

primes

#!/usr/bin/env python
import itertools

def primes():
    '''Generate the prime number series: 2, 3, 5 ... '''
    D = {}
    for n in itertools.count(2):
        p = D.pop(n, None)
        if p is None:
            yield n
            D[n * n] = n
        else:
            x = n + p
            while x in D:
                x += p
            D[x] = p

for p in primes():
    print(p)

This is a subtle little program which makes clever use of Python’s native hashed array container, the dictionary. In this case dictionary values are the primes less than n and the keys are composite multiples of these primes. The loop invariant, roughly speaking, is that the dictionary values are the primes less than n, and the corresponding keys are the lowest multiples of these primes greater than or equal to n. It’s a lazy, recursion-free take of Eratosthenes’ sieve.

For the purposes of this article the important things about this program are:

it generates an infinite series of numbers to standard output^[4], making it a good source for a shell pipeline
by making it executable and adding the usual shebang incantation, we can invoke this Python program seamlessly from the shell.

Pipe Connection

Recall the original puzzle:

Find the smallest number that can be expressed as the sum of 5, 17, 563, 641 consecutive prime numbers, and is itself a prime number.

First, let’s check the connections by solving a simpler problem which we can manually verify: to find prime numbers which are also the sum of 2 consecutive primes. As we noted before, this is the same as finding primes numbers which are the consecutive sums of 1 and 2 primes.

In one shell window we create a couple of named pipes, c.1 and c.2, which we’ll use to stream the consecutive sum series of 1 and 2 primes respectively. The results series comprises the duplicates when we merge these pipes.

Shell 1

$ mkfifo c.{1,2}
$ sort -mn c.{1,2} | uniq -d

In another shell window, stream data into c.1 and c.2:

Shell 2

$ for i in 1 2; do (primes | psum | sdiff $i > c.$i) & done

In the first window we see the single number 5, which is the first and only prime number equal to the sum of two consecutive primes.

Prime numbers equal to the sum of three consecutive primes are more interesting. In each shell window recall the previous commands and switch the 2s to 3s (a simple command history recall and edit, ^2^3^, does the trick). The merged output now looks like this:

$ sort -mn c.1 c.3 | uniq -d
23
31
41
...

We can check the first few values:

23 = 5 + 7 + 11
31 = 7 + 11 + 13
41 = 11 + 13 + 17

At this point we’re confident enough to give the actual puzzle a try. Start up the solutions stream.

$ mkfifo c.{1,5,17,563,641}
$ sort -mn c.{1,5,17,563,641} | uniq -c | grep "5 "

Here, we use a standard shell script set intersection recipe: uniq -c groups and counts repeated elements, and the grep pattern matches those numbers common to all five input streams.

Now we can kick off the processes which will feed into the consecutive sum streams, which sort is waiting on.

$ for i in 1 5 17 563 641; do (primes | psum | sdiff $i > c.$i) & done

Sure enough, after about 15 seconds elapsed time^[5], out pops the result:

$ sort -mn c.{1,5,17,563,641} | uniq -c | grep "5 "
    5 7002221

15 seconds seems an eternity for arithmetic on a modern computer (you could start up a word processor in less time!), and you might be inclined to blame the overhead of all those processes, files, large numbers, etc. In fact it took around 6 seconds for the Python program simply to generate prime numbers up to 7002221, and my pure Python solution ran in 9 seconds.

Portability

One of the most convenient things about Python is its portability. I don’t mean “portable so long as you conform to the language standard” or “portable if you stick to a subset of the language” — I mean that a Python program works whatever platform I use without me having to worry about it.

Non-portability put me off the Unix shell when I first encountered it: there seemed too many details, too many platform differences — which shell are you using? which extensions? which implementation of the core utilities, etc, etc? Readily available and well-written documentation didn’t help much here: generally I want the shell to just do what I mean, which is why I switched so happily to Perl when I discovered it.

Since then this situation has, for me, improved in many ways. Non-Unix platforms are declining as are the different flavours of Unix. Bash seems to have become the standard shell of choice and Cygwin gets better all the time. GNU coreutils predominate. As a consequence I’ve forgotten almost all the Perl I ever knew and am actively rediscovering the Unix shell.

Writing this article, though, I was reminded of the platform dependent behaviour which used to discourage me. On a Linux platform close to hand I had to use seq instead of jot, and awk formatted large integers in a scientific form with a loss of precision.

Loss of precision

$ echo '10000000001 0' | awk '{print $1 - $2}'
1e+10

On OS X the same command outputs 10000000001. I couldn’t tell you which implementation is more correct. The fix is to explicitly format these numbers as decimal integers, but the danger is that the shell silently swallows these discrepancies and you’ve got a portability problem you don’t even notice.

Precision recovered

$ echo '10000000001 0' | awk '{printf "%d\n", $1 - $2}'
10000000001

Stream Merge

I mentioned stream_merge() at the start of this article, a general purpose function written by Raymond Hettinger which I originally found in the Python Cookbook. As with the prime number generator, you might imagine the merge algorithm to be recursively defined:

to merge a pair of streams, take items from the first which are less than the head of the second, then swap;
to merge N streams, merge the first stream with the merged (N-1) rest.

Again the Python solution does it differently, this time using a heap as a priority queue of items from the input streams. It’s ingenious and efficient. Look how easy it is in Python to shunt functions and pairs in and out of queues.

from heapq import heapify, heappop, heapreplace

def stream_merge(*ss):
    '''Merge a collection of sorted streams.'''
    pqueue = []
    for i in map(iter, ss):
        try:
            pqueue.append((i.next(), i.next))
        except StopIteration:
            pass
    heapify(pqueue)
    while pqueue:
        val, it = pqueue[0]
        yield val
        try:
            heapreplace(pqueue, (it(), it))
        except StopIteration:
            heappop(pqueue)

A more sophisticated version of this code has made it into the Python standard library, where it goes by the name of heapq.merge (I wonder why it wasn’t filed in itertools?)

Alternative Solutions

As usual Haskell wins the elegance award, so I’ll quote in full a solution built without resorting to cookbookery which produces the (correct!) answer in 20 seconds.

module Main where

import List

isPrime x = all (\i -> 0/=x`mod`i) $ takeWhile (\i -> i*i <= x) primes

primes = 2:filter (\x -> isPrime x) [3..]

cplist n = map (sum . take n) (tails primes)

meet (x:xs) (y:ys) | x < y = meet xs (y:ys)
                   | y < x = meet (x:xs) ys
                   | x == y =  x:meet xs ys

main = print $ head $ \
(primes `meet` cplist 5) `meet` (cplist 17 `meet` cplist 563) `meet` cplist 641

1 CPython, more precisely — I don’t think anything in the Python language itself prohibits tail recursion. Even using CPython, yet another recipe from the online Python Cookbook explores the idea of an @tail_recursion decorator.

2 Tail is more commonly used to yield a fixed number of lines from the end of the file: by prefixing the line count argument with a + sign, it skips lines from the head of the file. The GNU version of head can similarly be used with a - prefix to skip lines at the tail of a file. The notation is {compact,powerful,subtle,implementation dependent}.

[3] Sort -m is a sort which doesn’t really sort — its inputs should already be sorted — rather like the +n option turning tail on its head.

[4] The series is infinite in theory only: at time n the number of items in the has_prime_factors dictionary equals the number of primes less than n, and each key in this dictionary is larger than n. So resource use increases steadily as n increases.

[5] I used a MacBook laptop used to run these scripts.

  Model Name:               MacBook
  Model Identifier:         MacBook1,1
  Processor Name:           Intel Core Duo
  Processor Speed:          2 GHz
  Number Of Processors:     1
  Total Number Of Cores:    2
  L2 Cache (per processor): 2 MB
  Memory:                   2 GB
  Bus Speed:                667 MHz

8 Queens Puzzle

tag@wordaligned.org (Thomas Guest) — 2016-04-04

♛♛♛♛♛♛♛♛

Here’s one of my favourite recipes, by Raymond Hettinger, lightly adapted for Python 3.

from itertools import permutations

n = width_of_chessboard = 8
sqs = range(n)

Qs = (Q for Q in permutations(sqs)
      if n == len({Q[i]+i for i in sqs})
           == len({Q[i]-i for i in sqs}))

We start by assigning sqs to the range 0 through 7.

>>> sqs = range(8)
>>> list(sqs)
[0, 1, 2, 3, 4, 5, 6, 7]

The range has 8 indices. If each index represents a column on a standard 8x8 chessboard and the value at that index represents a row on the same chessboard, then our range represents 8 positions on the board. Using the built-in enumerate function to generate these (index, value) pairs we see that sqs encodes the diagonal (0, 0) to (7, 7):

>>> list(enumerate(sqs))
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7)]

Next, permute the values — the rows.

>>> from itertools import permutations
>>> rooks = permutations(sqs)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 6, 7)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 7, 6)
>>> next(rooks)
(0, 1, 2, 3, 4, 6, 5, 7)
>>> list(rooks)[34567]
(6, 7, 0, 1, 3, 4, 5, 2)

Itertools.permutations generates values lazily. The snippet above shows the first two results, then skips forward 34568 places. Permutations(sqs) generates all possible arrangements of 8 pieces on a chessboard such that each row has exactly one piece on it and so does each column. That is, it generates all possible ways of placing 8 rooks on a chessboard so that no pair attacks each other.

In the final program, we filter these rook positions to generate solutions to the more challenging — and more interesting — eight Queens puzzle.

Consider our starting point, the diagonal (0, 0) to (7, 7)

>>> diagonal = range(8)
>>> {r-c for c,r in enumerate(diagonal)}
{0}
>>> {r+c for c,r in enumerate(diagonal)}
{0, 2, 4, 6, 8, 10, 12, 14}

Here, a set comprehension collects the distinct values taken by the difference between the row and column along this diagonal, which in this case gives {0}. That is, if we placed 8 bishops along this ↗ diagonal they would all attack each other along this diagonal. The sum of the row and column takes 8 distinct values, however, meaning no pair attacks along a ↖ diagonal.

Comparison operators chain in Python, so the expression:

n == len({Q[i]+i for i in sqs}) == len({Q[i]-i for i in sqs})

is True if both sets have 8 elements, that is, if the squares in Q are on distinct ↖ and ↗ diagonals; or, equivalently no pair of bishops placed on the squares in Q would attack each other. Since we already know Q positions 8 rooks so that no pair attacks each other, and a chess Queen combines the moves of a rook and a bishop, we can see that Qs generates every possible way of placing 8 Queens on a chessboard so that no pair attacks each other: which is to say, we’ve solved the 8 Queens puzzle.

Qs = (Q for Q in permutations(sqs)
      if n == len({Q[i]+i for i in sqs})
           == len({Q[i]-i for i in sqs}))

This is beautiful code and there’s one final twist.

Qs is a generator expression primed to permute squares into neighbourly rooks filtered by amicable bishops yielding unthreatening Queens. Until asked, however, it does nothing.

♕♕♕♕♕♕♕♕

Easy as Py

tag@wordaligned.org (Thomas Guest) — 2016-03-23

What makes Python Simple?

I consider Python a simple language. Here’s why.

Easy to Read

I can read and understand Python code (unless it’s wilfully perverse). Syntactic whitespace and the associated removal of punctuation results in a regular, open layout. The combination of built in containers, extensive standard libraries and high level constructs allow for clear, compact code: code which fits in your head.

Easy to Write

I can write Python code which is free of syntax errors and which does what I want. Of course it helps that I’ve been actively using the language for 15 years, but I’ve been using C++ for longer and still make mistakes with it: ask me to declare a pointer to a member function, for example, or to knock up a variadic template function, and I’ll need a moment or two.

Transparent

I also consider C a simple language. C offers a transparent abstraction of a register machine, with a stack, a heap, and addressable memory. If you can imagine the operation of such a machine, you can figure out C. Python is less transparent but reveals its workings if pressed. Dicts form a part of the language seen by users, and under the hood they provide the dynamic context which supports a running program. The read-eval-print loop makes it easy to poke and reshape your program. You can disassemble code to see what the virtual machine sees.

Consistent improvement

The language has got better since I first started using it. It has also got bigger, and this growth would, at first, seem at odds with simplicity. However, consider — as an example — the point when list comprehensions were introduced. Language support for building a list from an iterable results in compact declarative code. Simple code. What’s more, the square brackets which now delimit list comprehensions are the same square brackets that were previously used to delimit lists. The syntax may have been new but it didn’t surprise. Now consider the introduction of set and dict comprehensions, which follow logically and naturally from list comprehensions, almost as if they were discovered rather than invented.

There are many other examples where additions to the language have unified and simplified.

Vision

I’m not a Python insider and cannot comment on the exact balance of benevolence and dictatorship which goes into the language enhancement process. I would say Python doesn’t suffer from being designed by a committee. It sticks to its strengths and its direction, to its vision.

Sausages, sausages, sausages - slice, slice, slice

tag@wordaligned.org (Thomas Guest) — 2016-03-21

A friend asked for help reaching the next level of a puzzle game. The test which stalled her involves machine placement in a sausage factory.

… each sausage was branded with a letter for quality control purposes, thus: ypbtkizfgxptclcoirdsuhjwulqkoszrabfc

The string was then drawn through seven machines which rearranged the sausages in flavour enhancing ways.

Machine A: The Reversifier

Reverses the order of the sausages, so they get tastier as you go along.

…

Machine G: Secondhalffirstifier

move the second half of the string to the beginning, as the earlier sausages are too spicy to eat early in the morning.

He attached these machines in a certain sequence, though one of them was out for repair so only six were used. He then fed a string of sausages through and was surprised to discover the string that came out at the other end said lickyourlips. What order were the machines in?

It’s nicely phrased, but what’s really wanted is the sequence of simple transformations that takes input “ypbtkizfgxptclcoirdsuhjwulqkoszrabfc” and produces output “lickyourlips”.

It’s no doubt possible to work backwards and figure out a solution using no more than logic, pencil and paper. For example, only two of the machines change the length of the string, and — looking at the before and after lengths — these must both be used. It’s rather easier to write a short program to find a solution.

First we must simulate the seven sausage machines, A-G, which perform the following sequence operations.

reverse the order of a sequence
remove every other element of a sequence
remove every third element of a sequence
pairwise reverse elements of a sequence
move even numbered elements to the front of a sequence
move the last element of a sequence to the front
swap the front and back half of a sequence

None of these is difficult, especially in a high-level language which builds in support for sequence operations. What I found noteworthy is that a solution can be found without any loops or if statements. What’s more, every operation can handled using nothing more than slice operations.

Here’s my solution. The machines consist of slice operations, helped by a couple of conditional expressions and recursive calls. The solution can then be brute-forced: there are only 5040 ways of permuting 6 out of 7 machines.

I’ve used reduce to apply a chain of functions to a string of sausages — an explicit loop might be clearer, but I want a loop-free solution. For this same reason I use recursion in the pairwise swapper and the element dropper. Generally in Python, recursion is a poor choice. In this case I know I’m starting with a string of just 36 elements which cannot get any longer; there’s no risk of exceeding the system recursion limit.

The sequence reversal s[::-1] is idiomatic but alarming to the uninitiated. Slices have [start:stop:stride] fields, any of which may be defaulted. Usually start and stop default to the start and end of the sequence, but in this case the negative stride reverses them.

To rotate the last element of a sequence to the front, prefer:

return s[-1:] + s[:-1]

to:

return [s[-1]] + s[:-1]

because the latter raises an IndexError for an empty sequence.

Slicing is a formidable tool for sequence manipulation, especially when combined with the option of using negative indices to count back from the end. Slices allow you to reverse, rotate and partition sequences, to pairwise swap elements, and to drop every nth element.

The miniature recipes presented here don’t even use slice assignment, which gives me an excuse to reproduce this elegant prime sieve function, which does.

Sledgehammers vs Nut Crackers

tag@wordaligned.org (Thomas Guest) — 2016-02-23

Awk

I get awk and can read awk programs but find the language of little use. Its focus is narrow and its syntax can be surprising. Python matches it at home and smashes it away. Nonetheless, a number of the advent of code puzzles fit the awk processing model — line based instructions, the interpretation of which builds state contributing to the final result — and I enjoyed writing awk solutions. There’s satisfaction in using a tool which is up to the job, no more and no less: in using a nutcracker, rather than a sledgehammer, to crack a nut.

Puzzle

For example, the puzzle set on day 6 consists of a list of instructions for switching and toggling a 1000 x 1000 grid of lights. The instructions read:

turn on 296,50 through 729,664
turn on 212,957 through 490,987
toggle 171,31 through 688,88
turn off 991,989 through 994,998
....

and the question is, after following these instructions, how many lights are lit?

Each instruction is a single line; the actions — turn on, turn off, toggle — can be matched by patterns; and to follow these actions requires no more than an array and arithmetic: awk fits nicely.

Code

Comments

Here, the BEGIN action sets the field separator FS to the regular expression [ ,] which picks out the textual and numeric fields from each instruction. Awk is highly dynamic: use a variable as a number and it becomes a number, in this case the coordinates of a lighting grid; and similarly, the fields “on”, “off” and “toggle” are matched and treated as strings.

The grid of lights appears to be represented as a two dimensional array, accessed lights[x,y] rather than lights[x][y]. In fact, the array — like all arrays in awk — is an associative container, which maps from strings — not numbers — to values. The key x,y becomes a string which joins the values of x and y with a separator defaulted to "\034".

Niggles

The escape character at the end of line 5 is needed to continue the long line. I’d prefer to use parentheses to wrap the expression over more than one line, as I would in Python, but this trick doesn’t seem to work. I was somewhat surprised there was no built in sum() function to count up the number of lights turned on by the END. It would have been cute to pass on(), off() and toggle() as functions into switch(), separating traversal from action, but I couldn’t find a way to do this in awk.

My awk script solved the puzzle in 45 seconds. A Python solution took 17 seconds. I didn’t try optimising either.

Don’t use a sledgehammer to crack a nut!

This advice, commonly given to programmers, demands explanation. If it’s intended to imply a sledgehammer is more likely to pulverise the nut than open it, then fine, that’s true — but the analogy fails in this case: a solution written in Python would have been equally correct.

Alternatively, if we mean you shouldn’t use a powerful language when a less powerful one would do, then the question becomes: why not? Python is a general purpose programming language. It can crack nuts, peel bananas, serve web pages and so much more. If you know Python why bother with Awk?

At the outset of this post I admitted I don’t generally bother with awk. Sometimes, though, I encounter the language and need to read and possibly adapt an existing script. So that’s one reason to bother. Another reason is that it’s elegant and compact. Studying its operation and motivation may help us compose and factor our own programs — programs far more substantial than the scripts presented here, and in which there will surely be places for mini-languages of our own.