Popular recipes by Sander Evers

String templates with adaptive indenting (Python)

2014-02-19T12:53:03-08:00

Python recipe 578835 by Sander Evers (formatter, indent, templating).

An extension of Python's 'Hello {fieldname}!'.format(fieldname='world') functionality for multi-line strings. When {fieldname} is indented, all the lines in the inserted fieldvalue are indented to the same amount.

Finding sets in the card game SET! (Python)

2013-04-05T12:49:36-07:00

Python recipe 578508 by Sander Evers (algorithm, optimization, search, setgame). Revision 2.

In the card game SET!, players are shown an array of 12 (or more) symbol cards and try to identify a so-called 3-card set among these cards as quickly as possible.

A card has four attributes (number, shape, color and shading), each of which can take 3 possible values. In a set, for each attribute, all three cards should have either the same value, or the three different values.

This recipe solves the problem of finding all sets within an array of an arbitrary number of cards, showing some clever optimizations and celebrating the clarity of Python in expressing the algorithms.

Hash collision probability / Birthday problem (Python)

2012-12-21T09:32:54-08:00

Python recipe 578387 by Sander Evers (birthday, collision, hash).

Calculates the probability that, when making k random selections out of n possibilities, at least two of the selections are the same. See: http://en.wikipedia.org/wiki/Birthday_problem

What is the probability that (at least) two people in a class of 30 share their birthday?

>>> collide(30,365)
0.7063162427192688

What is the probability that ORA_HASH generates the same hash when hashing 25000 values?

>>> collide(25000,int(4.3e9))
0.07009388771353198

Sharing-aware tree transformations (Python)

2012-05-07T08:20:58-07:00

Python recipe 578117 by Sander Evers (fold, reduce, sharing, tree, yaml). Revision 2.

The function foldsh in this recipe is a general purpose tool for transforming tree-like recursive data structures while keeping track of shared subtrees.

# By default, a branch is encoded as a list of subtrees; each subtree can be a
# branch or a leaf (=anything non-iterable). Subtrees can be shared:
>>> subtree = [42,44]
>>> tree = [subtree,[subtree]]
# We can apply a function to all leaves:
>>> foldsh(tree, leaf= lambda x: x+1)
[[43, 45], [[43, 45]]]
# Or apply a function to the branches:
>>> foldsh(tree, branch= lambda t,c: list(reversed(c)))
[[[44, 42]], [44, 42]]
# The sharing is preserved:
>>> _[0][0] is _[1]
True
# Summing up the leaves without double counting of shared subtrees:
>>> foldsh(tree, branch= lambda t,c: sum(c), shared= lambda x: 0)
86

In particular, it is useful for transforming YAML documents. An example of this is given below.

Cycle-aware tree transformations (Python)

2012-06-20T08:09:13-07:00

Python recipe 578118 by Sander Evers (cyclic, fold, reduce, yaml).

A variation on Recipe 578117 that can deal with cycles. A cycle means that a tree has itself as a subtree somewhere. A fold over such a data structure has a chicken-and-egg-problem: it needs its own result in order to construct its own result. To solve this problem, we let branch construct a part of its result before going into recursion. After the recursion, branch gets a chance to complete its result using its children's results. Python's support for coroutines (using yield) provides a nice way to define such a two-stage branch function.

Nest a flat list (Python)

2010-02-25T03:50:09-08:00

Python recipe 577061 by Sander Evers (list, nest, nested, unflatten). Revision 2.

Turn a flat list into a nested list, with a specified number of lists per nesting level.