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 ..read more

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 ..read more

Recently I attended a demonstration of a product intended to help design software, right down to implementation details. It failed to convince me. It did, however, succeed in reminding me of this short work by Jorge Luis Borges: On Exactitude in Science Jorge Luis Borges, Collected Fictions, translated by Andrew Hurley. …In that Empire, the Art of Cartography attained such Perfection that the map of a single Province occupied the entirety of a City, and the map of the Empire, the entirety of a Province. In time, those Unconscionable Maps no longer satisfied, and the Cartographers Guilds struck ..read more

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. Th ..read more

Jurassic Jigsaw My thanks to Eric Wastl for another excellent Advent of Code. I’ve now worked through all 25 puzzles, some simple, some tough, some familiar, some new; all beautifully set and highly enjoyable. Day 20, Jurrasic Jigsaw, took me longest by far to complete. The puzzle is easy to understand. You have to assemble jigsaw pieces into a seascape. For part one, you need to find the corner pieces. For part two, you must locate monsters in the seascape. Here, a jigsaw piece is a monochrome square, represented like so ..read more

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 ..read more

Anyone able to help make sense of this bizarre tweet which appeared on my timeline? The challenge is to decipher the message — Thomas Guest (@thomasguest) June 8, 2019 Please answer using the same style so others can find their own solution. Bonus points for both quality and quantity ..read more

A colleague of mine shares my love of puzzles. Whilst I like solving them, he also likes to design and build them. What I hadn’t realised is that there’s a community of puzzlers out there, who hold conventions, share designs, and generally celebrate and advance the art of puzzling. Dr G — my colleague — is part of that community and also owns a 3D printer. He works from home but whenever he visits the office there’ll be a freshly-printed puzzle for us to play with. I feel as excited as a young hobbit when Gandalf visits the Shire. The best puzzles have just a few simple pieces. You can see how ..read more

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 seq ..read more

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 ..read more