Jim's Site
 Home 
 Climbing & Walking 
 Macaroni Penguins 
 Photo Gallery 
 Miscellaneous 
   Recommended Links 
   Tips 
 >Software 

Enigma Library (enigma.py)

Last Updated: Wed Jul 19 11:17:08 BST 2017



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.

Documentation

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:
    
    alphametic             - an alias for substituted_expression()
    argv                   - command line arguments (= sys.argv[1:])
    arg                    - extract command line arguments
    base2int               - convert a string in the specified base to an integer
    C                      - combinatorial function (nCk)
    cached                 - decorator for caching functions
    cbrt                   - the (real) cube root of a number
    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
    digrt                  - the digital root of a number
    divc                   - ceiling division
    divf                   - floor division
    divisor                - generate the divisors of a number
    divisor_pairs          - generate pairs of divisors of a number
    divisors               - the divisors of a number
    egcd                   - extended gcd
    factor                 - the prime factorisation of a number
    factorial              - factorial function
    farey                  - generate Farey sequences of coprime pairs
    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
    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
    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
    powerset               - the powerset of an iterator
    prime_factor           - generate terms in the prime factorisation of a number
    printf                 - print with interpolated variables
    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
    substitute             - substitute symbols for digits in text
    substituted_expression - a substituted expression (Alphametic) 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
    Alphametic             - an alias for SubstitutedExpression
    CrossFigure            - a class for solving cross figure puzzles
    Delay                  - a class for the delayed evaluation of a function
    Football               - a class for solving football league table puzzles
    MagicSquare            - a class for solving magic squares
    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) 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 2017-07-18 (Python 2.7.13)]
    
          % python3 enigma.py
          [enigma.py version 2017-07-18 (Python 3.6.1)]
    
    
      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[cd]
    
        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 -u                          
          [enigma.py version 2013-09-10 (Python 2.7.13)]
          checking for updates...
          latest version is 2017-07-18
          downloading latest version to "2017-07-18-enigma.py"
          ........
          download complete
    
        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".
    
        If you are running the latest version you will see something like
        this:
    
          % python enigma.py -u
          [enigma.py version 2017-07-18 (Python 2.7.13)]
          checking for updates...
          latest version is 2017-07-18
          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 2017-07-18 (Python 2.7.13)]
          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[cd] = check for updates [c = only check, d = always download]
            -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 / Alphametic
    
        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__.list(__builtin__.object)
        Polynomial
    __builtin__.object
        Accumulator
        CrossFigure
        Delay
        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
     |  
     |  Methods defined here:
     |  
     |  __init__(self, fn=<built-in function add>, value=None, data=None)
     |      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.
     |  
     |  ----------------------------------------------------------------------
     |  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)
     |  
     |  evaluate(self)
     |  
     |  reset(self)
     |  
     |  ----------------------------------------------------------------------
     |  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)
     |  Useful 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.
     |  
     |  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, 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.
     |      
     |      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)
     |      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 symbols that index into the dict() <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.
     |  
     |  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:
     |      
     |      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).
     |      
     |      B = football.table([ab, bc, bd], [1, 0, 0])
     |      print(B.played, B.w, B.d, B.l, B.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__(self, x)
     |  
     |  __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:
     |  
     |  __hash__ = None
     |  
     |  __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 substractions 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"
     |      
     |      
     |      [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 collections.Counter() object counting
     |      the number of times each answer occurs.
     |  
     |  save(self, file=None, quote=0)
     |      # generate appropriate command line arguments to reconstruct this instance
     |  
     |  substitute(self, s, text, digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
     |      given a solution to the substituted expression sum and some text,
     |      return the text with the letters substituted for digits.
     |  
     |  to_args(self, quote=0)
     |      # 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
     |  
     |  ----------------------------------------------------------------------
     |  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, env=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)
     |      env - additional environment for evaluation (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 collections.Counter() 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=0)
     |      # 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 True only the first solution is returned
     |      verbose - if set to >0 solutions are output as they are found, >1 additional information is output.
     |  
     |  substitute(self, s, text, digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
     |      given a solution to the substituted expression sum and some text,
     |      return the text with the letters substituted for digits.
     |  
     |  to_args(self, quote=0)
     |      # 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
     |  
     |  ----------------------------------------------------------------------
     |  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='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
     |      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='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
     |  
     |  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='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
     |      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,1,2,3,4,5,6,7,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 namespace(__builtin__.object)
     |  Methods defined here:
     |  
     |  __init__(self, name, vs)
     |  
     |  __repr__(self)
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors defined here:
     |  
     |  __dict__
     |      dictionary for instance variables (if defined)
     |  
     |  __weakref__
     |      list of weak references to the object (if defined)

FUNCTIONS
    C(n, k)
        combinatorial function: n C k.
        
        the number of unordered k-length selections from n elements
        (elements can only be used once).
        
        >>> C(10, 3)
        120
    
    M(n, k)
        multichoose function: n M k.
        
        the number of unordered k-length selections from n elements where
        elements may be 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 up to 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)
        check all arguments have the same value
        
        >>> all_same(1, 2, 3)
        False
        
        >>> all_same(1, 1, 1, 1, 1, 1)
        True
        
        >>> all_same()
        False
    
    arg(v, n, fn=<function identity>, argv=sys.argv[1:])
        if command line argument <n> is specified return fn(argv[n])
        otherwise return default value <v>
        
        >>> arg(42, 0, int, ['56'])
        56
        >>> arg(42, 1, int, ['56'])
        42
    
    base2int(s, base=10, strip=0, digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
        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
    
    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.
        
        >>> divc(100, 10)
        10
        >>> divc(101, 10)
        11
        >>> divc(101.1, 10)
        11.0
        >>> divc(4.5, 1)
        5.0
    
    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
    
    chunk(s, n=2)
        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)
        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)
        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'
    
    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
    
    divc(a, b)
        ceiling division.
        
        >>> divc(100, 10)
        10
        >>> divc(101, 10)
        11
        >>> divc(101.1, 10)
        11.0
        >>> divc(4.5, 1)
        5.0
    
    divf(a, b)
        floor division. (equivalent to Python's a // b).
        
        >>> divf(100, 10)
        10
        >>> divf(101, 10)
        10
        >>> divf(101.1, 10)
        10.0
        >>> divf(4.5, 1)
        4.0
    
    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> = <n>.
        
        the pairs are generated such that <a> <= <b>, in order of increasing <a>.
        
        >>> list(divisor_pairs(36))
        [(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)]
        >>> list(divisor_pairs(101))
        [(1, 101)]
    
    divisors(n)
        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]
    
    duplicate = is_duplicate(s)
        check to see if <s> (as a string) contains 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)
    
    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)]
    
    filter2(p, i)
        use a predicate to partition an iterable it those elements that
        satisfy the predicate, and those that do not.
        
        >>> 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>
        
        "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):
          ...
        AssertionError: 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.
        
        if you import itertools this would be a way to find the first 10 primes:
        >>> first((n for n in itertools.count(1) 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)
        fully flatten a nested structure <s> (to depth <depth>, default is to fully flatten).
        
        >>> 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']
    
    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
    
    gcd(a, b)
        greatest common divisor (on positive integers).
        
        >>> gcd(123, 456)
        3
        >>> gcd(5, 7)
        1
    
    gensym(x)
    
    grid_adjacency(n, m, deltas=None, include_adjacent=1, include_diagonal=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' and 'include_diagonal'
        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
        
        >>> 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(*v)
        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, 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
        
        This will examine all elements of <i> to verify there are exactly 4 primes
        less than 10:
        >>> icount(irange(1, 10), is_prime, 5) == 4
        True
        
        But this will stop after testing 73 (the 21st prime):
        >>> icount(irange(1, 100), is_prime, 21) == 20
        False
        
        To find if at least <n> elements of <i> satisfy <p> use:
        
        icount(i, p, n) == n
        
        The following will stop testing at 71 (the 20th prime):
        >>> icount(irange(1, 100), is_prime, 20) == 20
        True
        
        To find if at most <n> elements of <i> satisfy <p> use:
        
        icount(i, p, n + 1) < n + 1
        
        The following will stop testing at 73 (the 21st prime):
        >>> icount(irange(1, 100), is_prime, 21) < 21
        False
    
    identity(x)
        the identity function: identity(x) == x
    
    int2base(i, base=10, digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
        convert an integer <i> to a string representation in the specified base <base>.
        
        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
    
    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
    
    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 endpoints.
        
        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).
        
        >>> 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]
    
    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_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 <s> (as a string) contains duplicate characters.
        
        >>> is_duplicate("hello")
        True
        >>> is_duplicate("world")
        False
        >>> is_duplicate(99 ** 2)
        False
    
    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. 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(332306998946228968225951765070086168)
        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_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)) using Newton's method.
        
        >>> 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
    
    match(v, t)
        match a value (as a string) to a template (see fnmatch.fnmatch).
        
        >>> match("abcd", "?b??")
        True
        >>> match("abcd", "a*")
        True
        >>> match("abcd", "?b?")
        False
        >>> match(1234, '?2??')
        True
    
    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
    
    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 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, base=10)
        split an integer into digits (using base <base> representation)
        
        >>> 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)
    
    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)
    
    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_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_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(i, min_size=0, max_size=None)
        generate the powerset (i.e. all subsets) of an iterator.
        
        >>> list(powerset((1, 2, 3)))
        [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 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. 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 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
    
    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.
    
    recurring(a, b, recur=0, base=10)
        find recurring decimal representation of the fraction <a> / <b>
        return strings (<integer-part>, <non-recurring-decimal-part>, <recurring-decimal-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)
        # run command line arguments
    
    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(...)
        sqrt(x)
        
        Return the square root of x.
    
    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
    
    subseqs(iterable, min_size=0, max_size=None)
        generate the subsequences of an iterable.
        min_size and max_size can be used to limit the length of the sub-sequences.
        
        >>> list(subseqs((1, 2, 3)))
        [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
        >>> list(subseqs((1, 2, 3), min_size=1, max_size=2))
        [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]
    
    subsets = powerset(i, min_size=0, max_size=None)
        generate the powerset (i.e. all subsets) of an iterator.
        
        >>> list(powerset((1, 2, 3)))
        [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
    
    substitute(s2d, text, digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ')
        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)
        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>.
    
    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)]
    
    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 named parameters into a function that
        takes a tuple.
        
        To some extent this can be used to work around the removal of
        parameter unpacking in Python 3 (PEP 3113).
        
        >>> fn = lambda x, y: is_square(x ** 2 + y ** 2)
        >>> list(filter(unpack(fn), [(1, 2), (2, 3), (3, 4), (4, 5)]))
        [(3, 4)]
    
    update(s, ps=())
        create an updated version of object <s> which is the same as <s> except
        that the value at index <k> is <v> for the pairs (<k>, <v>) in <ps>.
        
        >>> update([0, 1, 2, 3], [(2, 'foo')])
        [0, 1, 'foo', 3]
        
        >>> update({ 'a': 1, 'b': 2, 'c': 3 }, zip('bc', (4, 9))) == { 'a': 1, 'b': 4, 'c': 9 }
        True
    
    writelines(fh, lines, sep=None, flush=1)
        # file.writelines does NOT include newline characters

VERSION
    2017-07-18

AUTHOR
    Jim Randell <jim.randell@gmail.com>

CREDITS
    Brian Gladman, contributor


All information on this site is copyright © 1994-2017 Jim Randell