| Jim's Site |  |
| Home | |
| Climbing & Walking | |
| Macaroni Penguins | |
| Photo Gallery | |
| Miscellaneous | |
| Recommended Links | |
| Tips | |
 Software |
Last Updated: Thu Nov 21 22:39:40 GMT 2019
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
choose - choose a sequence of values satisfying some functions
chunk - go through an iterable in chunks
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
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 - find the index of an object in an iterable
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
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
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_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)
mgcd - multiple gcd
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
pi - float approximation to pi
poly_* - routines manipulating polynomials, wrapped as Polynomial
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
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
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 2019-11-21 (Python 2.7.16)]
% python3 enigma.py
[enigma.py version 2019-11-21 (Python 3.8.0)]
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 function 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.16)]
checking for updates...
latest version is 2019-11-21
downloading latest version to "2019-11-21-enigma.py"
........
download complete
renaming "2019-11-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 2019-11-21 (Python 2.7.16)]
checking for updates...
latest version is 2019-11-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 2019-11-21 (Python 2.7.16)]
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
multiset
__builtin__.list(__builtin__.object)
Polynomial
__builtin__.object
Accumulator
CrossFigure
Delay
DominoGrid
Football
MagicSquare
Record
Slots
SubstitutedExpression
SubstitutedDivision
SubstitutedSum
Timer
namespace
__builtin__.tuple(__builtin__.object)
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>, value=None, data=None, 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, t=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.
|
| 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 DominoGrid(__builtin__.object)
| Methods defined here:
|
| __init__(self, N, M, grid)
|
| go(self, fixed=None, sep='', prefix='')
| # solve a grid and output solutions
|
| output_solution(self, s, prefix='')
| # output a solution grid
|
| solve(self, fixed=None)
| # solve the grid
| # fixed can contiain pairs of indices of fixed dominoes
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
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.
|
| 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 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)
|
| to_pairs(self)
|
| ----------------------------------------------------------------------
| Class methods defined here:
|
| from_pairs(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']).go()
| 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(self, check=None, first=None, verbose=None)
| find solutions to the substituted expression problem and output them.
|
| first - if set to True will stop after the first solution is output
|
| returns the number of solutions found, but if the "answer" parameter
| was set during init() returns a multiset() object counting
| the number of times each answer occurs.
|
| 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) 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.
|
| ----------------------------------------------------------------------
| Data descriptors inherited from SubstitutedExpression:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
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').go()
| (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, template=None, solution=None, header=None, distinct=1, check=None, env=None, code=None, process=1, reorder=1, first=0, 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
| 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)
|
| If you want to allow leading digits to be 0 pass an empty dictionary for d2i.
|
| go(self, check=None, first=None, verbose=None)
| find solutions to the substituted expression problem and output them.
|
| first - if set to True will stop after the first solution is output
|
| returns the number of solutions found, but if the "answer" parameter
| was set during init() returns a multiset() object counting
| the number of times each answer occurs.
|
| 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)
|
| 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) 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.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
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(self, check=None, first=0)
| find all solutions (matching the filter <fn>) and output them.
|
| 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.
|
| 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(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()
|
| Methods defined here:
|
| __enter__(self)
|
| __exit__(self, *args)
|
| __init__(self, name='timing', timer=<built-in function time>, file=<open file '<stderr>', mode 'w'>, exit_report=1, auto_start=1)
| 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.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
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:
|
| __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.
|
| __iter__(self)
| iterate through all elements of the multiset.
|
| for distinct elements use: s.keys()
|
| >>> sorted(multiset("banana"))
| ['a', 'a', 'a', 'b', 'n', 'n']
| >>> sorted(multiset("banana").keys())
| ['a', 'b', 'n']
|
| __len__(self)
| count all the elements in a multiset.
|
| to count the number of distinct elements use: len(s.keys())
|
| >>> len(multiset("banana"))
| 6
| >>> len(multiset("banana").keys())
| 3
|
| add(self, item, count=1)
| add an item to a multiset.
|
| count can be negative to remove items.
|
| combine(self, *rest)
| # combine self and some other multisets (item counts are summed)
|
| copy(self)
| # copy a multiset
|
| difference(self, m)
| return (self - m)
|
| differences(self, m)
| return the differences between self and another multiset m.
|
| returns (self - m, m - self)
|
| intersection(self, *rest)
| # intersection of self and some other multisets (minimal item counts are retained)
|
| issubset(self, m)
| # is multiset m a superset of self?
|
| issuperset(self, m)
| # is multiset m a subset of 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.
|
| remove(self, item, count=1)
| remove an item from a multiset.
|
| subsets(self, size=None, min_size=0, max_size=None)
| # generate subsets of a multiset
|
| symmetric_difference(self, m)
| # absolute difference in item counts of the two multisets
|
| union(self, *rest)
| # union of self and some other multiset (maximal item counts are retained)
|
| union_update(self, *rest)
| # union update of self and some other multiset (maximal item counts are retained)
|
| update(self, *rest)
| # update self with some other 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)
| 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) from __builtin__.type
| create a multiset from a sequence of items (or multiple sequences).
|
| ----------------------------------------------------------------------
| 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
|
| __ge__(...)
| x.__ge__(y) <==> x>=y
|
| __getattribute__(...)
| x.__getattribute__('name') <==> x.name
|
| __getitem__(...)
| x.__getitem__(y) <==> x[y]
|
| __gt__(...)
| x.__gt__(y) <==> x>y
|
| __le__(...)
| x.__le__(y) <==> x<=y
|
| __lt__(...)
| x.__lt__(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)
p = 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:
|
| __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.
|
| __iter__(self)
| iterate through all elements of the multiset.
|
| for distinct elements use: s.keys()
|
| >>> sorted(multiset("banana"))
| ['a', 'a', 'a', 'b', 'n', 'n']
| >>> sorted(multiset("banana").keys())
| ['a', 'b', 'n']
|
| __len__(self)
| count all the elements in a multiset.
|
| to count the number of distinct elements use: len(s.keys())
|
| >>> len(multiset("banana"))
| 6
| >>> len(multiset("banana").keys())
| 3
|
| add(self, item, count=1)
| add an item to a multiset.
|
| count can be negative to remove items.
|
| combine(self, *rest)
| # combine self and some other multisets (item counts are summed)
|
| copy(self)
| # copy a multiset
|
| difference(self, m)
| return (self - m)
|
| differences(self, m)
| return the differences between self and another multiset m.
|
| returns (self - m, m - self)
|
| intersection(self, *rest)
| # intersection of self and some other multisets (minimal item counts are retained)
|
| issubset(self, m)
| # is multiset m a superset of self?
|
| issuperset(self, m)
| # is multiset m a subset of 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.
|
| remove(self, item, count=1)
| remove an item from a multiset.
|
| subsets(self, size=None, min_size=0, max_size=None)
| # generate subsets of a multiset
|
| symmetric_difference(self, m)
| # absolute difference in item counts of the two multisets
|
| union(self, *rest)
| # union of self and some other multiset (maximal item counts are retained)
|
| union_update(self, *rest)
| # union update of self and some other multiset (maximal item counts are retained)
|
| update(self, *rest)
| # update self with some other 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)
| 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) from __builtin__.type
| create a multiset from a sequence of items (or multiple sequences).
|
| ----------------------------------------------------------------------
| 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
|
| __ge__(...)
| x.__ge__(y) <==> x>=y
|
| __getattribute__(...)
| x.__getattribute__('name') <==> x.name
|
| __getitem__(...)
| x.__getitem__(y) <==> x[y]
|
| __gt__(...)
| x.__gt__(y) <==> x>y
|
| __le__(...)
| x.__le__(y) <==> x<=y
|
| __lt__(...)
| x.__lt__(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
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 repeated.
>>> 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>>)
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>>)
# backwards compatibility
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
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>.
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 = 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
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, 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)]
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
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
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
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)
# compose functions in order (forward functional composition, "and then")
# so: fcompose(f, g, h)(x) == h(g(f(x)))
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.
alias: partition()
>>> 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>)
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]))[0]
[(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))[1]
[(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.
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]
flatten(s, fn=<type 'list'>)
flatten a list of lists (actually an iterator of iterators).
>>> 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 = 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
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)
return the numerator and denominator of the fraction a/b in lowest terms
>>> fraction(286, 1001)
(2, 7)
gcd(a, b)
greatest common divisor (on positive integers).
>>> gcd(123, 456)
3
>>> gcd(5, 7)
1
gensym(x)
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]
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
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.
>>> 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=' ')
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)
# set intersection of a bunch of sequences
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 endpoint is specified then this is taken as the highest
value, and a lowest value of 1 is used (so irange(n) produces n
integers from 1 to n).
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(9))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
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_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_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='')
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)
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
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
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)
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)
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)
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.
alias: partition()
>>> 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>)
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]))[0]
[(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))[1]
[(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 it's 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))]
poly_add(p, q)
# add two polynomials
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_from_pairs(ps, p=None)
# make a polynomial from (exponent, coefficient) pairs
# (we can use enumerate() to reverse the process)
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_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)
powerset = subsets(s, size=None, min_size=0, max_size=None, select='C', prepare=None)
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
'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
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)
# compose functions in reverse order (reverse functional composition, "after")
# so: 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)
generate repeated applications of function <fn> to value <v>.
>>> first(repeat(lambda x: x + 1), 10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
roman2int(x)
return the integer value of a Roman Numeral <x>.
>>> roman2int('IV')
4
>>> roman2int('IIII')
4
>>> roman2int('MCMXCIX')
1999
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 scripts
<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
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)
# add attributes to a function (to use as static variables)
# (but for better performance 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
subseqs = subsets(s, size=None, min_size=0, max_size=None, select='C', prepare=None)
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
'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)
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
'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.
>>> 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)
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)
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)
generate overlapping <n>-tuples from sequence <s>.
(for non-overlapping tuples see chunk()).
>>> list(tuples('12345'))
[('1', '2'), ('2', '3'), ('3', '4'), ('4', '5')]
>>> list(tuples(irange(1, 5), 3))
[(1, 2, 3), (2, 3, 4), (3, 4, 5)]
uC(s, k)
# unique combinations:
# like uniq(combinations(s, k) but more efficient
ucombinations(s, k=None)
union(ss)
# set union of a bunch of sequences
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
v = 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)
writelines(fh, lines, sep=None, flush=1)
# file.writelines does NOT include newline characters
VERSION
2019-11-21
AUTHOR
Jim Randell <jim.randell@gmail.com>
CREDITS
Brian Gladman, contributor
All information on this site is copyright © 1994-2019 Jim Randell