Last Updated: Sun Feb 21 18:03:46 GMT 2021
enigma.py is a library of functions useful for solving New Scientist Enigma puzzles in Python.
It is used in many of my programs on the Enigmatic Code site.
You can download the latest version here:
Once downloaded the module can perform update checks itself, see the documentation for the -u command line flag for details.The code is also available on GitHub.
To install the library you just need to place the enigma.py file in a directory where Python will find it. You can put it in the same directory as the program that uses it, or install it in a directory on your $PYTHONPATH for more general use.
NAME enigma - A collection of useful code for solving New Scientist Enigma (and similar) puzzles. DESCRIPTION The latest version is available at <http://www.magwag.plus.com/jim/enigma.html>. Currently this module provides the following functions and classes: arg - extract an argument from the command line args - extract a list of arguments from the command line base2int - convert a string in the specified base to an integer base_digits - get/set digits used in numerical base conversion bit_permutations - generate bit permutations C - combinatorial function (nCk) cached - decorator for caching functions cbrt - the (real) cube root of a number chain - see: flatten() choose - choose a sequence of values satisfying some functions chunk - go through an iterable in chunks clock - clock arithmetic variant on mod() collect - collect items according to accept/reject criteria compare - comparator function concat - concatenate a list of values into a string coprime_pairs - generate coprime pairs cslice - cumulative slices of an array csum - cumulative sum diff - sequence difference digit_map - create a map of digits to corresponding integer values digrt - the digital root of a number divc - ceiling division divf - floor division div - exact division divisor - generate the divisors of a number divisor_pairs - generate pairs of divisors of a number divisors - the divisors of a number divisors_pairs - generate pairs of divisors of a number drop_factors - reduce a number by removing factors dsum - digit sum of a number egcd - extended gcd express - express an amount using specific denominations factor - the prime factorisation of a number factorial - factorial function farey - generate Farey sequences of coprime pairs fib - generate fibonacci sequences filter2 - partition an iterator into values that satisfy a predicate, and those that do not filter_unique - partition an iterator into values that are unique, and those that are not find, rfind - find the index of an object in a sequence find_max - find the maximum value of a function find_min - find the minimum value of a function find_value - find where a function has a specified value find_zero - find where a function is zero first - return items from the start of an iterator flatten - flatten a list of lists flattened - fully flatten a nested structure format_recurring - output the result from recurring() fraction - convert numerator / denominator to lowest terms gcd - greatest common divisor grid_adjacency - adjacency matrix for an n x m grid group - collect values of a sequences into groups hypot - calculate hypotenuse icount - count the number of elements of an iterator that satisfy a predicate int2base - convert an integer to a string in the specified base int2roman - convert an integer to a Roman Numeral int2words - convert an integer to equivalent English words intc - ceiling conversion of float to int intf - floor conversion of float to int invmod - multiplicative inverse of n modulo m ipartitions - partition a sequence with repeated values by index irange - inclusive range iterator irangef - inclusive range iterator with fractional steps iroot - integer kth root function is_cube - check a number is a perfect cube is_distinct - check a value is distinct from other values is_duplicate - check to see if value (as a string) contains duplicate characters is_pairwise_distinct - check all arguments are distinct is_palindrome - check a sequence is palindromic is_power - check if n = i^k for some integer i is_power_of - check if n = k^i for some integer i is_prime - simple prime test is_prime_mr - Miller-Rabin fast prime test is_roman - check a Roman Numeral is valid is_square - check a number is a perfect square is_triangular - check a number is a triangular number isqrt - intf(sqrt(x)) join - concatenate strings lcm - lowest common multiple M - multichoose function (nMk) map2str - format a map for output mgcd - multiple gcd mod - return a function to find residues modulo m multiply - the product of numbers in a sequence nconcat - concatenate single digits into an integer nreverse - reverse the digits in an integer nsplit - split an integer into single digits number - create an integer from a string ignoring non-digits P - permutations function (nPk) partitions - partition a sequence of distinct values into tuples peek - return an element of a container pi - float approximation to pi poly_* - routines manipulating polynomials, wrapped as Polynomial powers - generate a range of powers prime_factor - generate terms in the prime factorisation of a number printf - print with interpolated variables pythagorean_triples - generate Pythagorean triples quadratic - determine roots of a quadratic equation reciprocals - generate reciprocals that sum to a given fraction recurring - decimal representation of fractions repeat - repeatedly apply a function to a value repdigit - number consisting of repeated digits roman2int - convert a Roman Numeral to an integer split - split a value into characters sprintf - interpolate variables into a string sqrt - the (positive) square root of a number subseqs - sub-sequences of an iterable subsets - generate subsequences of an iterator substitute - substitute symbols for digits in text substituted_expression - a substituted expression (alphametic/cryptarithm) solver substituted_sum - a solver for substituted sums T, tri - T(n) is the nth triangular number tau - tau(n) is the number of divisors of n timed - decorator for timing functions timer - a Timer object trirt - the (positive) triangular root of a number tuples - generate overlapping tuples from a sequence uniq - unique elements of an iterator unpack - return a function that unpacks its arguments update - return an updated copy of an object Accumulator - a class for accumulating values CrossFigure - a class for solving cross figure puzzles Delay - a class for the delayed evaluation of a function Denominations - express amounts using specified denominations DominoGrid - a class for solving domino grid puzzles Football - a class for solving football league table puzzles MagicSquare - a class for solving magic squares multiset - a class for manipulating multisets Polynomial - a class for manipulating polynomials Primes - a class for creating prime sieves Rational - select an implementation for rational numbers SubstitutedDivision - a class for solving substituted long division sums SubstitutedExpression - a class for solving general substituted expression (alphametic/cryptarithm) problems SubstitutedSum - a class for solving substituted addition sums Timer - a class for measuring elapsed timings COMMAND LINE USAGE enigma.py has the following command-line usage: python enigma.py The reports the current version of the enigma.py module, and the current python version: % python enigma.py [enigma.py version 2021-02-21 (Python 2.7.18)] % python3 enigma.py [enigma.py version 2021-02-21 (Python 3.9.2)] python enigma.py -t[v] This will use the doctest module to run the example code given in the documentation strings. If -t is specified there should be no further output from the tests, unless one of them fails. If there are test failures on your platform, please let me know (along with information on the platform you are using and the versions of Python and enigma.py), and I'll try to fix the code (or the test) to work on your platform. If -tv is specified then more verbose information about the status of the tests will be provided. python enigma.py -u[cdr] The enigma.py module can be used to check for updates. Running with the -u flag will check if there is a new version of the module available (requires a functioning internet connection), and if there is it will download it. If the module can be updated you will see something like this: % python enigma.py -ur [enigma.py version 2013-09-10 (Python 2.7.18)] checking for updates... latest version is 2021-02-21 downloading latest version to "2021-02-21-enigma.py" ........ download complete checksum verified renaming "2021-02-21-enigma.py" to "enigma.py" Note that the updated version is downloaded to a file named "<version>-enigma.py" in the current directory. You can then upgrade by renaming this file to "enigma.py" (this will happen automatically if the 'r' flag is passed). If you are running the latest version you will see something like this: % python enigma.py -u [enigma.py version 2021-02-21 (Python 2.7.18)] checking for updates... latest version is 2021-02-21 enigma.py is up to date If -uc is specified then the module will only check if an update is available, it won't download it. If -ud is specified then the latest version will always be downloaded. python enigma.py -h Provides a quick summary of the command line usage: % python enigma.py -h [enigma.py version 2021-02-21 (Python 2.7.18)] command line arguments: <class> <args> = run command_line(<args>) method on class [-r | --run] <file> [<additional-args>] = run the solver and args specified in <file> -t[v] = run tests [v = verbose] -u[cdr] = check for updates [c = only check, d = always download, r = rename] -h = this help Solvers that support the command_line() class method can be invoked directly from the command line like this: python enigma.py <class> <args> ... Supported solvers are: SubstitutedSum SubstitutedDivision SubstitutedExpression For example, Enigma 327 can be solved using: % python enigma.py SubstitutedSum "KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE" (KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE) (1912803 + 2428850 + 4312835 = 8654488) / A=4 B=9 D=3 E=8 G=2 K=1 Q=0 X=6 Y=5 Enigma 440 can be solved using: % python enigma.py SubstitutedDivision "????? / ?x = ??x" "??? - ?? = ?" "" "??? - ??x = 0" ????? / ?x = ??x (rem 0) [??? - ?? = ?, None, ??? - ??x = 0] 10176 / 96 = 106 (rem 0) [101 - 96 = 5, None, 576 - 576 = 0] / x=6 [1 solution] Enigma 1530 can be solved using: % python enigma.py SubstitutedExpression "TOM * 13 = DALEY" (TOM * 13 == DALEY) (796 * 13 == 10348) / A=0 D=1 E=4 L=3 M=6 O=9 T=7 Y=8 [1 solution] Alternatively the arguments to enigma.py can be placed in a text file and then executed with the --run / -r command, for example: % python enigma.py --run enigma327.run (KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE) (1912803 + 2428850 + 4312835 = 8654488) / A=4 B=9 D=3 E=8 G=2 K=1 Q=0 X=6 Y=5 CLASSES __builtin__.dict(__builtin__.object) multiset __builtin__.list(__builtin__.object) Polynomial __builtin__.object Accumulator CrossFigure Delay Denominations DominoGrid Football MagicSquare MultiAccumulator Record Slots SubstitutedExpression SubstitutedDivision SubstitutedSum Timer namespace __builtin__.tuple(__builtin__.object) Filter2 FilterUnique SubstitutedDivisionSolution exceptions.Exception(exceptions.BaseException) Impossible Solved class Accumulator(__builtin__.object) | A value accumulator. | | >>> a = Accumulator(fn=max) | >>> for x in (6, 5, 4, 7, 3, 1): a.accumulate(x) | >>> a.value | 7 | >>> a = Accumulator() | >>> for x in irange(1, 9): a.accumulate(x) | >>> a.value | 45 | >>> fdiv(a.value, a.count) | 5.0 | | Methods defined here: | | __init__(self, fn=<built-in function add>, fn1=<function identity>, value=None, data=None, collect=0, count=0) | create an Accumulator. | | The accumulation function and initial value can be specified. | | __repr__(self) | | accumulate(self, v=1) | Accumulate a value. | | If the current value is None then this value replaces the current value. | Otherwise it is combined with the current value using the accumulation | function which is called as fn(<current-value>, v). | | accumulate_data(self, v, data, target=None) | Accumulate a value, and check the accumulated value against a target value, | and if it matches record the data parameter. | | You can use this to record data where some function of the data is at an | extremum value. | | If the 'collect' parameter was set during initialisation, then all | values that hit current target are recorded in a list. Otherwise | only the most recent value is recorded. | | accumulate_data_from(self, s, value=0, data=1) | Accumulate values and data from iterable object <s>. | | <value>, <data> can be an index into elements from <s> | or a function to extract the appropriate value from an element. | | accumulate_from(self, s) | Accumulate values from iterable object <s>. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class CrossFigure(__builtin__.object) | A solver for simple cross-figure puzzles. | | As an example this is a simplified solution of Enigma 1755: | <http://enigmaticcode.wordpress.com/2013/06/26/enigma-1755-sudoprime-ii/#comment-2515> | | Consider the grid: | | A # # # B | C D # E F | # G H J # | K L # M N | P # # # Q | | The are 15 solution cells they are indexed 0 to 14, but we label them | as above to make things easier: | | >>> (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = irange(0, 14) | | Create the puzzle, the numbers A and G are already filled out: | | >>> p = CrossFigure('7?????3????????') | | The 2-digit answers are primes (for readability I've reduced the list of primes): | | >>> ans2 = [(A, C), (K, P), (B, F), (N, Q), (C, D), (E, F), (K, L), (M, N)] | >>> primes2 = [19, 31, 37, 41, 43, 47, 61, 67, 71, 73, 79] | >>> p.set_answer(ans2, primes2) | | The 3-digit answers are also primes (again this is a reduced list): | | >>> ans3 = [(D, G, L), (G, H, J), (E, J, M)] | >>> primes3 = [137, 139, 163, 167, 173, 307, 317, 367, 379, 397, 631, 673, 691] | >>> p.set_answer(ans3, primes3) | | No digit is repeated in a row, column or diagonal: | | >>> rows = [(A, B), (C, D, E, F), (G, H, J), (K, L, M, N), (P, Q)] | >>> cols = [(A, C, K, P), (D, G, L), (E, J, M), (B, F, N, Q)] | >>> diags = [(A, D, H, M, Q), (B, E, H, L, P)] | >>> p.set_distinct(rows + cols + diags) | | And the final check is that no even digit is repeated: | | >>> p.set_check(lambda grid: not any(grid.count(d) > 1 for d in '02468')) | | Now run the solver, which iterates over the solutions: | | >>> list(p.solve()) | [['7', '3', '3', '1', '6', '7', '3', '0', '7', '4', '7', '3', '1', '1', '9']] | | Note that the solution in the grid are returned as strings. | | Methods defined here: | | __init__(self, grid) | | get_answers(self, grid) | # return all answers in the grid (as strings) | | match(self, t, ns) | | set_answer(self, answers, candidates) | # set answers and their candidate solutions | | set_check(self, fn) | # set final check for a solution | | set_distinct(self, groups) | # set groups of distinct digits | | solve(self, grid=None, seen=None) | # the solver | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Delay(__builtin__.object) | # delayed evaluation (see also lazypy) | | Methods defined here: | | __getattr__(self, key) | | __init__(self, fn, *args, **kw) | create a delayed evaluation promise for fn(*args, **kw). | | Note that if you want the arguments themselves to be lazily evaluated | you will need to use: | | Delay(lambda: fn(expr1, expr2, opt1=expr3, opt2=expr4)) | | rather than: | | Delay(fn, expr1, expr2, opt1=expr3, opt2=expr4) | | example: | | x = Delay(expensive, 1) | x.evaluated --> False | x.value --> returns expensive(1) | x.evaluated --> True | x.value --> returns expensive(1) again, without re-evaluating it | x.reset() | x.evaluated --> False | x.value --> returns expensive(1), but re-evaluates it | | __repr__(self) | | evaluate(self) | | reset(self) | | ---------------------------------------------------------------------- | Class methods defined here: | | iter(self, *args) from __builtin__.type | create an iterator that takes a sequence of Delay() objects (or | callable objects with no arguments) and evaluates and returns each | one as next() is called. | | i = Delay.iter(Delay(expensive, 1), Delay(expensive, 2), Delay(expensive, 3)) | next(i) --> evaluates and returns expensive(1) | next(i) --> evaluates and returns expensive(2) | next(i) --> evaluates and returns expensive(3) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | immediate = 0 class Denominations(__builtin__.object) | An implementation of the Boecker-Liptak Money Changing algorithm. | | The denominations passed in are sorted into increasing order, and | accessible via the 'denominations' attribute. | | Quantities returned by 'express()' are in the same order as the | 'denominations' attribute. | | >>> sorted(Denominations(3, 5, 7).express(20)) | [(0, 4, 0), (1, 2, 1), (2, 0, 2), (5, 1, 0)] | | >>> sorted(Denominations(3, 5, 7).express(20, min_q=1)) | [(1, 2, 1)] | | the number of ways to change 1 pound into smaller coins: | >>> Denominations(1, 2, 5, 10, 20, 50).count(100) | 4562 | | using at least 1 of each type of coin: | >>> Denominations(1, 2, 5, 10, 20, 50).count(100, min_q=1) | 15 | | the largest non-McNugget number: | >>> Denominations(6, 9, 20).frobenius() | 43 | | Methods defined here: | | __init__(self, *denominations) | | count(self, amount, min_q=0) | count the number of ways of expressing an amount | | express(self, amount, min_q=0) | generate the different ways to express the given amount. | | if min_q is specified, at least that many instances of each | denomination must be used. | | frobenius(self) | return the largest amount not expressible using the denominations. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class DominoGrid(__builtin__.object) | Methods defined here: | | __init__(self, N, M, grid) | create a domino grid to solve. | | the grid is an NxM grid of dominoes, the values in the | grid are specified as a linearised list. | | "holes" in the grid are indicated with the value: None. | | go = run(self, fixed=None, used=[], sep='', prefix='') | | output_solution(self, s, prefix='') | given a solution from solve() output the solved grid. | | run(self, fixed=None, used=[], sep='', prefix='') | solve a grid and output the solutions | | solve(self, fixed=None, used=[]) | find placements of dominoes in the specified grid. | | fixed = pairs of indices of fixed dominoes | used = dominoes that are not available for use | | any domino identified in 'fixed' is automatically in 'used'. | | returns: (<solved grid>, <used dominoes>) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Filter2(__builtin__.tuple) | Filter2(true, false) | | Method resolution order: | Filter2 | __builtin__.tuple | __builtin__.object | | Methods defined here: | | __getnewargs__(self) | Return self as a plain tuple. Used by copy and pickle. | | __repr__(self) | Return a nicely formatted representation string | | _asdict(self) | Return a new OrderedDict which maps field names to their values | | _replace(_self, **kwds) | Return a new Filter2 object replacing specified fields with new values | | ---------------------------------------------------------------------- | Class methods defined here: | | _make(cls, iterable, new=<built-in method __new__ of type object>, len=<built-in function len>) from __builtin__.type | Make a new Filter2 object from a sequence or iterable | | ---------------------------------------------------------------------- | Static methods defined here: | | __new__(_cls, true, false) | Create new instance of Filter2(true, false) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | Return a new OrderedDict which maps field names to their values | | false | Alias for field number 1 | | true | Alias for field number 0 | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | _fields = ('true', 'false') | | ---------------------------------------------------------------------- | Methods inherited from __builtin__.tuple: | | __add__(...) | x.__add__(y) <==> x+y | | __contains__(...) | x.__contains__(y) <==> y in x | | __eq__(...) | x.__eq__(y) <==> x==y | | __ge__(...) | x.__ge__(y) <==> x>=y | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __gt__(...) | x.__gt__(y) <==> x>y | | __hash__(...) | x.__hash__() <==> hash(x) | | __iter__(...) | x.__iter__() <==> iter(x) | | __le__(...) | x.__le__(y) <==> x<=y | | __len__(...) | x.__len__() <==> len(x) | | __lt__(...) | x.__lt__(y) <==> x<y | | __mul__(...) | x.__mul__(n) <==> x*n | | __ne__(...) | x.__ne__(y) <==> x!=y | | __rmul__(...) | x.__rmul__(n) <==> n*x | | __sizeof__(...) | T.__sizeof__() -- size of T in memory, in bytes | | count(...) | T.count(value) -> integer -- return number of occurrences of value | | index(...) | T.index(value, [start, [stop]]) -> integer -- return first index of value. | Raises ValueError if the value is not present. class FilterUnique(__builtin__.tuple) | FilterUnique(unique, non_unique) | | Method resolution order: | FilterUnique | __builtin__.tuple | __builtin__.object | | Methods defined here: | | __getnewargs__(self) | Return self as a plain tuple. Used by copy and pickle. | | __repr__(self) | Return a nicely formatted representation string | | _asdict(self) | Return a new OrderedDict which maps field names to their values | | _replace(_self, **kwds) | Return a new FilterUnique object replacing specified fields with new values | | ---------------------------------------------------------------------- | Class methods defined here: | | _make(cls, iterable, new=<built-in method __new__ of type object>, len=<built-in function len>) from __builtin__.type | Make a new FilterUnique object from a sequence or iterable | | ---------------------------------------------------------------------- | Static methods defined here: | | __new__(_cls, unique, non_unique) | Create new instance of FilterUnique(unique, non_unique) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | Return a new OrderedDict which maps field names to their values | | non_unique | Alias for field number 1 | | unique | Alias for field number 0 | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | _fields = ('unique', 'non_unique') | | ---------------------------------------------------------------------- | Methods inherited from __builtin__.tuple: | | __add__(...) | x.__add__(y) <==> x+y | | __contains__(...) | x.__contains__(y) <==> y in x | | __eq__(...) | x.__eq__(y) <==> x==y | | __ge__(...) | x.__ge__(y) <==> x>=y | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __gt__(...) | x.__gt__(y) <==> x>y | | __hash__(...) | x.__hash__() <==> hash(x) | | __iter__(...) | x.__iter__() <==> iter(x) | | __le__(...) | x.__le__(y) <==> x<=y | | __len__(...) | x.__len__() <==> len(x) | | __lt__(...) | x.__lt__(y) <==> x<y | | __mul__(...) | x.__mul__(n) <==> x*n | | __ne__(...) | x.__ne__(y) <==> x!=y | | __rmul__(...) | x.__rmul__(n) <==> n*x | | __sizeof__(...) | T.__sizeof__() -- size of T in memory, in bytes | | count(...) | T.count(value) -> integer -- return number of occurrences of value | | index(...) | T.index(value, [start, [stop]]) -> integer -- return first index of value. | Raises ValueError if the value is not present. class Football(__builtin__.object) | Utility routines for solving Football League Table puzzles. | | For usage examples see: | Enigma 7 <http://enigmaticcode.wordpress.com/2012/11/24/enigma-7-football-substitutes/#comment-2911> | | Methods defined here: | | __init__(self, games=None, points=None, swap=None) | initialise the Football object. | | each match is considered to be between team 0 vs. team 1. | | <games> is a sequence of possible match outcomes, this defaults to | the following: 'w' win for team 0 (loss for team 1), 'd' draw, 'l' | loss for team 0 (win for team 1), 'x' match not played. | | <points> is a dictionary giving the points awarded for a match | outcome (from team 0's viewpoint). It defaults to 2 points for a | win, 1 point for a draw. | | <swap> is a dictionary used to change from team 0 to team 1's | perspective. By default it swaps 'w' to 'l' and vice versa. | | You might want to set <games> to 'wld' if all matches are played, | or 'wl' if there are no draws. And you can use <points> to | accommodate different scoring regimes. | | extract(self, d, t) | Extract values from dictionary <d> that are relevant to team <t>. | | A pair (<vs>, <ts>) is returned. | <vs> is the list of relevant values. | <ts> is the index of the team in the corresponding key | | Given a dictionary of matches outcomes <matches> the table row for | team A can be constructed with: | | (gs, ts) = football.extract(matches, A) | tableA = football.table(gs, ts) | | Similarly, with a dictionary of scores <scores>, goals for / | against can be calculated this: | | (ss, ts) = football.extract(scores, A) | (forA, againstA) = football.goals(ss, ts) | | extract_goals lambda self, ss, t | | extract_table lambda self, ms, t | # shortcuts to extract table row and goals for/against | | games(self, *gs, **kw) | A generator for possible game outcomes. | | Usually used like this: | | for (ab, bc, bd) in football.games(repeat=3): | print(ab, bc, bd) | | This will generate possible match outcomes for <ab>, <bc> and | <bd>. Each outcome will be chosen from the <games> parameter | specified in the creation of the Football object, so be default | will be: 'w', 'd', 'l', 'x'. | | Or you can specify specific outcomes: | | for (ab, bc, bd) in football.games('wd', 'dl', 'wl'): | print(ab, bc, bd) | | If no arguments are specified then a single outcome is assumed: | | for ab in football.games(): | print(ab) | | goals(self, ss, ts) | Return goals for and against given a sequence of scores <ss>, team | assignments <ts> and the total goals for <f> and against <a>. | | outcomes(self, ss, ts=None) | return a sequence of outcomes ('x', 'w', 'd', 'l') for a sequence of scores. | | output_matches(self, matches, scores=None, teams=None, d=None, start=None, end='') | output a collection of matches. | | matches - dict() of match outcomes. usually the result of a call | to substituted_table(). | | scores - dict() of scores in the matches. usually the result of a | call to substituted_table_goals(). | | teams - labels to use for the teams (rather than the row indices). | | d - dict() of symbol to value assignments to output. | | start, end - delimiters to use before and after the matches are | output. | | points(self, g, t=0) | # points for a game | | scores(self, gs, ts, f, a, pss=None, pts=None, min_goals=0, s=[]) | Generate possible score lines for a sequence of match outcomes <gs>, | team assignments <ts>, and total goals for <f> and against <a>. | | A sequence of scores for matches already played <pss> and | corresponding team assignments <pts> can be specified, in which case | the goals scored in these matches will be subtracted from <f> and | <a> before the score lines are calculated. | | <min_goals> is the minimum number of goals scored by each team. | | A sequence of scores matching the input templates will be | produced. Each score is a tuple (<team 0>, <team 1>) for a played | match, or None for an unplayed match. | | For example if team B has 9 goals for and 6 goal against: | | for (AB, BC, BD) in football.scores([ab, bc, bd], [1, 0, 0], 9, 6): | print(AB, BC, BD) | | substituted_table(self, table, teams=None, matches=None, d=None, vs=None) | solve a substituted table football problem where numbers in the | table have been substituted for letters. | | generates pairs (<matches>, <d>) where <matches> is a dict() of | match outcomes indexed by team indices, so the value at (<i>, <j>) | is the outcome for the match between the teams with indices <i> | and <j> in the table. <d> is dict() mapping letters used in the | table to their corresponding integer values. | | table - a dict() mapping the column names to the substituted | values in the columns of the table. '?' represents an empty cell | in the table. columns need not be specified if they have no | non-empty values. | | teams - a sequence of indices specifying the order the teams will | be processed in. if no order is specified a heuristic order will | be chosen. | | matches - a dictionary of known match outcomes. usually this is | the empty dictionary. | | d - a dictionary mapping known letters to numbers. usually this is | empty. | | vs - allowable values in the table. if not specified single digits | will be used. | | substituted_table_goals(self, gf, ga, matches, d=None, teams=None, scores=None, min_goals=0) | determine the scores in matches from a substituted table football problem. | | generates dicts <scores>, which give possible score lines for the | matches in <matches> (if a match is specified as 'x' (unplayed) a | score of None is returned). | | gf, ga - goals for, goals against columns in the table. specified | as maps of teams to symbols that index into <d> to give the actual | values. | | matches - the match outcomes. usually this will be the result of a | call to substituted_table(). | | teams - the order the teams are processed in. | | scores - known scores. usually this is empty. | | min_goals - minumum number of goals for each team in a match (usually 0). | | swap(self, m) | | table(self, gs, ts) | Compute the table given a sequence of match outcomes and team assignments. | | <gs> is a sequence of game outcomes (from team 0's point of view) | <ts> is a sequence identifying the team (0 for team 0, 1 for team 1) | | For example, to compute a table for team B: | | B = football.table([ab, bc, bd], [1, 0, 0]) | print(B.played, B.w, B.d, B.l, B.points) | | The returned table object has attributes named by the possible | match outcomes (by default, .w, .d, .l, .x) and also .played (the | total number of games played) and .points (calculated points). | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Impossible(exceptions.Exception) | Method resolution order: | Impossible | exceptions.Exception | exceptions.BaseException | __builtin__.object | | Data descriptors defined here: | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Methods inherited from exceptions.Exception: | | __init__(...) | x.__init__(...) initializes x; see help(type(x)) for signature | | ---------------------------------------------------------------------- | Data and other attributes inherited from exceptions.Exception: | | __new__ = <built-in method __new__ of type object> | T.__new__(S, ...) -> a new object with type S, a subtype of T | | ---------------------------------------------------------------------- | Methods inherited from exceptions.BaseException: | | __delattr__(...) | x.__delattr__('name') <==> del x.name | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __reduce__(...) | | __repr__(...) | x.__repr__() <==> repr(x) | | __setattr__(...) | x.__setattr__('name', value) <==> x.name = value | | __setstate__(...) | | __str__(...) | x.__str__() <==> str(x) | | __unicode__(...) | | ---------------------------------------------------------------------- | Data descriptors inherited from exceptions.BaseException: | | __dict__ | | args | | message class MagicSquare(__builtin__.object) | A magic square solver. | | e.g. to create a 3x3 magic square with 1 at the top centre: | | >>> p = MagicSquare(3) | >>> p.set(1, 1) | >>> p.solve() | True | >>> p.output() | [6] [1] [8] | [7] [5] [3] | [2] [9] [4] | | When referencing the individual squares through set() and get() | the squares are linearly indexed from 0 through to n^2-1. | | If you haven't filled out initial values for any squares then | solve() is likely to take a while, especially for larger magic squares. | | NOTE: This class will currently find _a_ solution for the square | (if it is solvable), but the solution is not necessarily unique. | A future version of this code may include a function that generates | all possible solutions. | | Methods defined here: | | __init__(self, n, numbers=None, lines=None) | create an empty n x n magic square puzzle. | | The numbers to fill out the magic square can be specified. | (If they are not specified numbers from 1 to n^2 are used). | | The magic lines can be specified as tuples of indices. | (If they are not specified then it is assumed that all the n | rows, n columns and 2 diagonals should sum to the magic value). | | become(self, other) | set the attributes of this object from the other object | | clone(self) | return a copy of this object | | complete(self) | strategy to complete missing squares where there is only one possibility | | get(self, i) | get the value of a square (linearly indexed from 0). | | hypothetical(self) | strategy that guesses a square and sees if the puzzle can be completed | | output(self) | print the magic square. | | set(self, i, v) | set the value of a square (linearly indexed from 0). | | solve(self) | solve the puzzle, returns True if a solution is found | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class MultiAccumulator(__builtin__.object) | # multiple accumulators: e.g. MultiAccumulator(fns=[min, max]) | | Methods defined here: | | __getitem__(self, i) | | __init__(self, fns) | | __repr__(self) | | accumulate(self, v) | | accumulate_data(self, v, data) | | accumulate_data_from(self, s, value=0, data=1) | | accumulate_from(self, s) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Polynomial(__builtin__.list) | Method resolution order: | Polynomial | __builtin__.list | __builtin__.object | | Methods defined here: | | __add__(self, other) | | __call__ = poly_value(p, x) | # evaluate a polynomial | | __hash__(self) | | __mul__(self, other) | | __neg__(self) | | __pow__(self, n) | | __repr__(self) | | __sub__(self, other) | | derivative(self, k=1) | | drop_factor(self, *qs) | | rational_roots(self, domain='Q', include='+-0') | | to_pairs(self) | | ---------------------------------------------------------------------- | Class methods defined here: | | from_pairs(self, ps) from __builtin__.type | | interpolate(self, ps) from __builtin__.type | | unit(self) from __builtin__.type | | zero(self) from __builtin__.type | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Methods inherited from __builtin__.list: | | __contains__(...) | x.__contains__(y) <==> y in x | | __delitem__(...) | x.__delitem__(y) <==> del x[y] | | __delslice__(...) | x.__delslice__(i, j) <==> del x[i:j] | | Use of negative indices is not supported. | | __eq__(...) | x.__eq__(y) <==> x==y | | __ge__(...) | x.__ge__(y) <==> x>=y | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __gt__(...) | x.__gt__(y) <==> x>y | | __iadd__(...) | x.__iadd__(y) <==> x+=y | | __imul__(...) | x.__imul__(y) <==> x*=y | | __init__(...) | x.__init__(...) initializes x; see help(type(x)) for signature | | __iter__(...) | x.__iter__() <==> iter(x) | | __le__(...) | x.__le__(y) <==> x<=y | | __len__(...) | x.__len__() <==> len(x) | | __lt__(...) | x.__lt__(y) <==> x<y | | __ne__(...) | x.__ne__(y) <==> x!=y | | __reversed__(...) | L.__reversed__() -- return a reverse iterator over the list | | __rmul__(...) | x.__rmul__(n) <==> n*x | | __setitem__(...) | x.__setitem__(i, y) <==> x[i]=y | | __setslice__(...) | x.__setslice__(i, j, y) <==> x[i:j]=y | | Use of negative indices is not supported. | | __sizeof__(...) | L.__sizeof__() -- size of L in memory, in bytes | | append(...) | L.append(object) -- append object to end | | count(...) | L.count(value) -> integer -- return number of occurrences of value | | extend(...) | L.extend(iterable) -- extend list by appending elements from the iterable | | index(...) | L.index(value, [start, [stop]]) -> integer -- return first index of value. | Raises ValueError if the value is not present. | | insert(...) | L.insert(index, object) -- insert object before index | | pop(...) | L.pop([index]) -> item -- remove and return item at index (default last). | Raises IndexError if list is empty or index is out of range. | | remove(...) | L.remove(value) -- remove first occurrence of value. | Raises ValueError if the value is not present. | | reverse(...) | L.reverse() -- reverse *IN PLACE* | | sort(...) | L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*; | cmp(x, y) -> -1, 0, 1 | | ---------------------------------------------------------------------- | Data and other attributes inherited from __builtin__.list: | | __new__ = <built-in method __new__ of type object> | T.__new__(S, ...) -> a new object with type S, a subtype of T class Record(__builtin__.object) | # a simple record type class for results | # (Python 3.3 introduced types.SimpleNamespace) | | Methods defined here: | | __init__ = update(self, **vs) | | __iter__(self) | | __repr__(self) | | map(self) | | update(self, **vs) | update values in a record | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Slots(__builtin__.object) | Methods defined here: | | __init__(self, wildcard='?', symbols='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz') | | allocate(self, ts) | # allocate a collection of slots for the input terms <ts> | | label(self, ss) | # return labels for a sequence of slots | | prop_items(self, k) | # return properties as <value, slots> | | slot_find(self, k, v, create=1) | # find (or create) a slot with this property | | slot_new(self, *props) | # allocate a new slot (with (k, v) properties) | | slot_setprops(self, i, *props) | | symbol(self, i) | # return the symbol for a slot | | symbols_used(self) | # return a string of the symbols currently assigned | | unify(self, s, t) | # unify two sequence of slots <s> and <t> | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Solved(exceptions.Exception) | Method resolution order: | Solved | exceptions.Exception | exceptions.BaseException | __builtin__.object | | Data descriptors defined here: | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Methods inherited from exceptions.Exception: | | __init__(...) | x.__init__(...) initializes x; see help(type(x)) for signature | | ---------------------------------------------------------------------- | Data and other attributes inherited from exceptions.Exception: | | __new__ = <built-in method __new__ of type object> | T.__new__(S, ...) -> a new object with type S, a subtype of T | | ---------------------------------------------------------------------- | Methods inherited from exceptions.BaseException: | | __delattr__(...) | x.__delattr__('name') <==> del x.name | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __reduce__(...) | | __repr__(...) | x.__repr__() <==> repr(x) | | __setattr__(...) | x.__setattr__('name', value) <==> x.name = value | | __setstate__(...) | | __str__(...) | x.__str__() <==> str(x) | | __unicode__(...) | | ---------------------------------------------------------------------- | Data descriptors inherited from exceptions.BaseException: | | __dict__ | | args | | message class SubstitutedDivision(SubstitutedExpression) | A solver for long division sums with letters substituted for digits. | | e.g. Enigma 206 | | - - - | ___________ | - - ) p k m k h | p m d | ----- | x p k | - - | ----- | k h h | m b g | ----- | k | ===== | | In this example there are the following intermediate (subtraction) sums: | | pkm - pmd = xp, xpk - ?? = kh, khh - mbg = k | | When the result contains a 0 digit there is no corresponding | intermediate sum, in this case the intermediate sum is specified as None. | | | Enigma 206 <https://enigmaticcode.wordpress.com/2014/07/13/enigma-206-division-some-letters-for-digits-some-digits-missing/> | | >>> SubstitutedDivision('pkmkh / ?? = ???', ['pkm - pmd = xp', 'xpk - ?? = kh', 'khh - mbg = k']).run().n | pkmkh / ?? = ??? (rem k) [pkm - pmd = xp, xpk - ?? = kh, khh - mbg = k] | 47670 / 77 = 619 (rem 7) [476 - 462 = 14, 147 - 77 = 70, 700 - 693 = 7] / b=9 d=2 g=3 h=0 k=7 m=6 p=4 x=1 | [1 solution] | 1 | | | See SubstitutedDivision.command_line() for more examples. | | Method resolution order: | SubstitutedDivision | SubstitutedExpression | __builtin__.object | | Methods defined here: | | __init__(self, *args, **kw) | create a substituted long division solver. | | args - the long division sum to solve. | | a long division sum is considered to have the following components: | | a / b = c remainder r | | the dividend = a | the divisor = b | the result = c | | along with a set of intermediate subtractions of the form: | | x - y = z | | one sum for each digit in the result (a 0 digit in the result | corresponds to an empty intermediate subtraction sum, which is | specified using None). | | the sum is specified in one of the following ways: | | 1. each component is separated out | (this is how the old SubstitutedDivision() solver was called) | | args = (<a>, <b>, <c>, [(<x>, <y>, <z>), ... ]) | | 2. the sums are specified as strings: | | args = ("<a> / <b> = <c>", ["<x> - <y> = <z>", ...]) | | or: | | args = ("<a> / <b> = <c>", "<x> - <y> = <z>", ...) | | | the following keyword arguments from SubstitutedExpression() can be used: | | digits - specify digits to be substituted | distinct - specify sets of symbols whose values should be distinct | d2i - invalid digit to symbol map | s2d - initial symbol to digit map | answer - collect solutions by answer | verbose - control output of solutions and tourist information | | output_solution(self, s) | | solution_intermediates(self, s) | | solve(self, check=None, first=None, verbose=None) | generate solutions for the substituted long division problem. | | solutions are returned as a SubstitutedDivisionSolution() object | | check - a boolean function called to reject unwanted solutions | first - if set to True only the first solution is returned | verbose - an integer controlling the output of solutions and additional information | | substitute_all(self, d, ss) | | ---------------------------------------------------------------------- | Class methods defined here: | | command_line(cls, args) from __builtin__.type | run the SubstitutedDivision solver with the specified command line | arguments. | | the division sum is specified on the command line as: | | "<a> / <b> = <c>" "<x> - <y> = <z>" ... | | there should be as many intermediate subtraction sums as there are | digits in the result <c>. when there is an empty intermediate sum | (which corresponds to a 0 in the result) an empty argument should | be passed. if there is no remainder the final intermediate | subtraction will look like "<x> - <y> = 0". | | literal digits in the arguments stand for themselves, a ? | character stands for any digit, and a letter stands for a digit | whose value is not known. | | solver parameters can be specified on the command line in the same | way as for the SubstitutedExpression solver, along with the | additional "--extra / -E" parameter. | | Some exapmles: | | | [Enigma 206] <https://enigmaticcode.wordpress.com/2014/07/13/enigma-206-division-some-letters-for-digits-some-digits-missing/> | | % python enigma.py SubstitutedDivision "pkmkh / ?? = ???" "pkm - pmd = xp" "xpk - ?? = kh" "khh - mbg = k" | 7????? / ?? = ????? (rem 0) [7? - ?? = ??, ??? - ?? = ?, None, ??? - ?? = ??, ??? - ??7 = 0] | 760287 / 33 = 23039 (rem 0) [76 - 66 = 10, 100 - 99 = 1, None, 128 - 99 = 29, 297 - 297 = 0] | [1 solution] | | | [Enigma 250] <https://enigmaticcode.wordpress.com/2015/01/13/enigma-250-a-couple-of-sevens/> | | The third intermediate subtraction sum is empty. | | % python enigma.py SubstitutedDivision "7????? / ?? = ?????" "7? - ?? = ??" "??? - ?? = ?" "" "??? - ?? = ??" "??? - ??7 = 0" | 7????? / ?? = ????? (rem 0) [7? - ?? = ??, ??? - ?? = ?, None, ??? - ?? = ??, ??? - ??7 = 0] | 760287 / 33 = 23039 (rem 0) [76 - 66 = 10, 100 - 99 = 1, None, 128 - 99 = 29, 297 - 297 = 0] | [1 solution] | | | [Enigma 226] <https://enigmaticcode.wordpress.com/2014/10/02/enigma-226-cold-comfort-five/> | | A solver parameter is used to stop X from taking on the value of 5. | | % python enigma.py SubstitutedDivision --invalid="5,X" "???0000 / ?? = ?????" "??? - ?? = ?" "?? - ?? = ??" "??? - ?X? = ??" "??? - ??? = ??" "??? - ??? = 0" | ???0000 / ?? = ????? (rem 0) [??? - ?? = ?, ?? - ?? = ??, ??? - ?X? = ??, ??? - ??? = ??, ??? - ??? = 0] | 1050000 / 48 = 21875 (rem 0) [105 - 96 = 9, 90 - 48 = 42, 420 - 384 = 36, 360 - 336 = 24, 240 - 240 = 0] / X=8 | [1 solution] | | | [Enigma 16] <https://enigmaticcode.wordpress.com/2012/12/12/enigma-16-four-five-six-seven/> | | The --extra parameter is used to provide an additional condition. | | % python enigma.py SubstitutedDivision --distinct="" "C??? / A? = ???" "C? - ?D = ?" "" "??? - B?? = 0" --extra="sum([A != 4, B != 5, C != 6, D != 7]) = 1" | C??? / A? = ??? (rem 0) [C? - ?D = ?, None, ??? - B?? = 0] | 6213 / 57 = 109 (rem 0) [62 - 57 = 5, None, 513 - 513 = 0] / A=5 B=5 C=6 D=7 | [1 solution] | | ---------------------------------------------------------------------- | Methods inherited from SubstitutedExpression: | | go = run(self, check=None, first=None, verbose=None) | find solutions to the substituted expression problem and output them. | | check - a function to accept/reject solutions | first - if set to True will stop after the first solution is output | verbose - control output | | returns a Record object with the following attributes: | n = the number of solutions found | answer = a multiset() object counting the number of times each answer | occurs (if the "answer" parameter was set in init()) | accumulate = result of accumulating the answers (if the "accumulate" | parameter was also set) | | run(self, check=None, first=None, verbose=None) | find solutions to the substituted expression problem and output them. | | check - a function to accept/reject solutions | first - if set to True will stop after the first solution is output | verbose - control output | | returns a Record object with the following attributes: | n = the number of solutions found | answer = a multiset() object counting the number of times each answer | occurs (if the "answer" parameter was set in init()) | accumulate = result of accumulating the answers (if the "accumulate" | parameter was also set) | | save(self, file=None, quote=1) | # generate appropriate command line arguments to reconstruct this instance | | substitute(self, s, text, digits=None) | given a solution to the substituted expression sum and some text, | return the text with the letters substituted for digits. | | to_args(self, quote=1) | # generate appropriate command line arguments to reconstruct this instance | | ---------------------------------------------------------------------- | Class methods inherited from SubstitutedExpression: | | from_args(cls, args) from __builtin__.type | # class method to make an object from arguments | | from_file(cls, file, args=None) from __builtin__.type | # class method to make an object from a file | | repl(cls, args=(), timed=1) from __builtin__.type | Provide a read/eval/print loop for evaluating alphametics. | | Use the following command to invoke it: | | % python enigma.py Alphametic.repl | | timed=1 will time the evaluation. | | run_file(cls, path, args=None) from __builtin__.type | # class method to load a run file | | ---------------------------------------------------------------------- | Data descriptors inherited from SubstitutedExpression: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Data and other attributes inherited from SubstitutedExpression: | | v1 = 28 | | v2 = 156 | | v3 = 444 | | v9 = 508 | | vA = 16 | | vC = 256 | | vE = 32 | | vH = 4 | | vI = 128 | | vP = 64 | | vT = 8 class SubstitutedDivisionSolution(__builtin__.tuple) | SubstitutedDivisionSolution(a, b, c, r, subs, d, s) | | Method resolution order: | SubstitutedDivisionSolution | __builtin__.tuple | __builtin__.object | | Methods defined here: | | __getnewargs__(self) | Return self as a plain tuple. Used by copy and pickle. | | __repr__(self) | Return a nicely formatted representation string | | _asdict(self) | Return a new OrderedDict which maps field names to their values | | _replace(_self, **kwds) | Return a new SubstitutedDivisionSolution object replacing specified fields with new values | | ---------------------------------------------------------------------- | Class methods defined here: | | _make(cls, iterable, new=<built-in method __new__ of type object>, len=<built-in function len>) from __builtin__.type | Make a new SubstitutedDivisionSolution object from a sequence or iterable | | ---------------------------------------------------------------------- | Static methods defined here: | | __new__(_cls, a, b, c, r, subs, d, s) | Create new instance of SubstitutedDivisionSolution(a, b, c, r, subs, d, s) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | Return a new OrderedDict which maps field names to their values | | a | Alias for field number 0 | | b | Alias for field number 1 | | c | Alias for field number 2 | | d | Alias for field number 5 | | r | Alias for field number 3 | | s | Alias for field number 6 | | subs | Alias for field number 4 | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | _fields = ('a', 'b', 'c', 'r', 'subs', 'd', 's') | | ---------------------------------------------------------------------- | Methods inherited from __builtin__.tuple: | | __add__(...) | x.__add__(y) <==> x+y | | __contains__(...) | x.__contains__(y) <==> y in x | | __eq__(...) | x.__eq__(y) <==> x==y | | __ge__(...) | x.__ge__(y) <==> x>=y | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __getslice__(...) | x.__getslice__(i, j) <==> x[i:j] | | Use of negative indices is not supported. | | __gt__(...) | x.__gt__(y) <==> x>y | | __hash__(...) | x.__hash__() <==> hash(x) | | __iter__(...) | x.__iter__() <==> iter(x) | | __le__(...) | x.__le__(y) <==> x<=y | | __len__(...) | x.__len__() <==> len(x) | | __lt__(...) | x.__lt__(y) <==> x<y | | __mul__(...) | x.__mul__(n) <==> x*n | | __ne__(...) | x.__ne__(y) <==> x!=y | | __rmul__(...) | x.__rmul__(n) <==> n*x | | __sizeof__(...) | T.__sizeof__() -- size of T in memory, in bytes | | count(...) | T.count(value) -> integer -- return number of occurrences of value | | index(...) | T.index(value, [start, [stop]]) -> integer -- return first index of value. | Raises ValueError if the value is not present. class SubstitutedExpression(__builtin__.object) | A solver for Python expressions with symbols substituted for numbers. | | It takes a Python expression and then tries all possible ways of assigning | symbols (by default the capital letters) in it to digits and returns those | assignments which result in the expression having a True value. | | While this is slower than the specialised solvers, like SubstitutedSum(), | it does allow for more general expressions to be evaluated. | | | Enigma 1530 <https://enigmaticcode.wordpress.com/2012/07/09/enigma-1530-tom-daley/> | >>> SubstitutedExpression('TOM * 13 = DALEY').run().n | (TOM * 13 = DALEY) | (796 * 13 = 10348) / A=0 D=1 E=4 L=3 M=6 O=9 T=7 Y=8 | [1 solution] | 1 | | | See SubstitutedExpression.command_line() for more examples. | | Methods defined here: | | __init__(self, exprs, base=10, symbols=None, digits=None, s2d=None, l2d=None, d2i=None, answer=None, accumulate=None, template=None, solution=None, header=None, distinct=1, check=None, env=None, code=None, process=1, reorder=1, first=0, denest=0, sane=1, verbose=1) | create a substituted expression solver. | | exprs - the expression(s) | | exprs can be a single expression, or a sequence of expressions. | | A single expression is of the form: | | "<expr>" or "<expr> = <value>" or (<expr>, <value>) | | where value is a valid "word" (sequence of symbols), or an integer value. | | The following parameters are optional: | base - the number base to operate in (default: 10) | symbols - the symbols to substituted in the expression (default: upper case letters) | digits - the digits to be substituted in (default: determined from base) | s2d - initial map of symbols to digits (default: all symbols unassigned) | d2i - map of digits to invalid symbol assignments (default: leading digits cannot be 0) | answer - an expression for the answer value | accumulate - accumulate answers using the specified object | distinct - symbols which should have distinct values (1 = all, 0 = none) (default: 1) | check - a boolean function used to accept/reject solutions (default: None) | env - additional environment for evaluation (default: None) | code - additional lines of code evaluated before solving (default: None) | denest - work around CPython statically nested block limit | sane - enable/disable sanity checks (default: 1) | verbose - control informational output (default: 1) | | If you want to allow leading digits to be 0 pass an empty dictionary for d2i. | | go = run(self, check=None, first=None, verbose=None) | | output_solution(self, d, template=None, solution=None) | # output a solution as: "<template> / <solution>" | # <template> = the given template with digits substituted for symbols | # <solution> = the assignment of symbols (given in <solution>) to digits (in base 10) | | run(self, check=None, first=None, verbose=None) | find solutions to the substituted expression problem and output them. | | check - a function to accept/reject solutions | first - if set to True will stop after the first solution is output | verbose - control output | | returns a Record object with the following attributes: | n = the number of solutions found | answer = a multiset() object counting the number of times each answer | occurs (if the "answer" parameter was set in init()) | accumulate = result of accumulating the answers (if the "accumulate" | parameter was also set) | | save(self, file=None, quote=1) | # generate appropriate command line arguments to reconstruct this instance | | solve(self, check=None, first=None, verbose=None) | generate solutions to the substituted expression problem. | | solutions are returned as a dictionary assigning symbols to digits. | | check - a boolean function called to reject unwanted solutions | first - if set to positive <n> only the first <n> solutions are returned | verbose - if set to >0 solutions are output as they are found, >1 additional information is output. | | substitute(self, s, text, digits=None) | given a solution to the substituted expression sum and some text, | return the text with the letters substituted for digits. | | to_args(self, quote=1) | # generate appropriate command line arguments to reconstruct this instance | | ---------------------------------------------------------------------- | Class methods defined here: | | command_line(cls, args) from __builtin__.type | run the SubstitutedExpression solver with the specified command | line arguments. | | we can solve substituted sum problems (although using | SubstitutedSum would be faster) | | | Enigma 327 <https://enigmaticcode.wordpress.com/2016/01/08/enigma-327-it-all-adds-up/> | % python enigma.py SubstitutedExpression "KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE" | (KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE) | (1912803 + 2428850 + 4312835 = 8654488) / A=4 B=9 D=3 E=8 G=2 K=1 Q=0 X=6 Y=5 | [1 solution] | | but we can also use SubstitutedExpression to solve problems that | don't have a specialsed solver. | | e.g. Sunday Times Teaser 2803 | % python enigma.py SubstitutedExpression --answer="ABCDEFGHIJ" "AB * CDE = FGHIJ" "AB + CD + EF + GH + IJ = CCC" | (AB * CDE = FGHIJ) (AB + CD + EF + GH + IJ = CCC) | (52 * 367 = 19084) (52 + 36 + 71 + 90 + 84 = 333) / A=5 B=2 C=3 D=6 E=7 F=1 G=9 H=0 I=8 J=4 / 5236719084 | ABCDEFGHIJ = 5236719084 [1 solution] | | e.g. Sunday Times Teaser 2796 | % python enigma.py SubstitutedExpression --answer="DRAGON" "SAINT + GEORGE = DRAGON" "E % 2 = 0" | (SAINT + GEORGE = DRAGON) (E % 2 = 0) | (72415 + 860386 = 932801) (6 % 2 = 0) / A=2 D=9 E=6 G=8 I=4 N=1 O=0 R=3 S=7 T=5 / 932801 | DRAGON = 932801 [1 solution] | | we also have access to any of the routines defined in enigma.py: | | e.g. Enigma 1180 <https://enigmaticcode.wordpress.com/2016/02/15/enigma-1180-anomalies/> | % python enigma.py SubstitutedExpression --answer="(FOUR, TEN)" "SEVEN - THREE = FOUR" "is_prime(SEVEN)" "is_prime(FOUR)" "is_prime(RUOF)" "is_square(TEN)" | (SEVEN - THREE = FOUR) (is_prime(SEVEN)) (is_prime(FOUR)) (is_prime(RUOF)) (is_square(TEN)) | (62129 - 58722 = 3407) (is_prime(62129)) (is_prime(3407)) (is_prime(7043)) (is_square(529)) / E=2 F=3 H=8 N=9 O=4 R=7 S=6 T=5 U=0 V=1 / (3407, 529) | (FOUR, TEN) = (3407, 529) [1 solution] | | from_args(cls, args) from __builtin__.type | # class method to make an object from arguments | | from_file(cls, file, args=None) from __builtin__.type | # class method to make an object from a file | | repl(cls, args=(), timed=1) from __builtin__.type | Provide a read/eval/print loop for evaluating alphametics. | | Use the following command to invoke it: | | % python enigma.py Alphametic.repl | | timed=1 will time the evaluation. | | run_file(cls, path, args=None) from __builtin__.type | # class method to load a run file | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | v1 = 28 | | v2 = 156 | | v3 = 444 | | v9 = 508 | | vA = 16 | | vC = 256 | | vE = 32 | | vH = 4 | | vI = 128 | | vP = 64 | | vT = 8 class SubstitutedSum(__builtin__.object) | A solver for addition sums with letters substituted for digits. | | A substituted sum object has the following useful attributes: | terms - the summands of the sum | result - the result of the sum | text - a textual form of the sum (e.g. "<term1> + <term2> = <result>") | | e.g. Enigma 21: "Solve: BPPDQPC + PRPDQBD = XVDWTRC" | <https://enigmaticcode.wordpress.com/2012/12/23/enigma-21-addition-letters-for-digits/> | >>> SubstitutedSum(['BPPDQPC', 'PRPDQBD'], 'XVDWTRC').go() | BPPDQPC + PRPDQBD = XVDWTRC | 3550657 + 5850630 = 9401287 / B=3 C=7 D=0 P=5 Q=6 R=8 T=2 V=4 W=1 X=9 | | e.g. Enigma 63: "Solve: LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL" | <https://enigmaticcode.wordpress.com/2013/01/08/enigma-63-addition-letters-for-digits/> | >>> SubstitutedSum(['LBRLQQR', 'LBBBESL', 'LBRERQR', 'LBBBEVR'], 'BBEKVMGL').go() | LBRLQQR + LBBBESL + LBRERQR + LBBBEVR = BBEKVMGL | 8308440 + 8333218 + 8302040 + 8333260 = 33276958 / B=3 E=2 G=5 K=7 L=8 M=9 Q=4 R=0 S=1 V=6 | | Methods defined here: | | __init__(self, terms, result, base=10, digits=None, l2d=None, d2i=None) | create a substituted addition sum puzzle. | | terms - a list of the summands of the sum. | result - the result of the sum (i.e. the sum of the terms). | | The following parameters are optional: | base - the number base the sum is in (default: 10) | digits - permissible digits to be substituted in (default: determined from base) | l2d - initial map of letters to digits (default: all letters unassigned) | d2i - map of digits to invalid letter assignments (default: leading digits cannot be 0) | | If you want to allow leading digits to be 0 pass an empty dictionary for d2i. | | go = run(self, check=None, first=0) | | output_solution(self, s, digits=None) | given a solution to the substituted sum output the assignment of letters | to digits and the sum with digits substituted for letters. | | run(self, check=None, first=0) | find all solutions (matching the filter <fn>) and output them. | | solution = output_solution(self, s, digits=None) | | solve(self, check=None, verbose=0) | generate solutions to the substituted addition sum puzzle. | | solutions are returned as a dictionary assigning letters to digits. | | substitute(self, s, text, digits=None) | given a solution to the substituted sum and some text return the text with | letters substituted for digits. | | ---------------------------------------------------------------------- | Class methods defined here: | | chain(cls, sums, base=10, digits=None, l2d=None, d2i=None) from __builtin__.type | solve a sequence of substituted sum problems. | | sums are specified as a sequence of: (<term>, <term>, ..., <result>) | | chain_go = chain_run(cls, sums, base=10, digits=None, l2d=None, d2i=None) from __builtin__.type | | chain_run(cls, sums, base=10, digits=None, l2d=None, d2i=None) from __builtin__.type | | command_line(cls, args) from __builtin__.type | run the SubstitutedSum solver with the specified command line arguments. | | e.g. Enigma 327 <https://enigmaticcode.wordpress.com/2016/01/08/enigma-327-it-all-adds-up/> | % python enigma.py SubstitutedSum "KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE" | (KBKGEQD + GAGEEYQ + ADKGEDY = EXYAAEE) | (1912803 + 2428850 + 4312835 = 8654488) / A=4 B=9 D=3 E=8 G=2 K=1 Q=0 X=6 Y=5 | | | Optional parameters: | | --base=<n> (or -b<n>) | | Specifies the numerical base of the sum, solutions are printed in the | specified base (so that the letters and digits match up, but don't get | confused by digits that are represented by letters in bases >10). | | e.g. Enigma 1663 <https://enigmaticcode.wordpress.com/2011/12/04/enigma-1663-flintoffs-farewell/> | % python enigma.py SubstitutedSum --base=11 "FAREWELL + FREDALO = FLINTOFF" | (FAREWELL + FREDALO = FLINTOFF) | (61573788 + 657A189 = 68042966) / A=1 D=10 E=7 F=6 I=0 L=8 N=4 O=9 R=5 T=2 W=3 | (6157A788 + 6573189 = 68042966) / A=1 D=3 E=7 F=6 I=0 L=8 N=4 O=9 R=5 T=2 W=10 | | | --assign=<letter>,<digit> (or -a<l>,<d>) | | Assign a digit to a letter. | | There can be multiple --assign options. | | e.g. Enigma 1361 <https://enigmaticcode.wordpress.com/2013/02/20/enigma-1361-enigma-variation/> | % python enigma.py SubstitutedSum --assign="O,0" "ELGAR + ENIGMA = NIMROD" | (ELGAR + ENIGMA = NIMROD) | (71439 + 785463 = 856902) / A=3 D=2 E=7 G=4 I=5 L=1 M=6 N=8 O=0 R=9 | | | --digits=<digit>,<digit>,... (or -d<d>,<d>,...) | | Specify the digits that can be assigned to unassigned letters. | (Note that the values of the digits are specified in base 10, even if you | have specified a --base=<n> option) | | e.g. Enigma 1272 <https://enigmaticcode.wordpress.com/2014/12/09/enigma-1272-jonny-wilkinson/> | % python enigma.py SubstitutedSum --digits="0-8" "WILKI + NSON = JONNY" | (WILKI + NSON = JONNY) | (48608 + 3723 = 52331) / I=8 J=5 K=0 L=6 N=3 O=2 S=7 W=4 Y=1 | (48708 + 3623 = 52331) / I=8 J=5 K=0 L=7 N=3 O=2 S=6 W=4 Y=1 | | | --invalid=<digits>,<letters> (or -i<ds>,<ls>) | | Specify letters that cannot be assigned to a digit. | | There can be multiple --invalid options, but they should be for different | <digit>s. | | If there are no --invalid options the default will be that leading zeros are | not allowed. If you want to allow them you can give a "--invalid=0," option. | | Enigma 171 <https://enigmaticcode.wordpress.com/2014/02/23/enigma-171-addition-digits-all-wrong/> | % python enigma.py SubstitutedSum -i0,016 -i1,1 -i3,3 -i5,5 -i6,6 -i7,7 -i8,8 -i9,9 "1939 + 1079 = 6856" | (1939 + 1079 = 6856) | (2767 + 2137 = 4904) / 0=1 1=2 3=6 5=0 6=4 7=3 8=9 9=7 | | | --help (or -h) | | Prints a usage summary. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) class Timer(__builtin__.object) | This module provides elapsed timing measures. | | There is a default timing object called "timer" created. So you can | determine the elapsed runtime of code fragments using: | | from enigma import timer | | timer.start() | | some_code() | | timer.stop() | | and when the program exits it will report the elapsed time thus: | | [timing] elapsed time: 0.0008729s (872.85us) | | By default the elapsed time reported when the Python interpreter | exits. But if you want more control you can do the following: | | from enigma import Timer | | ... | | # create the timer | timer = Timer('name') | | # start the timer | timer.start() | | # the code you want to time would go here | some_code() | | # stop the timer | timer.stop() | | # print the report | timer.report() | | | If you don't call start() then the timer will be started when it is | created. | | If you don't call report() then the elapsed time report will be | printed when the Python interpreter exits. | | If you don't call stop() then the timer will be stopped when the | Python interpreter exits, just before the report is printed. | | | You can create multiple timers. It might help to give them different | names to distinguish their reports. (The default name is "timing"). | | | You can also wrap code to be timed like this: | | with Timer('name'): | # the code you want to time goes here | some_code() | | | You can create a function that will report the timing each time it | is called by decorating it with the timed decorator: | | from enigma import timed | | @timed | def whatever(): | some_code() | | | When a Timer object is initialised the 'timer' parameter specifies what | timing function to use. A value of 'E' use elapsed (real) time and a | value of 'P' use process (CPU) time. 'E' should always be available, | 'P' may not be. You can specify 'PE', to try 'P', and if not 'E'. | | If you know what timeing function you want to use you can pass it | directly. (Or pass the name of the function in the 'time' module). | | Methods defined here: | | __enter__(self) | | __exit__(self, *args) | | __init__(self, name='timing', timer='PE', file=<open file '<stderr>', mode 'w'>, exit_report=1, auto_start=1, verbose=0) | Create (and start) a timer. | | name = the name used in the report | timer = function used to measure time (should return a number of seconds) | file = where the report is sent | exit_report = should the report be generated at exit | auto_start = should the timer be automatically started | | elapsed(self, disable_report=1) | Return the elapsed time of a stopped timer | | disable_report = should the report be disabled | | format(self, t, fmt='{:.2f}') | Format a time for the report. | | printf(self, fmt='', **kw) | | report(self, force=1) | Stop the timer and generate the report (if required). | | The report will only be generated once (if it's not been disabled). | | start(self) | Set the start time of a timer. | | stop(self) | Set the stop time of a timer. | | ---------------------------------------------------------------------- | Class methods defined here: | | init(self) from __builtin__.type | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | timers = {'E': <built-in function time>} class multiset(__builtin__.dict) | an implementation of multisets. | | it can be used as an alternative to collections.Counter(), but note | the following differences: | | len() counts the number of elements (not the number of distinct elements) | | iterating through a multiset provides all elements (not just distinct | elements) | | Method resolution order: | multiset | __builtin__.dict | __builtin__.object | | Methods defined here: | | __add__ = combine(self, *rest) | | __and__ = intersection(self, *rest) | | __bool__ = is_nonempty(self) | | __ge__ = issuperset(self, m, strict=0) | | __gt__ lambda self, m | | __iadd__ = update(self, *rest) | | __init__(self, *vs, **kw) | create a multiset from one of the following: | | a dict of <item> -> <count> values | | a sequence of (<item>, <count>) values | | a sequence of individual items (may have repeats) | | multiple initialisation arguments may be provided, the | items from each are added into the multiset. | | so these are different ways of making the same multiset: | | multiset("banana") | multiset(a=3, b=1, n=2) | multiset([('a', 3), ('b', 1), ('n', 2)]) | multiset(['b', 'a', 'n', 'a', 'n', 'a']) | multiset(dict(a=3, b=1, n=2)) | | for more control over the initialisation of the multiset you can | use: from_dict(), from_pairs(), from_seq() class methods or the | corresponding: update_from_dict(), update_from_pairs(), | update_from_seq() object methods. | | __ior__ = union_update(self, *rest) | | __iter__ = elements(self) | | __le__ = issubset(self, m, strict=0) | | __len__ = size(self) | | __lt__ lambda self, m | | __mul__ = multiply(self, n) | | __nonzero__ = is_nonempty(self) | | __or__ = union(self, *rest) | | __sub__ = difference(self, m) | | add(self, item, count=1) | add an item to a multiset. | | count can be negative to remove items. | | combine(self, *rest) | return a new multiset that is the result of the original multiset | updated with some other multisets (or objects that can be | interepreted as multisets). | | item counts are summed. | | copy(self) | return a copy of a multiset | | count(self, item) | return the number of times an item occurs. | | difference(self, m) | return (self - m) | | differences(self, m) | return the differences between self and another multiset m. | | returns (self - m, m - self) | | distinct_elements = keys(...) | D.keys() -> list of D's keys | | elements(self) | iterate through all elements of the multiset. | | for distinct elements use: s.keys() | | this function is used if a multiset is used as an iterator. | | >>> sorted(multiset("banana")) | ['a', 'a', 'a', 'b', 'n', 'n'] | >>> sorted(multiset("banana").keys()) | ['a', 'b', 'n'] | | intersection(self, *rest) | return a new multiset that is the result of the intersection of | the original multiset and some other multisets (or objects that | can be interpreted as multisets). | | minimal item counts are retained. | | is_disjoint(self, *rest) | # is this multiset disjoint from a bunch of other multisets | | is_empty(self) | | is_nonempty(self) | | issubset(self, m, strict=0) | test if this multiset is contained in multiset <m>. | | issuperset(self, m, strict=0) | test if this multiset contains multiset <m>. | | max(self, **kw) | return the maximum item value of a multiset (or <default>). | | equivalent to: max(self) | | min(self, **kw) | return the minimum item value of a multiset (or <default>). | | equivalent to: min(self) | | most_common(self, n=None) | return the items of the multiset in order of the most common. | | if n is specifed only the first n items are returned. | | multiply(self, n) | return a new mutliset derived from the original multiset by | multiplying item counts by <n>. | | remove(self, item, count=1) | remove an item from a multiset. | | size(self) | the cardinality of the multiset. | i.e. a count all the elements in a multiset. | | to count the number of distinct element types use: len(s.keys()) | | this function is used to implement the len() method on multisets. | | >>> multiset("banana").size() | 6 | >>> len(multiset("banana")) | 6 | >>> len(multiset("banana").keys()) | 3 | | subsets(self, size=None, min_size=0, max_size=None) | generate subsets of a multiset. | | sum(self) | return the sum of items in a multiset. | | equivalent to: sum(self) | | symmetric_difference(self, m) | symmetric difference of this multiset with multiset <m>. | | the difference in item counts is retained. | | union(self, *rest) | return a new multiset that is the result of the union of the | original multiset and some other multisets (or objects that can be | interpreted as multisets). | | maximal item counts are retained. | | union_update(self, *rest) | update a multiset with the union of itself and some other | multisets (or objects that can be interpreted as multisets). | | maximal item counts are retained. | | update(self, *rest) | update the multiset with some other multisets (or objects that can | be interpreted as multisets). | | item counts are summed. | | update_from_dict(self, d) | update a multiset from a dict of <item> -> <count> values. | | update_from_pairs(self, vs) | update a multiset from a sequence of (<item>, <count>) pairs. | | update_from_seq(self, vs, count=1) | update a multiset from a sequence of items. | | ---------------------------------------------------------------------- | Class methods defined here: | | from_dict(cls, *vs) from __builtin__.type | create a multiset from a dict of <item> -> <count> values | (or multiple dicts). | | from_pairs(self, *vs) from __builtin__.type | create a multiset from a sequence of (<item>, <count>) pairs | (or multiple sequences). | | from_seq(self, *vs, **kw) from __builtin__.type | create a multiset from a sequence of items (or multiple sequences). | | A keyword argument of 'count' specifies the multiplicity of each | element of the sequence inserted into the multiset. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Methods inherited from __builtin__.dict: | | __cmp__(...) | x.__cmp__(y) <==> cmp(x,y) | | __contains__(...) | D.__contains__(k) -> True if D has a key k, else False | | __delitem__(...) | x.__delitem__(y) <==> del x[y] | | __eq__(...) | x.__eq__(y) <==> x==y | | __getattribute__(...) | x.__getattribute__('name') <==> x.name | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __ne__(...) | x.__ne__(y) <==> x!=y | | __repr__(...) | x.__repr__() <==> repr(x) | | __setitem__(...) | x.__setitem__(i, y) <==> x[i]=y | | __sizeof__(...) | D.__sizeof__() -> size of D in memory, in bytes | | clear(...) | D.clear() -> None. Remove all items from D. | | fromkeys(...) | dict.fromkeys(S[,v]) -> New dict with keys from S and values equal to v. | v defaults to None. | | get(...) | D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None. | | has_key(...) | D.has_key(k) -> True if D has a key k, else False | | items(...) | D.items() -> list of D's (key, value) pairs, as 2-tuples | | iteritems(...) | D.iteritems() -> an iterator over the (key, value) items of D | | iterkeys(...) | D.iterkeys() -> an iterator over the keys of D | | itervalues(...) | D.itervalues() -> an iterator over the values of D | | keys(...) | D.keys() -> list of D's keys | | pop(...) | D.pop(k[,d]) -> v, remove specified key and return the corresponding value. | If key is not found, d is returned if given, otherwise KeyError is raised | | popitem(...) | D.popitem() -> (k, v), remove and return some (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | setdefault(...) | D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D | | values(...) | D.values() -> list of D's values | | viewitems(...) | D.viewitems() -> a set-like object providing a view on D's items | | viewkeys(...) | D.viewkeys() -> a set-like object providing a view on D's keys | | viewvalues(...) | D.viewvalues() -> an object providing a view on D's values | | ---------------------------------------------------------------------- | Data and other attributes inherited from __builtin__.dict: | | __hash__ = None | | __new__ = <built-in method __new__ of type object> | T.__new__(S, ...) -> a new object with type S, a subtype of T class namespace(__builtin__.object) | Methods defined here: | | __init__(self, name, vs) | | __repr__(self) | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) FUNCTIONS C(n, k) combinatorial function: n C k. the number of unordered k-length selections from n elements (elements can only be used once). >>> C(10, 3) 120 M(n, k) multichoose function: n M k. the number of unordered k-length selections from n elements where elements may be chosen multiple times. >>> M(10, 3) 220 P(n, k) permutations functions: n P k. the number of ordered k-length selections from n elements (elements can only be used once). >>> P(10, 3) 720 Primes(n=None, expandable=0, array=<type 'bytearray'>, fn=<function <lambda>>, verbose=0) Return a suitable prime sieve object. n - initial limit of the sieve (the sieve contains primes less than n) expandable - should the sieve expand as necessary array - list implementation to use fn - function used to increase the limit on expanding sieves If we are interested in a limited collection of primes, we can do this: >>> primes = Primes(50) >>> primes.list() [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] >>> sum(primes) 328 >>> 39 in primes False The collection can be extended manually to a new upper limit: >>> primes.extend(100) >>> sum(primes) 1060 >>> 97 in primes True but it doesn't automatically expand. If we want an automatically expanding version, we can set the 'expandable' flag to True. >>> primes = Primes(50, expandable=1) We can find out the current size and contents of the sieve: >>> primes.max 50 >>> primes.list() [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] But if we use it as a generator it will expand indefinitely, so we can only sum a restricted range: >>> sum(primes.range(0, 100)) 1060 If you don't know how many primes you'll need you can just use Primes() and get an expandable sieve with primes up to 1024, and the limit will double each time the sieve is expanded. So, to sum the first 1000 primes: >>> sum(first(Primes(), 1000)) 3682913 PrimesGenerator(n=None, array=<type 'bytearray'>, fn=<function <lambda>>) provided for backwatds compatability. use Primes() instead, Rational(src=None, verbose=None) select a class for representing rationals. >> F = Rational(verbose=1) [Rational: using gmpy2.mpq] >> F = Rational(src="fractions.Fraction", verbose=1) [Rational: using fractions.Fraction] T(n) T(n) is the nth triangular number. T(n) = n * (n + 1) // 2. >>> T(1) 1 >>> T(100) 5050 all_different = is_pairwise_distinct(*args) check all arguments are pairwise distinct >>> is_pairwise_distinct(0, 1, 2, 3) True >>> is_pairwise_distinct(2, 1, 2, 3) False >>> is_pairwise_distinct('h', 'e', 'l', 'l', 'o') False all_same(*args, **kw) check all arguments have the same value >>> all_same(1, 2, 3) False >>> all_same(1, 1, 1, 1, 1, 1) True >>> all_same() True arg(v, n, fn=<function identity>, prompt=None, argv=None) if command line argument <n> is specified return fn(argv[n]) otherwise return default value <v> if argv is None (the default), then the value of sysv.argv[1:] is used >>> arg(42, 0, int, argv=['56']) 56 >>> arg(42, 1, int, argv=['56']) 42 args(vs, n, fn=<function identity>, prompt=None, argv=None) # get a list of similar arguments # if no arguments are collected the value of <vs> is returned argv = get_argv(force=0, args=None) # fetch command line arguments from sys as_int(x, include='') can argument <x> be treated as an integer? <include> can be used to restrict the allowed range, by specifying one or more of: + = allow positive integers - = allow negative integers 0 = allow zero so things like this work: as_int(0) --> 0 as_int(42) --> 42 as_int(42.0) --> 42 as_int(Fraction(129, 3)) --> 43 as_int(sympy.Integer(42)) --> 42 as_int(sympy.Float(42.0)) --> 42 as_int(sympy.rational(129, 3)) --> 43 and things like this raise an error: as_int("42") as_int(42.5) as_int(Fraction(129, 2)) as_int(42+0j) as_int(42, include="-") as_int(0, include="+") base2int(s, base=10, strip=0, digits=None) convert a string representation of an integer in the specified base to an integer. >>> base2int('-42') -42 >>> base2int('xyzzy', base=3, digits='zyx') 190 >>> base2int('HELLO', base=36) 29234652 base_digits(*args) get or set the default string of digits used to represent numbers. with no arguments the current string of digits is returned. with an argument the current string is set, and the new string returned, if the argument is None (or any non-True value) then the standard default string is used (0-9 then A-Z). NOTE: this is a global setting and will affect all subsequent base conversions. bit_permutations(a, b=None) generate numbers in order that have the same number of bits set in their binary representation. numbers start at <a> and are generated while they are smaller than <b>. to generate all numbers with k bits start start with: a = 2 ** k - 1 a = (1 << k) - 1 >>> list(bit_permutations(3, 20)) [3, 5, 6, 9, 10, 12, 17, 18] >>> first(bit_permutations(1), 11) [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] cached(f) return a cached version of function <f>. catch(fn, *args, **kw) evaluate the function with the given arguments, but if it throws an exception return None instead. >>> catch(divmod, 7, 0) is None True cbrt(x) Return the cube root of a number (as a float). >>> cbrt(27.0) 3.0 >>> cbrt(-27.0) -3.0 cdiv = divc(a, b) ceiling division. always returns an int. >>> divc(100, 10) 10 >>> divc(101, 10) 11 >>> divc(101.1, 10) 11 >>> divc(4.5, 1) 5 ceil(x, m=1) return lowest multiple of m, not less than x chain(*s, **kw) a convenience function for calling flatten(): chain(a, b, c, ...) = flatten([a, b, c, ...], fn=iter) >>> chain("abc", (1, 2, 3), None, [4, 5, 6], fn=tuple) ('a', 'b', 'c', 1, 2, 3, 4, 5, 6) choose(vs, fns, s=None, distinct=0) choose values from <vs> satisfying <fns> in turn. if all values are acceptable then a value of None can be passed in <fns>. set 'distinct' if all values should be distinct. >>> list(choose([1, 2, 3], [None, (lambda a, b: abs(a - b) == 1), (lambda a, b, c: abs(b - c) == 1)])) [[1, 2, 1], [1, 2, 3], [2, 1, 2], [2, 3, 2], [3, 2, 1], [3, 2, 3]] chunk(s, n=2, pad=0, value=None, fn=<type 'tuple'>) iterate through iterable <s> in chunks of size <n>. (for overlapping tuples see tuples()) >>> list(chunk(irange(1, 8))) [(1, 2), (3, 4), (5, 6), (7, 8)] >>> list(chunk(irange(1, 8), 3)) [(1, 2, 3), (4, 5, 6), (7, 8)] clock(m) like mod(m) except instead of 0 the function returns <m>. >>> list(map(clock(12), irange(0, 23))) [12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] collect(s, accept=None, reject=None, every=0, fn=<type 'list'>) collect items from sequence <s> that are accepted by the <accept> function (if defined), and not rejected by the <reject> function (if defined). return the items that pass the tests (using <fn>) if every=1 then every item must be collected, otherwise None is returned. compare(a, b, vs=None) return -1 if a < b, 0 if a == b and +1 if a > b. >>> compare(42, 0) 1 >>> compare(0, 42) -1 >>> compare(42, 42) 0 >>> compare('evil', 'EVIL') 1 concat(*args, **kw) return a string consisting of the concatenation of the elements of the sequence <args>. the elements will be converted to strings (using str(x)) before concatenation. you can use it instead of str.join() to join non-string lists by specifying a 'sep' argument. >>> concat('h', 'e', 'l', 'l', 'o') 'hello' >>> concat(1, 2, 3, 4, 5) '12345' >>> concat(1, 2, 3, 4, 5, sep=',') '1,2,3,4,5' contains(seq, subseq) return the position in <seq> that <subseq> occurs as a contiguous subsequence or -1 if it is not found >>> contains("abcdefghijkl", "def") 3 >>> contains("abcdefghijkl", "hik") -1 >>> contains(Primes(), [11, 13, 17, 19]) 4 >>> contains([1, 2, 3], [1, 2, 3]) 0 >>> contains([1, 2, 3], []) 0 coprime_pairs(n=None, order=0) generate coprime pairs (a, b) with 0 < a < b =< n. the list is complete and no element appears more than once. if n is not specified then pairs will be generated indefinitely. if n is specified then farey() can be used instead to generate coprime pairs in numerical order (when considered as fractions). if order=1 is specified then the pairs will be produced in order. >>> sorted(p for p in coprime_pairs(20) if sum(p) == 20) [(1, 19), (3, 17), (7, 13), (9, 11)] >>> list(coprime_pairs(6, order=1)) [(1, 2), (1, 3), (2, 3), (1, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5), (1, 6), (5, 6)] cslice(x) generate an iterator that is the cumulative slices of an array. >>> list(cslice([1, 2, 3])) [[1], [1, 2], [1, 2, 3]] >>> list(cslice('python')) ['p', 'py', 'pyt', 'pyth', 'pytho', 'python'] csum(i, s=0, fn=<built-in function add>) generate an iterator that is the cumulative sum of an iterator. >>> list(csum(irange(1, 10))) [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] >>> list(csum(irange(1, 10), fn=operator.mul, s=1)) [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800] >>> list(csum('python', s='')) ['p', 'py', 'pyt', 'pyth', 'pytho', 'python'] cube = is_cube(n) check positive integer <n> is a perfect cube. >>> is_cube(27) 3 >>> is_cube(49) is not None False >>> is_cube(0) 0 derangements(s, k=None) # a simple implementation of derangements diff(a, b, *rest) return the subsequence of <a> that excludes elements in <b>. >>> diff((1, 2, 3, 4, 5), (3, 5, 2)) (1, 4) >>> join(diff('newhampshire', 'wham')) 'nepsire' digit_map(a=0, b=9, digits=None) create a map (dict) mapping individual digits to their numerical value. the symbols used for the digits can be provided, otherwise the default list set via base_digits() is used >>> digit_map(1, 3) == { '1': 1, '2': 2, '3': 3 } True digrt(n, base=10) return the digital root of positive integer <n>. >>> digrt(123456789) 9 >>> digrt(sum([1, 2, 3, 4, 5, 6, 7, 8, 9])) 9 >>> digrt(factorial(100)) 9 distinct = is_distinct(value, *args) check <value> is distinct from values in <args> >>> is_distinct(0, 1, 2, 3) True >>> is_distinct(2, 1, 2, 3) False >>> is_distinct('h', 'e', 'l', 'l', 'o') True distinct_values(s, n=None) # <s> has <n> distinct values div(a, b) returns (a // b) if b exactly divides a, otherwise None >>> div(1001, 13) 77 >>> bool(div(101, 13)) False >>> div(42, 0) is None True divc(a, b) ceiling division. always returns an int. >>> divc(100, 10) 10 >>> divc(101, 10) 11 >>> divc(101.1, 10) 11 >>> divc(4.5, 1) 5 divf(a, b) floor division. (similar to Python's a // b). always returns an int. >>> divf(100, 10) 10 >>> divf(101, 10) 10 >>> divf(101.1, 10) 10 >>> divf(4.5, 1) 4 divisor(n) generate divisors of positive integer <n> in numerical order. >>> list(divisor(36)) [1, 2, 3, 4, 6, 9, 12, 18, 36] >>> list(divisor(101)) [1, 101] divisor_pairs(n) generate divisors (a, b) of positive integer n, such that a =< b and a * b = n. the pairs are generated in order of increasing <a>. if you only want a few small divisors, this routine is OK, otherwise you are probably better using divisors_pairs(). >>> list(divisor_pairs(36)) [(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)] >>> list(divisor_pairs(101)) [(1, 101)] divisors(n, fn=<function prime_factor>) return the divisors of positive integer <n> as a sorted list. >>> divisors(36) [1, 2, 3, 4, 6, 9, 12, 18, 36] >>> divisors(101) [1, 101] divisors_pairs(n, fn=<function prime_factor>) generate divisors pairs (a, b) with a =< b, such that a * b = n. pairs are generated in order, by determining the factors of n. this is probably faster than divisor_pairs() if you want all divisors. drop_factors(n, k) remove factors of <k> from <n>. return (i, m) where n = (m)(k^i) such that m is not divisible by k dsum(n, k=None, base=10) calculate the digit sum of an integer (when represented in the specified base). the sign of the integer is ignored >>> dsum(123456789) 45 >>> dsum(123456789, base=2) 16 dsum2 lambda n # population count, Hamming weight, bitsum(), bit_count() duplicate = is_duplicate(*s) check to see if arguments (as strings) contain duplicate characters. >>> is_duplicate("hello") True >>> is_duplicate("world") False >>> is_duplicate(99 ** 2) False ediv(a, b) return (a // b) if b exactly divides a, otherwise raise a ValueError. egcd(a, b) Extended Euclidean Algorithm (on positive integers). returns integers (x, y, g) = egcd(a, b) where ax + by = g = gcd(a, b) Note that x and y are not necessarily positive integers. >>> egcd(120, 23) (-9, 47, 1) express(t, ds, qs=None, min_q=0, s=[]) express total <t> using denominations <ds>. optional: using quantities chosen from <qs> or: minimum quantity <min_q> <ds> and <qs> should be increasing sequences. generated values are the quantaties for each denomination in <ds>. >>> list(express(20, (3, 5, 7))) [[0, 4, 0], [1, 2, 1], [2, 0, 2], [5, 1, 0]] >>> list(express(20, (3, 5, 7), min_q=1)) [[1, 2, 1]] >>> list(express(20, (3, 5, 7), qs=(0, 1, 2))) [[1, 2, 1], [2, 0, 2]] the number of ways to change 1 pound into smaller coins >>> icount(express(100, (1, 2, 5, 10, 20, 50))) 4562 express_denominations(t, ds, min_q=0, s=[]) # express total <t> using denominations <ds>, min quantity <min_q> express_quantities(t, ds, qs, s=[]) # express total <t> using denominations <ds>, quantities chosen from <qs> factor(n, fn=<function prime_factor>) return a list of the prime factors of positive integer <n>. for integers less than 1, None is returned. The <fn> parameter is used to generate the prime factors of the number. (Defaults to using prime_factor()). >>> factor(101) [101] >>> factor(1001) [7, 11, 13] >>> factor(12) [2, 2, 3] >>> factor(125) [5, 5, 5] factorial(a, b=1) return a!/b!. >>> factorial(6) 720 >>> factorial(10, 7) 720 farey(n) generate the Farey sequence F(n) - the sequence of coprime pairs (a, b) where 0 < a < b =< n. pairs are generated in numerical order when considered as fractions a/b. the pairs (0, 0) and (1, 1) usually present at the start and end of the sequence are not generated by this function. >>> list(p for p in farey(20) if sum(p) == 20) [(1, 19), (3, 17), (7, 13), (9, 11)] fcompose(f, *gs) forward functional composition ("and then") fcompose(f, g, h)(x) == h(g(f(x))) >>> fcompose(is_square, is_not_none)(49) True >>> fcompose(is_square, is_not_none)(50) False fdiv(a, b) float result of <a> divided by <b>. >>> fdiv(3, 2) 1.5 >>> fdiv(9, 3) 3.0 fib(*s, **kw) generate Fibonacci type sequences. The initial k terms are provided as sequence s, subsequent terms are calculated as a function of the preceeding k terms. The default function being 'sum', but a different function can be specified using the 'fn' parameter (which should be a function that takes a sequence of k terms and computes the appropriate value). Standard Fibonacci numbers (OEIS A000045): >>> first(fib(0, 1), 10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] Lucas numbers (OEIS A000032): >>> first(fib(2, 1), 10) [2, 1, 3, 4, 7, 11, 18, 29, 47, 76] Tribonacci numbers (OEIS A001590): >>> first(fib(0, 1, 0), 10) [0, 1, 0, 1, 2, 3, 6, 11, 20, 37] Powers of 2 (using addition): >>> first(fib(1, fn=unpack(lambda x: x + x)), 10) [1, 2, 4, 8, 16, 32, 64, 128, 256, 512] filter2(p, i, fn=<type 'list'>) use a predicate to partition an iterable into those elements that satisfy the predicate, and those that do not. returns the partition of the original sequence as: (<values for which p is true>, <values for which p is false>) which can calso be accessed from return value r as: r.true r.false alias: partition() >>> tuple(filter2(lambda n: n % 2 == 0, irange(1, 10))) ([2, 4, 6, 8, 10], [1, 3, 5, 7, 9]) filter_unique(s, f=<function identity>, g=<function identity>) for every object, x, in sequence, s, consider the map f(x) -> g(x) and return a partition of s into those objects where f(x) implies a unique value for g(x), and those objects where f(x) implies multiple values for g(x). returns the partition of the original sequence as: (<unique values>, <non-unique values>) which can also be accessed from return value r as: r.unique r.non_unique See: Enigma 265 <https://enigmaticcode.wordpress.com/2015/03/14/enigma-265-the-parable-of-the-wise-fool/#comment-4167> alias: partition_unique() "If I told you the first number you could deduce the second" >>> filter_unique([(1, 1), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3)], (lambda v: v[0])).unique [(2, 1)] "If I told you the first number you could not deduce if the second was odd or even" >>> filter_unique([(1, 1), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3)], (lambda v: v[0]), (lambda v: v[1] % 2)).non_unique [(3, 1), (3, 2), (3, 3)] find(s, v) find the first index of a value in a sequence, return -1 if not found. for a string it works like str.find() (for single characters) >>> find('abc', 'b') 1 >>> find('abc', 'z') -1 but it also works on lists >>> find([1, 2, 3], 2) 1 >>> find([1, 2, 3], 7) -1 and on iterators in general (don't try this with a non-prime value) >>> find(Primes(), 10007) 1229 Note that this function works by attempting to use the index() method of the sequence. If it implements index() in a non-compatible way this function won't work. find_max(f, a, b, t=1e-09) find the maximum value of a (well behaved) function over an interval. f = function to maximise (should take a single float argument) a, b = the interval to maximise over (a < b) t = the tolerance to work to the result is returned as a record with the following fields: v = the calculated value at which the function is maximised fv = the value of the function at v t = the tolerance used >>> r = find_max(lambda x: 9 - (x - 2) ** 2, 0.0, 10.0) >>> round(r.v, 6) 2.0 find_min(f, a, b, t=1e-09, m=None) find the minimum value of a (well behaved) function over an interval. f = function to minimise (should take a single float argument) a, b = the interval to minimise over (a < b) t = the tolerance to work to m = the metric we want to minimise (default is None = the value of the function) the result is returned as a record with the following fields: v = the calculated value at which the function is minimised fv = the value of the function at v t = the tolerance used >>> r = find_min(lambda x: (x - 2) ** 2, 0.0, 10.0) >>> round(r.v, 6) 2.0 find_value(f, v, a, b, t=1e-09, ft=1e-06) find the value of a (well behaved) function over an interval. f = function to find the value of (should take a single float argument) a, b = the interval to search over (a < b) t = the tolerance to work to the result is returned as a record with the following fields: v = the calculated value at which the function is the specified value fv = the value of the function at v t = the tolerance used >>> r = find_value(lambda x: x ** 2 + 4, 8.0, 0.0, 10.0) >>> round(r.v, 6) 2.0 find_zero(f, a, b, t=1e-09, ft=1e-06) find the zero of a (well behaved) function over an interval. f = function to find the zero of (should take a single float argument) a, b = the interval to maximise over (a < b) t = the tolerance to work to the result is returned as a record with the following fields: v = the calculated value at which the function is zero fv = the value of the function at v t = the tolerance used >>> r = find_zero(lambda x: x ** 2 - 4, 0.0, 10.0) >>> round(r.v, 6) 2.0 >>> r = find_zero(lambda x: x ** 2 + 4, 0.0, 10.0) # doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last): ... ValueError: Value not found first(i, count=1, skip=0, fn=<type 'list'>) return the first <count> items in iterator <i> (skipping the initial <skip> items) as a list (or other object specified by <fn>). <count> can be a callable object, in which case items are collected from <i> while <count> returns a true value when it is passed each item (after skipping the first <skip> items). <skip> can also be a callable, in which case items are skipped while <skip> returns a true value when it is passed each item. this would be a way to find the first 10 primes: >>> first((n for n in irange(1, inf) if is_prime(n)), count=10) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] >>> first(p for p in Primes() if p % 17 == 1) [103] flatten(s, fn=<type 'list'>) flatten a list of lists (actually an iterator of iterators). the function: chain(*s) = flatten(s) is provided as a convenience. >>> flatten([[1, 2], [3, 4, 5], [6, 7, 8, 9]]) [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> flatten(((1, 2), (3, 4, 5), (6, 7, 8, 9)), fn=tuple) (1, 2, 3, 4, 5, 6, 7, 8, 9) >>> flatten([['abc'], ['def', 'ghi']]) ['abc', 'def', 'ghi'] flattened(s, depth=None, test=<function _flatten_test>, fn=None) fully flatten a nested structure <s> (to depth <depth>, default is to fully flatten). <test> can be used to determine how objects are flattened, it should return either - None, if the object is not to be flattened, or - an iterable of objects representing one level of flattening default behaviour is to flatten sequences other than strings >>> list(flattened([[1, [2, [3, 4, [5], [[]], [[6, 7], 8], [[9]]]], []]])) [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> list(flattened([[1, [2, [3, 4, [5], [[]], [[6, 7], 8], [[9]]]], []]], depth=3)) [1, 2, 3, 4, [5], [[]], [[6, 7], 8], [[9]]] >>> list(flattened([['abc'], ['def', 'ghi']])) ['abc', 'def', 'ghi'] >>> flattened(42) 42 floor(x, m=1) return largest multiple of m, not greater than x format_recurring(*args, **kw) format the (i, nr, rr) return from recurring() as a string >>> format_recurring(recurring(1, 7)) '0.(142857)...' >>> format_recurring(recurring(3, 2)) '1.5' >>> format_recurring(recurring(3, 2, recur=1)) '1.4(9)...' >>> format_recurring(recurring(5, 17, base=16)) '0.(4B)...' fraction(a, b, *rest) return the numerator and denominator of the fraction a/b in lowest terms if more than 2 arguments are specified the sum of the arguments as (numerator, denominator) pairs is determined, so: fraction(a, b, c, d, e, f, ...) -> a/b + c/d + e/f + ... >>> fraction(286, 1001) (2, 7) >>> fraction(1, 2, 1, 3, 1, 6) (1, 1) >>> fraction(1, 2, 3, 4, 5, 6) (25, 12) gcd(a, b) greatest common divisor (on positive integers). >>> gcd(123, 456) 3 >>> gcd(5, 7) 1 gensym(x) generate a unique string starting with <x>. >> gensym('foo') 'foo1' >> gensym('foo') 'foo2' get_argv(force=0, args=None) # fetch command line arguments from sys grid_adjacency(n, m, deltas=None, include_adjacent=1, include_diagonal=0, include_self=0) this function generates the adjacency matrix for a grid with n columns and m rows, represented by a linear array of size n*m the element in the (i, j)th position in the grid is at index (i + n*j) in the array it returns an array, where the entry at index k is a list of indices into the linear array that are adjacent to the square at index k. the default behaviour is to treat the squares immediately N, S, E, W of the target square as being adjacent, although this can be controlled with the 'deltas' parameter, it can be specified as a list of (x, y) deltas to use instead. if 'deltas' is not specified the 'include_adjacent', 'include_diagonal' and 'include_self' flags are used to specify which squares are adjacent to the target square. 'include_adjacent' includes the N, S, E, W squares 'include_diagonal' includes the NW, NE, SW, SE squares 'include_self' includes the square itself >>> grid_adjacency(2, 2) [[1, 2], [0, 3], [0, 3], [1, 2]] >>> sorted(grid_adjacency(3, 3)[4]) [1, 3, 5, 7] >>> sorted(grid_adjacency(3, 3, include_diagonal=1)[4]) [0, 1, 2, 3, 5, 6, 7, 8] group(s, by=<function identity>, st=None, fn=<function identity>) group the items of sequence <s> together using the <by> function. items in the same group return the same value when passed to <by>. if the <st> function is specified, only items that satisfy it will be considered. a dict() is returned where the keys of the dict are the values of the <by> function applied to the items of the sequence, and the values of the dict are the grouped items (collected using <fn>, which by default will collect the items in a list, in the order of the original sequence <s>). >>> group(irange(0, 9), by=mod(2)) {0: [0, 2, 4, 6, 8], 1: [1, 3, 5, 7, 9]} gss_minimiser = find_min(f, a, b, t=1e-09, m=None) find the minimum value of a (well behaved) function over an interval. f = function to minimise (should take a single float argument) a, b = the interval to minimise over (a < b) t = the tolerance to work to m = the metric we want to minimise (default is None = the value of the function) the result is returned as a record with the following fields: v = the calculated value at which the function is minimised fv = the value of the function at v t = the tolerance used >>> r = find_min(lambda x: (x - 2) ** 2, 0.0, 10.0) >>> round(r.v, 6) 2.0 hypot(*vs) return hypotenuse of a right angled triangle with shorter sides <a> and <b>. hypot(a, b) = sqrt(a**2 + b**2) >>> hypot(3.0, 4.0) 5.0 icount(i, p=None, t=None) count the number of elements in iterator <i> that satisfy predicate <p>, the termination limit <t> controls how much of the iterator we visit, so we don't have to count all occurrences. So, to find if exactly <n> elements of <i> satisfy <p> use: icount(i, p, n + 1) == n which is what icount_exactly(i, p, n) does. This will examine all elements of <i> to verify there are exactly 4 primes less than 10: >>> icount_exactly(irange(1, 10), is_prime, 4) True But this will stop after testing 73 (the 21st prime): >>> icount_exactly(irange(1, 100), is_prime, 20) False To find if at least <n> elements of <i> satisfy <p> use: icount(i, p, n) == n This is what icount_at_least(i, p, n) does. The following will stop testing at 71 (the 20th prime): >>> icount_at_least(irange(1, 100), is_prime, 20) True To find if at most <n> elements of <i> satisfy <p> use: icount(i, p, n + 1) < n + 1 This is what icount_at_most(i, p, n) does. The following will stop testing at 73 (the 21st prime): >>> icount_at_most(irange(1, 100), is_prime, 20) False If p is not specified a function that always returns True is used, so you can use this function to count the number of items in a (finite) iterator: >>> icount(Primes(1000)) 168 icount_at_least lambda i, p, n icount_at_most lambda i, p, n icount_exactly lambda i, p, n # icount recipes identity(x) the identity function: identity(x) == x implies(p, q) logical implication: (p -> q) = (not(p) or q) >>> list(p for p in irange(1, 100) if not implies(is_prime(p), p % 6 in (1, 5))) [2, 3] int2base(i, base=10, width=None, pad=None, group=None, sep=',', digits=None) convert an integer <i> to a string representation in the specified base <base>. if the <width> parameter is specified the number of digits will be padded to value of <width> using the <pad> character. if <width> is positive pad characters will be added on the left, if negative they are added on the right. The default pad character is the digit 0. if the <group> parameter is specified the digits are grouped into blocks of <group> digits and separated by the string <sep> (this happens after the digits are padded to any specified <width>). if <group> is positive the groups start from the right, if negative they start from the left. By default this routine only handles single digits up 36 in any given base, but the <digits> parameter can be specified to give the symbols for larger bases. And if the error=1 parameter is given then invalid digits will be substituted with"<n>", where n is the digit value in decimal. >>> int2base(-42) '-42' >>> int2base(3735928559, base=16) 'DEADBEEF' >>> int2base(-3735928559, base=16, digits='0123456789abcdef') '-deadbeef' >>> int2base(190, base=3, digits='zyx') 'xyzzy' >>> int2base(29234652, base=36) 'HELLO' >>> int(int2base(123456, base=14), base=14) 123456 >>> int2base(84, base=2, width=9, group=3, sep="_") '001_010_100' int2bcd(n, base=10, bits_per_digit=4) convert integer n into BCD (Binary Coded Decimal) the base and bits_per_integer can be specified (if desired) >>> int2bcd(123456) 1193046 >>> int2bcd(123456) == 0x123456 True int2roman(x) return a representation of an integer <x> (from 1 to 4999) as a Roman Numeral >>> int2roman(4) 'IV' >>> int2roman(1999) 'MCMXCIX' int2words(n, scale='short', sep='', hyphen=' ', lang='en') convert an integer <n> to a string representing the number in English. scale - 'short' (for short scale numbers), or 'long' (for long scale numbers) sep - separator between groups hyphen - separator between tens and units >>> int2words(1234) 'one thousand two hundred and thirty four' >>> int2words(-7) 'minus seven' >>> int2words(factorial(13)) 'six billion two hundred and twenty seven million twenty thousand eight hundred' >>> int2words(factorial(13), sep=',') 'six billion, two hundred and twenty seven million, twenty thousand, eight hundred' >>> int2words(factorial(13), sep=',', hyphen='-') 'six billion, two hundred and twenty-seven million, twenty thousand, eight hundred' >>> int2words(factorial(13), scale='long') 'six thousand two hundred and twenty seven million twenty thousand eight hundred' intc(x) ceiling conversion (smallest integer not less than x) of float to int. >>> intc(1.0) 1 >>> intc(1.5) 2 >>> intc(-1.5) -1 intersect(ss, fn=<type 'set'>) construct a set that is the intersection of the sequences in <ss>. intf(x) floor conversion (largest integer not greater than x) of float to int. >>> intf(1.0) 1 >>> intf(1.5) 1 >>> intf(-1.5) -2 invmod(n, m) return the multiplicative inverse of n mod m (or None if there is no inverse) e.g. the inverse of 2 (mod 9) is 5, as (2 * 5) % 9 = 1 >>> invmod(2, 9) 5 ipartitions(s, n) partition a sequence by index. >>> list(ipartitions((1, 0, 1, 0), 2)) [((1, 0), (1, 0)), ((1, 1), (0, 0)), ((1, 0), (0, 1))] irange(a, b=None, step=1) a range iterator that includes both integer endpoints, <a> and <b>. if only one value <n> is specified for the endpoints, then <n> values are produced suitable for indexing into an array of size <n> (so irange(n) produces n integers from 0 to n - 1). if <b> is specified as inf (or -inf for negative steps) the iterator generate will values indefinitely. >>> list(irange(1, 9)) [1, 2, 3, 4, 5, 6, 7, 8, 9] >>> list(irange(9, 1, step=-1)) [9, 8, 7, 6, 5, 4, 3, 2, 1] >>> list(irange(0, 10, step=3)) [0, 3, 6, 9] >>> list(irange(10)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> list(irange(10, step=-1)) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] irangef(a, b, step=1) inclusive range iterator that allows the endpoints and the step to be fractional values. >>> list(irangef(1, 2.5, step=0.5)) [1.0, 1.5, 2.0, 2.5] iroot(n, k) compute the largest integer x such that x^k =< n. i.e. x is the integer k-th root of n. it is the exact root if: (x ** k == n) (which is what is_power() does) is_coprime(a, b) is_cube(n) check positive integer <n> is a perfect cube. >>> is_cube(27) 3 >>> is_cube(49) is not None False >>> is_cube(0) 0 is_cube_p lambda *args, **kw is_distinct(value, *args) check <value> is distinct from values in <args> >>> is_distinct(0, 1, 2, 3) True >>> is_distinct(2, 1, 2, 3) False >>> is_distinct('h', 'e', 'l', 'l', 'o') True is_duplicate(*s) check to see if arguments (as strings) contain duplicate characters. >>> is_duplicate("hello") True >>> is_duplicate("world") False >>> is_duplicate(99 ** 2) False is_equal(x, y) is_equal(x, y) is the same as (x == y) >>> is_equal(1, 2) False >>> is_equal(42, 42) True >>> is_equal([1, 2, 3], (1, 2, 3)) False is_multiple = div(a, b) returns (a // b) if b exactly divides a, otherwise None >>> div(1001, 13) 77 >>> bool(div(101, 13)) False >>> div(42, 0) is None True is_not_none lambda x is_pairwise_distinct(*args) check all arguments are pairwise distinct >>> is_pairwise_distinct(0, 1, 2, 3) True >>> is_pairwise_distinct(2, 1, 2, 3) False >>> is_pairwise_distinct('h', 'e', 'l', 'l', 'o') False is_palindrome(s) check to see if sequence <s> is palindromic. >>> is_palindrome([1, 2, 3, 2, 1]) True >>> is_palindrome("ABBA") True >>> first(n for n in irange(0, inf) if not is_palindrome(nsplit(11 ** n))) [5] is_power(n, k) check positive integer <n> is a perfect <k>th power of some integer. if <n> is a perfect <k>th power, returns the integer <k>th root. if <n> is not a perfect <k>th power, returns None. >>> is_power(49, 2) 7 >>> is_power(49, 3) is not None False >>> is_power(0, 2) 0 >>> n = (2 ** 60 + 1) >>> (is_power(n ** 2, 2) is not None, is_power(n ** 2 + 1, 2) is not None) (True, False) >>> (is_power(n ** 3, 3) is not None, is_power(n ** 3 + 1, 3) is not None) (True, False) is_power_of(n, k) check <n> is a power of <k>. returns <m> such that pow(k, m) = n or None. >>> is_power_of(128, 2) 7 >>> is_power_of(1, 2) 0 >>> is_power_of(0, 2) is None True >>> is_power_of(0, 0) 1 is_prime(n) return True if the positive integer <n> is prime. Note: for numbers up to 2^64 is_prime_mr() is a fast, accurate prime test. (And for larger numbers it is probabilistically accurate). >>> is_prime(101) True >>> is_prime(1001) False is_prime_mr(n, r=0) Miller-Rabin primality test for <n>. <r> is the number of random extra rounds performed for large numbers return value: 0 = the number is definitely not prime (definitely composite for n > 1) 1 = the number is probably prime 2 = the number is definitely prime for numbers less than 2^64, the prime test is completely accurate, and deterministic, the extra rounds are not performed. for larger numbers <r> additional rounds are performed, and if the number cannot be found to be composite a value of 1 (probably prime) is returned. confidence can be increased by using more additional rounds. >>> is_prime_mr(288230376151711813) 2 >>> is_prime_mr(316912650057057350374175801351) 1 >>> is_prime_mr(332306998946228968225951765070086171) 0 is_roman(x) check if a Roman Numeral <x> is valid. >>> is_roman('IV') True >>> is_roman('IIII') True >>> is_roman('XIVI') False is_square(n) check positive integer <n> is a perfect square. if <n> is a perfect square, returns the integer square root. if <n> is not a perfect square, returns None. >>> is_square(49) 7 >>> is_square(50) is not None False >>> is_square(0) 0 is_square_free(n, fn=<function prime_factor>) a positive integer is "square free" if it is not divisibly by a perfect square greater than 1. >>> is_square_free(8596) False >>> is_square_free(8970) True is_square_p lambda *args, **kw is_triangular(n) check positive integer <n> is a triangular number. if <n> is a triangular number, returns <i> such that T(i) == n. if <n> is not a triangular number, returns None. >>> is_triangular(5050) 100 >>> is_triangular(49) is not None False isqrt(n) calculate intf(sqrt(n)). >>> isqrt(9) 3 >>> isqrt(15) 3 >>> isqrt(16) 4 >>> isqrt(17) 4 join(s, sep='', enc='') join the items in sequence <s> as strings, separated by separator <sep>. the default separator is the empty string so you can just use: join(s) instead of: ''.join(s) >>> join(['a', 'b', 'cd']) 'abcd' >>> join(['a', 'b', 'cd'], sep=',') 'a,b,cd' >>> join([5, 700, 5]) '57005' lcm(a, b) lowest common multiple (on positive integers). >>> lcm(123, 456) 18696 >>> lcm(5, 7) 35 mP(d, n) # multiset permutations: # a bit like uniq(permutations(s, k)) but more efficient, however items # will not be generated in the same order # # there are more sophisticated algorithms, but this one does the job: # # >>> with Timer(): icount(uniq(subsets("mississippi", select="P"))) # 107899 # [timing] elapsed time: 68.9407666s (68.94s) # # >>> with Timer(): icount(subsets("mississippi", select="mP")) # 107899 # [timing] elapsed time: 0.5661372s (566.14ms) make_namespace(name, vs) map2str(m, sort=1, enc='()', sep=', ', arr='=') convert a map into a string (usually for output). the map may be a dict() type object or a collection of (key, value) pairs. >>> map2str(dict(a=1, b=2, c=3)) '(a=1, b=2, c=3)' >>> map2str(multiset("banana")) '(a=3, b=1, n=2)' >>> map2str(zip("abc", irange(1, 3))) '(a=1, b=2, c=3)' match(v, t) match a value (as a string) to a template (see fnmatch.fnmatch). to make matching numbers easier if the template starts with a minus sign ('-') then so must the value. if the template starts with a plus sign ('+') then the value must not start with a minus sign. so to match a 4-digit positive number use '+????' as a template. >>> match("abcd", "?b??") True >>> match("abcd", "a*") True >>> match("abcd", "?b?") False >>> match(1234, '+?2??') True >>> match(-1234, '-??3?') True >>> match(-123, '???3') True mcombinations(s, k=None) mgcd(a, *rest) GCD of multiple (two or more) integers. >>> mgcd(123, 456) 3 >>> mgcd(123, 234, 345, 456, 567, 678, 789) 3 >>> mgcd(11, 37, 228) 1 >>> mgcd(56, 65, 671) 1 mlcm(a, *rest) LCM of multiple (two or more) integers. >>> mlcm(2, 3, 5, 9) 90 mod(m) return a function to compute residues modulo <m>. >>> list(map(mod(2), irange(0, 9))) [0, 1, 0, 1, 0, 1, 0, 1, 0, 1] mpermutations(s, k=None) multiples(ps) given a list of (<m>, <n>) pairs, return all numbers that can be formed by multiplying together the <m>s, with each <m> occurring up to <n> times. the multiples are returned as a sorted list the practical upshot of this is that the divisors of a number <x> can be found using the expression: multiples(prime_factor(x)) >>> multiples(prime_factor(180)) [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180] multiply(s) return the product of the sequence <s>. >>> multiply(range(1, 7)) 720 >>> multiply([2] * 8) 256 nconcat(*digits, **kw) return an integer consisting of the concatenation of the list <digits> of single digits the digits can be specified as individual arguments, or as a single argument consisting of a sequence of digits. >>> nconcat(1, 2, 3, 4, 5) 12345 >>> nconcat([1, 2, 3, 4, 5]) 12345 >>> nconcat(13, 14, 10, 13, base=16) 57005 >>> nconcat(123,456,789, base=1000) 123456789 >>> nconcat([127, 0, 0, 1], base=256) 2130706433 ndigits(n, base=10) return the number of digits in a number, when represented in the specified base. >>> ndigits(factorial(70)) 101 nreverse(n, base=10) reverse an integer (using base <base> representation) >>> nreverse(12345) 54321 >>> nreverse(-12345) -54321 >>> nreverse(0xedacaf, base=16) == 0xfacade True >>> nreverse(100) 1 nsplit(n, k=None, base=10, fn=<type 'tuple'>) split an integer into digits (using base <base> representation) if <k> is specified it gives the number of digits to return, if the number has too few digits the the result is zero padded at the beginning, if the number has too many digits then the result includes only the rightmost digits. the sign of the integer is ignored. >>> nsplit(12345) (1, 2, 3, 4, 5) >>> nsplit(57005, base=16) (13, 14, 10, 13) >>> nsplit(123456789, base=1000) (123, 456, 789) >>> nsplit(2130706433, base=256) (127, 0, 0, 1) >>> nsplit(7, 3) (0, 0, 7) >>> nsplit(111 ** 2, 3) (3, 2, 1) nsplitter(n, k=None, base=10) # split n into digits, starting with the least significant number(s, base=10) make an integer from a string, ignoring non-digit characters >>> number('123,456,789') 123456789 >>> number('100,000,001') 100000001 >>> number('-1,024') -1024 >>> number('DEAD.BEEF', base=16) == 0xdeadbeef True ordered(*args, **kw) return args as a tuple in order. this is useful for making a key for a dictionary. >>> ordered(2, 1, 3) (1, 2, 3) >>> ordered(2, 1, 3, reverse=1) (3, 2, 1) pairwise_distinct = is_pairwise_distinct(*args) check all arguments are pairwise distinct >>> is_pairwise_distinct(0, 1, 2, 3) True >>> is_pairwise_distinct(2, 1, 2, 3) False >>> is_pairwise_distinct('h', 'e', 'l', 'l', 'o') False parsefile(path, args=None, interleave=None) partition = filter2(p, i, fn=<type 'list'>) use a predicate to partition an iterable into those elements that satisfy the predicate, and those that do not. returns the partition of the original sequence as: (<values for which p is true>, <values for which p is false>) which can calso be accessed from return value r as: r.true r.false alias: partition() >>> tuple(filter2(lambda n: n % 2 == 0, irange(1, 10))) ([2, 4, 6, 8, 10], [1, 3, 5, 7, 9]) partition_unique = filter_unique(s, f=<function identity>, g=<function identity>) for every object, x, in sequence, s, consider the map f(x) -> g(x) and return a partition of s into those objects where f(x) implies a unique value for g(x), and those objects where f(x) implies multiple values for g(x). returns the partition of the original sequence as: (<unique values>, <non-unique values>) which can also be accessed from return value r as: r.unique r.non_unique See: Enigma 265 <https://enigmaticcode.wordpress.com/2015/03/14/enigma-265-the-parable-of-the-wise-fool/#comment-4167> alias: partition_unique() "If I told you the first number you could deduce the second" >>> filter_unique([(1, 1), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3)], (lambda v: v[0])).unique [(2, 1)] "If I told you the first number you could not deduce if the second was odd or even" >>> filter_unique([(1, 1), (1, 3), (2, 1), (3, 1), (3, 2), (3, 3)], (lambda v: v[0]), (lambda v: v[1] % 2)).non_unique [(3, 1), (3, 2), (3, 3)] partitions(s, n, pad=0, value=None, distinct=None) partition a sequence <s> into subsequences of length <n>. if <pad> is True then the sequence will be padded (using <value>) until its length is a integer multiple of <n>. if sequence <s> contains distinct elements then <distinct> can be set to True, if it is not set then <s> will be examined for repeated elements. >>> list(partitions((1, 2, 3, 4), 2)) [((1, 2), (3, 4)), ((1, 3), (2, 4)), ((1, 4), (2, 3))] peek(s, k=0, **kw) return an element of a container. empty containers return the specified 'default' value, or raise a ValueError. if k is specified the first k values chosen are discarded (so, for a sequence, you will get s[k]). note that if the container is an iterator, items will be consumed. >>> peek(set([1])) 1 >>> peek([1, 2, 3]) 1 >>> peek("banana") 'b' >>> peek("banana", 4) 'n' >>> peek(Primes(), 10) 31 >>> peek(p for p in Primes() if p % 17 == 1) 103 poly_add(p, q) # add two polynomials poly_derivative(p, k=1) # derivative of a polynomial poly_divmod(p, q, div=None) # divide two polynomials # div() is used for coefficient division, if the leading coefficient of q is not 1 # (you probably want to use a rational implementation such as fractions.Fraction) poly_drop_factor(p, *qs) # drop factors in qs from polynomial p poly_from_pairs(ps, p=None) # make a polynomial from (exponent, coefficient) pairs # (we can use enumerate() to reverse the process) poly_interpolate(ps) # polynomial interpolation from a number of points poly_map(p, fn) # map a function over the coefficients of a polynomial poly_mul(p, q) # we can multiply two polynomials poly_multiply(*ps) # and multiply any number of polynomials poly_neg(p) # negate a polynomial poly_pow(p, n) # and raise a polynomial to a (positive) integer power poly_print(p) # print a polynomial in a more friendly form poly_rational_roots(p, domain='Q', include='+-0') find rational roots for the polynomial p (with rational coefficients). the type of roots returned can be controlled with the 'domain' and 'include' parameters: domain='Q' - find rational roots domain='Z' - find integer roots include='+' - include positive roots include='0' - include zero include='-' - include negative roots poly_sub(p, q) # subtract two polynomials poly_sum(*ps) # add any number of polynomials poly_trim(p) # remove extraneous zero coefficients poly_value(p, x) # evaluate a polynomial power = is_power(n, k) check positive integer <n> is a perfect <k>th power of some integer. if <n> is a perfect <k>th power, returns the integer <k>th root. if <n> is not a perfect <k>th power, returns None. >>> is_power(49, 2) 7 >>> is_power(49, 3) is not None False >>> is_power(0, 2) 0 >>> n = (2 ** 60 + 1) >>> (is_power(n ** 2, 2) is not None, is_power(n ** 2 + 1, 2) is not None) (True, False) >>> (is_power(n ** 3, 3) is not None, is_power(n ** 3 + 1, 3) is not None) (True, False) powers(a, b, k=2) generate powers (n ** k) for n in irange(a, b) >>> list(powers(1, 10)) [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] >>> list(powers(1, 10, 3)) [1, 8, 27, 64, 125, 216, 343, 512, 729, 1000] powerset = subsets(s, size=None, min_size=0, max_size=None, select='C', prepare=None, fn=<type 'tuple'>) generate tuples representing the subsequences of a (finite) iterator. 'min_size' and 'max_size' can be used to limit the size of the subsequences or 'size' can be specified to produce subsequences of a particular size. the way the elements of the subsequences are selected can be controlled with the 'select' parameter: 'C' = combinations (default) 'P' = permutations 'D' = derangements 'R' = combinations with replacement 'M' = product 'uC' = unique combinations 'mC' = multiset combinations 'mP' = multiset permutations or you can provide your own function. aliases: subseqs(), powerset(). >>> list(subsets((1, 2, 3))) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] >>> list(subsets((1, 2, 3), size=2, select='C')) [(1, 2), (1, 3), (2, 3)] >>> list(subsets((1, 2, 3), size=2, select='P')) [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] >>> list(subsets((1, 2, 3), size=2, select='R')) [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)] >>> list(subsets((1, 2, 3), size=2, select='M')) [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)] prime = is_prime(n) return True if the positive integer <n> is prime. Note: for numbers up to 2^64 is_prime_mr() is a fast, accurate prime test. (And for larger numbers it is probabilistically accurate). >>> is_prime(101) True >>> is_prime(1001) False prime_factor(n) generate (<prime>, <exponent>) pairs in the prime factorisation of positive integer <n>. no pairs are returned for 1 (or for non-positive integers). >>> list(prime_factor(60)) [(2, 2), (3, 1), (5, 1)] >>> list(prime_factor(factorial(12))) [(2, 10), (3, 5), (5, 2), (7, 1), (11, 1)] printf(fmt='', **kw) print format string <fmt> with interpolated local variables and keyword arguments. the final newline can be suppressed by ending the string with ''. >>> (a, b, c) = (1, 2, 3) >>> printf("a={a} b={b} c={c}") a=1 b=2 c=3 >>> printf("a={a} b={b} c={c}", c=42) a=1 b=2 c=42 product = multiply(s) return the product of the sequence <s>. >>> multiply(range(1, 7)) 720 >>> multiply([2] * 8) 256 pythagorean_triples(n=None, primitive=0, order=0) generate pythagorean triples (x, y, z) where x < y < z and x^2 + y^2 = z^2. n - maximum allowed hypotenuse (z) primitive - if set only primitive triples are generated order - if set triples are generated in order order is by shortest z, then shortest y, then shortest x (i.e. reverse lexicographic) if 'primitive' is set, then n can be None, and primitive triples will be generated indefinitely (although it will eventually run out of memory) >>> list(pythagorean_triples(20, primitive=0, order=1)) [(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)] >>> list(pythagorean_triples(20, primitive=1, order=1)) [(3, 4, 5), (5, 12, 13), (8, 15, 17)] >>> icount(pythagorean_triples(10000, primitive=1)) 1593 >>> icount(pythagorean_triples(10000, primitive=0)) 12471 quadratic(a, b, c, domain='Q') find roots of the equation: a.x^2 + b.x + c = 0 in the specified domain: "Z" finds integer solutions "Q" finds rational solutions "F" finds float solutions "C" finds complex solutions >>> sorted(quadratic(1, 1, -6, domain="Z")) [-3, 2] rational(*args, **kw) create an object representing a rational number. the class used is selected using Rational(), so for more control use: >> rational = Rational(verbose=1) or: >> rational = Rational(src="<preferred-implementations>", verbose=1) to see what implementation is being used. (or set the 'v' flag in the environment variable PY_ENIGMA). >>> rational(1, 49) * 49 == 1 True raw_input(...) raw_input([prompt]) -> string Read a string from standard input. The trailing newline is stripped. If the user hits EOF (Unix: Ctl-D, Windows: Ctl-Z+Return), raise EOFError. On Unix, GNU readline is used if enabled. The prompt string, if given, is printed without a trailing newline before reading. rcompose(*fns) reverse functional composition rcompose(f, g, h)(x) == f(g(h(x))) reciprocals(k, b=1, a=1, m=1, g=0) generate k whole numbers (d1, d2, ..., dk) such that 1/d1 + 1/d2 + ... + 1/dk = a/b the numbers are generated as an ordered list m = minimum allowed number g = minimum allowed gap between numbers e.g. sums of 3 reciprocals that sum to 1 1/2 + 1/3 + 1/6 = 1 1/2 + 1/4 + 1/4 = 1 1/3 + 1/3 + 1/3 = 1 >>> list(reciprocals(3, 1)) [[2, 3, 6], [2, 4, 4], [3, 3, 3]] recurring(a, b, recur=0, base=10, digits=None) find recurring representation of the fraction <a> / <b> in the specified base. return strings (<integer-part>, <non-recurring-part>, <recurring-part>) if you want rationals that normally terminate represented as non-terminating set <recur> >>> recurring(1, 7) ('0', '', '142857') >>> recurring(3, 2) ('1', '5', '') >>> recurring(3, 2, recur=1) ('1', '4', '9') >>> recurring(5, 17, base=16) ('0', '', '4B') reduce(...) reduce(function, sequence[, initial]) -> value Apply a function of two arguments cumulatively to the items of a sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). If initial is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty. repdigit(n, d=1, base=10) return a number consisting of the digit <d> repeated <n> times, in base <base> default digit is d=1 (to return repunits) default base is base=10 >>> repdigit(6) 111111 >>> repdigit(6, 7) 777777 >>> repdigit(6, 7, base=16) 7829367 >>> repdigit(6, 7, base=16) == 0x777777 True repeat(fn, v=0, k=inf) generate repeated applications of function <fn> to value <v>. >>> list(repeat((lambda x: x + 1), 0, 10)) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] rfind(s, v) find the last index of a value in a sequence, return -1 if not found. roman2int(x) return the integer value of a Roman Numeral <x>. >>> roman2int('IV') 4 >>> roman2int('IIII') 4 >>> roman2int('MCMXCIX') 1999 root lambda x, n # root: calculate the nth root of a (positive) number # we use math.pow rather than ** to avoid generating complex numbers rotate(s, k=1) rotate a sequence by moving <k> elements from the beginning to the end >>> rotate([1, 2, 3, 4], 1) [2, 3, 4, 1] >>> rotate([1, 2, 3, 4], -1) [4, 1, 2, 3] run(cmd, *args, **kw) run with command line arguments <cmd> can be a class in enigma.py that accepts a command line, or it can be a run file, Python program or other script <args> are the command line arguments to be provided additional options are: timed - if set, time the execution of <cmd> flags - 'p' = enable prompts, 'v' = enable verbose interpreter - interpreter to use seq_all_different(s) check all elements of <s> are pairwise distinct >>> seq_all_different([0, 1, 2, 3]) True >>> seq_all_different([2, 1, 2, 3]) False >>> seq_all_different(p % 100 for p in Primes()) False seq_all_same(s, **kw) >>> seq_all_same([1, 2, 3]) False >>> seq_all_same([1, 1, 1, 1, 1, 1]) True >>> seq_all_same([1, 1, 1, 1, 1, 1], value=4) False >>> seq_all_same(Primes(expandable=True)) False sigusr1 lambda pid # shortcuts to send signals sigusr2 lambda pid split(x, fn=None) split <x> into characters (which may be subsequently post-processed by <fn>). >>> split('hello') ['h', 'e', 'l', 'l', 'o'] >>> split(12345) ['1', '2', '3', '4', '5'] >>> list(split(12345, int)) [1, 2, 3, 4, 5] sprintf(fmt='', **kw) interpolate local variables and any keyword arguments into the format string <fmt>. >>> (a, b, c) = (1, 2, 3) >>> sprintf("a={a} b={b} c={c}") 'a=1 b=2 c=3' >>> sprintf("a={a} b={b} c={c}", c=42) 'a=1 b=2 c=42' sqrt(a, b=None) the (real) square root of a / b (or just a if b is None) >>> sqrt(9) 3.0 >>> sqrt(9, 4) 1.5 square = is_square(n) check positive integer <n> is a perfect square. if <n> is a perfect square, returns the integer square root. if <n> is not a perfect square, returns None. >>> is_square(49) 7 >>> is_square(50) is not None False >>> is_square(0) 0 static(**kw) simulates static variables in a function by adding attributes to it. static variable <v> in function <f> is accessed as <f.v>. e.g.: @static(n=0) def gensym(x): gensym.n += 1 return concat(x, gensym.n) >> gensym('foo') 'foo1' >> gensym('bar') 'bar2' >> gensym('baz') 'baz3' (for better performance you can use global variables) status(fn, at_exit=0) stop(files=None, files_extra=None, use_exit=0, verbose=1) # this looks for a "STOP" file, and if present removes it and returns True subfactorial(n) # can be cached() if necessary subseqs = subsets(s, size=None, min_size=0, max_size=None, select='C', prepare=None, fn=<type 'tuple'>) generate tuples representing the subsequences of a (finite) iterator. 'min_size' and 'max_size' can be used to limit the size of the subsequences or 'size' can be specified to produce subsequences of a particular size. the way the elements of the subsequences are selected can be controlled with the 'select' parameter: 'C' = combinations (default) 'P' = permutations 'D' = derangements 'R' = combinations with replacement 'M' = product 'uC' = unique combinations 'mC' = multiset combinations 'mP' = multiset permutations or you can provide your own function. aliases: subseqs(), powerset(). >>> list(subsets((1, 2, 3))) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] >>> list(subsets((1, 2, 3), size=2, select='C')) [(1, 2), (1, 3), (2, 3)] >>> list(subsets((1, 2, 3), size=2, select='P')) [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] >>> list(subsets((1, 2, 3), size=2, select='R')) [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)] >>> list(subsets((1, 2, 3), size=2, select='M')) [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)] subsets(s, size=None, min_size=0, max_size=None, select='C', prepare=None, fn=<type 'tuple'>) generate tuples representing the subsequences of a (finite) iterator. 'min_size' and 'max_size' can be used to limit the size of the subsequences or 'size' can be specified to produce subsequences of a particular size. the way the elements of the subsequences are selected can be controlled with the 'select' parameter: 'C' = combinations (default) 'P' = permutations 'D' = derangements 'R' = combinations with replacement 'M' = product 'uC' = unique combinations 'mC' = multiset combinations 'mP' = multiset permutations or you can provide your own function. aliases: subseqs(), powerset(). >>> list(subsets((1, 2, 3))) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] >>> list(subsets((1, 2, 3), size=2, select='C')) [(1, 2), (1, 3), (2, 3)] >>> list(subsets((1, 2, 3), size=2, select='P')) [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] >>> list(subsets((1, 2, 3), size=2, select='R')) [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)] >>> list(subsets((1, 2, 3), size=2, select='M')) [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)] substitute(s2d, text, digits=None) given a symbol-to-digit mapping <s2d> and some text <text>, return the text with the digits (as defined by the sequence <digits>) substituted for the symbols. characters in the text that don't occur in the mapping are unaltered. if there are braces present in <text> then only those portions of the <text> enclosed in braces are substituted. >>> substitute(dict(zip('DEMNORSY', (7, 5, 1, 6, 0, 8, 9, 2))), "SEND + MORE = MONEY") '9567 + 1085 = 10652' substituted_expression(*args, **kw) substituted_sum(terms, result, digits=None, l2d=None, d2i=None, base=10) a substituted addition sum solver - encapsulated by the SubstitutedSum class. terms - list of summands in the sum result - result of the sum (sum of the terms) digits - digits to be allocated (default: 0 - base-1, less any allocated digits) l2d - initial allocation of digits (default: all digits unallocated) d2i - invalid allocations (default: leading digits cannot be 0) base - base we're working in (default: 10) sym lambda x # local variable used to represent symbol x tau(n, fn=<function prime_factor>) count the number of divisors of a positive integer <n>. tau(n) = len(divisors(n)) (but faster) >>> tau(factorial(12)) 792 timed(f) Return a timed version of function <f>. timed_run(*args) translate(t, m, s='', embed=1) translate the text in <t> according to map <m> (and symbols <s>) <t> is a string (sequence of letters), if there are sections of the string enclosed in curly braces only those sections will be translated, otherwise the whole string is processed (providing the 'embed' parameter is not disabled). <m> can be: - a dict of <letter> -> <replacement> mappings - a sequence of letters to replace, in which case <s> should give the corresponding substitutions - a function called for each replacement, that should provide the replacement value substitutions can be multiple letters >>> translate("A={A} B={B} C={C}", dict(A=1, B=2, C=3)) 'A=1 B=2 C=3' >>> translate("9567 + 1085 = 10652", "75160892", "DEMNORSY") 'SEND + MORE = MONEY' >>> translate("1->{1}; 2->{2}; 3->{3}", (lambda x: int(x) ** 2)) '1->1; 2->4; 3->9' tri = T(n) T(n) is the nth triangular number. T(n) = n * (n + 1) // 2. >>> T(1) 1 >>> T(100) 5050 trirt(x) return the triangular root of <x> (as a float) >>> trirt(5050) 100.0 >>> round(trirt(2), 8) 1.56155281 tuples(s, n=2, circular=0) generate overlapping <n>-tuples from sequence <s>. (for non-overlapping tuples see chunk()). if 'circular' is set to true, then values from the beginning of <s> will be used to complete tuples when the end is reached. >>> list(tuples('ABCDE')) [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E')] >>> list(tuples(irange(1, 5), 3)) [(1, 2, 3), (2, 3, 4), (3, 4, 5)] >>> list(tuples(irange(1, 5), 3, circular=1)) [(1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 1), (5, 1, 2)] uC(s, k) # unique combinations: # like uniq(combinations(s, k) but more efficient ucombinations(s, k=None) ulambda(arg, expr=None) provide an equivalent to: lambda {arg}: {expr} in Python 3 where {arg} specifies a complex parameter unpacking for a single argument e.g.: >>> dist = ulambda("((x1, y1), (x2, y2))", "hypot(x2 - x1, y2 - y1)") >>> dist(((1, 2), (5, 5))) 5.0 union(ss, fn=<type 'set'>) construct a set that is the union of the sequences in <ss>. uniq(i, fn=None) generate unique values from iterator <i> (maintaining order). >>> list(uniq([5, 7, 0, 0, 5])) [5, 7, 0] >>> list(uniq('mississippi')) ['m', 'i', 's', 'p'] >>> list(uniq([1, 2, 3, 4, 5, 6, 7, 8, 9], fn=lambda x: x % 3)) [1, 2, 3] uniq1(i, fn=None) generate unique consecutive values from iterator <i> (maintaining order), where values are compared using <fn>. this function assumes that common elements are generated in <i> together, so it only needs to track the last value. essentially it collapses repeated consecutive values to a single value. >>> list(uniq1((1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5))) [1, 2, 3, 4, 5] >>> list(uniq1('mississippi')) ['m', 'i', 's', 'i', 's', 'i', 'p', 'i'] unpack(fn) Turn a function that takes multiple parameters into a function that takes a tuple of those parameters. To some extent this can be used to work around the removal of parameter unpacking in Python 3 (PEP 3113): In Python 2.7 we could write: > fn = lambda (x, y): is_square(x * x + y * y) > fn((3, 4)) 5 but this is not allowed in Python 3. Instead we can write: > fn = unpack(lambda x, y: is_square(x * x + y * y)) > fn((3, 4)) 5 to provide the same functionality. >>> fn = unpack(lambda x, y: is_square(x * x + y * y)) >>> list(filter(fn, [(1, 2), (2, 3), (3, 4), (4, 5)])) [(3, 4)] update(s, ps=(), vs=None) create an updated version of object <s> which is the same as <s> except that the value at index <k> is <v> for the keys and values provided in <ps> and <vs>. <ps> can either be a sequence of (<key>, <value>) pairs, or <ps> can be a sequence of keys and <vs> the corresponding sequence of values. >>> update([0, 1, 2, 3], [(2, 'foo')]) [0, 1, 'foo', 3] >>> update(dict(a=1, b=2, c=3), 'bc', (4, 9)) == dict(a=1, b=4, c=9) True >>> update((1, 2, 3), [(2, 4)]) (1, 2, 4) writelines(fh, lines, sep=None, flush=1) # file.writelines does NOT include newline characters VERSION 2021-02-21 AUTHOR Jim Randell <jim.randell@gmail.com> CREDITS Brian Gladman, contributor
All information on this site is copyright © 1994-2021 Jim Randell