spiffyscore

Hex Artifact Content
Login

Artifact 99f93e22cf312f11e5651e4c7f466ae749444d49:


0000: 23 20 43 6f 70 79 72 69 67 68 74 20 28 63 29 20  # Copyright (c) 
0010: 32 30 30 37 20 52 41 44 4c 6f 67 69 63 0a 23 20  2007 RADLogic.# 
0020: 0a 23 20 50 65 72 6d 69 73 73 69 6f 6e 20 69 73  .# Permission is
0030: 20 68 65 72 65 62 79 20 67 72 61 6e 74 65 64 2c   hereby granted,
0040: 20 66 72 65 65 20 6f 66 20 63 68 61 72 67 65 2c   free of charge,
0050: 20 74 6f 20 61 6e 79 20 70 65 72 73 6f 6e 20 6f   to any person o
0060: 62 74 61 69 6e 69 6e 67 20 61 20 63 6f 70 79 0a  btaining a copy.
0070: 23 20 6f 66 20 74 68 69 73 20 73 6f 66 74 77 61  # of this softwa
0080: 72 65 20 61 6e 64 20 61 73 73 6f 63 69 61 74 65  re and associate
0090: 64 20 64 6f 63 75 6d 65 6e 74 61 74 69 6f 6e 20  d documentation 
00a0: 66 69 6c 65 73 20 28 74 68 65 20 22 53 6f 66 74  files (the "Soft
00b0: 77 61 72 65 22 29 2c 20 74 6f 20 64 65 61 6c 0a  ware"), to deal.
00c0: 23 20 69 6e 20 74 68 65 20 53 6f 66 74 77 61 72  # in the Softwar
00d0: 65 20 77 69 74 68 6f 75 74 20 72 65 73 74 72 69  e without restri
00e0: 63 74 69 6f 6e 2c 20 69 6e 63 6c 75 64 69 6e 67  ction, including
00f0: 20 77 69 74 68 6f 75 74 20 6c 69 6d 69 74 61 74   without limitat
0100: 69 6f 6e 20 74 68 65 20 72 69 67 68 74 73 0a 23  ion the rights.#
0110: 20 74 6f 20 75 73 65 2c 20 63 6f 70 79 2c 20 6d   to use, copy, m
0120: 6f 64 69 66 79 2c 20 6d 65 72 67 65 2c 20 70 75  odify, merge, pu
0130: 62 6c 69 73 68 2c 20 64 69 73 74 72 69 62 75 74  blish, distribut
0140: 65 2c 20 73 75 62 6c 69 63 65 6e 73 65 2c 20 61  e, sublicense, a
0150: 6e 64 2f 6f 72 20 73 65 6c 6c 0a 23 20 63 6f 70  nd/or sell.# cop
0160: 69 65 73 20 6f 66 20 74 68 65 20 53 6f 66 74 77  ies of the Softw
0170: 61 72 65 2c 20 61 6e 64 20 74 6f 20 70 65 72 6d  are, and to perm
0180: 69 74 20 70 65 72 73 6f 6e 73 20 74 6f 20 77 68  it persons to wh
0190: 6f 6d 20 74 68 65 20 53 6f 66 74 77 61 72 65 20  om the Software 
01a0: 69 73 0a 23 20 66 75 72 6e 69 73 68 65 64 20 74  is.# furnished t
01b0: 6f 20 64 6f 20 73 6f 2c 20 73 75 62 6a 65 63 74  o do so, subject
01c0: 20 74 6f 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   to the followin
01d0: 67 20 63 6f 6e 64 69 74 69 6f 6e 73 3a 0a 23 20  g conditions:.# 
01e0: 0a 23 20 54 68 65 20 61 62 6f 76 65 20 63 6f 70  .# The above cop
01f0: 79 72 69 67 68 74 20 6e 6f 74 69 63 65 20 61 6e  yright notice an
0200: 64 20 74 68 69 73 20 70 65 72 6d 69 73 73 69 6f  d this permissio
0210: 6e 20 6e 6f 74 69 63 65 20 73 68 61 6c 6c 20 62  n notice shall b
0220: 65 20 69 6e 63 6c 75 64 65 64 20 69 6e 0a 23 20  e included in.# 
0230: 61 6c 6c 20 63 6f 70 69 65 73 20 6f 72 20 73 75  all copies or su
0240: 62 73 74 61 6e 74 69 61 6c 20 70 6f 72 74 69 6f  bstantial portio
0250: 6e 73 20 6f 66 20 74 68 65 20 53 6f 66 74 77 61  ns of the Softwa
0260: 72 65 2e 0a 23 20 0a 23 20 54 48 45 20 53 4f 46  re..# .# THE SOF
0270: 54 57 41 52 45 20 49 53 20 50 52 4f 56 49 44 45  TWARE IS PROVIDE
0280: 44 20 22 41 53 20 49 53 22 2c 20 57 49 54 48 4f  D "AS IS", WITHO
0290: 55 54 20 57 41 52 52 41 4e 54 59 20 4f 46 20 41  UT WARRANTY OF A
02a0: 4e 59 20 4b 49 4e 44 2c 20 45 58 50 52 45 53 53  NY KIND, EXPRESS
02b0: 20 4f 52 0a 23 20 49 4d 50 4c 49 45 44 2c 20 49   OR.# IMPLIED, I
02c0: 4e 43 4c 55 44 49 4e 47 20 42 55 54 20 4e 4f 54  NCLUDING BUT NOT
02d0: 20 4c 49 4d 49 54 45 44 20 54 4f 20 54 48 45 20   LIMITED TO THE 
02e0: 57 41 52 52 41 4e 54 49 45 53 20 4f 46 20 4d 45  WARRANTIES OF ME
02f0: 52 43 48 41 4e 54 41 42 49 4c 49 54 59 2c 0a 23  RCHANTABILITY,.#
0300: 20 46 49 54 4e 45 53 53 20 46 4f 52 20 41 20 50   FITNESS FOR A P
0310: 41 52 54 49 43 55 4c 41 52 20 50 55 52 50 4f 53  ARTICULAR PURPOS
0320: 45 20 41 4e 44 20 4e 4f 4e 49 4e 46 52 49 4e 47  E AND NONINFRING
0330: 45 4d 45 4e 54 2e 20 49 4e 20 4e 4f 20 45 56 45  EMENT. IN NO EVE
0340: 4e 54 20 53 48 41 4c 4c 20 54 48 45 0a 23 20 41  NT SHALL THE.# A
0350: 55 54 48 4f 52 53 20 4f 52 20 43 4f 50 59 52 49  UTHORS OR COPYRI
0360: 47 48 54 20 48 4f 4c 44 45 52 53 20 42 45 20 4c  GHT HOLDERS BE L
0370: 49 41 42 4c 45 20 46 4f 52 20 41 4e 59 20 43 4c  IABLE FOR ANY CL
0380: 41 49 4d 2c 20 44 41 4d 41 47 45 53 20 4f 52 20  AIM, DAMAGES OR 
0390: 4f 54 48 45 52 0a 23 20 4c 49 41 42 49 4c 49 54  OTHER.# LIABILIT
03a0: 59 2c 20 57 48 45 54 48 45 52 20 49 4e 20 41 4e  Y, WHETHER IN AN
03b0: 20 41 43 54 49 4f 4e 20 4f 46 20 43 4f 4e 54 52   ACTION OF CONTR
03c0: 41 43 54 2c 20 54 4f 52 54 20 4f 52 20 4f 54 48  ACT, TORT OR OTH
03d0: 45 52 57 49 53 45 2c 20 41 52 49 53 49 4e 47 20  ERWISE, ARISING 
03e0: 46 52 4f 4d 2c 0a 23 20 4f 55 54 20 4f 46 20 4f  FROM,.# OUT OF O
03f0: 52 20 49 4e 20 43 4f 4e 4e 45 43 54 49 4f 4e 20  R IN CONNECTION 
0400: 57 49 54 48 20 54 48 45 20 53 4f 46 54 57 41 52  WITH THE SOFTWAR
0410: 45 20 4f 52 20 54 48 45 20 55 53 45 20 4f 52 20  E OR THE USE OR 
0420: 4f 54 48 45 52 20 44 45 41 4c 49 4e 47 53 20 49  OTHER DEALINGS I
0430: 4e 0a 23 20 54 48 45 20 53 4f 46 54 57 41 52 45  N.# THE SOFTWARE
0440: 2e 0a 22 22 22 50 72 6f 76 69 64 65 20 76 61 72  .."""Provide var
0450: 69 6f 75 73 20 68 61 6e 64 79 20 50 79 74 68 6f  ious handy Pytho
0460: 6e 20 66 75 6e 63 74 69 6f 6e 73 2e 0a 0a 52 75  n functions...Ru
0470: 6e 6e 69 6e 67 20 74 68 69 73 20 73 63 72 69 70  nning this scrip
0480: 74 20 64 69 72 65 63 74 6c 79 20 77 69 6c 6c 20  t directly will 
0490: 65 78 65 63 75 74 65 20 74 68 65 20 64 6f 63 74  execute the doct
04a0: 65 73 74 73 2e 0a 0a 46 75 6e 63 74 69 6f 6e 73  ests...Functions
04b0: 3a 0a 69 6e 74 32 62 69 6e 28 69 2c 20 6e 29 20  :.int2bin(i, n) 
04c0: 2d 2d 20 43 6f 6e 76 65 72 74 20 69 6e 74 65 67  -- Convert integ
04d0: 65 72 20 74 6f 20 62 69 6e 61 72 79 20 73 74 72  er to binary str
04e0: 69 6e 67 2e 0a 62 69 6e 32 69 6e 74 28 62 69 6e  ing..bin2int(bin
04f0: 5f 73 74 72 69 6e 67 29 20 2d 2d 20 43 6f 6e 76  _string) -- Conv
0500: 65 72 74 20 62 69 6e 61 72 79 20 73 74 72 69 6e  ert binary strin
0510: 67 20 74 6f 20 69 6e 74 65 67 65 72 2e 0a 72 65  g to integer..re
0520: 76 65 72 73 65 28 69 6e 70 75 74 5f 73 74 72 69  verse(input_stri
0530: 6e 67 29 20 2d 2d 20 52 65 76 65 72 73 65 20 61  ng) -- Reverse a
0540: 20 73 74 72 69 6e 67 2e 0a 74 72 61 6e 73 70 6f   string..transpo
0550: 73 65 28 6d 61 74 72 69 78 29 20 2d 2d 20 54 72  se(matrix) -- Tr
0560: 61 6e 73 70 6f 73 65 20 61 20 6c 69 73 74 20 6f  anspose a list o
0570: 66 20 6c 69 73 74 73 2e 0a 70 6f 6c 79 67 6f 6e  f lists..polygon
0580: 5f 61 72 65 61 28 70 6f 69 6e 74 73 5f 6c 69 73  _area(points_lis
0590: 74 29 20 2d 2d 20 43 61 6c 63 75 6c 61 74 65 20  t) -- Calculate 
05a0: 74 68 65 20 61 72 65 61 20 6f 66 20 61 6e 20 61  the area of an a
05b0: 72 62 69 74 72 61 72 79 20 70 6f 6c 79 67 6f 6e  rbitrary polygon
05c0: 2e 0a 74 69 6d 65 73 74 61 6d 70 28 29 20 2d 2d  ..timestamp() --
05d0: 20 52 65 74 75 72 6e 20 73 74 72 69 6e 67 20 63   Return string c
05e0: 6f 6e 74 61 69 6e 69 6e 67 20 63 75 72 72 65 6e  ontaining curren
05f0: 74 20 74 69 6d 65 20 73 74 61 6d 70 2e 0a 70 74  t time stamp..pt
0600: 32 73 74 72 28 70 6f 69 6e 74 29 20 2d 2d 20 52  2str(point) -- R
0610: 65 74 75 72 6e 20 70 72 65 74 74 69 65 72 20 73  eturn prettier s
0620: 74 72 69 6e 67 20 76 65 72 73 69 6f 6e 20 6f 66  tring version of
0630: 20 70 6f 69 6e 74 20 74 75 70 6c 65 2e 0a 67 63   point tuple..gc
0640: 66 28 61 2c 20 62 29 20 2d 2d 20 52 65 74 75 72  f(a, b) -- Retur
0650: 6e 20 74 68 65 20 67 72 65 61 74 65 73 74 20 63  n the greatest c
0660: 6f 6d 6d 6f 6e 20 66 61 63 74 6f 72 20 6f 66 20  ommon factor of 
0670: 74 77 6f 20 6e 75 6d 62 65 72 73 2e 0a 6c 63 6d  two numbers..lcm
0680: 28 61 2c 20 62 29 20 2d 2d 20 52 65 74 75 72 6e  (a, b) -- Return
0690: 20 74 68 65 20 6c 65 61 73 74 20 63 6f 6d 6d 6f   the least commo
06a0: 6e 20 6d 75 6c 74 69 70 6c 65 20 6f 66 20 74 77  n multiple of tw
06b0: 6f 20 6e 75 6d 62 65 72 73 2e 0a 70 65 72 6d 75  o numbers..permu
06c0: 74 61 74 69 6f 6e 73 28 69 6e 70 75 74 5f 6c 69  tations(input_li
06d0: 73 74 29 20 2d 2d 20 47 65 6e 65 72 61 74 65 20  st) -- Generate 
06e0: 61 6c 6c 20 70 65 72 6d 75 74 61 74 69 6f 6e 73  all permutations
06f0: 20 6f 66 20 61 20 6c 69 73 74 20 6f 66 20 69 74   of a list of it
0700: 65 6d 73 2e 0a 72 65 64 75 63 65 5f 66 72 61 63  ems..reduce_frac
0710: 74 69 6f 6e 28 66 72 61 63 74 69 6f 6e 29 20 2d  tion(fraction) -
0720: 2d 20 52 65 64 75 63 65 20 66 72 61 63 74 69 6f  - Reduce fractio
0730: 6e 20 28 6e 75 6d 2c 20 64 65 6e 6f 6d 29 20 74  n (num, denom) t
0740: 6f 20 73 69 6d 70 6c 65 73 74 20 66 6f 72 6d 2e  o simplest form.
0750: 0a 71 75 61 6e 74 69 6c 65 28 6c 2c 20 70 29 20  .quantile(l, p) 
0760: 2d 2d 20 52 65 74 75 72 6e 20 70 20 71 75 61 6e  -- Return p quan
0770: 74 69 6c 65 20 6f 66 20 6c 69 73 74 20 6c 2e 20  tile of list l. 
0780: 45 2e 67 2e 20 70 3d 30 2e 32 35 20 66 6f 72 20  E.g. p=0.25 for 
0790: 71 31 2e 0a 74 72 69 6d 28 6c 29 20 2d 2d 20 44  q1..trim(l) -- D
07a0: 69 73 63 61 72 64 20 76 61 6c 75 65 73 20 69 6e  iscard values in
07b0: 20 6c 69 73 74 20 6d 6f 72 65 20 74 68 61 6e 20   list more than 
07c0: 31 2e 35 2a 49 51 52 20 6f 75 74 73 69 64 65 20  1.5*IQR outside 
07d0: 49 51 52 2e 0a 6e 69 63 65 5f 75 6e 69 74 73 28  IQR..nice_units(
07e0: 76 61 6c 75 65 29 20 2d 2d 20 52 65 74 75 72 6e  value) -- Return
07f0: 20 76 61 6c 75 65 20 63 6f 6e 76 65 72 74 65 64   value converted
0800: 20 74 6f 20 68 75 6d 61 6e 20 72 65 61 64 61 62   to human readab
0810: 6c 65 20 75 6e 69 74 73 2e 0a 75 6e 69 71 75 69  le units..uniqui
0820: 66 79 28 73 65 71 29 20 2d 2d 20 52 65 74 75 72  fy(seq) -- Retur
0830: 6e 20 73 65 71 75 65 6e 63 65 20 77 69 74 68 20  n sequence with 
0840: 64 75 70 6c 69 63 61 74 65 20 69 74 65 6d 73 20  duplicate items 
0850: 69 6e 20 73 65 71 75 65 6e 63 65 20 73 65 71 20  in sequence seq 
0860: 72 65 6d 6f 76 65 64 2e 0a 72 65 76 65 72 73 65  removed..reverse
0870: 5f 64 69 63 74 28 64 29 20 2d 2d 20 52 65 74 75  _dict(d) -- Retu
0880: 72 6e 20 74 68 65 20 64 69 63 74 69 6f 6e 61 72  rn the dictionar
0890: 79 20 77 69 74 68 20 74 68 65 20 69 74 65 6d 73  y with the items
08a0: 20 61 73 20 6b 65 79 73 20 61 6e 64 20 76 69 63   as keys and vic
08b0: 65 2d 76 65 72 73 61 2e 0a 6c 73 62 28 78 2c 20  e-versa..lsb(x, 
08c0: 6e 29 20 2d 2d 20 52 65 74 75 72 6e 20 74 68 65  n) -- Return the
08d0: 20 6e 20 6c 65 61 73 74 20 73 69 67 6e 69 66 69   n least signifi
08e0: 63 61 6e 74 20 62 69 74 73 20 6f 66 20 78 2e 0a  cant bits of x..
08f0: 67 72 61 79 5f 65 6e 63 6f 64 65 28 69 29 20 2d  gray_encode(i) -
0900: 2d 20 47 72 61 79 20 65 6e 63 6f 64 65 20 74 68  - Gray encode th
0910: 65 20 67 69 76 65 6e 20 69 6e 74 65 67 65 72 2e  e given integer.
0920: 0a 72 61 6e 64 6f 6d 5f 76 65 63 28 62 69 74 73  .random_vec(bits
0930: 2c 20 6d 61 78 5f 76 61 6c 75 65 3d 4e 6f 6e 65  , max_value=None
0940: 29 20 2d 2d 20 52 65 74 75 72 6e 20 61 20 72 61  ) -- Return a ra
0950: 6e 64 6f 6d 20 62 69 6e 61 72 79 20 76 65 63 74  ndom binary vect
0960: 6f 72 2e 0a 62 69 6e 61 72 79 5f 72 61 6e 67 65  or..binary_range
0970: 28 62 69 74 73 29 20 2d 2d 20 52 65 74 75 72 6e  (bits) -- Return
0980: 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 70 6f 73   list of all pos
0990: 73 69 62 6c 65 20 62 69 6e 61 72 79 20 6e 75 6d  sible binary num
09a0: 62 65 72 73 20 77 69 64 74 68 3d 62 69 74 73 2e  bers width=bits.
09b0: 0a 66 6c 6f 61 74 5f 72 61 6e 67 65 28 5b 73 74  .float_range([st
09c0: 61 72 74 5d 2c 20 73 74 6f 70 2c 20 5b 73 74 65  art], stop, [ste
09d0: 70 5d 29 20 2d 2d 20 52 65 74 75 72 6e 20 72 61  p]) -- Return ra
09e0: 6e 67 65 20 6f 66 20 66 6c 6f 61 74 73 2e 0a 66  nge of floats..f
09f0: 69 6e 64 5f 63 6f 6d 6d 6f 6e 5f 66 69 78 65 73  ind_common_fixes
0a00: 28 73 31 2c 20 73 32 29 20 2d 2d 20 46 69 6e 64  (s1, s2) -- Find
0a10: 20 63 6f 6d 6d 6f 6e 20 28 70 72 65 66 69 78 2c   common (prefix,
0a20: 20 73 75 66 66 69 78 29 20 6f 66 20 74 77 6f 20   suffix) of two 
0a30: 73 74 72 69 6e 67 73 2e 0a 69 73 5f 72 6f 74 61  strings..is_rota
0a40: 74 65 64 28 73 65 71 31 2c 20 73 65 71 32 29 20  ted(seq1, seq2) 
0a50: 2d 2d 20 52 65 74 75 72 6e 20 74 72 75 65 20 69  -- Return true i
0a60: 66 20 74 68 65 20 6c 69 73 74 20 69 73 20 61 20  f the list is a 
0a70: 72 6f 74 61 74 69 6f 6e 20 6f 66 20 6f 74 68 65  rotation of othe
0a80: 72 20 6c 69 73 74 2e 0a 67 65 74 6d 6f 64 75 6c  r list..getmodul
0a90: 65 28 6f 62 6a 29 20 2d 2d 20 52 65 74 75 72 6e  e(obj) -- Return
0aa0: 20 74 68 65 20 6d 6f 64 75 6c 65 20 74 68 61 74   the module that
0ab0: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 6f 62   contains the ob
0ac0: 6a 65 63 74 20 64 65 66 69 6e 69 74 69 6f 6e 20  ject definition 
0ad0: 6f 66 20 6f 62 6a 2e 0a 20 20 20 20 20 20 20 20  of obj..        
0ae0: 20 20 20 20 20 20 20 20 20 20 28 75 73 65 20 69            (use i
0af0: 6e 73 70 65 63 74 2e 67 65 74 6d 6f 64 75 6c 65  nspect.getmodule
0b00: 20 69 6e 73 74 65 61 64 2c 20 74 68 6f 75 67 68   instead, though
0b10: 29 0a 67 65 74 5f 61 72 67 73 28 61 72 67 76 29  ).get_args(argv)
0b20: 20 2d 2d 20 53 74 6f 72 65 20 63 6f 6d 6d 61 6e   -- Store comman
0b30: 64 2d 6c 69 6e 65 20 61 72 67 73 20 69 6e 20 61  d-line args in a
0b40: 20 64 69 63 74 69 6f 6e 61 72 79 2e 0a 0a 54 68   dictionary...Th
0b50: 69 73 20 6d 6f 64 75 6c 65 20 72 65 71 75 69 72  is module requir
0b60: 65 73 20 50 79 74 68 6f 6e 20 3e 3d 20 32 2e 32  es Python >= 2.2
0b70: 0a 0a 22 22 22 0a 5f 5f 61 75 74 68 6f 72 5f 5f  ..""".__author__
0b80: 20 3d 20 27 54 69 6d 20 57 65 67 65 6e 65 72 20   = 'Tim Wegener 
0b90: 3c 74 77 65 67 65 6e 65 72 40 72 61 64 6c 6f 67  <twegener@radlog
0ba0: 69 63 2e 63 6f 6d 2e 61 75 3e 27 0a 5f 5f 64 61  ic.com.au>'.__da
0bb0: 74 65 5f 5f 20 3d 20 27 24 44 61 74 65 3a 20 32  te__ = '$Date: 2
0bc0: 30 30 37 2f 30 33 2f 32 37 20 30 33 3a 31 35 3a  007/03/27 03:15:
0bd0: 30 36 20 24 27 0a 5f 5f 76 65 72 73 69 6f 6e 5f  06 $'.__version_
0be0: 5f 20 3d 20 27 24 52 65 76 69 73 69 6f 6e 3a 20  _ = '$Revision: 
0bf0: 30 2e 34 35 20 24 27 0a 5f 5f 63 72 65 64 69 74  0.45 $'.__credit
0c00: 73 5f 5f 20 3d 20 22 22 22 0a 20 20 20 20 20 20  s__ = """.      
0c10: 20 20 20 20 20 20 20 20 44 61 76 69 64 20 43 68          David Ch
0c20: 61 6e 64 6c 65 72 2c 20 66 6f 72 20 70 6f 6c 79  andler, for poly
0c30: 67 6f 6e 20 61 72 65 61 20 61 6c 67 6f 72 69 74  gon area algorit
0c40: 68 6d 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20  hm..            
0c50: 20 20 20 28 68 74 74 70 3a 2f 2f 77 77 77 2e 64     (http://www.d
0c60: 61 76 69 64 63 68 61 6e 64 6c 65 72 2e 63 6f 6d  avidchandler.com
0c70: 2f 41 72 65 61 4f 66 41 47 65 6e 65 72 61 6c 50  /AreaOfAGeneralP
0c80: 6f 6c 79 67 6f 6e 2e 70 64 66 29 0a 20 20 20 20  olygon.pdf).    
0c90: 20 20 20 20 20 20 20 20 20 20 22 22 22 0a 0a 69            """..i
0ca0: 6d 70 6f 72 74 20 72 65 0a 69 6d 70 6f 72 74 20  mport re.import 
0cb0: 73 79 73 0a 69 6d 70 6f 72 74 20 74 69 6d 65 0a  sys.import time.
0cc0: 69 6d 70 6f 72 74 20 72 61 6e 64 6f 6d 0a 0a 74  import random..t
0cd0: 72 79 3a 0a 20 20 20 20 54 72 75 65 2c 20 46 61  ry:.    True, Fa
0ce0: 6c 73 65 0a 65 78 63 65 70 74 20 4e 61 6d 65 45  lse.except NameE
0cf0: 72 72 6f 72 3a 0a 20 20 20 20 54 72 75 65 2c 20  rror:.    True, 
0d00: 46 61 6c 73 65 20 3d 20 28 31 3d 3d 31 2c 20 30  False = (1==1, 0
0d10: 3d 3d 31 29 0a 0a 0a 64 65 66 20 69 6e 74 32 62  ==1)...def int2b
0d20: 69 6e 28 69 2c 20 6e 29 3a 0a 20 20 20 20 22 22  in(i, n):.    ""
0d30: 22 43 6f 6e 76 65 72 74 20 64 65 63 69 6d 61 6c  "Convert decimal
0d40: 20 69 6e 74 65 67 65 72 20 69 20 74 6f 20 6e 2d   integer i to n-
0d50: 62 69 74 20 62 69 6e 61 72 79 20 6e 75 6d 62 65  bit binary numbe
0d60: 72 20 28 73 74 72 69 6e 67 29 2e 0a 0a 20 20 20  r (string)...   
0d70: 20 3e 3e 3e 20 69 6e 74 32 62 69 6e 28 30 2c 20   >>> int2bin(0, 
0d80: 38 29 0a 20 20 20 20 27 30 30 30 30 30 30 30 30  8).    '00000000
0d90: 27 0a 0a 20 20 20 20 3e 3e 3e 20 69 6e 74 32 62  '..    >>> int2b
0da0: 69 6e 28 31 32 33 2c 20 38 29 0a 20 20 20 20 27  in(123, 8).    '
0db0: 30 31 31 31 31 30 31 31 27 0a 0a 20 20 20 20 3e  01111011'..    >
0dc0: 3e 3e 20 69 6e 74 32 62 69 6e 28 31 32 33 4c 2c  >> int2bin(123L,
0dd0: 20 38 29 0a 20 20 20 20 27 30 31 31 31 31 30 31   8).    '0111101
0de0: 31 27 0a 0a 20 20 20 20 3e 3e 3e 20 69 6e 74 32  1'..    >>> int2
0df0: 62 69 6e 28 31 35 2c 20 32 29 0a 20 20 20 20 54  bin(15, 2).    T
0e00: 72 61 63 65 62 61 63 6b 20 28 6d 6f 73 74 20 72  raceback (most r
0e10: 65 63 65 6e 74 20 63 61 6c 6c 20 6c 61 73 74 29  ecent call last)
0e20: 3a 0a 20 20 20 20 56 61 6c 75 65 45 72 72 6f 72  :.    ValueError
0e30: 3a 20 56 61 6c 75 65 20 74 6f 6f 20 6c 61 72 67  : Value too larg
0e40: 65 20 66 6f 72 20 67 69 76 65 6e 20 6e 75 6d 62  e for given numb
0e50: 65 72 20 6f 66 20 62 69 74 73 2e 0a 0a 20 20 20  er of bits...   
0e60: 20 22 22 22 0a 20 20 20 20 68 65 78 32 62 69 6e   """.    hex2bin
0e70: 20 3d 20 7b 27 30 27 3a 20 27 30 30 30 30 27 2c   = {'0': '0000',
0e80: 20 27 31 27 3a 20 27 30 30 30 31 27 2c 20 27 32   '1': '0001', '2
0e90: 27 3a 20 27 30 30 31 30 27 2c 20 27 33 27 3a 20  ': '0010', '3': 
0ea0: 27 30 30 31 31 27 2c 0a 20 20 20 20 20 20 20 20  '0011',.        
0eb0: 20 20 20 20 20 20 20 27 34 27 3a 20 27 30 31 30         '4': '010
0ec0: 30 27 2c 20 27 35 27 3a 20 27 30 31 30 31 27 2c  0', '5': '0101',
0ed0: 20 27 36 27 3a 20 27 30 31 31 30 27 2c 20 27 37   '6': '0110', '7
0ee0: 27 3a 20 27 30 31 31 31 27 2c 0a 20 20 20 20 20  ': '0111',.     
0ef0: 20 20 20 20 20 20 20 20 20 20 27 38 27 3a 20 27            '8': '
0f00: 31 30 30 30 27 2c 20 27 39 27 3a 20 27 31 30 30  1000', '9': '100
0f10: 31 27 2c 20 27 61 27 3a 20 27 31 30 31 30 27 2c  1', 'a': '1010',
0f20: 20 27 62 27 3a 20 27 31 30 31 31 27 2c 0a 20 20   'b': '1011',.  
0f30: 20 20 20 20 20 20 20 20 20 20 20 20 20 27 63 27               'c'
0f40: 3a 20 27 31 31 30 30 27 2c 20 27 64 27 3a 20 27  : '1100', 'd': '
0f50: 31 31 30 31 27 2c 20 27 65 27 3a 20 27 31 31 31  1101', 'e': '111
0f60: 30 27 2c 20 27 66 27 3a 20 27 31 31 31 31 27 7d  0', 'f': '1111'}
0f70: 0a 20 20 20 20 23 20 43 6f 6e 76 65 72 74 20 74  .    # Convert t
0f80: 6f 20 68 65 78 20 74 68 65 6e 20 6d 61 70 20 65  o hex then map e
0f90: 61 63 68 20 68 65 78 20 64 69 67 69 74 20 74 6f  ach hex digit to
0fa0: 20 62 69 6e 61 72 79 20 65 71 75 69 76 61 6c 65   binary equivale
0fb0: 6e 74 2e 0a 20 20 20 20 72 65 73 75 6c 74 20 3d  nt..    result =
0fc0: 20 27 27 2e 6a 6f 69 6e 28 5b 68 65 78 32 62 69   ''.join([hex2bi
0fd0: 6e 5b 78 5d 20 66 6f 72 20 78 20 69 6e 20 68 65  n[x] for x in he
0fe0: 78 28 69 29 2e 6c 6f 77 65 72 28 29 2e 72 65 70  x(i).lower().rep
0ff0: 6c 61 63 65 28 27 6c 27 2c 27 27 29 5b 32 3a 5d  lace('l','')[2:]
1000: 5d 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ]).             
1010: 20 20 20 20 20 20 20 20 20 0a 20 20 20 20 23 20           .    # 
1020: 53 68 72 69 6e 6b 20 72 65 73 75 6c 74 20 74 6f  Shrink result to
1030: 20 61 70 70 72 6f 70 72 69 61 74 65 20 6c 65 6e   appropriate len
1040: 67 74 68 2e 0a 20 20 20 20 23 20 52 61 69 73 65  gth..    # Raise
1050: 20 61 6e 20 65 72 72 6f 72 20 69 66 20 74 68 65   an error if the
1060: 20 76 61 6c 75 65 20 69 73 20 63 68 61 6e 67 65   value is change
1070: 64 20 62 79 20 74 68 65 20 74 72 75 6e 63 61 74  d by the truncat
1080: 69 6f 6e 2e 0a 20 20 20 20 69 66 20 27 31 27 20  ion..    if '1' 
1090: 69 6e 20 72 65 73 75 6c 74 5b 3a 2d 6e 5d 3a 0a  in result[:-n]:.
10a0: 20 20 20 20 20 20 20 20 72 61 69 73 65 20 56 61          raise Va
10b0: 6c 75 65 45 72 72 6f 72 28 22 56 61 6c 75 65 20  lueError("Value 
10c0: 74 6f 6f 20 6c 61 72 67 65 20 66 6f 72 20 67 69  too large for gi
10d0: 76 65 6e 20 6e 75 6d 62 65 72 20 6f 66 20 62 69  ven number of bi
10e0: 74 73 2e 22 29 0a 20 20 20 20 72 65 73 75 6c 74  ts.").    result
10f0: 20 3d 20 72 65 73 75 6c 74 5b 2d 6e 3a 5d 0a 20   = result[-n:]. 
1100: 20 20 20 23 20 5a 65 72 6f 2d 70 61 64 20 69 66     # Zero-pad if
1110: 20 6c 65 6e 67 74 68 20 6c 6f 6e 67 65 72 20 74   length longer t
1120: 68 61 6e 20 6d 61 70 70 65 64 20 72 65 73 75 6c  han mapped resul
1130: 74 2e 0a 20 20 20 20 72 65 73 75 6c 74 20 3d 20  t..    result = 
1140: 27 30 27 2a 28 6e 2d 6c 65 6e 28 72 65 73 75 6c  '0'*(n-len(resul
1150: 74 29 29 20 2b 20 72 65 73 75 6c 74 0a 20 20 20  t)) + result.   
1160: 20 72 65 74 75 72 6e 20 72 65 73 75 6c 74 0a 0a   return result..
1170: 0a 64 65 66 20 62 69 6e 32 69 6e 74 28 62 69 6e  .def bin2int(bin
1180: 5f 73 74 72 69 6e 67 29 3a 0a 20 20 20 20 22 22  _string):.    ""
1190: 22 43 6f 6e 76 65 72 74 20 62 69 6e 61 72 79 20  "Convert binary 
11a0: 6e 75 6d 62 65 72 20 73 74 72 69 6e 67 20 74 6f  number string to
11b0: 20 64 65 63 69 6d 61 6c 20 69 6e 74 65 67 65 72   decimal integer
11c0: 2e 0a 20 20 20 20 0a 20 20 20 20 4e 6f 74 65 3a  ..    .    Note:
11d0: 20 50 79 74 68 6f 6e 20 3e 20 76 32 20 68 61 73   Python > v2 has
11e0: 20 69 6e 74 28 62 69 6e 5f 73 74 72 69 6e 67 2c   int(bin_string,
11f0: 20 32 29 0a 0a 20 20 20 20 3e 3e 3e 20 62 69 6e   2)..    >>> bin
1200: 32 69 6e 74 28 27 31 31 31 31 27 29 0a 20 20 20  2int('1111').   
1210: 20 31 35 0a 0a 20 20 20 20 3e 3e 3e 20 62 69 6e   15..    >>> bin
1220: 32 69 6e 74 28 27 30 31 30 31 27 29 0a 20 20 20  2int('0101').   
1230: 20 35 0a 0a 20 20 20 20 22 22 22 0a 23 23 20 20   5..    """.##  
1240: 20 20 20 72 65 73 75 6c 74 20 3d 20 30 0a 23 23     result = 0.##
1250: 20 20 20 20 20 62 69 6e 5f 6c 69 73 74 20 3d 20       bin_list = 
1260: 6c 69 73 74 28 62 69 6e 5f 73 74 72 69 6e 67 29  list(bin_string)
1270: 0a 23 23 20 20 20 20 20 69 66 20 6c 65 6e 28 66  .##     if len(f
1280: 69 6c 74 65 72 28 6c 61 6d 62 64 61 20 78 3a 20  ilter(lambda x: 
1290: 78 20 69 6e 20 28 27 31 27 2c 27 30 27 29 2c 20  x in ('1','0'), 
12a0: 62 69 6e 5f 6c 69 73 74 29 29 20 3c 20 6c 65 6e  bin_list)) < len
12b0: 28 62 69 6e 5f 6c 69 73 74 29 3a 0a 23 23 20 20  (bin_list):.##  
12c0: 20 20 20 20 20 20 20 72 61 69 73 65 20 45 78 63         raise Exc
12d0: 65 70 74 69 6f 6e 20 28 22 62 69 6e 32 69 6e 74  eption ("bin2int
12e0: 3a 20 45 72 72 6f 72 20 2d 20 6e 6f 74 20 61 20  : Error - not a 
12f0: 62 69 6e 61 72 79 20 6e 75 6d 62 65 72 3a 20 25  binary number: %
1300: 73 22 0a 23 23 20 20 20 20 20 20 20 20 20 20 20  s".##           
1310: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 25                 %
1320: 20 62 69 6e 5f 73 74 72 69 6e 67 29 0a 23 23 20   bin_string).## 
1330: 20 20 20 20 62 69 74 5f 6c 69 73 74 20 3d 20 6d      bit_list = m
1340: 61 70 28 69 6e 74 2c 20 62 69 6e 5f 6c 69 73 74  ap(int, bin_list
1350: 29 0a 23 23 20 20 20 20 20 62 69 74 5f 6c 69 73  ).##     bit_lis
1360: 74 2e 72 65 76 65 72 73 65 28 29 20 20 23 20 4d  t.reverse()  # M
1370: 61 6b 65 20 6d 6f 73 74 20 73 69 67 6e 69 66 69  ake most signifi
1380: 63 61 6e 74 20 62 69 74 20 68 61 76 65 20 68 69  cant bit have hi
1390: 67 68 65 73 74 20 69 6e 64 65 78 2e 0a 23 23 20  ghest index..## 
13a0: 20 20 20 20 66 6f 72 20 62 69 74 5f 70 6c 61 63      for bit_plac
13b0: 65 20 69 6e 20 72 61 6e 67 65 28 6c 65 6e 28 62  e in range(len(b
13c0: 69 74 5f 6c 69 73 74 29 29 3a 0a 23 23 20 20 20  it_list)):.##   
13d0: 20 20 20 20 20 20 72 65 73 75 6c 74 20 3d 20 72        result = r
13e0: 65 73 75 6c 74 20 2b 20 28 28 32 2a 2a 62 69 74  esult + ((2**bit
13f0: 5f 70 6c 61 63 65 29 20 2a 20 62 69 74 5f 6c 69  _place) * bit_li
1400: 73 74 5b 62 69 74 5f 70 6c 61 63 65 5d 29 0a 23  st[bit_place]).#
1410: 23 20 20 20 20 20 72 65 74 75 72 6e 20 72 65 73  #     return res
1420: 75 6c 74 0a 20 20 20 20 72 65 74 75 72 6e 20 69  ult.    return i
1430: 6e 74 28 62 69 6e 5f 73 74 72 69 6e 67 2c 20 32  nt(bin_string, 2
1440: 29 0a 0a 0a 64 65 66 20 72 65 76 65 72 73 65 28  )...def reverse(
1450: 69 6e 70 75 74 5f 73 74 72 69 6e 67 29 3a 0a 20  input_string):. 
1460: 20 20 20 22 22 22 52 65 76 65 72 73 65 20 61 20     """Reverse a 
1470: 73 74 72 69 6e 67 2e 20 55 73 65 66 75 6c 20 66  string. Useful f
1480: 6f 72 20 73 74 72 69 6e 67 73 20 6f 66 20 62 69  or strings of bi
1490: 6e 61 72 79 20 6e 75 6d 62 65 72 73 2e 0a 0a 20  nary numbers... 
14a0: 20 20 20 3e 3e 3e 20 72 65 76 65 72 73 65 28 27     >>> reverse('
14b0: 61 62 63 27 29 0a 20 20 20 20 27 63 62 61 27 0a  abc').    'cba'.
14c0: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 73 74 72  .    """.    str
14d0: 5f 6c 69 73 74 20 3d 20 6c 69 73 74 28 69 6e 70  _list = list(inp
14e0: 75 74 5f 73 74 72 69 6e 67 29 0a 20 20 20 20 73  ut_string).    s
14f0: 74 72 5f 6c 69 73 74 2e 72 65 76 65 72 73 65 28  tr_list.reverse(
1500: 29 0a 20 20 20 20 72 65 74 75 72 6e 20 27 27 2e  ).    return ''.
1510: 6a 6f 69 6e 28 73 74 72 5f 6c 69 73 74 29 0a 0a  join(str_list)..
1520: 0a 64 65 66 20 74 72 61 6e 73 70 6f 73 65 28 6d  .def transpose(m
1530: 61 74 72 69 78 29 3a 0a 20 20 20 20 22 22 22 54  atrix):.    """T
1540: 72 61 6e 73 70 6f 73 65 20 61 20 6c 69 73 74 20  ranspose a list 
1550: 6f 66 20 6c 69 73 74 73 2e 0a 0a 20 20 20 20 3e  of lists...    >
1560: 3e 3e 20 74 72 61 6e 73 70 6f 73 65 28 5b 5b 27  >> transpose([['
1570: 61 27 2c 20 27 62 27 2c 20 27 63 27 5d 2c 20 5b  a', 'b', 'c'], [
1580: 27 64 27 2c 20 27 65 27 2c 20 27 66 27 5d 2c 20  'd', 'e', 'f'], 
1590: 5b 27 67 27 2c 20 27 68 27 2c 20 27 69 27 5d 5d  ['g', 'h', 'i']]
15a0: 29 0a 20 20 20 20 5b 5b 27 61 27 2c 20 27 64 27  ).    [['a', 'd'
15b0: 2c 20 27 67 27 5d 2c 20 5b 27 62 27 2c 20 27 65  , 'g'], ['b', 'e
15c0: 27 2c 20 27 68 27 5d 2c 20 5b 27 63 27 2c 20 27  ', 'h'], ['c', '
15d0: 66 27 2c 20 27 69 27 5d 5d 0a 0a 20 20 20 20 3e  f', 'i']]..    >
15e0: 3e 3e 20 74 72 61 6e 73 70 6f 73 65 28 5b 5b 27  >> transpose([['
15f0: 61 27 2c 20 27 62 27 2c 20 27 63 27 5d 2c 20 5b  a', 'b', 'c'], [
1600: 27 64 27 2c 20 27 65 27 2c 20 27 66 27 5d 5d 29  'd', 'e', 'f']])
1610: 0a 20 20 20 20 5b 5b 27 61 27 2c 20 27 64 27 5d  .    [['a', 'd']
1620: 2c 20 5b 27 62 27 2c 20 27 65 27 5d 2c 20 5b 27  , ['b', 'e'], ['
1630: 63 27 2c 20 27 66 27 5d 5d 0a 0a 20 20 20 20 3e  c', 'f']]..    >
1640: 3e 3e 20 74 72 61 6e 73 70 6f 73 65 28 5b 5b 27  >> transpose([['
1650: 61 27 2c 20 27 62 27 5d 2c 20 5b 27 64 27 2c 20  a', 'b'], ['d', 
1660: 27 65 27 5d 2c 20 5b 27 67 27 2c 20 27 68 27 5d  'e'], ['g', 'h']
1670: 5d 29 0a 20 20 20 20 5b 5b 27 61 27 2c 20 27 64  ]).    [['a', 'd
1680: 27 2c 20 27 67 27 5d 2c 20 5b 27 62 27 2c 20 27  ', 'g'], ['b', '
1690: 65 27 2c 20 27 68 27 5d 5d 0a 0a 20 20 20 20 22  e', 'h']]..    "
16a0: 22 22 0a 20 20 20 20 72 65 73 75 6c 74 20 3d 20  "".    result = 
16b0: 7a 69 70 28 2a 6d 61 74 72 69 78 29 0a 20 20 20  zip(*matrix).   
16c0: 20 23 20 43 6f 6e 76 65 72 74 20 6c 69 73 74 20   # Convert list 
16d0: 6f 66 20 74 75 70 6c 65 73 20 74 6f 20 6c 69 73  of tuples to lis
16e0: 74 20 6f 66 20 6c 69 73 74 73 2e 0a 20 20 20 20  t of lists..    
16f0: 23 20 6d 61 70 20 69 73 20 66 61 73 74 65 72 20  # map is faster 
1700: 74 68 61 6e 20 61 20 6c 69 73 74 20 63 6f 6d 70  than a list comp
1710: 72 65 68 65 6e 73 69 6f 6e 20 73 69 6e 63 65 20  rehension since 
1720: 69 74 20 69 73 20 62 65 69 6e 67 20 75 73 65 64  it is being used
1730: 20 77 69 74 68 0a 20 20 20 20 23 20 61 20 62 75   with.    # a bu
1740: 69 6c 74 2d 69 6e 20 66 75 6e 63 74 69 6f 6e 20  ilt-in function 
1750: 61 73 20 61 6e 20 61 72 67 75 6d 65 6e 74 2e 0a  as an argument..
1760: 20 20 20 20 72 65 73 75 6c 74 20 3d 20 6d 61 70      result = map
1770: 28 6c 69 73 74 2c 20 72 65 73 75 6c 74 29 0a 20  (list, result). 
1780: 20 20 20 72 65 74 75 72 6e 20 72 65 73 75 6c 74     return result
1790: 0a 0a 0a 64 65 66 20 70 6f 6c 79 67 6f 6e 5f 61  ...def polygon_a
17a0: 72 65 61 28 70 6f 69 6e 74 73 5f 6c 69 73 74 2c  rea(points_list,
17b0: 20 70 72 65 63 69 73 69 6f 6e 3d 31 30 30 29 3a   precision=100):
17c0: 0a 20 20 20 20 22 22 22 43 61 6c 63 75 6c 61 74  .    """Calculat
17d0: 65 20 61 72 65 61 20 6f 66 20 61 6e 20 61 72 62  e area of an arb
17e0: 69 74 72 61 72 79 20 70 6f 6c 79 67 6f 6e 20 75  itrary polygon u
17f0: 73 69 6e 67 20 61 6e 20 61 6c 67 6f 72 69 74 68  sing an algorith
1800: 6d 20 66 72 6f 6d 20 74 68 65 20 77 65 62 2e 0a  m from the web..
1810: 0a 20 20 20 20 52 65 74 75 72 6e 20 74 68 65 20  .    Return the 
1820: 61 72 65 61 20 6f 66 20 74 68 65 20 70 6f 6c 79  area of the poly
1830: 67 6f 6e 20 61 73 20 61 20 70 6f 73 69 74 69 76  gon as a positiv
1840: 65 20 66 6c 6f 61 74 2e 20 0a 0a 20 20 20 20 41  e float. ..    A
1850: 72 67 75 6d 65 6e 74 73 3a 0a 20 20 20 20 70 6f  rguments:.    po
1860: 69 6e 74 73 5f 6c 69 73 74 20 2d 2d 20 6c 69 73  ints_list -- lis
1870: 74 20 6f 66 20 70 6f 69 6e 74 20 74 75 70 6c 65  t of point tuple
1880: 73 20 5b 28 78 30 2c 20 79 30 29 2c 20 28 78 31  s [(x0, y0), (x1
1890: 2c 20 79 31 29 2c 20 28 78 32 2c 20 79 32 29 2c  , y1), (x2, y2),
18a0: 20 2e 2e 2e 5d 0a 20 20 20 20 20 20 20 20 20 20   ...].          
18b0: 20 20 20 20 20 20 20 20 20 28 55 6e 63 6c 6f 73           (Unclos
18c0: 65 64 20 70 6f 6c 79 67 6f 6e 73 20 77 69 6c 6c  ed polygons will
18d0: 20 62 65 20 63 6c 6f 73 65 64 20 61 75 74 6f 6d   be closed autom
18e0: 61 74 69 63 61 6c 6c 79 2e 0a 20 20 20 20 70 72  atically..    pr
18f0: 65 63 69 73 69 6f 6e 20 2d 2d 20 49 6e 74 65 72  ecision -- Inter
1900: 6e 61 6c 20 61 72 69 74 68 6d 65 74 69 63 20 70  nal arithmetic p
1910: 72 65 63 69 73 69 6f 6e 20 28 69 6e 74 65 67 65  recision (intege
1920: 72 20 61 72 69 74 68 6d 65 74 69 63 29 2e 0a 0a  r arithmetic)...
1930: 20 20 20 20 3e 3e 3e 20 70 6f 6c 79 67 6f 6e 5f      >>> polygon_
1940: 61 72 65 61 28 5b 28 30 2c 20 30 29 2c 20 28 30  area([(0, 0), (0
1950: 2c 20 31 29 2c 20 28 31 2c 20 31 29 2c 20 28 31  , 1), (1, 1), (1
1960: 2c 20 32 29 2c 20 28 32 2c 20 32 29 2c 20 28 32  , 2), (2, 2), (2
1970: 2c 20 30 29 2c 20 28 30 2c 20 30 29 5d 29 0a 20  , 0), (0, 0)]). 
1980: 20 20 20 33 2e 30 0a 0a 20 20 20 20 43 72 65 64     3.0..    Cred
1990: 69 74 73 3a 0a 20 20 20 20 41 72 65 61 20 6f 66  its:.    Area of
19a0: 20 61 20 47 65 6e 65 72 61 6c 20 50 6f 6c 79 67   a General Polyg
19b0: 6f 6e 20 62 79 20 44 61 76 69 64 20 43 68 61 6e  on by David Chan
19c0: 64 6c 65 72 0a 20 20 20 20 68 74 74 70 3a 2f 2f  dler.    http://
19d0: 77 77 77 2e 64 61 76 69 64 63 68 61 6e 64 6c 65  www.davidchandle
19e0: 72 2e 63 6f 6d 2f 41 72 65 61 4f 66 41 47 65 6e  r.com/AreaOfAGen
19f0: 65 72 61 6c 50 6f 6c 79 67 6f 6e 2e 70 64 66 0a  eralPolygon.pdf.
1a00: 20 20 20 20 0a 20 20 20 20 22 22 22 0a 20 20 20      .    """.   
1a10: 20 23 20 53 63 61 6c 65 20 75 70 20 63 6f 2d 6f   # Scale up co-o
1a20: 72 64 69 6e 61 74 65 73 20 61 6e 64 20 63 6f 6e  rdinates and con
1a30: 76 65 72 74 20 74 68 65 6d 20 74 6f 20 69 6e 74  vert them to int
1a40: 65 67 65 72 73 2e 0a 20 20 20 20 66 6f 72 20 69  egers..    for i
1a50: 20 69 6e 20 72 61 6e 67 65 28 6c 65 6e 28 70 6f   in range(len(po
1a60: 69 6e 74 73 5f 6c 69 73 74 29 29 3a 0a 20 20 20  ints_list)):.   
1a70: 20 20 20 20 20 70 6f 69 6e 74 73 5f 6c 69 73 74       points_list
1a80: 5b 69 5d 20 3d 20 28 69 6e 74 28 70 6f 69 6e 74  [i] = (int(point
1a90: 73 5f 6c 69 73 74 5b 69 5d 5b 30 5d 20 2a 20 70  s_list[i][0] * p
1aa0: 72 65 63 69 73 69 6f 6e 29 2c 0a 20 20 20 20 20  recision),.     
1ab0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1ac0: 20 20 20 20 20 69 6e 74 28 70 6f 69 6e 74 73 5f       int(points_
1ad0: 6c 69 73 74 5b 69 5d 5b 31 5d 20 2a 20 70 72 65  list[i][1] * pre
1ae0: 63 69 73 69 6f 6e 29 29 0a 20 20 20 20 23 20 43  cision)).    # C
1af0: 6c 6f 73 65 20 70 6f 6c 79 67 6f 6e 20 69 66 20  lose polygon if 
1b00: 6e 6f 74 20 63 6c 6f 73 65 64 2e 0a 20 20 20 20  not closed..    
1b10: 69 66 20 70 6f 69 6e 74 73 5f 6c 69 73 74 5b 2d  if points_list[-
1b20: 31 5d 20 21 3d 20 70 6f 69 6e 74 73 5f 6c 69 73  1] != points_lis
1b30: 74 5b 30 5d 3a 0a 20 20 20 20 20 20 20 20 70 6f  t[0]:.        po
1b40: 69 6e 74 73 5f 6c 69 73 74 2e 61 70 70 65 6e 64  ints_list.append
1b50: 28 70 6f 69 6e 74 73 5f 6c 69 73 74 5b 30 5d 29  (points_list[0])
1b60: 0a 20 20 20 20 23 20 43 61 6c 63 75 6c 61 74 65  .    # Calculate
1b70: 20 61 72 65 61 2e 0a 20 20 20 20 61 72 65 61 20   area..    area 
1b80: 3d 20 30 0a 20 20 20 20 66 6f 72 20 69 20 69 6e  = 0.    for i in
1b90: 20 72 61 6e 67 65 28 6c 65 6e 28 70 6f 69 6e 74   range(len(point
1ba0: 73 5f 6c 69 73 74 29 2d 31 29 3a 0a 20 20 20 20  s_list)-1):.    
1bb0: 20 20 20 20 28 78 5f 69 2c 20 79 5f 69 29 20 3d      (x_i, y_i) =
1bc0: 20 70 6f 69 6e 74 73 5f 6c 69 73 74 5b 69 5d 0a   points_list[i].
1bd0: 20 20 20 20 20 20 20 20 28 78 5f 69 5f 70 6c 75          (x_i_plu
1be0: 73 5f 31 2c 20 79 5f 69 5f 70 6c 75 73 5f 31 29  s_1, y_i_plus_1)
1bf0: 20 3d 20 70 6f 69 6e 74 73 5f 6c 69 73 74 5b 69   = points_list[i
1c00: 2b 31 5d 0a 20 20 20 20 20 20 20 20 61 72 65 61  +1].        area
1c10: 20 3d 20 61 72 65 61 20 2b 20 28 78 5f 69 5f 70   = area + (x_i_p
1c20: 6c 75 73 5f 31 20 2a 20 79 5f 69 29 20 2d 20 28  lus_1 * y_i) - (
1c30: 79 5f 69 5f 70 6c 75 73 5f 31 20 2a 20 78 5f 69  y_i_plus_1 * x_i
1c40: 29 0a 20 20 20 20 61 72 65 61 20 3d 20 61 62 73  ).    area = abs
1c50: 28 61 72 65 61 20 2f 20 32 29 0a 20 20 20 20 23  (area / 2).    #
1c60: 20 55 6e 73 63 61 6c 65 20 61 72 65 61 2e 0a 20   Unscale area.. 
1c70: 20 20 20 61 72 65 61 20 3d 20 66 6c 6f 61 74 28     area = float(
1c80: 61 72 65 61 29 2f 28 70 72 65 63 69 73 69 6f 6e  area)/(precision
1c90: 2a 2a 32 29 0a 20 20 20 20 72 65 74 75 72 6e 20  **2).    return 
1ca0: 61 72 65 61 0a 0a 0a 64 65 66 20 74 69 6d 65 73  area...def times
1cb0: 74 61 6d 70 28 29 3a 0a 20 20 20 20 22 22 22 52  tamp():.    """R
1cc0: 65 74 75 72 6e 20 73 74 72 69 6e 67 20 63 6f 6e  eturn string con
1cd0: 74 61 69 6e 69 6e 67 20 63 75 72 72 65 6e 74 20  taining current 
1ce0: 74 69 6d 65 20 73 74 61 6d 70 2e 0a 0a 20 20 20  time stamp...   
1cf0: 20 4e 6f 74 65 3a 20 49 6e 20 50 79 74 68 6f 6e   Note: In Python
1d00: 20 32 20 6f 6e 77 61 72 64 73 20 63 61 6e 20 75   2 onwards can u
1d10: 73 65 20 74 69 6d 65 2e 61 73 63 74 69 6d 65 28  se time.asctime(
1d20: 29 20 77 69 74 68 20 6e 6f 20 61 72 67 75 6d 65  ) with no argume
1d30: 6e 74 73 2e 0a 0a 20 20 20 20 22 22 22 0a 0a 20  nts...    """.. 
1d40: 20 20 20 72 65 74 75 72 6e 20 74 69 6d 65 2e 61     return time.a
1d50: 73 63 74 69 6d 65 28 29 0a 0a 0a 64 65 66 20 70  sctime()...def p
1d60: 74 32 73 74 72 28 70 6f 69 6e 74 29 3a 0a 20 20  t2str(point):.  
1d70: 20 20 22 22 22 52 65 74 75 72 6e 20 70 72 65 74    """Return pret
1d80: 74 69 65 72 20 73 74 72 69 6e 67 20 76 65 72 73  tier string vers
1d90: 69 6f 6e 20 6f 66 20 70 6f 69 6e 74 20 74 75 70  ion of point tup
1da0: 6c 65 2e 0a 0a 20 20 20 20 3e 3e 3e 20 70 74 32  le...    >>> pt2
1db0: 73 74 72 28 28 31 2e 38 2c 20 31 2e 39 29 29 0a  str((1.8, 1.9)).
1dc0: 20 20 20 20 27 28 31 2e 38 2c 20 31 2e 39 29 27      '(1.8, 1.9)'
1dd0: 0a 0a 20 20 20 20 22 22 22 0a 20 20 20 20 72 65  ..    """.    re
1de0: 74 75 72 6e 20 22 28 25 73 2c 20 25 73 29 22 20  turn "(%s, %s)" 
1df0: 25 20 28 73 74 72 28 70 6f 69 6e 74 5b 30 5d 29  % (str(point[0])
1e00: 2c 20 73 74 72 28 70 6f 69 6e 74 5b 31 5d 29 29  , str(point[1]))
1e10: 0a 0a 0a 64 65 66 20 67 63 66 28 61 2c 20 62 2c  ...def gcf(a, b,
1e20: 20 65 70 73 69 6c 6f 6e 3d 31 65 2d 31 36 29 3a   epsilon=1e-16):
1e30: 0a 20 20 20 20 22 22 22 52 65 74 75 72 6e 20 74  .    """Return t
1e40: 68 65 20 67 72 65 61 74 65 73 74 20 63 6f 6d 6d  he greatest comm
1e50: 6f 6e 20 66 61 63 74 6f 72 20 6f 66 20 61 20 61  on factor of a a
1e60: 6e 64 20 62 2c 20 75 73 69 6e 67 20 45 75 63 6c  nd b, using Eucl
1e70: 69 64 65 61 6e 20 61 6c 67 6f 72 69 74 68 6d 2e  idean algorithm.
1e80: 0a 0a 20 20 20 20 41 72 67 75 6d 65 6e 74 73 3a  ..    Arguments:
1e90: 0a 20 20 20 20 61 2c 20 62 20 2d 2d 20 74 77 6f  .    a, b -- two
1ea0: 20 6e 75 6d 62 65 72 73 0a 20 20 20 20 20 20 20   numbers.       
1eb0: 20 20 20 20 20 49 66 20 62 6f 74 68 20 6e 75 6d       If both num
1ec0: 62 65 72 73 20 61 72 65 20 69 6e 74 65 67 65 72  bers are integer
1ed0: 73 20 72 65 74 75 72 6e 20 61 6e 20 69 6e 74 65  s return an inte
1ee0: 67 65 72 20 72 65 73 75 6c 74 2c 20 0a 20 20 20  ger result, .   
1ef0: 20 20 20 20 20 20 20 20 20 6f 74 68 65 72 77 69           otherwi
1f00: 73 65 20 72 65 74 75 72 6e 20 61 20 66 6c 6f 61  se return a floa
1f10: 74 20 72 65 73 75 6c 74 2e 0a 20 20 20 20 65 70  t result..    ep
1f20: 73 69 6c 6f 6e 20 2d 2d 20 66 6c 6f 61 74 73 20  silon -- floats 
1f30: 6c 65 73 73 20 74 68 61 6e 20 74 68 69 73 20 6d  less than this m
1f40: 61 67 6e 69 74 75 64 65 20 61 72 65 20 63 6f 6e  agnitude are con
1f50: 73 69 64 65 72 65 64 20 74 6f 20 62 65 20 7a 65  sidered to be ze
1f60: 72 6f 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ro.             
1f70: 20 20 28 64 65 66 61 75 6c 74 3a 20 31 65 2d 31    (default: 1e-1
1f80: 36 29 0a 0a 20 20 20 20 45 78 61 6d 70 6c 65 73  6)..    Examples
1f90: 3a 0a 0a 20 20 20 20 3e 3e 3e 20 67 63 66 28 31  :..    >>> gcf(1
1fa0: 32 2c 20 33 34 29 0a 20 20 20 20 32 0a 0a 20 20  2, 34).    2..  
1fb0: 20 20 3e 3e 3e 20 67 63 66 28 31 33 2e 35 2c 20    >>> gcf(13.5, 
1fc0: 34 29 0a 20 20 20 20 30 2e 35 0a 0a 20 20 20 20  4).    0.5..    
1fd0: 3e 3e 3e 20 67 63 66 28 2d 32 2c 20 34 29 0a 20  >>> gcf(-2, 4). 
1fe0: 20 20 20 32 0a 0a 20 20 20 20 3e 3e 3e 20 67 63     2..    >>> gc
1ff0: 66 28 35 2c 20 30 29 0a 20 20 20 20 35 0a 0a 20  f(5, 0).    5.. 
2000: 20 20 20 42 79 20 28 61 20 63 6f 6e 76 65 6e 69     By (a conveni
2010: 65 6e 74 29 20 64 65 66 69 6e 69 74 69 6f 6e 3a  ent) definition:
2020: 0a 20 20 20 20 3e 3e 3e 20 67 63 66 28 30 2c 20  .    >>> gcf(0, 
2030: 30 29 0a 20 20 20 20 30 0a 0a 20 20 20 20 22 22  0).    0..    ""
2040: 22 0a 20 20 20 20 72 65 73 75 6c 74 20 3d 20 6d  ".    result = m
2050: 61 78 28 61 2c 20 62 29 0a 20 20 20 20 72 65 6d  ax(a, b).    rem
2060: 61 69 6e 64 65 72 20 3d 20 6d 69 6e 28 61 2c 20  ainder = min(a, 
2070: 62 29 0a 20 20 20 20 77 68 69 6c 65 20 72 65 6d  b).    while rem
2080: 61 69 6e 64 65 72 20 61 6e 64 20 61 62 73 28 72  ainder and abs(r
2090: 65 6d 61 69 6e 64 65 72 29 20 3e 20 65 70 73 69  emainder) > epsi
20a0: 6c 6f 6e 3a 0a 20 20 20 20 20 20 20 20 6e 65 77  lon:.        new
20b0: 5f 72 65 6d 61 69 6e 64 65 72 20 3d 20 72 65 73  _remainder = res
20c0: 75 6c 74 20 25 20 72 65 6d 61 69 6e 64 65 72 0a  ult % remainder.
20d0: 20 20 20 20 20 20 20 20 72 65 73 75 6c 74 20 3d          result =
20e0: 20 72 65 6d 61 69 6e 64 65 72 0a 20 20 20 20 20   remainder.     
20f0: 20 20 20 72 65 6d 61 69 6e 64 65 72 20 3d 20 6e     remainder = n
2100: 65 77 5f 72 65 6d 61 69 6e 64 65 72 0a 20 20 20  ew_remainder.   
2110: 20 72 65 74 75 72 6e 20 61 62 73 28 72 65 73 75   return abs(resu
2120: 6c 74 29 0a 0a 64 65 66 20 6c 63 6d 28 61 2c 20  lt)..def lcm(a, 
2130: 62 2c 20 70 72 65 63 69 73 69 6f 6e 3d 4e 6f 6e  b, precision=Non
2140: 65 29 3a 0a 20 20 20 20 22 22 22 52 65 74 75 72  e):.    """Retur
2150: 6e 20 74 68 65 20 6c 65 61 73 74 20 63 6f 6d 6d  n the least comm
2160: 6f 6e 20 6d 75 6c 74 69 70 6c 65 20 6f 66 20 61  on multiple of a
2170: 20 61 6e 64 20 62 2c 20 75 73 69 6e 67 20 74 68   and b, using th
2180: 65 20 67 63 66 20 66 75 6e 63 74 69 6f 6e 2e 0a  e gcf function..
2190: 0a 20 20 20 20 41 72 67 75 6d 65 6e 74 73 3a 0a  .    Arguments:.
21a0: 20 20 20 20 61 2c 20 62 20 2d 2d 20 74 77 6f 20      a, b -- two 
21b0: 6e 75 6d 62 65 72 73 2e 20 49 66 20 62 6f 74 68  numbers. If both
21c0: 20 61 72 65 20 69 6e 74 65 67 65 72 73 20 72 65   are integers re
21d0: 74 75 72 6e 20 61 6e 20 69 6e 74 65 67 65 72 20  turn an integer 
21e0: 72 65 73 75 6c 74 2c 20 0a 20 20 20 20 20 20 20  result, .       
21f0: 20 20 20 20 20 6f 74 68 65 72 77 69 73 65 20 61       otherwise a
2200: 20 72 65 74 75 72 6e 20 61 20 66 6c 6f 61 74 20   return a float 
2210: 72 65 73 75 6c 74 2e 0a 20 20 20 20 70 72 65 63  result..    prec
2220: 69 73 69 6f 6e 20 2d 2d 20 73 63 61 6c 69 6e 67  ision -- scaling
2230: 20 66 61 63 74 6f 72 20 69 66 20 61 20 61 6e 64   factor if a and
2240: 2f 6f 72 20 62 20 61 72 65 20 66 6c 6f 61 74 73  /or b are floats
2250: 2e 0a 0a 20 20 20 20 3e 3e 3e 20 6c 63 6d 28 32  ...    >>> lcm(2
2260: 31 2c 20 36 29 0a 20 20 20 20 34 32 0a 0a 20 20  1, 6).    42..  
2270: 20 20 3e 3e 3e 20 6c 63 6d 28 32 2e 35 2c 20 33    >>> lcm(2.5, 3
2280: 2e 35 29 0a 20 20 20 20 31 37 2e 35 0a 0a 20 20  .5).    17.5..  
2290: 20 20 3e 3e 3e 20 73 74 72 28 6c 63 6d 28 31 2e    >>> str(lcm(1.
22a0: 35 65 2d 38 2c 20 32 2e 35 65 2d 38 2c 20 70 72  5e-8, 2.5e-8, pr
22b0: 65 63 69 73 69 6f 6e 3d 31 65 39 29 29 0a 20 20  ecision=1e9)).  
22c0: 20 20 27 37 2e 35 65 2d 30 38 27 0a 0a 20 20 20    '7.5e-08'..   
22d0: 20 42 79 20 28 61 6e 20 61 72 62 69 74 61 72 79   By (an arbitary
22e0: 29 20 64 65 66 69 6e 69 74 69 6f 6e 3a 0a 20 20  ) definition:.  
22f0: 20 20 3e 3e 3e 20 6c 63 6d 28 30 2c 20 30 29 0a    >>> lcm(0, 0).
2300: 20 20 20 20 30 0a 0a 20 20 20 20 22 22 22 0a 20      0..    """. 
2310: 20 20 20 23 20 4e 6f 74 65 3a 20 44 75 6d 6d 79     # Note: Dummy
2320: 20 70 72 65 63 69 73 69 6f 6e 20 61 72 67 75 6d   precision argum
2330: 65 6e 74 20 69 73 20 66 6f 72 20 62 61 63 6b 77  ent is for backw
2340: 61 72 64 73 20 63 6f 6d 70 61 74 69 62 69 6c 69  ards compatibili
2350: 74 79 2e 0a 20 20 20 20 23 20 44 6f 20 74 68 65  ty..    # Do the
2360: 20 64 69 76 69 73 69 6f 6e 20 66 69 72 73 74 2e   division first.
2370: 0a 20 20 20 20 23 20 28 53 65 65 20 68 74 74 70  .    # (See http
2380: 3a 2f 2f 65 6e 2e 77 69 6b 69 70 65 64 69 61 2e  ://en.wikipedia.
2390: 6f 72 67 2f 77 69 6b 69 2f 4c 65 61 73 74 5f 63  org/wiki/Least_c
23a0: 6f 6d 6d 6f 6e 5f 6d 75 6c 74 69 70 6c 65 20 29  ommon_multiple )
23b0: 0a 20 20 20 20 64 65 6e 6f 6d 20 3d 20 67 63 66  .    denom = gcf
23c0: 28 61 2c 20 62 29 0a 20 20 20 20 69 66 20 64 65  (a, b).    if de
23d0: 6e 6f 6d 20 3d 3d 20 30 3a 0a 20 20 20 20 20 20  nom == 0:.      
23e0: 20 20 72 65 73 75 6c 74 20 3d 20 30 0a 20 20 20    result = 0.   
23f0: 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 72   else:.        r
2400: 65 73 75 6c 74 20 3d 20 61 20 2a 20 28 62 20 2f  esult = a * (b /
2410: 20 64 65 6e 6f 6d 29 0a 20 20 20 20 72 65 74 75   denom).    retu
2420: 72 6e 20 72 65 73 75 6c 74 0a 0a 0a 64 65 66 20  rn result...def 
2430: 70 65 72 6d 75 74 61 74 69 6f 6e 73 28 69 6e 70  permutations(inp
2440: 75 74 5f 6c 69 73 74 29 3a 0a 20 20 20 20 22 22  ut_list):.    ""
2450: 22 52 65 74 75 72 6e 20 61 20 6c 69 73 74 20 63  "Return a list c
2460: 6f 6e 74 61 69 6e 69 6e 67 20 61 6c 6c 20 70 65  ontaining all pe
2470: 72 6d 75 74 61 74 69 6f 6e 73 20 6f 66 20 74 68  rmutations of th
2480: 65 20 69 6e 70 75 74 20 6c 69 73 74 2e 0a 0a 20  e input list... 
2490: 20 20 20 4e 6f 74 65 3a 20 54 68 69 73 20 69 73     Note: This is
24a0: 20 61 20 72 65 63 75 72 73 69 76 65 20 66 75 6e   a recursive fun
24b0: 63 74 69 6f 6e 2e 0a 0a 20 20 20 20 3e 3e 3e 20  ction...    >>> 
24c0: 70 65 72 6d 73 20 3d 20 70 65 72 6d 75 74 61 74  perms = permutat
24d0: 69 6f 6e 73 28 5b 27 61 27 2c 20 27 62 27 2c 20  ions(['a', 'b', 
24e0: 27 63 27 5d 29 0a 20 20 20 20 3e 3e 3e 20 70 65  'c']).    >>> pe
24f0: 72 6d 73 2e 73 6f 72 74 28 29 0a 20 20 20 20 3e  rms.sort().    >
2500: 3e 3e 20 66 6f 72 20 70 65 72 6d 20 69 6e 20 70  >> for perm in p
2510: 65 72 6d 73 3a 0a 20 20 20 20 2e 2e 2e 20 20 20  erms:.    ...   
2520: 20 20 70 72 69 6e 74 20 70 65 72 6d 0a 20 20 20    print perm.   
2530: 20 5b 27 61 27 2c 20 27 62 27 2c 20 27 63 27 5d   ['a', 'b', 'c']
2540: 0a 20 20 20 20 5b 27 61 27 2c 20 27 63 27 2c 20  .    ['a', 'c', 
2550: 27 62 27 5d 0a 20 20 20 20 5b 27 62 27 2c 20 27  'b'].    ['b', '
2560: 61 27 2c 20 27 63 27 5d 0a 20 20 20 20 5b 27 62  a', 'c'].    ['b
2570: 27 2c 20 27 63 27 2c 20 27 61 27 5d 0a 20 20 20  ', 'c', 'a'].   
2580: 20 5b 27 63 27 2c 20 27 61 27 2c 20 27 62 27 5d   ['c', 'a', 'b']
2590: 0a 20 20 20 20 5b 27 63 27 2c 20 27 62 27 2c 20  .    ['c', 'b', 
25a0: 27 61 27 5d 0a 0a 20 20 20 20 22 22 22 0a 20 20  'a']..    """.  
25b0: 20 20 6f 75 74 5f 6c 69 73 74 73 20 3d 20 5b 5d    out_lists = []
25c0: 0a 20 20 20 20 69 66 20 6c 65 6e 28 69 6e 70 75  .    if len(inpu
25d0: 74 5f 6c 69 73 74 29 20 3e 20 31 3a 0a 20 20 20  t_list) > 1:.   
25e0: 20 20 20 20 20 23 20 45 78 74 72 61 63 74 20 66       # Extract f
25f0: 69 72 73 74 20 69 74 65 6d 20 69 6e 20 6c 69 73  irst item in lis
2600: 74 2e 0a 20 20 20 20 20 20 20 20 69 74 65 6d 20  t..        item 
2610: 3d 20 69 6e 70 75 74 5f 6c 69 73 74 5b 30 5d 0a  = input_list[0].
2620: 20 20 20 20 20 20 20 20 23 20 46 69 6e 64 20 61          # Find a
2630: 6c 6c 20 70 65 72 6d 75 74 61 74 69 6f 6e 73 20  ll permutations 
2640: 6f 66 20 72 65 6d 61 69 6e 64 65 72 20 6f 66 20  of remainder of 
2650: 6c 69 73 74 2e 20 28 52 65 63 75 72 73 69 76 65  list. (Recursive
2660: 20 63 61 6c 6c 2e 29 0a 20 20 20 20 20 20 20 20   call.).        
2670: 73 75 62 5f 6c 69 73 74 73 20 3d 20 70 65 72 6d  sub_lists = perm
2680: 75 74 61 74 69 6f 6e 73 28 69 6e 70 75 74 5f 6c  utations(input_l
2690: 69 73 74 5b 31 3a 5d 29 0a 20 20 20 20 20 20 20  ist[1:]).       
26a0: 20 23 20 46 6f 72 20 65 76 65 72 79 20 70 65 72   # For every per
26b0: 6d 75 74 61 74 69 6f 6e 20 6f 66 20 74 68 65 20  mutation of the 
26c0: 73 75 62 20 6c 69 73 74 2e 2e 2e 0a 20 20 20 20  sub list....    
26d0: 20 20 20 20 66 6f 72 20 73 75 62 5f 6c 69 73 74      for sub_list
26e0: 20 69 6e 20 73 75 62 5f 6c 69 73 74 73 3a 0a 20   in sub_lists:. 
26f0: 20 20 20 20 20 20 20 20 20 20 20 23 20 49 6e 73             # Ins
2700: 65 72 74 20 74 68 65 20 65 78 74 72 61 63 74 65  ert the extracte
2710: 64 20 66 69 72 73 74 20 69 74 65 6d 20 61 74 20  d first item at 
2720: 65 76 65 72 79 20 70 6f 73 69 74 69 6f 6e 20 6f  every position o
2730: 66 20 74 68 65 20 6c 69 73 74 2e 0a 20 20 20 20  f the list..    
2740: 20 20 20 20 20 20 20 20 66 6f 72 20 69 20 69 6e          for i in
2750: 20 72 61 6e 67 65 28 6c 65 6e 28 69 6e 70 75 74   range(len(input
2760: 5f 6c 69 73 74 29 29 3a 0a 20 20 20 20 20 20 20  _list)):.       
2770: 20 20 20 20 20 20 20 20 20 6e 65 77 5f 6c 69 73           new_lis
2780: 74 20 3d 20 73 75 62 5f 6c 69 73 74 5b 3a 5d 0a  t = sub_list[:].
2790: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
27a0: 6e 65 77 5f 6c 69 73 74 2e 69 6e 73 65 72 74 28  new_list.insert(
27b0: 69 2c 20 69 74 65 6d 29 0a 20 20 20 20 20 20 20  i, item).       
27c0: 20 20 20 20 20 20 20 20 20 6f 75 74 5f 6c 69 73           out_lis
27d0: 74 73 2e 61 70 70 65 6e 64 28 6e 65 77 5f 6c 69  ts.append(new_li
27e0: 73 74 29 0a 20 20 20 20 65 6c 73 65 3a 0a 20 20  st).    else:.  
27f0: 20 20 20 20 20 20 23 20 54 65 72 6d 69 6e 61 74        # Terminat
2800: 69 6f 6e 20 63 6f 6e 64 69 74 69 6f 6e 3a 20 6f  ion condition: o
2810: 6e 6c 79 20 6f 6e 65 20 69 74 65 6d 20 69 6e 20  nly one item in 
2820: 69 6e 70 75 74 20 6c 69 73 74 2e 0a 20 20 20 20  input list..    
2830: 20 20 20 20 6f 75 74 5f 6c 69 73 74 73 20 3d 20      out_lists = 
2840: 5b 69 6e 70 75 74 5f 6c 69 73 74 5d 0a 20 20 20  [input_list].   
2850: 20 72 65 74 75 72 6e 20 6f 75 74 5f 6c 69 73 74   return out_list
2860: 73 0a 0a 0a 64 65 66 20 72 65 64 75 63 65 5f 66  s...def reduce_f
2870: 72 61 63 74 69 6f 6e 28 66 72 61 63 74 69 6f 6e  raction(fraction
2880: 29 3a 0a 20 20 20 20 22 22 22 52 65 64 75 63 65  ):.    """Reduce
2890: 20 66 72 61 63 74 69 6f 6e 20 74 75 70 6c 65 20   fraction tuple 
28a0: 74 6f 20 73 69 6d 70 6c 65 73 74 20 66 6f 72 6d  to simplest form
28b0: 2e 20 66 72 61 63 74 69 6f 6e 3d 28 6e 75 6d 2c  . fraction=(num,
28c0: 20 64 65 6e 6f 6d 29 0a 20 20 20 20 0a 20 20 20   denom).    .   
28d0: 20 3e 3e 3e 20 72 65 64 75 63 65 5f 66 72 61 63   >>> reduce_frac
28e0: 74 69 6f 6e 28 28 31 34 2c 20 37 29 29 0a 20 20  tion((14, 7)).  
28f0: 20 20 28 32 2c 20 31 29 0a 0a 20 20 20 20 3e 3e    (2, 1)..    >>
2900: 3e 20 72 65 64 75 63 65 5f 66 72 61 63 74 69 6f  > reduce_fractio
2910: 6e 28 28 2d 32 2c 20 34 29 29 0a 20 20 20 20 28  n((-2, 4)).    (
2920: 2d 31 2c 20 32 29 0a 0a 20 20 20 20 3e 3e 3e 20  -1, 2)..    >>> 
2930: 72 65 64 75 63 65 5f 66 72 61 63 74 69 6f 6e 28  reduce_fraction(
2940: 28 30 2c 20 34 29 29 0a 20 20 20 20 28 30 2c 20  (0, 4)).    (0, 
2950: 31 29 0a 0a 20 20 20 20 3e 3e 3e 20 72 65 64 75  1)..    >>> redu
2960: 63 65 5f 66 72 61 63 74 69 6f 6e 28 28 34 2c 20  ce_fraction((4, 
2970: 30 29 29 0a 20 20 20 20 28 31 2c 20 30 29 0a 20  0)).    (1, 0). 
2980: 20 20 20 0a 20 20 20 20 22 22 22 0a 20 20 20 20     .    """.    
2990: 28 6e 75 6d 65 72 61 74 6f 72 2c 20 64 65 6e 6f  (numerator, deno
29a0: 6d 69 6e 61 74 6f 72 29 20 3d 20 66 72 61 63 74  minator) = fract
29b0: 69 6f 6e 0a 20 20 20 20 63 6f 6d 6d 6f 6e 5f 66  ion.    common_f
29c0: 61 63 74 6f 72 20 3d 20 61 62 73 28 67 63 66 28  actor = abs(gcf(
29d0: 6e 75 6d 65 72 61 74 6f 72 2c 20 64 65 6e 6f 6d  numerator, denom
29e0: 69 6e 61 74 6f 72 29 29 0a 20 20 20 20 72 65 73  inator)).    res
29f0: 75 6c 74 20 3d 20 28 6e 75 6d 65 72 61 74 6f 72  ult = (numerator
2a00: 2f 63 6f 6d 6d 6f 6e 5f 66 61 63 74 6f 72 2c 20  /common_factor, 
2a10: 64 65 6e 6f 6d 69 6e 61 74 6f 72 2f 63 6f 6d 6d  denominator/comm
2a20: 6f 6e 5f 66 61 63 74 6f 72 29 0a 20 20 20 20 72  on_factor).    r
2a30: 65 74 75 72 6e 20 72 65 73 75 6c 74 0a 0a 0a 64  eturn result...d
2a40: 65 66 20 71 75 61 6e 74 69 6c 65 28 6c 2c 20 70  ef quantile(l, p
2a50: 29 3a 0a 20 20 20 20 22 22 22 52 65 74 75 72 6e  ):.    """Return
2a60: 20 70 20 71 75 61 6e 74 69 6c 65 20 6f 66 20 6c   p quantile of l
2a70: 69 73 74 20 6c 2e 20 45 2e 67 2e 20 70 3d 30 2e  ist l. E.g. p=0.
2a80: 32 35 20 66 6f 72 20 71 31 2e 0a 0a 20 20 20 20  25 for q1...    
2a90: 53 65 65 3a 0a 20 20 20 20 68 74 74 70 3a 2f 2f  See:.    http://
2aa0: 72 77 65 62 2e 73 74 61 74 2e 75 6d 6e 2e 65 64  rweb.stat.umn.ed
2ab0: 75 2f 52 2f 6c 69 62 72 61 72 79 2f 62 61 73 65  u/R/library/base
2ac0: 2f 68 74 6d 6c 2f 71 75 61 6e 74 69 6c 65 2e 68  /html/quantile.h
2ad0: 74 6d 6c 0a 0a 20 20 20 20 22 22 22 0a 20 20 20  tml..    """.   
2ae0: 20 6c 5f 73 6f 72 74 20 3d 20 6c 5b 3a 5d 0a 20   l_sort = l[:]. 
2af0: 20 20 20 6c 5f 73 6f 72 74 2e 73 6f 72 74 28 29     l_sort.sort()
2b00: 0a 20 20 20 20 6e 20 3d 20 6c 65 6e 28 6c 29 0a  .    n = len(l).
2b10: 20 20 20 20 72 20 3d 20 31 20 2b 20 28 28 6e 20      r = 1 + ((n 
2b20: 2d 20 31 29 20 2a 20 70 29 0a 20 20 20 20 69 20  - 1) * p).    i 
2b30: 3d 20 69 6e 74 28 72 29 0a 20 20 20 20 66 20 3d  = int(r).    f =
2b40: 20 72 20 2d 20 69 0a 20 20 20 20 69 66 20 69 20   r - i.    if i 
2b50: 3c 20 6e 3a 0a 20 20 20 20 20 20 20 20 72 65 73  < n:.        res
2b60: 75 6c 74 20 3d 20 20 28 31 2d 66 29 2a 6c 5f 73  ult =  (1-f)*l_s
2b70: 6f 72 74 5b 69 2d 31 5d 20 2b 20 66 2a 6c 5f 73  ort[i-1] + f*l_s
2b80: 6f 72 74 5b 69 5d 0a 20 20 20 20 65 6c 73 65 3a  ort[i].    else:
2b90: 0a 20 20 20 20 20 20 20 20 72 65 73 75 6c 74 20  .        result 
2ba0: 3d 20 6c 5f 73 6f 72 74 5b 69 2d 31 5d 0a 20 20  = l_sort[i-1].  
2bb0: 20 20 72 65 74 75 72 6e 20 72 65 73 75 6c 74 0a    return result.
2bc0: 0a 0a 64 65 66 20 74 72 69 6d 28 6c 29 3a 0a 20  ..def trim(l):. 
2bd0: 20 20 20 22 22 22 44 69 73 63 61 72 64 20 76 61     """Discard va
2be0: 6c 75 65 73 20 69 6e 20 6c 69 73 74 20 6d 6f 72  lues in list mor
2bf0: 65 20 74 68 61 6e 20 31 2e 35 2a 49 51 52 20 6f  e than 1.5*IQR o
2c00: 75 74 73 69 64 65 20 49 51 52 2e 0a 0a 20 20 20  utside IQR...   
2c10: 20 28 49 51 52 20 69 73 20 69 6e 74 65 72 2d 71   (IQR is inter-q
2c20: 75 61 72 74 69 6c 65 2d 72 61 6e 67 65 29 0a 0a  uartile-range)..
2c30: 20 20 20 20 54 68 69 73 20 66 75 6e 63 74 69 6f      This functio
2c40: 6e 20 75 73 65 73 20 72 61 64 5f 75 74 69 6c 2e  n uses rad_util.
2c50: 71 75 61 6e 74 69 6c 65 0a 0a 20 20 20 20 31 2e  quantile..    1.
2c60: 35 2a 49 51 52 20 2d 2d 20 6d 69 6c 64 20 6f 75  5*IQR -- mild ou
2c70: 74 6c 69 65 72 0a 20 20 20 20 33 2a 49 51 52 20  tlier.    3*IQR 
2c80: 2d 2d 20 65 78 74 72 65 6d 65 20 6f 75 74 6c 69  -- extreme outli
2c90: 65 72 0a 0a 20 20 20 20 53 65 65 3a 0a 20 20 20  er..    See:.   
2ca0: 20 68 74 74 70 3a 2f 2f 77 69 6e 64 2e 63 63 2e   http://wind.cc.
2cb0: 77 68 65 63 6e 2e 65 64 75 2f 7e 70 77 69 6c 64  whecn.edu/~pwild
2cc0: 6d 61 6e 2f 73 74 61 74 6e 65 77 2f 73 65 63 74  man/statnew/sect
2cd0: 69 6f 6e 5f 37 5f 2d 5f 65 78 70 6c 6f 72 61 74  ion_7_-_explorat
2ce0: 6f 72 79 5f 64 61 74 61 5f 61 6e 61 6c 79 73 69  ory_data_analysi
2cf0: 73 2e 68 74 6d 0a 0a 20 20 20 20 22 22 22 0a 20  s.htm..    """. 
2d00: 20 20 20 6c 5f 73 6f 72 74 20 3d 20 6c 5b 3a 5d     l_sort = l[:]
2d10: 0a 20 20 20 20 6c 5f 73 6f 72 74 2e 73 6f 72 74  .    l_sort.sort
2d20: 28 29 0a 20 20 20 20 23 20 43 61 6c 63 75 6c 61  ().    # Calcula
2d30: 74 65 20 6d 65 64 69 61 6e 73 63 6f 72 65 20 20  te medianscore  
2d40: 28 62 61 73 65 64 20 6f 6e 20 73 74 61 74 73 2e  (based on stats.
2d50: 70 79 20 6c 6d 65 64 69 61 6e 73 63 6f 72 65 20  py lmedianscore 
2d60: 62 79 20 47 61 72 79 20 53 74 72 61 6e 67 6d 61  by Gary Strangma
2d70: 6e 29 0a 20 20 20 20 69 66 20 6c 65 6e 28 6c 5f  n).    if len(l_
2d80: 73 6f 72 74 29 20 25 20 32 20 3d 3d 20 30 3a 0a  sort) % 2 == 0:.
2d90: 20 20 20 20 20 20 20 20 23 20 49 66 20 65 76 65          # If eve
2da0: 6e 20 6e 75 6d 62 65 72 20 6f 66 20 73 63 6f 72  n number of scor
2db0: 65 73 2c 20 61 76 65 72 61 67 65 20 6d 69 64 64  es, average midd
2dc0: 6c 65 20 32 2e 0a 20 20 20 20 20 20 20 20 69 6e  le 2..        in
2dd0: 64 65 78 20 3d 20 69 6e 74 28 6c 65 6e 28 6c 5f  dex = int(len(l_
2de0: 73 6f 72 74 29 20 2f 20 32 29 20 20 23 20 49 6e  sort) / 2)  # In
2df0: 74 65 67 65 72 20 64 69 76 69 73 69 6f 6e 20 63  teger division c
2e00: 6f 72 72 65 63 74 0a 20 20 20 20 20 20 20 20 6d  orrect.        m
2e10: 65 64 69 61 6e 20 3d 20 66 6c 6f 61 74 28 6c 5f  edian = float(l_
2e20: 73 6f 72 74 5b 69 6e 64 65 78 5d 20 2b 20 6c 5f  sort[index] + l_
2e30: 73 6f 72 74 5b 69 6e 64 65 78 2d 31 5d 29 20 2f  sort[index-1]) /
2e40: 20 32 0a 20 20 20 20 65 6c 73 65 3a 0a 20 20 20   2.    else:.   
2e50: 20 20 20 20 20 23 20 69 6e 74 20 64 69 76 73 69       # int divsi
2e60: 6f 6e 20 67 69 76 65 73 20 6d 69 64 20 76 61 6c  on gives mid val
2e70: 75 65 20 77 68 65 6e 20 63 6f 75 6e 74 20 66 72  ue when count fr
2e80: 6f 6d 20 30 0a 20 20 20 20 20 20 20 20 69 6e 64  om 0.        ind
2e90: 65 78 20 3d 20 69 6e 74 28 6c 65 6e 28 6c 5f 73  ex = int(len(l_s
2ea0: 6f 72 74 29 20 2f 20 32 29 0a 20 20 20 20 20 20  ort) / 2).      
2eb0: 20 20 6d 65 64 69 61 6e 20 3d 20 6c 5f 73 6f 72    median = l_sor
2ec0: 74 5b 69 6e 64 65 78 5d 0a 20 20 20 20 23 20 43  t[index].    # C
2ed0: 61 6c 63 75 6c 61 74 65 20 49 51 52 2e 0a 20 20  alculate IQR..  
2ee0: 20 20 71 31 20 3d 20 71 75 61 6e 74 69 6c 65 28    q1 = quantile(
2ef0: 6c 5f 73 6f 72 74 2c 20 30 2e 32 35 29 0a 20 20  l_sort, 0.25).  
2f00: 20 20 71 33 20 3d 20 71 75 61 6e 74 69 6c 65 28    q3 = quantile(
2f10: 6c 5f 73 6f 72 74 2c 20 30 2e 37 35 29 0a 20 20  l_sort, 0.75).  
2f20: 20 20 69 71 72 20 3d 20 71 33 20 2d 20 71 31 0a    iqr = q3 - q1.
2f30: 20 20 20 20 69 71 72 5f 65 78 74 72 61 20 3d 20      iqr_extra = 
2f40: 69 71 72 20 2a 20 31 2e 35 0a 20 20 20 20 64 65  iqr * 1.5.    de
2f50: 66 20 69 6e 5f 69 6e 74 65 72 76 61 6c 28 78 2c  f in_interval(x,
2f60: 20 69 3d 69 71 72 5f 65 78 74 72 61 2c 20 71 31   i=iqr_extra, q1
2f70: 3d 71 31 2c 20 71 33 3d 71 33 29 3a 0a 20 20 20  =q1, q3=q3):.   
2f80: 20 20 20 20 20 72 65 74 75 72 6e 20 28 78 20 3e       return (x >
2f90: 3d 20 71 31 2d 69 20 61 6e 64 20 78 20 3c 3d 20  = q1-i and x <= 
2fa0: 71 33 2b 69 29 0a 20 20 20 20 6c 5f 74 72 69 6d  q3+i).    l_trim
2fb0: 6d 65 64 20 3d 20 5b 78 20 66 6f 72 20 78 20 69  med = [x for x i
2fc0: 6e 20 6c 5f 73 6f 72 74 20 69 66 20 69 6e 5f 69  n l_sort if in_i
2fd0: 6e 74 65 72 76 61 6c 28 78 29 5d 0a 20 20 20 20  nterval(x)].    
2fe0: 72 65 74 75 72 6e 20 6c 5f 74 72 69 6d 6d 65 64  return l_trimmed
2ff0: 0a 0a 0a 64 65 66 20 6e 69 63 65 5f 75 6e 69 74  ...def nice_unit
3000: 73 28 76 61 6c 75 65 2c 20 64 70 3d 30 2c 20 73  s(value, dp=0, s
3010: 69 67 66 69 67 73 3d 4e 6f 6e 65 2c 20 73 75 66  igfigs=None, suf
3020: 66 69 78 3d 27 27 2c 20 73 70 61 63 65 3d 27 20  fix='', space=' 
3030: 27 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ',.             
3040: 20 20 75 73 65 5f 65 78 74 72 61 5f 70 72 65 66    use_extra_pref
3050: 69 78 65 73 3d 46 61 6c 73 65 2c 20 75 73 65 5f  ixes=False, use_
3060: 66 75 6c 6c 5f 6e 61 6d 65 3d 46 61 6c 73 65 2c  full_name=False,
3070: 20 6d 6f 64 65 3d 27 73 69 27 29 3a 0a 20 20 20   mode='si'):.   
3080: 20 22 22 22 52 65 74 75 72 6e 20 76 61 6c 75 65   """Return value
3090: 20 63 6f 6e 76 65 72 74 65 64 20 74 6f 20 68 75   converted to hu
30a0: 6d 61 6e 20 72 65 61 64 61 62 6c 65 20 75 6e 69  man readable uni
30b0: 74 73 20 65 67 20 6d 69 6c 6c 69 2c 20 6d 69 63  ts eg milli, mic
30c0: 72 6f 2c 20 65 74 63 2e 0a 0a 20 20 20 20 41 72  ro, etc...    Ar
30d0: 67 75 6d 65 6e 74 73 3a 0a 20 20 20 20 76 61 6c  guments:.    val
30e0: 75 65 20 2d 2d 20 6e 75 6d 62 65 72 20 69 6e 20  ue -- number in 
30f0: 62 61 73 65 20 75 6e 69 74 73 0a 20 20 20 20 64  base units.    d
3100: 70 20 2d 2d 20 6e 75 6d 62 65 72 20 6f 66 20 64  p -- number of d
3110: 65 63 69 6d 61 6c 20 70 6c 61 63 65 73 20 74 6f  ecimal places to
3120: 20 64 69 73 70 6c 61 79 20 28 72 6f 75 6e 64 65   display (rounde
3130: 64 29 0a 20 20 20 20 73 69 67 66 69 67 73 20 2d  d).    sigfigs -
3140: 2d 20 6e 75 6d 62 65 72 20 6f 66 20 73 69 67 6e  - number of sign
3150: 69 66 69 63 61 6e 74 20 66 69 67 75 72 65 73 20  ificant figures 
3160: 74 6f 20 64 69 73 70 6c 61 79 20 28 72 6f 75 6e  to display (roun
3170: 64 65 64 29 0a 20 20 20 20 20 20 20 20 20 20 20  ded).           
3180: 20 20 20 20 54 68 69 73 20 6f 76 65 72 72 69 64      This overrid
3190: 65 73 20 64 70 20 69 66 20 73 65 74 2e 0a 20 20  es dp if set..  
31a0: 20 20 73 75 66 66 69 78 20 2d 2d 20 6f 70 74 69    suffix -- opti
31b0: 6f 6e 61 6c 20 75 6e 69 74 20 73 75 66 66 69 78  onal unit suffix
31c0: 20 74 6f 20 61 70 70 65 6e 64 20 74 6f 20 75 6e   to append to un
31d0: 69 74 20 6d 75 6c 74 69 70 6c 69 65 72 0a 20 20  it multiplier.  
31e0: 20 20 73 70 61 63 65 20 2d 2d 20 73 65 70 65 72    space -- seper
31f0: 61 74 6f 72 20 62 65 74 77 65 65 6e 20 76 61 6c  ator between val
3200: 75 65 20 61 6e 64 20 75 6e 69 74 20 6d 75 6c 74  ue and unit mult
3210: 69 70 6c 69 65 72 20 28 64 65 66 61 75 6c 74 3a  iplier (default:
3220: 20 27 20 27 29 0a 20 20 20 20 75 73 65 5f 65 78   ' ').    use_ex
3230: 74 72 61 5f 70 72 65 66 69 78 65 73 20 2d 2d 20  tra_prefixes -- 
3240: 75 73 65 20 68 65 63 74 6f 2c 20 64 65 6b 61 2c  use hecto, deka,
3250: 20 64 65 63 69 20 61 6e 64 20 63 65 6e 74 69 20   deci and centi 
3260: 61 73 20 77 65 6c 6c 20 69 66 20 73 65 74 2e 0a  as well if set..
3270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3280: 20 20 20 20 20 20 20 20 20 20 28 64 65 66 61 75            (defau
3290: 6c 74 3a 20 46 61 6c 73 65 29 0a 20 20 20 20 75  lt: False).    u
32a0: 73 65 5f 66 75 6c 6c 5f 6e 61 6d 65 20 2d 2d 20  se_full_name -- 
32b0: 75 73 65 20 66 75 6c 6c 20 6e 61 6d 65 20 66 6f  use full name fo
32c0: 72 20 6d 75 6c 74 69 70 6c 69 65 72 20 73 79 6d  r multiplier sym
32d0: 62 6f 6c 2c 0a 20 20 20 20 20 20 20 20 20 20 20  bol,.           
32e0: 20 20 20 20 20 20 20 20 20 20 65 2e 67 2e 20 6d            e.g. m
32f0: 69 6c 6c 69 20 69 6e 73 74 65 61 64 20 6f 66 20  illi instead of 
3300: 6d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  m.              
3310: 20 20 20 20 20 20 20 28 64 65 66 61 75 6c 74 3a         (default:
3320: 20 46 61 6c 73 65 29 0a 20 20 20 20 6d 6f 64 65   False).    mode
3330: 20 2d 2d 20 27 73 69 27 20 66 6f 72 20 53 49 20   -- 'si' for SI 
3340: 70 72 65 66 69 78 65 73 2c 20 27 62 69 6e 27 20  prefixes, 'bin' 
3350: 66 6f 72 20 62 69 6e 61 72 79 20 6d 75 6c 74 69  for binary multi
3360: 70 6c 69 65 72 73 20 28 31 30 32 34 2c 20 65 74  pliers (1024, et
3370: 63 2e 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  c.).            
3380: 28 44 65 66 61 75 6c 74 3a 20 27 73 69 27 29 0a  (Default: 'si').
3390: 0a 20 20 20 20 53 49 20 70 72 65 66 69 78 65 73  .    SI prefixes
33a0: 20 66 72 6f 6d 3a 0a 20 20 20 20 68 74 74 70 3a   from:.    http:
33b0: 2f 2f 70 68 79 73 69 63 73 2e 6e 69 73 74 2e 67  //physics.nist.g
33c0: 6f 76 2f 63 75 75 2f 55 6e 69 74 73 2f 70 72 65  ov/cuu/Units/pre
33d0: 66 69 78 65 73 2e 68 74 6d 6c 0a 20 20 20 20 28  fixes.html.    (
33e0: 47 72 65 65 6b 20 6d 75 20 63 68 61 6e 67 65 64  Greek mu changed
33f0: 20 74 6f 20 75 2e 29 0a 20 20 20 20 42 69 6e 61   to u.).    Bina
3400: 72 79 20 70 72 65 66 69 78 65 73 20 62 61 73 65  ry prefixes base
3410: 64 20 6f 6e 3a 0a 20 20 20 20 68 74 74 70 3a 2f  d on:.    http:/
3420: 2f 70 68 79 73 69 63 73 2e 6e 69 73 74 2e 67 6f  /physics.nist.go
3430: 76 2f 63 75 75 2f 55 6e 69 74 73 2f 62 69 6e 61  v/cuu/Units/bina
3440: 72 79 2e 68 74 6d 6c 0a 0a 20 20 20 20 3e 3e 3e  ry.html..    >>>
3450: 20 6e 69 63 65 5f 75 6e 69 74 73 28 32 65 2d 31   nice_units(2e-1
3460: 31 29 0a 20 20 20 20 27 32 30 20 70 27 0a 0a 20  1).    '20 p'.. 
3470: 20 20 20 3e 3e 3e 20 6e 69 63 65 5f 75 6e 69 74     >>> nice_unit
3480: 73 28 32 65 2d 31 31 2c 20 73 70 61 63 65 3d 27  s(2e-11, space='
3490: 27 29 0a 20 20 20 20 27 32 30 70 27 0a 0a 20 20  ').    '20p'..  
34a0: 20 20 22 22 22 0a 20 20 20 20 73 69 5f 70 72 65    """.    si_pre
34b0: 66 69 78 65 73 20 3d 20 7b 31 65 32 34 3a 20 20  fixes = {1e24:  
34c0: 28 27 59 27 2c 20 27 79 6f 74 74 61 27 29 2c 0a  ('Y', 'yotta'),.
34d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
34e0: 20 20 20 31 65 32 31 3a 20 20 28 27 5a 27 2c 20     1e21:  ('Z', 
34f0: 27 7a 65 74 74 61 27 29 2c 0a 20 20 20 20 20 20  'zetta'),.      
3500: 20 20 20 20 20 20 20 20 20 20 20 20 20 31 65 31               1e1
3510: 38 3a 20 20 28 27 45 27 2c 20 27 65 78 61 27 29  8:  ('E', 'exa')
3520: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,.              
3530: 20 20 20 20 20 31 65 31 35 3a 20 20 28 27 50 27       1e15:  ('P'
3540: 2c 20 27 70 65 74 61 27 29 2c 0a 20 20 20 20 20  , 'peta'),.     
3550: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31 65                1e
3560: 31 32 3a 20 20 28 27 54 27 2c 20 27 74 65 72 61  12:  ('T', 'tera
3570: 27 29 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20  '),.            
3580: 20 20 20 20 20 20 20 31 65 39 3a 20 20 20 28 27         1e9:   ('
3590: 47 27 2c 20 27 67 69 67 61 27 29 2c 0a 20 20 20  G', 'giga'),.   
35a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
35b0: 31 65 36 3a 20 20 20 28 27 4d 27 2c 20 27 6d 65  1e6:   ('M', 'me
35c0: 67 61 27 29 2c 0a 20 20 20 20 20 20 20 20 20 20  ga'),.          
35d0: 20 20 20 20 20 20 20 20 20 31 65 33 3a 20 20 20           1e3:   
35e0: 28 27 6b 27 2c 20 27 6b 69 6c 6f 27 29 2c 0a 20  ('k', 'kilo'),. 
35f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3600: 20 20 31 65 2d 33 3a 20 20 28 27 6d 27 2c 20 27    1e-3:  ('m', '
3610: 6d 69 6c 6c 69 27 29 2c 0a 20 20 20 20 20 20 20  milli'),.       
3620: 20 20 20 20 20 20 20 20 20 20 20 20 31 65 2d 36              1e-6
3630: 3a 20 20 28 27 75 27 2c 20 27 6d 69 63 72 6f 27  :  ('u', 'micro'
3640: 29 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ),.             
3650: 20 20 20 20 20 20 31 65 2d 39 3a 20 20 28 27 6e        1e-9:  ('n
3660: 27 2c 20 27 6e 61 6e 6f 27 29 2c 0a 20 20 20 20  ', 'nano'),.    
3670: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 31                 1
3680: 65 2d 31 32 3a 20 28 27 70 27 2c 20 27 70 69 63  e-12: ('p', 'pic
3690: 6f 27 29 2c 0a 20 20 20 20 20 20 20 20 20 20 20  o'),.           
36a0: 20 20 20 20 20 20 20 20 31 65 2d 31 35 3a 20 28          1e-15: (
36b0: 27 66 27 2c 20 27 66 65 6d 74 6f 27 29 2c 0a 20  'f', 'femto'),. 
36c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
36d0: 20 20 31 65 2d 31 38 3a 20 28 27 61 27 2c 20 27    1e-18: ('a', '
36e0: 61 74 74 6f 27 29 2c 0a 20 20 20 20 20 20 20 20  atto'),.        
36f0: 20 20 20 20 20 20 20 20 20 20 20 31 65 2d 32 31             1e-21
3700: 3a 20 28 27 7a 27 2c 20 27 7a 65 70 74 6f 27 29  : ('z', 'zepto')
3710: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,.              
3720: 20 20 20 20 20 31 65 2d 32 34 3a 20 28 27 79 27       1e-24: ('y'
3730: 2c 20 27 79 6f 63 74 6f 27 29 0a 20 20 20 20 20  , 'yocto').     
3740: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
3750: 20 20 20 20 69 66 20 75 73 65 5f 65 78 74 72 61      if use_extra
3760: 5f 70 72 65 66 69 78 65 73 3a 0a 20 20 20 20 20  _prefixes:.     
3770: 20 20 20 73 69 5f 70 72 65 66 69 78 65 73 2e 75     si_prefixes.u
3780: 70 64 61 74 65 28 7b 31 65 32 3a 20 20 28 27 68  pdate({1e2:  ('h
3790: 27 2c 20 27 68 65 63 74 6f 27 29 2c 0a 20 20 20  ', 'hecto'),.   
37a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
37b0: 20 20 20 20 20 20 20 20 20 31 65 31 3a 20 20 28           1e1:  (
37c0: 27 64 61 27 2c 20 27 64 65 6b 61 27 29 2c 0a 20  'da', 'deka'),. 
37d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
37e0: 20 20 20 20 20 20 20 20 20 20 20 31 65 2d 31 3a             1e-1:
37f0: 20 28 27 64 27 2c 20 27 64 65 63 69 27 29 2c 0a   ('d', 'deci'),.
3800: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3810: 20 20 20 20 20 20 20 20 20 20 20 20 31 65 2d 32              1e-2
3820: 3a 20 28 27 63 27 2c 20 27 63 65 6e 74 69 27 29  : ('c', 'centi')
3830: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
3840: 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 29 0a               }).
3850: 20 20 20 20 62 69 6e 5f 70 72 65 66 69 78 65 73      bin_prefixes
3860: 20 3d 20 7b 32 2a 2a 31 30 3a 20 28 27 4b 27 2c   = {2**10: ('K',
3870: 20 27 6b 69 6c 6f 27 29 2c 0a 20 20 20 20 20 20   'kilo'),.      
3880: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 32 2a                2*
3890: 2a 32 30 3a 20 28 27 4d 27 2c 20 27 6d 65 67 61  *20: ('M', 'mega
38a0: 27 29 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20  '),.            
38b0: 20 20 20 20 20 20 20 20 32 2a 2a 33 30 3a 20 28          2**30: (
38c0: 27 47 27 2c 20 27 6d 65 67 61 27 29 2c 0a 20 20  'G', 'mega'),.  
38d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
38e0: 20 20 32 2a 2a 34 30 3a 20 28 27 54 27 2c 20 27    2**40: ('T', '
38f0: 74 65 72 61 27 29 2c 0a 20 20 20 20 20 20 20 20  tera'),.        
3900: 20 20 20 20 20 20 20 20 20 20 20 20 32 2a 2a 35              2**5
3910: 30 3a 20 28 27 50 27 2c 20 27 70 65 74 61 27 29  0: ('P', 'peta')
3920: 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,.              
3930: 20 20 20 20 20 20 32 2a 2a 36 30 3a 20 28 27 45        2**60: ('E
3940: 27 2c 20 27 65 78 61 27 29 0a 20 20 20 20 20 20  ', 'exa').      
3950: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 7d 0a                }.
3960: 20 20 20 20 69 66 20 6d 6f 64 65 20 3d 3d 20 27      if mode == '
3970: 62 69 6e 27 3a 0a 20 20 20 20 20 20 20 20 70 72  bin':.        pr
3980: 65 66 69 78 65 73 20 3d 20 62 69 6e 5f 70 72 65  efixes = bin_pre
3990: 66 69 78 65 73 0a 20 20 20 20 65 6c 73 65 3a 0a  fixes.    else:.
39a0: 20 20 20 20 20 20 20 20 70 72 65 66 69 78 65 73          prefixes
39b0: 20 3d 20 73 69 5f 70 72 65 66 69 78 65 73 0a 20   = si_prefixes. 
39c0: 20 20 20 70 72 65 66 69 78 65 73 5b 31 5d 20 3d     prefixes[1] =
39d0: 20 28 27 27 2c 20 27 27 29 20 20 23 20 55 6e 69   ('', '')  # Uni
39e0: 74 79 2e 0a 20 20 20 20 23 20 44 65 74 65 72 6d  ty..    # Determ
39f0: 69 6e 65 20 61 70 70 72 6f 70 72 69 61 74 65 20  ine appropriate 
3a00: 6d 75 6c 74 69 70 6c 69 65 72 2e 0a 20 20 20 20  multiplier..    
3a10: 6d 75 6c 74 69 70 6c 69 65 72 73 20 3d 20 70 72  multipliers = pr
3a20: 65 66 69 78 65 73 2e 6b 65 79 73 28 29 0a 20 20  efixes.keys().  
3a30: 20 20 6d 75 6c 74 69 70 6c 69 65 72 73 2e 73 6f    multipliers.so
3a40: 72 74 28 29 0a 20 20 20 20 6d 75 6c 74 20 3d 20  rt().    mult = 
3a50: 4e 6f 6e 65 0a 20 20 20 20 66 6f 72 20 69 20 69  None.    for i i
3a60: 6e 20 72 61 6e 67 65 28 6c 65 6e 28 6d 75 6c 74  n range(len(mult
3a70: 69 70 6c 69 65 72 73 29 20 2d 20 31 29 3a 0a 20  ipliers) - 1):. 
3a80: 20 20 20 20 20 20 20 6c 6f 77 65 72 5f 6d 75 6c         lower_mul
3a90: 74 20 3d 20 6d 75 6c 74 69 70 6c 69 65 72 73 5b  t = multipliers[
3aa0: 69 5d 0a 20 20 20 20 20 20 20 20 75 70 70 65 72  i].        upper
3ab0: 5f 6d 75 6c 74 20 3d 20 6d 75 6c 74 69 70 6c 69  _mult = multipli
3ac0: 65 72 73 5b 69 2b 31 5d 0a 20 20 20 20 20 20 20  ers[i+1].       
3ad0: 20 69 66 20 6c 6f 77 65 72 5f 6d 75 6c 74 20 3c   if lower_mult <
3ae0: 3d 20 76 61 6c 75 65 20 3c 20 75 70 70 65 72 5f  = value < upper_
3af0: 6d 75 6c 74 3a 0a 20 20 20 20 20 20 20 20 20 20  mult:.          
3b00: 20 20 6d 75 6c 74 5f 69 20 3d 20 69 0a 20 20 20    mult_i = i.   
3b10: 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 0a 20           break. 
3b20: 20 20 20 69 66 20 6d 75 6c 74 20 69 73 20 4e 6f     if mult is No
3b30: 6e 65 3a 0a 20 20 20 20 20 20 20 20 69 66 20 76  ne:.        if v
3b40: 61 6c 75 65 20 3c 20 6d 75 6c 74 69 70 6c 69 65  alue < multiplie
3b50: 72 73 5b 30 5d 3a 0a 20 20 20 20 20 20 20 20 20  rs[0]:.         
3b60: 20 20 20 6d 75 6c 74 5f 69 20 3d 20 30 0a 20 20     mult_i = 0.  
3b70: 20 20 20 20 20 20 65 6c 69 66 20 76 61 6c 75 65        elif value
3b80: 20 3e 3d 20 6d 75 6c 74 69 70 6c 69 65 72 73 5b   >= multipliers[
3b90: 2d 31 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20  -1]:.           
3ba0: 20 6d 75 6c 74 5f 69 20 3d 20 6c 65 6e 28 6d 75   mult_i = len(mu
3bb0: 6c 74 69 70 6c 69 65 72 73 29 20 2d 20 31 0a 20  ltipliers) - 1. 
3bc0: 20 20 20 6d 75 6c 74 20 3d 20 6d 75 6c 74 69 70     mult = multip
3bd0: 6c 69 65 72 73 5b 6d 75 6c 74 5f 69 5d 0a 20 20  liers[mult_i].  
3be0: 20 20 23 20 43 6f 6e 76 65 72 74 20 76 61 6c 75    # Convert valu
3bf0: 65 20 66 6f 72 20 74 68 69 73 20 6d 75 6c 74 69  e for this multi
3c00: 70 6c 69 65 72 2e 0a 20 20 20 20 6e 65 77 5f 76  plier..    new_v
3c10: 61 6c 75 65 20 3d 20 76 61 6c 75 65 20 2f 20 6d  alue = value / m
3c20: 75 6c 74 0a 20 20 20 20 23 20 44 65 61 6c 20 77  ult.    # Deal w
3c30: 69 74 68 20 73 70 65 63 69 61 6c 20 63 61 73 65  ith special case
3c40: 20 64 75 65 20 74 6f 20 72 6f 75 6e 64 69 6e 67   due to rounding
3c50: 2e 0a 20 20 20 20 69 66 20 73 69 67 66 69 67 73  ..    if sigfigs
3c60: 20 69 73 20 4e 6f 6e 65 3a 0a 20 20 20 20 20 20   is None:.      
3c70: 20 20 69 66 20 6d 75 6c 74 5f 69 20 3c 20 28 6c    if mult_i < (l
3c80: 65 6e 28 6d 75 6c 74 69 70 6c 69 65 72 73 29 20  en(multipliers) 
3c90: 2d 20 31 29 20 61 6e 64 20 5c 0a 20 20 20 20 20  - 1) and \.     
3ca0: 20 20 20 20 20 20 20 20 20 20 72 6f 75 6e 64 28            round(
3cb0: 6e 65 77 5f 76 61 6c 75 65 2c 20 64 70 29 20 3d  new_value, dp) =
3cc0: 3d 20 5c 0a 20 20 20 20 20 20 20 20 20 20 20 20  = \.            
3cd0: 20 20 20 72 6f 75 6e 64 28 28 6d 75 6c 74 69 70     round((multip
3ce0: 6c 69 65 72 73 5b 6d 75 6c 74 5f 69 2b 31 5d 20  liers[mult_i+1] 
3cf0: 2f 20 6d 75 6c 74 29 2c 20 64 70 29 3a 0a 20 20  / mult), dp):.  
3d00: 20 20 20 20 20 20 20 20 20 20 6d 75 6c 74 20 3d            mult =
3d10: 20 6d 75 6c 74 69 70 6c 69 65 72 73 5b 6d 75 6c   multipliers[mul
3d20: 74 5f 69 20 2b 20 31 5d 0a 20 20 20 20 20 20 20  t_i + 1].       
3d30: 20 20 20 20 20 6e 65 77 5f 76 61 6c 75 65 20 3d       new_value =
3d40: 20 76 61 6c 75 65 20 2f 20 6d 75 6c 74 0a 20 20   value / mult.  
3d50: 20 20 23 20 43 6f 6e 63 61 74 65 6e 61 74 65 20    # Concatenate 
3d60: 6d 75 6c 74 69 70 6c 69 65 72 20 73 79 6d 62 6f  multiplier symbo
3d70: 6c 2e 0a 20 20 20 20 69 66 20 75 73 65 5f 66 75  l..    if use_fu
3d80: 6c 6c 5f 6e 61 6d 65 3a 0a 20 20 20 20 20 20 20  ll_name:.       
3d90: 20 6c 61 62 65 6c 5f 74 79 70 65 20 3d 20 31 0a   label_type = 1.
3da0: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
3db0: 20 20 6c 61 62 65 6c 5f 74 79 70 65 20 3d 20 30    label_type = 0
3dc0: 0a 20 20 20 20 23 20 52 6f 75 6e 64 20 61 6e 64  .    # Round and
3dd0: 20 74 72 75 6e 63 61 74 65 20 74 6f 20 61 70 70   truncate to app
3de0: 72 6f 70 72 69 61 74 65 20 70 72 65 63 69 73 69  ropriate precisi
3df0: 6f 6e 2e 0a 20 20 20 20 69 66 20 73 69 67 66 69  on..    if sigfi
3e00: 67 73 20 69 73 20 4e 6f 6e 65 3a 0a 20 20 20 20  gs is None:.    
3e10: 20 20 20 20 73 74 72 5f 76 61 6c 75 65 20 3d 20      str_value = 
3e20: 65 76 61 6c 28 27 22 25 2e 27 2b 73 74 72 28 64  eval('"%.'+str(d
3e30: 70 29 2b 27 66 22 20 25 20 6e 65 77 5f 76 61 6c  p)+'f" % new_val
3e40: 75 65 27 2c 20 6c 6f 63 61 6c 73 28 29 2c 20 7b  ue', locals(), {
3e50: 7d 29 0a 20 20 20 20 65 6c 73 65 3a 0a 20 20 20  }).    else:.   
3e60: 20 20 20 20 20 73 74 72 5f 76 61 6c 75 65 20 3d       str_value =
3e70: 20 65 76 61 6c 28 27 22 25 2e 27 2b 73 74 72 28   eval('"%.'+str(
3e80: 73 69 67 66 69 67 73 29 2b 27 67 22 20 25 20 6e  sigfigs)+'g" % n
3e90: 65 77 5f 76 61 6c 75 65 27 2c 20 6c 6f 63 61 6c  ew_value', local
3ea0: 73 28 29 2c 20 7b 7d 29 0a 20 20 20 20 72 65 74  s(), {}).    ret
3eb0: 75 72 6e 20 73 74 72 5f 76 61 6c 75 65 20 2b 20  urn str_value + 
3ec0: 73 70 61 63 65 20 2b 20 70 72 65 66 69 78 65 73  space + prefixes
3ed0: 5b 6d 75 6c 74 5d 5b 6c 61 62 65 6c 5f 74 79 70  [mult][label_typ
3ee0: 65 5d 20 2b 20 73 75 66 66 69 78 0a 0a 0a 64 65  e] + suffix...de
3ef0: 66 20 75 6e 69 71 75 69 66 79 28 73 65 71 2c 20  f uniquify(seq, 
3f00: 70 72 65 73 65 72 76 65 5f 6f 72 64 65 72 3d 46  preserve_order=F
3f10: 61 6c 73 65 29 3a 0a 20 20 20 20 22 22 22 52 65  alse):.    """Re
3f20: 74 75 72 6e 20 73 65 71 75 65 6e 63 65 20 77 69  turn sequence wi
3f30: 74 68 20 64 75 70 6c 69 63 61 74 65 20 69 74 65  th duplicate ite
3f40: 6d 73 20 69 6e 20 73 65 71 75 65 6e 63 65 20 73  ms in sequence s
3f50: 65 71 20 72 65 6d 6f 76 65 64 2e 0a 0a 20 20 20  eq removed...   
3f60: 20 54 68 65 20 63 6f 64 65 20 69 73 20 62 61 73   The code is bas
3f70: 65 64 20 6f 6e 20 75 73 65 6e 65 74 20 70 6f 73  ed on usenet pos
3f80: 74 20 62 79 20 54 69 6d 20 50 65 74 65 72 73 2e  t by Tim Peters.
3f90: 0a 0a 20 20 20 20 54 68 69 73 20 63 6f 64 65 20  ..    This code 
3fa0: 69 73 20 4f 28 4e 29 20 69 66 20 74 68 65 20 73  is O(N) if the s
3fb0: 65 71 75 65 6e 63 65 20 69 74 65 6d 73 20 61 72  equence items ar
3fc0: 65 20 68 61 73 68 61 62 6c 65 2c 20 4f 28 4e 2a  e hashable, O(N*
3fd0: 2a 32 29 20 69 66 20 6e 6f 74 2e 0a 20 20 20 20  *2) if not..    
3fe0: 0a 20 20 20 20 50 65 74 65 72 20 42 65 6e 67 74  .    Peter Bengt
3ff0: 73 73 6f 6e 20 68 61 73 20 61 20 62 6c 6f 67 20  sson has a blog 
4000: 70 6f 73 74 20 77 69 74 68 20 61 6e 20 65 6d 70  post with an emp
4010: 69 72 69 63 61 6c 20 63 6f 6d 70 61 72 69 73 6f  irical compariso
4020: 6e 20 6f 66 20 6f 74 68 65 72 0a 20 20 20 20 61  n of other.    a
4030: 70 70 72 6f 61 63 68 65 73 3a 0a 20 20 20 20 68  pproaches:.    h
4040: 74 74 70 3a 2f 2f 77 77 77 2e 70 65 74 65 72 62  ttp://www.peterb
4050: 65 2e 63 6f 6d 2f 70 6c 6f 67 2f 75 6e 69 71 69  e.com/plog/uniqi
4060: 66 69 65 72 73 2d 62 65 6e 63 68 6d 61 72 6b 0a  fiers-benchmark.
4070: 0a 20 20 20 20 49 66 20 6f 72 64 65 72 20 69 73  .    If order is
4080: 20 6e 6f 74 20 69 6d 70 6f 72 74 61 6e 74 20 61   not important a
4090: 6e 64 20 74 68 65 20 73 65 71 75 65 6e 63 65 20  nd the sequence 
40a0: 69 74 65 6d 73 20 61 72 65 20 68 61 73 68 61 62  items are hashab
40b0: 6c 65 20 74 68 65 6e 0a 20 20 20 20 6c 69 73 74  le then.    list
40c0: 28 73 65 74 28 73 65 71 29 29 20 69 73 20 72 65  (set(seq)) is re
40d0: 61 64 61 62 6c 65 20 61 6e 64 20 65 66 66 69 63  adable and effic
40e0: 69 65 6e 74 2e 0a 0a 20 20 20 20 49 66 20 6f 72  ient...    If or
40f0: 64 65 72 20 69 73 20 69 6d 70 6f 72 74 61 6e 74  der is important
4100: 20 61 6e 64 20 74 68 65 20 73 65 71 75 65 6e 63   and the sequenc
4110: 65 20 69 74 65 6d 73 20 61 72 65 20 68 61 73 68  e items are hash
4120: 61 62 6c 65 20 67 65 6e 65 72 61 74 6f 72 0a 20  able generator. 
4130: 20 20 20 65 78 70 72 65 73 73 69 6f 6e 73 20 63     expressions c
4140: 61 6e 20 62 65 20 75 73 65 64 20 28 69 6e 20 70  an be used (in p
4150: 79 20 3e 3d 20 32 2e 34 29 20 28 75 73 65 66 75  y >= 2.4) (usefu
4160: 6c 20 66 6f 72 20 6c 61 72 67 65 20 73 65 71 75  l for large sequ
4170: 65 6e 63 65 73 29 3a 0a 20 20 20 20 73 65 65 6e  ences):.    seen
4180: 20 3d 20 73 65 74 28 29 0a 20 20 20 20 64 6f 5f   = set().    do_
4190: 73 6f 6d 65 74 68 69 6e 67 28 78 20 66 6f 72 20  something(x for 
41a0: 78 20 69 6e 20 73 65 71 20 69 66 20 78 20 6e 6f  x in seq if x no
41b0: 74 20 69 6e 20 73 65 65 6e 20 6f 72 20 73 65 65  t in seen or see
41c0: 6e 2e 61 64 64 28 78 29 29 0a 0a 20 20 20 20 41  n.add(x))..    A
41d0: 72 67 75 6d 65 6e 74 73 3a 0a 20 20 20 20 73 65  rguments:.    se
41e0: 71 20 2d 2d 20 73 65 71 75 65 6e 63 65 0a 20 20  q -- sequence.  
41f0: 20 20 70 72 65 73 65 72 76 65 5f 6f 72 64 65 72    preserve_order
4200: 20 2d 2d 20 69 66 20 6e 6f 74 20 73 65 74 20 74   -- if not set t
4210: 68 65 20 6f 72 64 65 72 20 77 69 6c 6c 20 62 65  he order will be
4220: 20 61 72 62 69 74 72 61 72 79 0a 20 20 20 20 20   arbitrary.     
4230: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4240: 20 55 73 69 6e 67 20 74 68 69 73 20 6f 70 74 69   Using this opti
4250: 6f 6e 20 77 69 6c 6c 20 69 6e 63 75 72 20 61 20  on will incur a 
4260: 73 70 65 65 64 20 70 65 6e 61 6c 74 79 2e 0a 20  speed penalty.. 
4270: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4280: 20 20 20 20 20 28 64 65 66 61 75 6c 74 3a 20 46       (default: F
4290: 61 6c 73 65 29 0a 0a 20 20 20 20 45 78 61 6d 70  alse)..    Examp
42a0: 6c 65 20 73 68 6f 77 69 6e 67 20 6f 72 64 65 72  le showing order
42b0: 20 70 72 65 73 65 72 76 61 74 69 6f 6e 3a 0a 0a   preservation:..
42c0: 20 20 20 20 3e 3e 3e 20 75 6e 69 71 75 69 66 79      >>> uniquify
42d0: 28 5b 27 61 27 2c 20 27 61 61 27 2c 20 27 62 27  (['a', 'aa', 'b'
42e0: 2c 20 27 62 27 2c 20 27 63 63 63 27 2c 20 27 63  , 'b', 'ccc', 'c
42f0: 63 63 27 2c 20 27 64 27 5d 2c 20 70 72 65 73 65  cc', 'd'], prese
4300: 72 76 65 5f 6f 72 64 65 72 3d 54 72 75 65 29 0a  rve_order=True).
4310: 20 20 20 20 5b 27 61 27 2c 20 27 61 61 27 2c 20      ['a', 'aa', 
4320: 27 62 27 2c 20 27 63 63 63 27 2c 20 27 64 27 5d  'b', 'ccc', 'd']
4330: 0a 0a 20 20 20 20 45 78 61 6d 70 6c 65 20 75 73  ..    Example us
4340: 69 6e 67 20 61 20 73 65 71 75 65 6e 63 65 20 6f  ing a sequence o
4350: 66 20 75 6e 2d 68 61 73 68 61 62 6c 65 20 69 74  f un-hashable it
4360: 65 6d 73 3a 0a 0a 20 20 20 20 3e 3e 3e 20 75 6e  ems:..    >>> un
4370: 69 71 75 69 66 79 28 5b 5b 27 7a 27 5d 2c 20 5b  iquify([['z'], [
4380: 27 78 27 5d 2c 20 5b 27 79 27 5d 2c 20 5b 27 7a  'x'], ['y'], ['z
4390: 27 5d 5d 2c 20 70 72 65 73 65 72 76 65 5f 6f 72  ']], preserve_or
43a0: 64 65 72 3d 54 72 75 65 29 0a 20 20 20 20 5b 5b  der=True).    [[
43b0: 27 7a 27 5d 2c 20 5b 27 78 27 5d 2c 20 5b 27 79  'z'], ['x'], ['y
43c0: 27 5d 5d 0a 0a 20 20 20 20 54 68 65 20 73 6f 72  ']]..    The sor
43d0: 74 65 64 20 6f 75 74 70 75 74 20 6f 72 20 74 68  ted output or th
43e0: 65 20 6e 6f 6e 2d 6f 72 64 65 72 2d 70 72 65 73  e non-order-pres
43f0: 65 72 76 69 6e 67 20 61 70 70 72 6f 61 63 68 20  erving approach 
4400: 73 68 6f 75 6c 64 20 65 71 75 61 6c 0a 20 20 20  should equal.   
4410: 20 74 68 61 74 20 6f 66 20 74 68 65 20 73 6f 72   that of the sor
4420: 74 65 64 20 6f 72 64 65 72 2d 70 72 65 73 65 72  ted order-preser
4430: 76 69 6e 67 20 61 70 70 72 6f 61 63 68 20 6f 75  ving approach ou
4440: 74 70 75 74 3a 0a 20 20 20 20 0a 20 20 20 20 3e  tput:.    .    >
4450: 3e 3e 20 75 6e 6f 72 64 65 72 65 64 20 3d 20 75  >> unordered = u
4460: 6e 69 71 75 69 66 79 28 5b 33 2c 20 33 2c 20 31  niquify([3, 3, 1
4470: 2c 20 32 5d 2c 20 70 72 65 73 65 72 76 65 5f 6f  , 2], preserve_o
4480: 72 64 65 72 3d 46 61 6c 73 65 29 0a 20 20 20 20  rder=False).    
4490: 3e 3e 3e 20 75 6e 6f 72 64 65 72 65 64 2e 73 6f  >>> unordered.so
44a0: 72 74 28 29 0a 20 20 20 20 3e 3e 3e 20 6f 72 64  rt().    >>> ord
44b0: 65 72 65 64 20 3d 20 75 6e 69 71 75 69 66 79 28  ered = uniquify(
44c0: 5b 33 2c 20 33 2c 20 31 2c 20 32 5d 2c 20 70 72  [3, 3, 1, 2], pr
44d0: 65 73 65 72 76 65 5f 6f 72 64 65 72 3d 54 72 75  eserve_order=Tru
44e0: 65 29 0a 20 20 20 20 3e 3e 3e 20 6f 72 64 65 72  e).    >>> order
44f0: 65 64 2e 73 6f 72 74 28 29 0a 20 20 20 20 3e 3e  ed.sort().    >>
4500: 3e 20 6f 72 64 65 72 65 64 0a 20 20 20 20 5b 31  > ordered.    [1
4510: 2c 20 32 2c 20 33 5d 0a 20 20 20 20 3e 3e 3e 20  , 2, 3].    >>> 
4520: 69 6e 74 28 6f 72 64 65 72 65 64 20 3d 3d 20 75  int(ordered == u
4530: 6e 6f 72 64 65 72 65 64 29 0a 20 20 20 20 31 0a  nordered).    1.
4540: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 74 72 79  .    """.    try
4550: 3a 0a 20 20 20 20 20 20 20 20 23 20 41 74 74 65  :.        # Atte
4560: 6d 70 74 20 66 61 73 74 20 61 6c 67 6f 72 69 74  mpt fast algorit
4570: 68 6d 2e 0a 20 20 20 20 20 20 20 20 64 20 3d 20  hm..        d = 
4580: 7b 7d 0a 20 20 20 20 20 20 20 20 69 66 20 70 72  {}.        if pr
4590: 65 73 65 72 76 65 5f 6f 72 64 65 72 3a 0a 20 20  eserve_order:.  
45a0: 20 20 20 20 20 20 20 20 20 20 23 20 54 68 69 73            # This
45b0: 20 69 73 20 62 61 73 65 64 20 6f 6e 20 44 61 76   is based on Dav
45c0: 65 20 4b 69 72 62 79 27 73 20 6d 65 74 68 6f 64  e Kirby's method
45d0: 20 28 66 38 29 20 6e 6f 74 65 64 20 69 6e 20 74   (f8) noted in t
45e0: 68 65 20 70 6f 73 74 3a 0a 20 20 20 20 20 20 20  he post:.       
45f0: 20 20 20 20 20 23 20 68 74 74 70 3a 2f 2f 77 77       # http://ww
4600: 77 2e 70 65 74 65 72 62 65 2e 63 6f 6d 2f 70 6c  w.peterbe.com/pl
4610: 6f 67 2f 75 6e 69 71 69 66 69 65 72 73 2d 62 65  og/uniqifiers-be
4620: 6e 63 68 6d 61 72 6b 0a 20 20 20 20 20 20 20 20  nchmark.        
4630: 20 20 20 20 72 65 74 75 72 6e 20 5b 78 20 66 6f      return [x fo
4640: 72 20 78 20 69 6e 20 73 65 71 20 69 66 20 28 78  r x in seq if (x
4650: 20 6e 6f 74 20 69 6e 20 64 29 20 61 6e 64 20 6e   not in d) and n
4660: 6f 74 20 64 2e 5f 5f 73 65 74 69 74 65 6d 5f 5f  ot d.__setitem__
4670: 28 78 2c 20 30 29 5d 0a 20 20 20 20 20 20 20 20  (x, 0)].        
4680: 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20  else:.          
4690: 20 20 66 6f 72 20 78 20 69 6e 20 73 65 71 3a 0a    for x in seq:.
46a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
46b0: 64 5b 78 5d 20 3d 20 30 0a 20 20 20 20 20 20 20  d[x] = 0.       
46c0: 20 20 20 20 20 72 65 74 75 72 6e 20 64 2e 6b 65       return d.ke
46d0: 79 73 28 29 0a 20 20 20 20 65 78 63 65 70 74 20  ys().    except 
46e0: 54 79 70 65 45 72 72 6f 72 3a 0a 20 20 20 20 20  TypeError:.     
46f0: 20 20 20 23 20 48 61 76 65 20 61 6e 20 75 6e 68     # Have an unh
4700: 61 73 68 61 62 6c 65 20 6f 62 6a 65 63 74 2c 20  ashable object, 
4710: 73 6f 20 75 73 65 20 73 6c 6f 77 20 61 6c 67 6f  so use slow algo
4720: 72 69 74 68 6d 2e 0a 20 20 20 20 20 20 20 20 72  rithm..        r
4730: 65 73 75 6c 74 20 3d 20 5b 5d 0a 20 20 20 20 20  esult = [].     
4740: 20 20 20 61 70 70 20 3d 20 72 65 73 75 6c 74 2e     app = result.
4750: 61 70 70 65 6e 64 0a 20 20 20 20 20 20 20 20 66  append.        f
4760: 6f 72 20 78 20 69 6e 20 73 65 71 3a 0a 20 20 20  or x in seq:.   
4770: 20 20 20 20 20 20 20 20 20 69 66 20 78 20 6e 6f           if x no
4780: 74 20 69 6e 20 72 65 73 75 6c 74 3a 0a 20 20 20  t in result:.   
4790: 20 20 20 20 20 20 20 20 20 20 20 20 20 61 70 70               app
47a0: 28 78 29 0a 20 20 20 20 20 20 20 20 72 65 74 75  (x).        retu
47b0: 72 6e 20 72 65 73 75 6c 74 0a 0a 23 20 41 6c 69  rn result..# Ali
47c0: 61 73 20 74 6f 20 6e 6f 75 6e 20 66 6f 72 6d 20  as to noun form 
47d0: 66 6f 72 20 62 61 63 6b 77 61 72 64 20 63 6f 6d  for backward com
47e0: 70 61 74 69 62 69 6c 69 74 79 2e 0a 75 6e 69 71  patibility..uniq
47f0: 75 65 20 3d 20 75 6e 69 71 75 69 66 79 0a 0a 0a  ue = uniquify...
4800: 64 65 66 20 72 65 76 65 72 73 65 5f 64 69 63 74  def reverse_dict
4810: 28 64 29 3a 0a 20 20 20 20 22 22 22 52 65 76 65  (d):.    """Reve
4820: 72 73 65 20 61 20 64 69 63 74 69 6f 6e 61 72 79  rse a dictionary
4830: 20 73 6f 20 74 68 65 20 69 74 65 6d 73 20 62 65   so the items be
4840: 63 6f 6d 65 20 74 68 65 20 6b 65 79 73 20 61 6e  come the keys an
4850: 64 20 76 69 63 65 2d 76 65 72 73 61 2e 0a 0a 20  d vice-versa... 
4860: 20 20 20 4e 6f 74 65 3a 20 54 68 65 20 72 65 73     Note: The res
4870: 75 6c 74 73 20 77 69 6c 6c 20 62 65 20 61 72 62  ults will be arb
4880: 69 74 72 61 72 79 20 69 66 20 74 68 65 20 69 74  itrary if the it
4890: 65 6d 73 20 61 72 65 20 6e 6f 74 20 75 6e 69 71  ems are not uniq
48a0: 75 65 2e 0a 0a 20 20 20 20 3e 3e 3e 20 64 20 3d  ue...    >>> d =
48b0: 20 72 65 76 65 72 73 65 5f 64 69 63 74 28 7b 27   reverse_dict({'
48c0: 61 27 3a 20 31 2c 20 27 62 27 3a 20 32 7d 29 0a  a': 1, 'b': 2}).
48d0: 20 20 20 20 3e 3e 3e 20 64 5f 69 74 65 6d 73 20      >>> d_items 
48e0: 3d 20 64 2e 69 74 65 6d 73 28 29 0a 20 20 20 20  = d.items().    
48f0: 3e 3e 3e 20 64 5f 69 74 65 6d 73 2e 73 6f 72 74  >>> d_items.sort
4900: 28 29 0a 20 20 20 20 3e 3e 3e 20 64 5f 69 74 65  ().    >>> d_ite
4910: 6d 73 0a 20 20 20 20 5b 28 31 2c 20 27 61 27 29  ms.    [(1, 'a')
4920: 2c 20 28 32 2c 20 27 62 27 29 5d 0a 0a 20 20 20  , (2, 'b')]..   
4930: 20 22 22 22 0a 20 20 20 20 72 65 73 75 6c 74 20   """.    result 
4940: 3d 20 7b 7d 0a 20 20 20 20 66 6f 72 20 6b 65 79  = {}.    for key
4950: 2c 20 76 61 6c 75 65 20 69 6e 20 64 2e 69 74 65  , value in d.ite
4960: 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 72 65  ms():.        re
4970: 73 75 6c 74 5b 76 61 6c 75 65 5d 20 3d 20 6b 65  sult[value] = ke
4980: 79 0a 20 20 20 20 72 65 74 75 72 6e 20 72 65 73  y.    return res
4990: 75 6c 74 0a 0a 20 20 20 20 0a 64 65 66 20 6c 73  ult..    .def ls
49a0: 62 28 78 2c 20 6e 29 3a 0a 20 20 20 20 22 22 22  b(x, n):.    """
49b0: 52 65 74 75 72 6e 20 74 68 65 20 6e 20 6c 65 61  Return the n lea
49c0: 73 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62  st significant b
49d0: 69 74 73 20 6f 66 20 78 2e 0a 0a 20 20 20 20 3e  its of x...    >
49e0: 3e 3e 20 6c 73 62 28 31 33 2c 20 33 29 0a 20 20  >> lsb(13, 3).  
49f0: 20 20 35 0a 0a 20 20 20 20 22 22 22 0a 20 20 20    5..    """.   
4a00: 20 72 65 74 75 72 6e 20 78 20 26 20 28 28 32 20   return x & ((2 
4a10: 2a 2a 20 6e 29 20 2d 20 31 29 0a 0a 0a 64 65 66  ** n) - 1)...def
4a20: 20 67 72 61 79 5f 65 6e 63 6f 64 65 28 69 29 3a   gray_encode(i):
4a30: 0a 20 20 20 20 22 22 22 47 72 61 79 20 65 6e 63  .    """Gray enc
4a40: 6f 64 65 20 74 68 65 20 67 69 76 65 6e 20 69 6e  ode the given in
4a50: 74 65 67 65 72 2e 22 22 22 0a 0a 20 20 20 20 72  teger."""..    r
4a60: 65 74 75 72 6e 20 69 20 5e 20 28 69 20 3e 3e 20  eturn i ^ (i >> 
4a70: 31 29 0a 0a 0a 64 65 66 20 72 61 6e 64 6f 6d 5f  1)...def random_
4a80: 76 65 63 28 62 69 74 73 2c 20 6d 61 78 5f 76 61  vec(bits, max_va
4a90: 6c 75 65 3d 4e 6f 6e 65 29 3a 0a 20 20 20 20 22  lue=None):.    "
4aa0: 22 22 47 65 6e 65 72 61 74 65 20 61 20 72 61 6e  ""Generate a ran
4ab0: 64 6f 6d 20 62 69 6e 61 72 79 20 76 65 63 74 6f  dom binary vecto
4ac0: 72 20 6f 66 20 6c 65 6e 67 74 68 20 62 69 74 73  r of length bits
4ad0: 20 61 6e 64 20 67 69 76 65 6e 20 6d 61 78 20 76   and given max v
4ae0: 61 6c 75 65 2e 22 22 22 0a 0a 20 20 20 20 76 65  alue."""..    ve
4af0: 63 74 6f 72 20 3d 20 22 22 0a 20 20 20 20 66 6f  ctor = "".    fo
4b00: 72 20 5f 20 69 6e 20 72 61 6e 67 65 28 69 6e 74  r _ in range(int
4b10: 28 62 69 74 73 20 2f 20 31 30 29 20 2b 20 31 29  (bits / 10) + 1)
4b20: 3a 0a 20 20 20 20 20 20 20 20 69 20 3d 20 69 6e  :.        i = in
4b30: 74 28 28 32 2a 2a 31 30 29 20 2a 20 72 61 6e 64  t((2**10) * rand
4b40: 6f 6d 2e 72 61 6e 64 6f 6d 28 29 29 0a 20 20 20  om.random()).   
4b50: 20 20 20 20 20 76 65 63 74 6f 72 20 2b 3d 20 69       vector += i
4b60: 6e 74 32 62 69 6e 28 69 2c 20 31 30 29 0a 0a 20  nt2bin(i, 10).. 
4b70: 20 20 20 69 66 20 6d 61 78 5f 76 61 6c 75 65 20     if max_value 
4b80: 61 6e 64 20 28 6d 61 78 5f 76 61 6c 75 65 20 3c  and (max_value <
4b90: 20 32 20 2a 2a 20 62 69 74 73 20 2d 20 31 29 3a   2 ** bits - 1):
4ba0: 0a 20 20 20 20 20 20 20 20 76 65 63 74 6f 72 20  .        vector 
4bb0: 3d 20 69 6e 74 32 62 69 6e 28 28 69 6e 74 28 76  = int2bin((int(v
4bc0: 65 63 74 6f 72 2c 20 32 29 20 2f 20 28 32 20 2a  ector, 2) / (2 *
4bd0: 2a 20 62 69 74 73 20 2d 20 31 29 29 20 2a 20 6d  * bits - 1)) * m
4be0: 61 78 5f 76 61 6c 75 65 2c 20 62 69 74 73 29 0a  ax_value, bits).
4bf0: 20 20 20 20 0a 20 20 20 20 72 65 74 75 72 6e 20      .    return 
4c00: 76 65 63 74 6f 72 5b 30 3a 62 69 74 73 5d 0a 0a  vector[0:bits]..
4c10: 0a 64 65 66 20 62 69 6e 61 72 79 5f 72 61 6e 67  .def binary_rang
4c20: 65 28 62 69 74 73 29 3a 0a 20 20 20 20 22 22 22  e(bits):.    """
4c30: 52 65 74 75 72 6e 20 61 20 6c 69 73 74 20 6f 66  Return a list of
4c40: 20 61 6c 6c 20 70 6f 73 73 69 62 6c 65 20 62 69   all possible bi
4c50: 6e 61 72 79 20 6e 75 6d 62 65 72 73 20 69 6e 20  nary numbers in 
4c60: 6f 72 64 65 72 20 77 69 74 68 20 77 69 64 74 68  order with width
4c70: 3d 62 69 74 73 2e 20 0a 20 20 20 20 0a 20 20 20  =bits. .    .   
4c80: 20 49 74 20 77 6f 75 6c 64 20 62 65 20 6e 69 63   It would be nic
4c90: 65 20 74 6f 20 65 78 74 65 6e 64 20 69 74 20 74  e to extend it t
4ca0: 6f 20 6d 61 74 63 68 20 74 68 65 0a 20 20 20 20  o match the.    
4cb0: 66 75 6e 63 74 69 6f 6e 61 6c 69 74 79 20 6f 66  functionality of
4cc0: 20 70 79 74 68 6f 6e 27 73 20 72 61 6e 67 65 28   python's range(
4cd0: 29 20 62 75 69 6c 74 2d 69 6e 20 66 75 6e 63 74  ) built-in funct
4ce0: 69 6f 6e 2e 0a 20 20 20 20 0a 20 20 20 20 22 22  ion..    .    ""
4cf0: 22 0a 20 20 20 20 6c 20 3d 20 5b 5d 0a 20 20 20  ".    l = [].   
4d00: 20 76 20 3d 20 5b 27 30 27 5d 20 2a 20 62 69 74   v = ['0'] * bit
4d10: 73 0a 0a 20 20 20 20 74 6f 67 67 6c 65 20 3d 20  s..    toggle = 
4d20: 5b 31 5d 20 2b 20 5b 30 5d 20 2a 20 62 69 74 73  [1] + [0] * bits
4d30: 0a 20 20 20 20 0a 20 20 20 20 77 68 69 6c 65 20  .    .    while 
4d40: 74 6f 67 67 6c 65 5b 62 69 74 73 5d 20 21 3d 20  toggle[bits] != 
4d50: 31 3a 0a 20 20 20 20 20 20 20 20 76 5f 63 6f 70  1:.        v_cop
4d60: 79 20 3d 20 76 5b 3a 5d 0a 20 20 20 20 20 20 20  y = v[:].       
4d70: 20 76 5f 63 6f 70 79 2e 72 65 76 65 72 73 65 28   v_copy.reverse(
4d80: 29 0a 20 20 20 20 20 20 20 20 6c 2e 61 70 70 65  ).        l.appe
4d90: 6e 64 28 27 27 2e 6a 6f 69 6e 28 76 5f 63 6f 70  nd(''.join(v_cop
4da0: 79 29 29 0a 20 20 20 20 20 20 20 20 0a 20 20 20  y)).        .   
4db0: 20 20 20 20 20 74 6f 67 67 6c 65 20 3d 20 5b 31       toggle = [1
4dc0: 5d 20 2b 20 5b 30 5d 2a 62 69 74 73 0a 20 20 20  ] + [0]*bits.   
4dd0: 20 20 20 20 20 69 20 3d 20 30 0a 20 20 20 20 20       i = 0.     
4de0: 20 20 20 77 68 69 6c 65 20 69 20 3c 20 62 69 74     while i < bit
4df0: 73 20 61 6e 64 20 74 6f 67 67 6c 65 5b 69 5d 20  s and toggle[i] 
4e00: 3d 3d 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20  == 1:.          
4e10: 20 20 69 66 20 74 6f 67 67 6c 65 5b 69 5d 3a 0a    if toggle[i]:.
4e20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4e30: 69 66 20 76 5b 69 5d 20 3d 3d 20 27 30 27 3a 0a  if v[i] == '0':.
4e40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4e50: 20 20 20 20 76 5b 69 5d 20 3d 20 27 31 27 0a 20      v[i] = '1'. 
4e60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4e70: 20 20 20 74 6f 67 67 6c 65 5b 69 2b 31 5d 20 3d     toggle[i+1] =
4e80: 20 30 0a 20 20 20 20 20 20 20 20 20 20 20 20 20   0.             
4e90: 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20     else:.       
4ea0: 20 20 20 20 20 20 20 20 20 20 20 20 20 76 5b 69               v[i
4eb0: 5d 20 3d 20 27 30 27 0a 20 20 20 20 20 20 20 20  ] = '0'.        
4ec0: 20 20 20 20 20 20 20 20 20 20 20 20 74 6f 67 67              togg
4ed0: 6c 65 5b 69 2b 31 5d 20 3d 20 31 0a 20 20 20 20  le[i+1] = 1.    
4ee0: 20 20 20 20 20 20 20 20 69 20 2b 3d 20 31 0a 20          i += 1. 
4ef0: 20 20 20 72 65 74 75 72 6e 20 6c 0a 0a 0a 64 65     return l...de
4f00: 66 20 66 6c 6f 61 74 5f 72 61 6e 67 65 28 73 74  f float_range(st
4f10: 61 72 74 2c 20 73 74 6f 70 3d 4e 6f 6e 65 2c 20  art, stop=None, 
4f20: 73 74 65 70 3d 4e 6f 6e 65 29 3a 0a 20 20 20 20  step=None):.    
4f30: 22 22 22 52 65 74 75 72 6e 20 61 20 6c 69 73 74  """Return a list
4f40: 20 63 6f 6e 74 61 69 6e 69 6e 67 20 61 6e 20 61   containing an a
4f50: 72 69 74 68 6d 65 74 69 63 20 70 72 6f 67 72 65  rithmetic progre
4f60: 73 73 69 6f 6e 20 6f 66 20 66 6c 6f 61 74 73 2e  ssion of floats.
4f70: 0a 0a 20 20 20 20 52 65 74 75 72 6e 20 61 20 6c  ..    Return a l
4f80: 69 73 74 20 6f 66 20 66 6c 6f 61 74 73 20 62 65  ist of floats be
4f90: 74 77 65 65 6e 20 30 2e 30 20 28 6f 72 20 73 74  tween 0.0 (or st
4fa0: 61 72 74 29 20 61 6e 64 20 73 74 6f 70 20 77 69  art) and stop wi
4fb0: 74 68 20 61 6e 0a 20 20 20 20 69 6e 63 72 65 6d  th an.    increm
4fc0: 65 6e 74 20 6f 66 20 73 74 65 70 2e 20 0a 0a 20  ent of step. .. 
4fd0: 20 20 20 54 68 69 73 20 69 73 20 69 6e 20 66 75     This is in fu
4fe0: 6e 63 74 69 6f 6e 61 6c 69 74 79 20 74 6f 20 70  nctionality to p
4ff0: 79 74 68 6f 6e 27 73 20 72 61 6e 67 65 28 29 20  ython's range() 
5000: 62 75 69 6c 74 2d 69 6e 20 66 75 6e 63 74 69 6f  built-in functio
5010: 6e 20 0a 20 20 20 20 62 75 74 20 63 61 6e 20 61  n .    but can a
5020: 63 63 65 70 74 20 66 6c 6f 61 74 20 69 6e 63 72  ccept float incr
5030: 65 6d 65 6e 74 73 2e 0a 0a 20 20 20 20 41 73 20  ements...    As 
5040: 77 69 74 68 20 72 61 6e 67 65 28 29 2c 20 73 74  with range(), st
5050: 6f 70 20 69 73 20 6f 6d 69 74 74 65 64 20 66 72  op is omitted fr
5060: 6f 6d 20 74 68 65 20 6c 69 73 74 2e 0a 0a 20 20  om the list...  
5070: 20 20 22 22 22 0a 20 20 20 20 69 66 20 73 74 6f    """.    if sto
5080: 70 20 69 73 20 4e 6f 6e 65 3a 0a 20 20 20 20 20  p is None:.     
5090: 20 20 20 73 74 6f 70 20 3d 20 66 6c 6f 61 74 28     stop = float(
50a0: 73 74 61 72 74 29 0a 20 20 20 20 20 20 20 20 73  start).        s
50b0: 74 61 72 74 20 3d 20 30 2e 30 0a 0a 20 20 20 20  tart = 0.0..    
50c0: 69 66 20 73 74 65 70 20 69 73 20 4e 6f 6e 65 3a  if step is None:
50d0: 0a 20 20 20 20 20 20 20 20 73 74 65 70 20 3d 20  .        step = 
50e0: 31 2e 30 0a 0a 20 20 20 20 63 75 72 20 3d 20 66  1.0..    cur = f
50f0: 6c 6f 61 74 28 73 74 61 72 74 29 0a 20 20 20 20  loat(start).    
5100: 6c 20 3d 20 5b 5d 0a 20 20 20 20 77 68 69 6c 65  l = [].    while
5110: 20 63 75 72 20 3c 20 73 74 6f 70 3a 0a 20 20 20   cur < stop:.   
5120: 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 63 75       l.append(cu
5130: 72 29 0a 20 20 20 20 20 20 20 20 63 75 72 20 2b  r).        cur +
5140: 3d 20 73 74 65 70 0a 0a 20 20 20 20 72 65 74 75  = step..    retu
5150: 72 6e 20 6c 0a 0a 0a 64 65 66 20 66 69 6e 64 5f  rn l...def find_
5160: 63 6f 6d 6d 6f 6e 5f 66 69 78 65 73 28 73 31 2c  common_fixes(s1,
5170: 20 73 32 29 3a 0a 20 20 20 20 22 22 22 46 69 6e   s2):.    """Fin
5180: 64 20 63 6f 6d 6d 6f 6e 20 28 70 72 65 66 69 78  d common (prefix
5190: 2c 20 73 75 66 66 69 78 29 20 6f 66 20 74 77 6f  , suffix) of two
51a0: 20 73 74 72 69 6e 67 73 2e 0a 0a 20 20 20 20 3e   strings...    >
51b0: 3e 3e 20 66 69 6e 64 5f 63 6f 6d 6d 6f 6e 5f 66  >> find_common_f
51c0: 69 78 65 73 28 27 61 62 63 27 2c 20 27 64 65 66  ixes('abc', 'def
51d0: 27 29 0a 20 20 20 20 28 27 27 2c 20 27 27 29 0a  ').    ('', '').
51e0: 0a 20 20 20 20 3e 3e 3e 20 66 69 6e 64 5f 63 6f  .    >>> find_co
51f0: 6d 6d 6f 6e 5f 66 69 78 65 73 28 27 61 62 63 65  mmon_fixes('abce
5200: 6c 65 70 68 61 6e 74 64 65 66 27 2c 20 27 61 62  lephantdef', 'ab
5210: 63 63 6f 77 64 65 66 27 29 0a 20 20 20 20 28 27  ccowdef').    ('
5220: 61 62 63 27 2c 20 27 64 65 66 27 29 0a 0a 20 20  abc', 'def')..  
5230: 20 20 3e 3e 3e 20 66 69 6e 64 5f 63 6f 6d 6d 6f    >>> find_commo
5240: 6e 5f 66 69 78 65 73 28 27 61 62 63 65 6c 65 70  n_fixes('abcelep
5250: 68 61 6e 74 64 65 66 27 2c 20 27 61 62 63 63 6f  hantdef', 'abcco
5260: 77 27 29 0a 20 20 20 20 28 27 61 62 63 27 2c 20  w').    ('abc', 
5270: 27 27 29 0a 0a 20 20 20 20 3e 3e 3e 20 66 69 6e  '')..    >>> fin
5280: 64 5f 63 6f 6d 6d 6f 6e 5f 66 69 78 65 73 28 27  d_common_fixes('
5290: 65 6c 65 70 68 61 6e 74 64 65 66 27 2c 20 27 61  elephantdef', 'a
52a0: 62 63 63 6f 77 64 65 66 27 29 0a 20 20 20 20 28  bccowdef').    (
52b0: 27 27 2c 20 27 64 65 66 27 29 0a 0a 20 20 20 20  '', 'def')..    
52c0: 22 22 22 0a 20 20 20 20 70 72 65 66 69 78 20 3d  """.    prefix =
52d0: 20 5b 5d 0a 20 20 20 20 73 75 66 66 69 78 20 3d   [].    suffix =
52e0: 20 5b 5d 0a 0a 20 20 20 20 69 20 3d 20 30 0a 20   []..    i = 0. 
52f0: 20 20 20 63 6f 6d 6d 6f 6e 5f 6c 65 6e 20 3d 20     common_len = 
5300: 6d 69 6e 28 6c 65 6e 28 73 31 29 2c 20 6c 65 6e  min(len(s1), len
5310: 28 73 32 29 29 0a 20 20 20 20 77 68 69 6c 65 20  (s2)).    while 
5320: 69 20 3c 20 63 6f 6d 6d 6f 6e 5f 6c 65 6e 3a 0a  i < common_len:.
5330: 20 20 20 20 20 20 20 20 69 66 20 73 31 5b 69 5d          if s1[i]
5340: 20 21 3d 20 73 32 5b 69 5d 3a 0a 20 20 20 20 20   != s2[i]:.     
5350: 20 20 20 20 20 20 20 62 72 65 61 6b 0a 0a 20 20         break..  
5360: 20 20 20 20 20 20 70 72 65 66 69 78 2e 61 70 70        prefix.app
5370: 65 6e 64 28 73 31 5b 69 5d 29 0a 20 20 20 20 20  end(s1[i]).     
5380: 20 20 20 69 20 2b 3d 20 31 0a 0a 20 20 20 20 69     i += 1..    i
5390: 20 3d 20 31 0a 20 20 20 20 77 68 69 6c 65 20 69   = 1.    while i
53a0: 20 3c 20 28 63 6f 6d 6d 6f 6e 5f 6c 65 6e 20 2b   < (common_len +
53b0: 20 31 29 3a 0a 20 20 20 20 20 20 20 20 69 66 20   1):.        if 
53c0: 73 31 5b 2d 69 5d 20 21 3d 20 73 32 5b 2d 69 5d  s1[-i] != s2[-i]
53d0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 62 72  :.            br
53e0: 65 61 6b 0a 20 20 20 20 20 20 20 20 0a 20 20 20  eak.        .   
53f0: 20 20 20 20 20 73 75 66 66 69 78 2e 61 70 70 65       suffix.appe
5400: 6e 64 28 73 31 5b 2d 69 5d 29 0a 20 20 20 20 20  nd(s1[-i]).     
5410: 20 20 20 69 20 2b 3d 20 31 0a 0a 20 20 20 20 73     i += 1..    s
5420: 75 66 66 69 78 2e 72 65 76 65 72 73 65 28 29 0a  uffix.reverse().
5430: 0a 20 20 20 20 70 72 65 66 69 78 20 3d 20 27 27  .    prefix = ''
5440: 2e 6a 6f 69 6e 28 70 72 65 66 69 78 29 0a 20 20  .join(prefix).  
5450: 20 20 73 75 66 66 69 78 20 3d 20 27 27 2e 6a 6f    suffix = ''.jo
5460: 69 6e 28 73 75 66 66 69 78 29 0a 20 20 20 20 20  in(suffix).     
5470: 20 20 20 0a 20 20 20 20 72 65 74 75 72 6e 20 28     .    return (
5480: 70 72 65 66 69 78 2c 20 73 75 66 66 69 78 29 0a  prefix, suffix).
5490: 0a 0a 64 65 66 20 69 73 5f 72 6f 74 61 74 65 64  ..def is_rotated
54a0: 28 73 65 71 31 2c 20 73 65 71 32 29 3a 0a 20 20  (seq1, seq2):.  
54b0: 20 20 22 22 22 52 65 74 75 72 6e 20 74 72 75 65    """Return true
54c0: 20 69 66 20 74 68 65 20 66 69 72 73 74 20 73 65   if the first se
54d0: 71 75 65 6e 63 65 20 69 73 20 61 20 72 6f 74 61  quence is a rota
54e0: 74 69 6f 6e 20 6f 66 20 74 68 65 20 73 65 63 6f  tion of the seco
54f0: 6e 64 20 73 65 71 75 65 6e 63 65 2e 0a 0a 20 20  nd sequence...  
5500: 20 20 3e 3e 3e 20 73 65 71 31 20 3d 20 5b 27 41    >>> seq1 = ['A
5510: 27 2c 20 27 42 27 2c 20 27 43 27 2c 20 27 44 27  ', 'B', 'C', 'D'
5520: 5d 0a 20 20 20 20 3e 3e 3e 20 73 65 71 32 20 3d  ].    >>> seq2 =
5530: 20 5b 27 43 27 2c 20 27 44 27 2c 20 27 41 27 2c   ['C', 'D', 'A',
5540: 20 27 42 27 5d 0a 20 20 20 20 3e 3e 3e 20 69 6e   'B'].    >>> in
5550: 74 28 69 73 5f 72 6f 74 61 74 65 64 28 73 65 71  t(is_rotated(seq
5560: 31 2c 20 73 65 71 32 29 29 0a 20 20 20 20 31 0a  1, seq2)).    1.
5570: 0a 20 20 20 20 3e 3e 3e 20 73 65 71 32 20 3d 20  .    >>> seq2 = 
5580: 5b 27 43 27 2c 20 27 44 27 2c 20 27 42 27 2c 20  ['C', 'D', 'B', 
5590: 27 41 27 5d 0a 20 20 20 20 3e 3e 3e 20 69 6e 74  'A'].    >>> int
55a0: 28 69 73 5f 72 6f 74 61 74 65 64 28 73 65 71 31  (is_rotated(seq1
55b0: 2c 20 73 65 71 32 29 29 0a 20 20 20 20 30 0a 0a  , seq2)).    0..
55c0: 20 20 20 20 3e 3e 3e 20 73 65 71 31 20 3d 20 5b      >>> seq1 = [
55d0: 27 41 27 2c 20 27 42 27 2c 20 27 43 27 2c 20 27  'A', 'B', 'C', '
55e0: 41 27 5d 0a 20 20 20 20 3e 3e 3e 20 73 65 71 32  A'].    >>> seq2
55f0: 20 3d 20 5b 27 41 27 2c 20 27 41 27 2c 20 27 42   = ['A', 'A', 'B
5600: 27 2c 20 27 43 27 5d 0a 20 20 20 20 3e 3e 3e 20  ', 'C'].    >>> 
5610: 69 6e 74 28 69 73 5f 72 6f 74 61 74 65 64 28 73  int(is_rotated(s
5620: 65 71 31 2c 20 73 65 71 32 29 29 0a 20 20 20 20  eq1, seq2)).    
5630: 31 0a 0a 20 20 20 20 3e 3e 3e 20 73 65 71 32 20  1..    >>> seq2 
5640: 3d 20 5b 27 41 27 2c 20 27 42 27 2c 20 27 43 27  = ['A', 'B', 'C'
5650: 2c 20 27 41 27 5d 0a 20 20 20 20 3e 3e 3e 20 69  , 'A'].    >>> i
5660: 6e 74 28 69 73 5f 72 6f 74 61 74 65 64 28 73 65  nt(is_rotated(se
5670: 71 31 2c 20 73 65 71 32 29 29 0a 20 20 20 20 31  q1, seq2)).    1
5680: 0a 0a 20 20 20 20 3e 3e 3e 20 73 65 71 32 20 3d  ..    >>> seq2 =
5690: 20 5b 27 41 27 2c 20 27 41 27 2c 20 27 43 27 2c   ['A', 'A', 'C',
56a0: 20 27 42 27 5d 0a 20 20 20 20 3e 3e 3e 20 69 6e   'B'].    >>> in
56b0: 74 28 69 73 5f 72 6f 74 61 74 65 64 28 73 65 71  t(is_rotated(seq
56c0: 31 2c 20 73 65 71 32 29 29 0a 20 20 20 20 30 0a  1, seq2)).    0.
56d0: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 23 20 44  .    """.    # D
56e0: 6f 20 61 20 73 61 6e 69 74 79 20 63 68 65 63 6b  o a sanity check
56f0: 2e 0a 20 20 20 20 69 66 20 6c 65 6e 28 73 65 71  ..    if len(seq
5700: 31 29 20 21 3d 20 6c 65 6e 28 73 65 71 32 29 3a  1) != len(seq2):
5710: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
5720: 46 61 6c 73 65 0a 20 20 20 20 23 20 4c 6f 6f 6b  False.    # Look
5730: 20 66 6f 72 20 6f 63 63 75 72 72 65 6e 63 65 73   for occurrences
5740: 20 6f 66 20 73 65 63 6f 6e 64 20 73 65 71 75 65   of second seque
5750: 6e 63 65 20 68 65 61 64 20 69 74 65 6d 20 69 6e  nce head item in
5760: 20 66 69 72 73 74 20 73 65 71 75 65 6e 63 65 2e   first sequence.
5770: 0a 20 20 20 20 73 74 61 72 74 5f 69 6e 64 65 78  .    start_index
5780: 65 73 20 3d 20 5b 5d 0a 20 20 20 20 68 65 61 64  es = [].    head
5790: 5f 69 74 65 6d 20 3d 20 73 65 71 32 5b 30 5d 0a  _item = seq2[0].
57a0: 20 20 20 20 66 6f 72 20 69 6e 64 65 78 31 20 69      for index1 i
57b0: 6e 20 72 61 6e 67 65 28 6c 65 6e 28 73 65 71 31  n range(len(seq1
57c0: 29 29 3a 0a 20 20 20 20 20 20 20 20 69 66 20 73  )):.        if s
57d0: 65 71 31 5b 69 6e 64 65 78 31 5d 20 3d 3d 20 68  eq1[index1] == h
57e0: 65 61 64 5f 69 74 65 6d 3a 0a 20 20 20 20 20 20  ead_item:.      
57f0: 20 20 20 20 20 20 73 74 61 72 74 5f 69 6e 64 65        start_inde
5800: 78 65 73 2e 61 70 70 65 6e 64 28 69 6e 64 65 78  xes.append(index
5810: 31 29 0a 20 20 20 20 23 20 43 68 65 63 6b 20 74  1).    # Check t
5820: 68 61 74 20 77 72 61 70 70 65 64 20 73 65 71 75  hat wrapped sequ
5830: 65 6e 63 65 20 6d 61 74 63 68 65 73 2e 0a 20 20  ence matches..  
5840: 20 20 64 6f 75 62 6c 65 5f 73 65 71 31 20 3d 20    double_seq1 = 
5850: 73 65 71 31 20 2b 20 73 65 71 31 0a 20 20 20 20  seq1 + seq1.    
5860: 66 6f 72 20 69 6e 64 65 78 31 20 69 6e 20 73 74  for index1 in st
5870: 61 72 74 5f 69 6e 64 65 78 65 73 3a 0a 20 20 20  art_indexes:.   
5880: 20 20 20 20 20 69 66 20 64 6f 75 62 6c 65 5f 73       if double_s
5890: 65 71 31 5b 69 6e 64 65 78 31 3a 69 6e 64 65 78  eq1[index1:index
58a0: 31 2b 6c 65 6e 28 73 65 71 31 29 5d 20 3d 3d 20  1+len(seq1)] == 
58b0: 73 65 71 32 3a 0a 20 20 20 20 20 20 20 20 20 20  seq2:.          
58c0: 20 20 72 65 74 75 72 6e 20 54 72 75 65 0a 20 20    return True.  
58d0: 20 20 72 65 74 75 72 6e 20 46 61 6c 73 65 0a 0a    return False..
58e0: 64 65 66 20 67 65 74 6d 6f 64 75 6c 65 28 6f 62  def getmodule(ob
58f0: 6a 29 3a 0a 20 20 20 20 22 22 22 52 65 74 75 72  j):.    """Retur
5900: 6e 20 74 68 65 20 6d 6f 64 75 6c 65 20 74 68 61  n the module tha
5910: 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 6f  t contains the o
5920: 62 6a 65 63 74 20 64 65 66 69 6e 69 74 69 6f 6e  bject definition
5930: 20 6f 66 20 6f 62 6a 2e 0a 0a 20 20 20 20 4e 6f   of obj...    No
5940: 74 65 3a 20 55 73 65 20 69 6e 73 70 65 63 74 2e  te: Use inspect.
5950: 67 65 74 6d 6f 64 75 6c 65 20 69 6e 73 74 65 61  getmodule instea
5960: 64 2e 0a 0a 20 20 20 20 41 72 67 75 6d 65 6e 74  d...    Argument
5970: 73 3a 0a 20 20 20 20 6f 62 6a 20 2d 2d 20 70 79  s:.    obj -- py
5980: 74 68 6f 6e 20 6f 62 6a 2c 20 67 65 6e 65 72 61  thon obj, genera
5990: 6c 6c 79 20 61 20 63 6c 61 73 73 20 6f 72 20 61  lly a class or a
59a0: 20 66 75 6e 63 74 69 6f 6e 0a 0a 20 20 20 20 45   function..    E
59b0: 78 61 6d 70 6c 65 73 3a 0a 20 20 20 20 0a 20 20  xamples:.    .  
59c0: 20 20 41 20 66 75 6e 63 74 69 6f 6e 3a 0a 20 20    A function:.  
59d0: 20 20 3e 3e 3e 20 6d 6f 64 75 6c 65 20 3d 20 67    >>> module = g
59e0: 65 74 6d 6f 64 75 6c 65 28 72 61 6e 64 6f 6d 2e  etmodule(random.
59f0: 63 68 6f 69 63 65 29 0a 20 20 20 20 3e 3e 3e 20  choice).    >>> 
5a00: 6d 6f 64 75 6c 65 2e 5f 5f 6e 61 6d 65 5f 5f 0a  module.__name__.
5a10: 20 20 20 20 27 72 61 6e 64 6f 6d 27 0a 20 20 20      'random'.   
5a20: 20 3e 3e 3e 20 6d 6f 64 75 6c 65 20 69 73 20 72   >>> module is r
5a30: 61 6e 64 6f 6d 0a 20 20 20 20 31 0a 0a 20 20 20  andom.    1..   
5a40: 20 41 20 63 6c 61 73 73 3a 0a 20 20 20 20 3e 3e   A class:.    >>
5a50: 3e 20 6d 6f 64 75 6c 65 20 3d 20 67 65 74 6d 6f  > module = getmo
5a60: 64 75 6c 65 28 72 61 6e 64 6f 6d 2e 52 61 6e 64  dule(random.Rand
5a70: 6f 6d 29 0a 20 20 20 20 3e 3e 3e 20 6d 6f 64 75  om).    >>> modu
5a80: 6c 65 2e 5f 5f 6e 61 6d 65 5f 5f 0a 20 20 20 20  le.__name__.    
5a90: 27 72 61 6e 64 6f 6d 27 0a 20 20 20 20 3e 3e 3e  'random'.    >>>
5aa0: 20 6d 6f 64 75 6c 65 20 69 73 20 72 61 6e 64 6f   module is rando
5ab0: 6d 0a 20 20 20 20 31 0a 0a 20 20 20 20 41 20 63  m.    1..    A c
5ac0: 6c 61 73 73 20 69 6e 68 65 72 69 74 69 6e 67 20  lass inheriting 
5ad0: 66 72 6f 6d 20 61 20 63 6c 61 73 73 20 69 6e 20  from a class in 
5ae0: 61 6e 6f 74 68 65 72 20 6d 6f 64 75 6c 65 3a 0a  another module:.
5af0: 20 20 20 20 28 6e 6f 74 65 3a 20 54 68 65 20 69      (note: The i
5b00: 6e 68 65 72 69 74 69 6e 67 20 63 6c 61 73 73 20  nheriting class 
5b10: 6d 75 73 74 20 64 65 66 69 6e 65 20 61 74 20 6c  must define at l
5b20: 65 61 73 74 20 6f 6e 65 20 66 75 6e 63 74 69 6f  east one functio
5b30: 6e 2e 29 0a 20 20 20 20 3e 3e 3e 20 63 6c 61 73  n.).    >>> clas
5b40: 73 20 4d 79 52 61 6e 64 6f 6d 28 72 61 6e 64 6f  s MyRandom(rando
5b50: 6d 2e 52 61 6e 64 6f 6d 29 3a 0a 20 20 20 20 2e  m.Random):.    .
5b60: 2e 2e 20 20 20 20 20 64 65 66 20 70 6c 61 79 28  ..     def play(
5b70: 73 65 6c 66 29 3a 0a 20 20 20 20 2e 2e 2e 20 20  self):.    ...  
5b80: 20 20 20 20 20 20 20 70 61 73 73 0a 20 20 20 20         pass.    
5b90: 3e 3e 3e 20 6d 6f 64 75 6c 65 20 3d 20 67 65 74  >>> module = get
5ba0: 6d 6f 64 75 6c 65 28 4d 79 52 61 6e 64 6f 6d 29  module(MyRandom)
5bb0: 0a 20 20 20 20 3e 3e 3e 20 69 66 20 5f 5f 6e 61  .    >>> if __na
5bc0: 6d 65 5f 5f 20 3d 3d 20 27 5f 5f 6d 61 69 6e 5f  me__ == '__main_
5bd0: 5f 27 3a 0a 20 20 20 20 2e 2e 2e 20 20 20 20 20  _':.    ...     
5be0: 6e 61 6d 65 20 3d 20 27 72 61 64 5f 75 74 69 6c  name = 'rad_util
5bf0: 27 0a 20 20 20 20 2e 2e 2e 20 65 6c 73 65 3a 0a  '.    ... else:.
5c00: 20 20 20 20 2e 2e 2e 20 20 20 20 20 6e 61 6d 65      ...     name
5c10: 20 3d 20 6d 6f 64 75 6c 65 2e 5f 5f 6e 61 6d 65   = module.__name
5c20: 5f 5f 0a 20 20 20 20 3e 3e 3e 20 6e 61 6d 65 0a  __.    >>> name.
5c30: 20 20 20 20 27 72 61 64 5f 75 74 69 6c 27 0a 20      'rad_util'. 
5c40: 20 20 20 3e 3e 3e 20 6d 6f 64 75 6c 65 20 69 73     >>> module is
5c50: 20 73 79 73 2e 6d 6f 64 75 6c 65 73 5b 5f 5f 6e   sys.modules[__n
5c60: 61 6d 65 5f 5f 5d 0a 20 20 20 20 31 0a 0a 20 20  ame__].    1..  
5c70: 20 20 44 69 73 63 75 73 73 69 6f 6e 3a 0a 20 20    Discussion:.  
5c80: 20 20 54 68 69 73 20 61 70 70 72 6f 61 63 68 20    This approach 
5c90: 69 73 20 73 6c 69 67 68 74 6c 79 20 68 61 63 6b  is slightly hack
5ca0: 69 73 68 2c 20 61 6e 64 20 77 6f 6e 27 74 20 77  ish, and won't w
5cb0: 6f 72 6b 20 69 6e 20 76 61 72 69 6f 75 73 20 73  ork in various s
5cc0: 69 74 75 61 74 69 6f 6e 73 2e 0a 20 20 20 20 48  ituations..    H
5cd0: 6f 77 65 76 65 72 2c 20 74 68 69 73 20 77 61 73  owever, this was
5ce0: 20 74 68 65 20 61 70 70 72 6f 61 63 68 20 72 65   the approach re
5cf0: 63 6f 6d 6d 65 6e 64 65 64 20 62 79 20 47 76 52  commended by GvR
5d00: 2c 20 73 6f 20 69 74 27 73 20 61 73 20 67 6f 6f  , so it's as goo
5d10: 64 20 61 73 0a 20 20 20 20 79 6f 75 27 6c 6c 20  d as.    you'll 
5d20: 67 65 74 2e 0a 0a 20 20 20 20 53 65 65 20 47 76  get...    See Gv
5d30: 52 27 73 20 70 6f 73 74 20 69 6e 20 74 68 69 73  R's post in this
5d40: 20 74 68 72 65 61 64 3a 0a 20 20 20 20 68 74 74   thread:.    htt
5d50: 70 3a 2f 2f 67 72 6f 75 70 73 2e 67 6f 6f 67 6c  p://groups.googl
5d60: 65 2e 63 6f 6d 2e 61 75 2f 67 72 6f 75 70 2f 63  e.com.au/group/c
5d70: 6f 6d 70 2e 6c 61 6e 67 2e 70 79 74 68 6f 6e 2f  omp.lang.python/
5d80: 62 72 6f 77 73 65 5f 74 68 72 65 61 64 2f 74 68  browse_thread/th
5d90: 72 65 61 64 2f 39 36 36 61 37 62 64 65 65 30 37  read/966a7bdee07
5da0: 65 33 62 33 34 2f 63 33 63 61 62 33 66 34 31 65  e3b34/c3cab3f41e
5db0: 61 38 34 32 33 36 3f 6c 6e 6b 3d 73 74 26 71 3d  a84236?lnk=st&q=
5dc0: 70 79 74 68 6f 6e 2b 64 65 74 65 72 6d 69 6e 65  python+determine
5dd0: 2b 63 6c 61 73 73 2b 6d 6f 64 75 6c 65 26 72 6e  +class+module&rn
5de0: 75 6d 3d 34 26 68 6c 3d 65 6e 23 63 33 63 61 62  um=4&hl=en#c3cab
5df0: 33 66 34 31 65 61 38 34 32 33 36 0a 20 20 20 20  3f41ea84236.    
5e00: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 69 66 20  .    """.    if 
5e10: 68 61 73 61 74 74 72 28 6f 62 6a 2c 20 27 66 75  hasattr(obj, 'fu
5e20: 6e 63 5f 67 6c 6f 62 61 6c 73 27 29 3a 0a 20 20  nc_globals'):.  
5e30: 20 20 20 20 20 20 66 75 6e 63 20 3d 20 6f 62 6a        func = obj
5e40: 0a 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20  .    else:.     
5e50: 20 20 20 23 20 48 61 6e 64 6c 65 20 63 6c 61 73     # Handle clas
5e60: 73 65 73 2e 0a 20 20 20 20 20 20 20 20 66 75 6e  ses..        fun
5e70: 63 20 3d 20 4e 6f 6e 65 0a 20 20 20 20 20 20 20  c = None.       
5e80: 20 66 6f 72 20 69 74 65 6d 20 69 6e 20 6f 62 6a   for item in obj
5e90: 2e 5f 5f 64 69 63 74 5f 5f 2e 76 61 6c 75 65 73  .__dict__.values
5ea0: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
5eb0: 69 66 20 68 61 73 61 74 74 72 28 69 74 65 6d 2c  if hasattr(item,
5ec0: 20 27 66 75 6e 63 5f 67 6c 6f 62 61 6c 73 27 29   'func_globals')
5ed0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
5ee0: 20 20 66 75 6e 63 20 3d 20 69 74 65 6d 0a 20 20    func = item.  
5ef0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 62 72                br
5f00: 65 61 6b 0a 20 20 20 20 20 20 20 20 69 66 20 66  eak.        if f
5f10: 75 6e 63 20 69 73 20 4e 6f 6e 65 3a 0a 20 20 20  unc is None:.   
5f20: 20 20 20 20 20 20 20 20 20 72 61 69 73 65 20 56           raise V
5f30: 61 6c 75 65 45 72 72 6f 72 28 22 4e 6f 20 66 75  alueError("No fu
5f40: 6e 63 74 69 6f 6e 73 20 61 74 74 61 63 68 65 64  nctions attached
5f50: 20 74 6f 20 6f 62 6a 65 63 74 3a 20 25 72 22 20   to object: %r" 
5f60: 25 20 6f 62 6a 29 0a 20 20 20 20 6d 6f 64 75 6c  % obj).    modul
5f70: 65 5f 6e 61 6d 65 20 3d 20 66 75 6e 63 2e 66 75  e_name = func.fu
5f80: 6e 63 5f 67 6c 6f 62 61 6c 73 5b 27 5f 5f 6e 61  nc_globals['__na
5f90: 6d 65 5f 5f 27 5d 0a 20 20 20 20 23 20 47 65 74  me__'].    # Get
5fa0: 20 6d 6f 64 75 6c 65 2e 0a 20 20 20 20 6d 6f 64   module..    mod
5fb0: 75 6c 65 20 3d 20 73 79 73 2e 6d 6f 64 75 6c 65  ule = sys.module
5fc0: 73 5b 6d 6f 64 75 6c 65 5f 6e 61 6d 65 5d 0a 20  s[module_name]. 
5fd0: 20 20 20 72 65 74 75 72 6e 20 6d 6f 64 75 6c 65     return module
5fe0: 0a 0a 0a 64 65 66 20 72 6f 75 6e 64 5f 67 72 69  ...def round_gri
5ff0: 64 28 76 61 6c 75 65 2c 20 67 72 69 64 2c 20 6d  d(value, grid, m
6000: 6f 64 65 3d 30 29 3a 0a 20 20 20 20 22 22 22 52  ode=0):.    """R
6010: 6f 75 6e 64 20 6f 66 66 20 74 68 65 20 67 69 76  ound off the giv
6020: 65 6e 20 76 61 6c 75 65 20 74 6f 20 74 68 65 20  en value to the 
6030: 67 69 76 65 6e 20 67 72 69 64 20 73 69 7a 65 2e  given grid size.
6040: 0a 0a 20 20 20 20 41 72 67 75 6d 65 6e 74 73 3a  ..    Arguments:
6050: 0a 20 20 20 20 76 61 6c 75 65 20 2d 2d 20 76 61  .    value -- va
6060: 6c 75 65 20 74 6f 20 62 65 20 72 6f 75 64 6e 65  lue to be roudne
6070: 0a 20 20 20 20 67 72 69 64 20 2d 2d 20 72 65 73  .    grid -- res
6080: 75 6c 74 20 6d 75 73 74 20 62 65 20 61 20 6d 75  ult must be a mu
6090: 6c 74 69 70 6c 65 20 6f 66 20 74 68 69 73 0a 20  ltiple of this. 
60a0: 20 20 20 6d 6f 64 65 20 2d 2d 20 30 20 6e 65 61     mode -- 0 nea
60b0: 72 65 73 74 2c 20 31 20 75 70 2c 20 2d 31 20 64  rest, 1 up, -1 d
60c0: 6f 77 6e 0a 0a 20 20 20 20 45 78 61 6d 70 6c 65  own..    Example
60d0: 73 3a 0a 20 20 20 20 0a 20 20 20 20 3e 3e 3e 20  s:.    .    >>> 
60e0: 72 6f 75 6e 64 5f 67 72 69 64 28 37 2e 35 2c 20  round_grid(7.5, 
60f0: 35 29 0a 20 20 20 20 31 30 0a 0a 20 20 20 20 3e  5).    10..    >
6100: 3e 3e 20 72 6f 75 6e 64 5f 67 72 69 64 28 37 2e  >> round_grid(7.
6110: 35 2c 20 35 2c 20 6d 6f 64 65 3d 2d 31 29 0a 20  5, 5, mode=-1). 
6120: 20 20 20 35 0a 0a 20 20 20 20 3e 3e 3e 20 72 6f     5..    >>> ro
6130: 75 6e 64 5f 67 72 69 64 28 37 2e 33 2c 20 35 2c  und_grid(7.3, 5,
6140: 20 6d 6f 64 65 3d 31 29 0a 20 20 20 20 31 30 0a   mode=1).    10.
6150: 0a 20 20 20 20 3e 3e 3e 20 72 6f 75 6e 64 5f 67  .    >>> round_g
6160: 72 69 64 28 37 2e 33 2c 20 35 2e 30 2c 20 6d 6f  rid(7.3, 5.0, mo
6170: 64 65 3d 31 29 0a 20 20 20 20 31 30 2e 30 0a 0a  de=1).    10.0..
6180: 20 20 20 20 22 22 22 0a 20 20 20 20 6f 66 66 5f      """.    off_
6190: 67 72 69 64 20 3d 20 76 61 6c 75 65 20 25 20 67  grid = value % g
61a0: 72 69 64 0a 20 20 20 20 69 66 20 6d 6f 64 65 20  rid.    if mode 
61b0: 3d 3d 20 30 3a 0a 20 20 20 20 20 20 20 20 61 64  == 0:.        ad
61c0: 64 5f 6f 6e 65 20 3d 20 69 6e 74 28 6f 66 66 5f  d_one = int(off_
61d0: 67 72 69 64 20 3e 3d 20 28 67 72 69 64 20 2f 20  grid >= (grid / 
61e0: 32 2e 30 29 29 0a 20 20 20 20 65 6c 69 66 20 6d  2.0)).    elif m
61f0: 6f 64 65 20 3d 3d 20 31 20 61 6e 64 20 6f 66 66  ode == 1 and off
6200: 5f 67 72 69 64 3a 0a 20 20 20 20 20 20 20 20 61  _grid:.        a
6210: 64 64 5f 6f 6e 65 20 3d 20 31 0a 20 20 20 20 65  dd_one = 1.    e
6220: 6c 69 66 20 6d 6f 64 65 20 3d 3d 20 2d 31 20 61  lif mode == -1 a
6230: 6e 64 20 6f 66 66 5f 67 72 69 64 3a 0a 20 20 20  nd off_grid:.   
6240: 20 20 20 20 20 61 64 64 5f 6f 6e 65 20 3d 20 30       add_one = 0
6250: 0a 20 20 20 20 72 65 73 75 6c 74 20 3d 20 28 28  .    result = ((
6260: 69 6e 74 28 76 61 6c 75 65 20 2f 20 67 72 69 64  int(value / grid
6270: 29 20 2b 20 61 64 64 5f 6f 6e 65 29 20 2a 20 67  ) + add_one) * g
6280: 72 69 64 29 0a 20 20 20 20 72 65 74 75 72 6e 20  rid).    return 
6290: 72 65 73 75 6c 74 0a 0a 0a 64 65 66 20 67 65 74  result...def get
62a0: 5f 61 72 67 73 28 61 72 67 76 29 3a 0a 20 20 20  _args(argv):.   
62b0: 20 22 22 22 53 74 6f 72 65 20 63 6f 6d 6d 61 6e   """Store comman
62c0: 64 2d 6c 69 6e 65 20 61 72 67 73 20 69 6e 20 61  d-line args in a
62d0: 20 64 69 63 74 69 6f 6e 61 72 79 2e 0a 20 20 20   dictionary..   
62e0: 20 0a 20 20 20 20 2d 2c 20 2d 2d 20 70 72 65 66   .    -, -- pref
62f0: 69 78 65 73 20 61 72 65 20 72 65 6d 6f 76 65 64  ixes are removed
6300: 0a 20 20 20 20 49 74 65 6d 73 20 6e 6f 74 20 70  .    Items not p
6310: 72 65 66 69 78 65 64 20 77 69 74 68 20 2d 20 6f  refixed with - o
6320: 72 20 2d 2d 20 61 72 65 20 73 74 6f 72 65 64 20  r -- are stored 
6330: 61 73 20 61 20 6c 69 73 74 2c 20 69 6e 64 65 78  as a list, index
6340: 65 64 20 62 79 20 27 61 72 67 73 27 0a 0a 20 20  ed by 'args'..  
6350: 20 20 46 6f 72 20 6f 70 74 69 6f 6e 73 20 74 68    For options th
6360: 61 74 20 74 61 6b 65 20 61 20 76 61 6c 75 65 20  at take a value 
6370: 75 73 65 20 2d 2d 6f 70 74 69 6f 6e 3d 76 61 6c  use --option=val
6380: 75 65 0a 0a 20 20 20 20 43 6f 6e 73 69 64 65 72  ue..    Consider
6390: 20 75 73 69 6e 67 20 6f 70 74 70 61 72 73 65 20   using optparse 
63a0: 6f 72 20 67 65 74 6f 70 74 20 28 69 6e 20 50 79  or getopt (in Py
63b0: 74 68 6f 6e 20 73 74 61 6e 64 61 72 64 20 6c 69  thon standard li
63c0: 62 72 61 72 79 29 20 69 6e 73 74 65 61 64 2e 0a  brary) instead..
63d0: 0a 20 20 20 20 22 22 22 0a 20 20 20 20 64 20 3d  .    """.    d =
63e0: 20 7b 7d 0a 20 20 20 20 61 72 67 73 20 3d 20 5b   {}.    args = [
63f0: 5d 0a 20 20 20 20 0a 20 20 20 20 66 6f 72 20 61  ].    .    for a
6400: 72 67 20 69 6e 20 61 72 67 76 3a 0a 20 20 20 20  rg in argv:.    
6410: 20 20 20 20 20 20 20 20 0a 20 20 20 20 20 20 20          .       
6420: 20 69 66 20 61 72 67 2e 73 74 61 72 74 73 77 69   if arg.startswi
6430: 74 68 28 27 2d 27 29 3a 0a 20 20 20 20 20 20 20  th('-'):.       
6440: 20 20 20 20 20 70 61 72 74 73 20 3d 20 72 65 2e       parts = re.
6450: 73 75 62 28 72 27 5e 2d 2b 27 2c 20 27 27 2c 20  sub(r'^-+', '', 
6460: 61 72 67 29 2e 73 70 6c 69 74 28 27 3d 27 29 0a  arg).split('=').
6470: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 6c              if l
6480: 65 6e 28 70 61 72 74 73 29 20 3d 3d 20 32 3a 0a  en(parts) == 2:.
6490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
64a0: 64 5b 70 61 72 74 73 5b 30 5d 5d 20 3d 20 70 61  d[parts[0]] = pa
64b0: 72 74 73 5b 31 5d 0a 20 20 20 20 20 20 20 20 20  rts[1].         
64c0: 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20     else:.       
64d0: 20 20 20 20 20 20 20 20 20 64 5b 70 61 72 74 73           d[parts
64e0: 5b 30 5d 5d 20 3d 20 4e 6f 6e 65 0a 20 20 20 20  [0]] = None.    
64f0: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
6500: 20 20 20 20 20 20 61 72 67 73 2e 61 70 70 65 6e        args.appen
6510: 64 28 61 72 67 29 0a 0a 20 20 20 20 64 5b 27 61  d(arg)..    d['a
6520: 72 67 73 27 5d 20 3d 20 61 72 67 73 0a 20 20 20  rgs'] = args.   
6530: 20 0a 20 20 20 20 72 65 74 75 72 6e 20 64 0a 0a   .    return d..
6540: 0a 69 66 20 5f 5f 6e 61 6d 65 5f 5f 20 3d 3d 20  .if __name__ == 
6550: 27 5f 5f 6d 61 69 6e 5f 5f 27 3a 0a 20 20 20 20  '__main__':.    
6560: 69 6d 70 6f 72 74 20 64 6f 63 74 65 73 74 0a 20  import doctest. 
6570: 20 20 20 64 6f 63 74 65 73 74 2e 74 65 73 74 6d     doctest.testm
6580: 6f 64 28 73 79 73 2e 6d 6f 64 75 6c 65 73 5b 27  od(sys.modules['
6590: 5f 5f 6d 61 69 6e 5f 5f 27 5d 29 0a 0a           __main__'])..